Searchable second normal form sorting network with autocomplete. More...

#include <Autocomplete.h>

Inheritance diagram for CAutocomplete:

Public Member Functions
	CAutocomplete (CMatching &, const size_t)
	Constructor. More...

Public Member Functions inherited from C2NF
	C2NF (CMatching &, const size_t)
	Constructor. More...

void	Backtrack ()
	Backtracking search. More...

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

virtual void	Backtrack ()
	Backtracking search. More...

const size_t	GetCount () const
	Get count. More...

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

Public Member Functions inherited from CSortingNetwork
	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
void	SetToS ()
	Set top of stack. More...

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

void	Initialize ()
	Initialize the sorting test. More...

void	initLastLevel ()
	Initialize the last level of the comparator network. More...

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

Protected Member Functions inherited from C2NF
void	Save ()
	Save comparator network. More...

Protected Member Functions inherited from CSearchable
void	FirstComparatorNetwork (size_t)
	Set to first comparator network. More...

bool	NextComparatorNetwork ()
	Change to next comparator network. More...

void	SynchMatchingRepresentations (size_t)
	Synchronize the two different matching representations. More...

void	InitMatchingRepresentations (size_t)
	Initialize the two different matching representations. More...

virtual void	Save ()
	Save comparator network. More...

virtual void	SetToS ()
	Set top of stack. More...

virtual void	Process ()
	Process a candidate comparator network. More...

void	Search ()
	Do the actual search. More...

Protected Member Functions inherited from C1NF
void	Initialize ()
	Initialize the sorting test. More...

bool	Sorts ()
	Does it sort all inputs? More...

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

bool	EvenSorts ()
	Does it sort if there are an odd number of inputs and we fix the value on the last channel? More...

Protected Member Functions inherited from CSortingNetwork
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...

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...

Protected Attributes inherited from C2NF
size_t	m_nLevel2Index = 0
	Index of current level 2 candidate. More...

Protected Attributes inherited from CSearchable
size_t	m_nCount = 0
	Number of comparator networks found that sort. More...

CMatching	m_cMatching [MAXDEPTH]
	Matchings that make up comparator network in a form that makes searching faster. More...

int	m_nStack [MAXDEPTH] = {0}
	Stack to remove recursion from search. More...

int	m_nToS = 0
	Top of stack. More...

size_t	m_nNumMatchings = 0
	Number of matchings of this size. More...

size_t	m_nTop = 0
	Topmost level. More...

Protected Attributes inherited from CSortingNetwork
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...

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

A searchable second normal form sorting network that tries to autocomplete the last level instead of iterating through all possibilities. The image below shows a sorting network with an input of zeros and ones (left) and the autocompleted path followed by a change of a zero to a one (right)."

Definition at line 41 of file Autocomplete.h.

Constructor & Destructor Documentation

◆ CAutocomplete()

CAutocomplete::CAutocomplete	(	CMatching &	L2Matching,
		const size_t	index
	)

Constructor.

Parameters

L2Matching	Level 2 matching.
index	Lexicographics number of level 2 matching.

Definition at line 34 of file Autocomplete.cpp.

Member Function Documentation

◆ Initialize()

void CAutocomplete::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. Yhis differs from C1NF::Initialize() in that it doesn't initialize values in the first and last levels.

Reimplemented from C1NF.

Definition at line 76 of file Autocomplete.cpp.

◆ initLastLevel()

void CAutocomplete::initLastLevel ( )

protected

Initializes the testable representation of the last level of the sorting network to be empty, that is, containing no comparators.

Definition at line 85 of file Autocomplete.cpp.

◆ SetToS()

void CAutocomplete::SetToS ( )

protectedvirtual

Set top of stack m_nToS to the second-last level of the sorting network.

Reimplemented from CSearchable.

Reimplemented in CNearsort, and CNearsort2.

Definition at line 122 of file Autocomplete.cpp.

◆ Sorts()

bool CAutocomplete::Sorts ( )

protectedvirtual

Check whether sorting network sorts all inputs. The difference between this and CSortingNetwork::Sorts() is that this version has to handle any hypothetical last even-numbered channel separately, testing it first with value zero then with value 1.

Returns: true iff it sorts

Reimplemented from C1NF.

Definition at line 96 of file Autocomplete.cpp.

◆ StillSorts()

bool CAutocomplete::StillSorts ( const size_t delta )

protectedvirtual

Check whether stub of a sorting network sorts when the current input has channel flipped. This overrides CSortingNetwork::sort(). Attempts to build the last level while testing it.

Parameters

delta Index of channel to flip.

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

Reimplemented from C1NF.

Definition at line 44 of file Autocomplete.cpp.

Public Member Functions

Protected Member Functions

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ CAutocomplete()

Member Function Documentation

◆ Initialize()

◆ initLastLevel()

◆ SetToS()

◆ Sorts()

◆ StillSorts()