Sorting network. More...

#include <SortingNetwork.h>

Inheritance diagram for CSortingNetwork:

Public Member Functions
	CSortingNetwork ()
	Constructor. More...

	~CSortingNetwork ()
	Destructor. More...

Public Member Functions inherited from CComparatorNetwork
	CComparatorNetwork ()
	Constructor. More...

virtual	~CComparatorNetwork ()
	Destructor. More...

void	Save (const std::string &)
	Save to file. More...

Protected Member Functions
virtual void	Initialize ()
	Initialize the sorting test. More...

virtual bool	Sorts ()
	Does it sort? More...

virtual bool	StillSorts (const size_t)
	Does it still sort when a bit is changed? More...

size_t	FlipInput (size_t, const size_t, const size_t)
	Recompute network values when a bit is changed. More...

void	InitValues (const size_t, const size_t)
	Initialize the network values to the all zero input. More...

Protected Attributes
CBinaryGrayCode *	m_pGrayCode = nullptr
	Gray code generator. More...

size_t	m_nValue [MAXDEPTH][MAXINPUTS] = {0}
	Values at each level when sorting. More...

size_t	m_nZeros = 0
	Number of zeros in the input. More...

Protected Attributes inherited from CComparatorNetwork
size_t	m_nComparator [MAXDEPTH][MAXINPUTS] = {0}
	Comparator array. More...

Additional Inherited Members
Static Public Member Functions inherited from CSettings
static void	SetWidth (const size_t)
	Set width. More...

static void	SetDepth (const size_t)
	Set depth. More...

Static Protected Attributes inherited from CSettings
static size_t	m_nWidth = 9
	Comparator network width. More...

static size_t	m_nDepth = 6
	Comparator network depth. More...

Detailed Description

CSortingNetwork combines a comparator network with a binary Gray code generator CBinaryGrayCode to test whether the comparator network sorts based on the Zero-One Principle, which says that a comparator network is a sorting network if and only if it sorts all inputs made up of only zeros and ones. See Knuth Volume 3 for the details. Using a Gray code generator instead of a standard binary string generator simplifies and speeds up the test. The main function of interest here is CSortingNetwork::Sorts() which returns true if the base comparator network sorts all inputs.

Definition at line 46 of file SortingNetwork.h.

Constructor & Destructor Documentation

◆ CSortingNetwork()

CSortingNetwork::CSortingNetwork ( )

Create a binary Gray code generator.

Definition at line 30 of file SortingNetwork.cpp.

◆ ~CSortingNetwork()

CSortingNetwork::~CSortingNetwork ( )

Delete the binary Gray code generator.

Definition at line 36 of file SortingNetwork.cpp.

Member Function Documentation

◆ FlipInput()

size_t CSortingNetwork::FlipInput	(	size_t	j,
		const size_t	first,
		const size_t	last
	)

protected

Flip bit and propagate down the comparator network. Note that when a bit is flipped at a certain level, exactly one bit is changed at subsequent levels following a path to the outputs. An example is shown in the following figure.

On the left we see a 6-input sorting network of depth 5 on input \(1, 1, 1, 0, 0, 0\). The output is in ascending order from top to bottom. On the right we see what happens when we flip the second-from-last input from a 0 to a 1. That change follows a path from the input channel to the channel formerly carrying the last 0, shown in red.

Parameters

j	Flip value in this channel.
first	Flip value starting at this level.
last	Propagate change down to this level.

Returns: Channel whose value is flipped after the last level.

Definition at line 75 of file SortingNetwork.cpp.

◆ Initialize()

void CSortingNetwork::Initialize ( )

protectedvirtual

Initialize the network for the sorting test, that is, make the Gray code word for input be all zeros, and the values on every channel at every level be zero.

Reimplemented in C1NF, and CAutocomplete.

Definition at line 54 of file SortingNetwork.cpp.

◆ InitValues()

void CSortingNetwork::InitValues	(	const size_t	first,
		const size_t	last
	)

protected

Set the values on every channel between two levels to zero.

Parameters

first	First level to set to zero.
last	Last level to set to zero.

Definition at line 44 of file SortingNetwork.cpp.

◆ Sorts()

bool CSortingNetwork::Sorts ( )

protectedvirtual

Check whether sorting network sorts all inputs.

Returns: true if it sorts.

Reimplemented in C1NF, and CAutocomplete.

Definition at line 104 of file SortingNetwork.cpp.

◆ StillSorts()

bool CSortingNetwork::StillSorts ( const size_t delta )

protectedvirtual

Check whether sorting network sorts when the input value on a given channel is flipped.

Parameters

delta Index of channel to flip.

Returns: true if it still sorts when channel is flipped.

Reimplemented in C1NF, and CAutocomplete.

Definition at line 96 of file SortingNetwork.cpp.

Member Data Documentation

◆ m_nValue

size_t CSortingNetwork::m_nValue[MAXDEPTH][MAXINPUTS] = {0}

protected

Definition at line 49 of file SortingNetwork.h.

◆ m_nZeros

size_t CSortingNetwork::m_nZeros = 0

protected

Definition at line 50 of file SortingNetwork.h.

◆ m_pGrayCode

CBinaryGrayCode* CSortingNetwork::m_pGrayCode = nullptr

protected

Definition at line 48 of file SortingNetwork.h.

Public Member Functions

Protected Member Functions

Protected Attributes

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ CSortingNetwork()

◆ ~CSortingNetwork()

Member Function Documentation

◆ FlipInput()

◆ Initialize()

◆ InitValues()

◆ Sorts()

◆ StillSorts()

Member Data Documentation

◆ m_nValue

◆ m_nZeros

◆ m_pGrayCode