Searchable sorting network with nearsort. More...

#include <Nearsort.h>

Inheritance diagram for CNearsort:

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

Public Member Functions inherited from CAutocomplete
	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
bool	StillNearsorts (const size_t)
	Does it still nearsort with this input change? More...

bool	EvenNearsorts ()
	Does it nearly sort, even number of inputs? More...

bool	Nearsorts ()
	Does it nearly sort? More...

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

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

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

Protected Attributes
bool	m_bReachableFrom [MAXINPUTS][MAXINPUTS] = {false}
	Reachable from. More...

int	m_nReachCountFrom [MAXINPUTS] = {0}
	Count of channels reachable from. More...

bool	m_bReachableTo [MAXINPUTS][MAXINPUTS] = {false}
	Reachable to. More...

int	m_nReachCountTo [MAXINPUTS] = {0}
	Count of channels reachable to. More...

bool	m_bReachable [MAXINPUTS][MAXINPUTS] = {false}
	Reachable from or to. More...

int	m_nReachCount [MAXINPUTS] = {0}
	Count of channels reachable from or to. 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...

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

CNearsort is a version of CAutocomplete that uses the nearsort heuristic, which is based on reachability, to prune the second-last level.

Definition at line 38 of file Nearsort.h.

Constructor & Destructor Documentation

◆ CNearsort()

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

Constructor.

Parameters

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

Definition at line 33 of file Nearsort.cpp.

Member Function Documentation

◆ EvenNearsorts()

bool CNearsort::EvenNearsorts ( )

protected

Check whether sorting network nearsorts all inputs.

Returns: true iff it sorts

Definition at line 40 of file Nearsort.cpp.

◆ Nearsorts()

bool CNearsort::Nearsorts ( )

protected

Check whether sorting network nearsorts all inputs. Works for both odd and even n.

Returns: true iff it nearsorts

Definition at line 58 of file Nearsort.cpp.

◆ Process()

void CNearsort::Process ( )

protectedvirtual

Process a comparator network, which is pretty much the same as CSearchable::Process() except that you stop one level early and prune if the network so far fails to nearsort all inputs. If it fails to nearsort, then it won't sort. Continue with those that nearsort because some of them might actually sort.

Reimplemented from CSearchable.

Reimplemented in CNearsort2.

Definition at line 134 of file Nearsort.cpp.

◆ SetToS()

void CNearsort::SetToS ( )

protectedvirtual

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

Reimplemented from CAutocomplete.

Reimplemented in CNearsort2.

Definition at line 150 of file Nearsort.cpp.

◆ StillNearsorts()

bool CNearsort::StillNearsorts ( const size_t delta )

protected

Check whether sorting network nearsorts when the current input has channel flipped.

Parameters

delta Index of channel to flip.

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

Definition at line 95 of file Nearsort.cpp.

Member Data Documentation

◆ m_bReachable

bool CNearsort::m_bReachable[MAXINPUTS][MAXINPUTS] = {false}

protected

Definition at line 46 of file Nearsort.h.

◆ m_bReachableFrom

bool CNearsort::m_bReachableFrom[MAXINPUTS][MAXINPUTS] = {false}

protected

Definition at line 40 of file Nearsort.h.

◆ m_bReachableTo

bool CNearsort::m_bReachableTo[MAXINPUTS][MAXINPUTS] = {false}

protected

Definition at line 43 of file Nearsort.h.

◆ m_nReachCount

int CNearsort::m_nReachCount[MAXINPUTS] = {0}

protected

Definition at line 47 of file Nearsort.h.

◆ m_nReachCountFrom

int CNearsort::m_nReachCountFrom[MAXINPUTS] = {0}

protected

Definition at line 41 of file Nearsort.h.

◆ m_nReachCountTo

int CNearsort::m_nReachCountTo[MAXINPUTS] = {0}

protected

Definition at line 44 of file Nearsort.h.

Public Member Functions

Protected Member Functions

Protected Attributes

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ CNearsort()

Member Function Documentation

◆ EvenNearsorts()

◆ Nearsorts()

◆ Process()

◆ SetToS()

◆ StillNearsorts()

Member Data Documentation

◆ m_bReachable

◆ m_bReachableFrom

◆ m_bReachableTo

◆ m_nReachCount

◆ m_nReachCountFrom

◆ m_nReachCountTo