Searchable sorting network with nearsort2. More...

#include <Nearsort2.h>

Inheritance diagram for CNearsort2:

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

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

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

bool	Nearsorts2 ()
	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 CNearsort
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...

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

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

CNearsort2 is a version of CNearsort that uses the nearsort2 heuristic, which is based on reachability, to prune two levels from the end.

Definition at line 37 of file Nearsort2.h.

Constructor & Destructor Documentation

◆ CNearsort2()

CNearsort2::CNearsort2	(	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 Nearsort2.cpp.

Member Function Documentation

◆ EvenNearsorts2()

bool CNearsort2::EvenNearsorts2 ( )

protected

Check whether sorting network nearsorts2 all inputs. Works for even width, and for odd width it doesn't change the last input.

Returns: true iff it sorts

Definition at line 41 of file Nearsort2.cpp.

◆ Nearsorts2()

bool CNearsort2::Nearsorts2 ( )

protected

Check whether sorting network nearsorts2 all inputs. Works for both odd and even m_nWidth.

Returns: true iff it nearsorts2

Definition at line 59 of file Nearsort2.cpp.

◆ Process()

void CNearsort2::Process ( )

protectedvirtual

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

Reimplemented from CNearsort.

Definition at line 133 of file Nearsort2.cpp.

◆ SetToS()

void CNearsort2::SetToS ( )

protectedvirtual

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

Reimplemented from CNearsort.

Definition at line 149 of file Nearsort2.cpp.

◆ StillNearsorts2()

bool CNearsort2::StillNearsorts2 ( const size_t delta )

protected

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

Parameters

delta Index of channel to flip.

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

Definition at line 94 of file Nearsort2.cpp.

Public Member Functions

Protected Member Functions

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ CNearsort2()

Member Function Documentation

◆ EvenNearsorts2()

◆ Nearsorts2()

◆ Process()

◆ SetToS()

◆ StillNearsorts2()