Searchable sorting network. More...

#include <Searchable.h>

Inheritance diagram for CSearchable:

Public Member Functions
	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	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
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

The searchable sorting network class will perform a backtracking search for a sorting network of a given depth and number of inputs.

Definition at line 39 of file Searchable.h.

Constructor & Destructor Documentation

◆ CSearchable()

CSearchable::CSearchable ( )

Compute the number of matchings and store it in m_nNumMatchings.

Definition at line 30 of file Searchable.cpp.

Member Function Documentation

◆ Backtrack()

void CSearchable::Backtrack ( )

virtual

Initialize and then start a backtracking search for all sorting networks of given width and depth.

Reimplemented in C2NF.

Definition at line 82 of file Searchable.cpp.

◆ FirstComparatorNetwork()

void CSearchable::FirstComparatorNetwork ( size_t toplevel )

protected

Set to first comparator network from some given level down to the bottom.

Parameters

toplevel Top level of comparator network we are constructing here.

Definition at line 91 of file Searchable.cpp.

◆ GetCount()

const size_t CSearchable::GetCount ( ) const

Reader function for the number of sorting networks found.

Returns: The number of sorting networks found.

Definition at line 160 of file Searchable.cpp.

◆ InitMatchingRepresentations()

void CSearchable::InitMatchingRepresentations ( size_t level )

protected

Initialize m_nComparator and m_cMatching to the first matching at a given level.

Parameters

level The level at which to initialize matchings.

Definition at line 120 of file Searchable.cpp.

◆ NextComparatorNetwork()

bool CSearchable::NextComparatorNetwork ( )

protected

Change to next comparator network. This implementation uses a stack in the standard way to remove the need for recursion.

Returns: false if there are no more comparator networks.

Definition at line 135 of file Searchable.cpp.

◆ Process()

void CSearchable::Process ( )

protectedvirtual

Process a comparator network, which means testing whether it sorts, and if it does, saving it to a file and incrementing a counter.

Reimplemented in CNearsort, and CNearsort2.

Definition at line 60 of file Searchable.cpp.

◆ Save()

void CSearchable::Save ( )

protectedvirtual

Save a generated sorting network into a file with a suitable name. Save comparator network to a file whose name encodes number of inputs, depth, and order found. For example, an 8-input comparator network of depth 5 that is the 20th sorting network found would be saved to file w8d5n20.txt.

Reimplemented in C2NF.

Definition at line 42 of file Searchable.cpp.

◆ Search()

void CSearchable::Search ( )

protected

Perform a backtracking search, assuming everything has been initialized in a suitable fashion.

Definition at line 70 of file Searchable.cpp.

◆ SetToS()

void CSearchable::SetToS ( )

protectedvirtual

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

Reimplemented in CAutocomplete, CNearsort, and CNearsort2.

Definition at line 53 of file Searchable.cpp.

◆ SynchMatchingRepresentations()

void CSearchable::SynchMatchingRepresentations ( size_t level )

protected

Synchronize m_nComparator to m_cMatching at a given level. The latter is assumed to be correct.

Parameters

level The level at which to synchronize matchings.

Definition at line 102 of file Searchable.cpp.

Member Data Documentation

◆ m_cMatching

CMatching CSearchable::m_cMatching[MAXDEPTH]

protected

Definition at line 43 of file Searchable.h.

◆ m_nCount

size_t CSearchable::m_nCount = 0

protected

Definition at line 41 of file Searchable.h.

◆ m_nNumMatchings

size_t CSearchable::m_nNumMatchings = 0

protected

Definition at line 48 of file Searchable.h.

◆ m_nStack

int CSearchable::m_nStack[MAXDEPTH] = {0}

protected

Definition at line 45 of file Searchable.h.

◆ m_nTop

size_t CSearchable::m_nTop = 0

protected

Definition at line 49 of file Searchable.h.

◆ m_nToS

int CSearchable::m_nToS = 0

protected

Definition at line 46 of file Searchable.h.

Public Member Functions

Protected Member Functions

Protected Attributes

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ CSearchable()

Member Function Documentation

◆ Backtrack()

◆ FirstComparatorNetwork()

◆ GetCount()

◆ InitMatchingRepresentations()

◆ NextComparatorNetwork()

◆ Process()

◆ Save()

◆ Search()

◆ SetToS()

◆ SynchMatchingRepresentations()

Member Data Documentation

◆ m_cMatching

◆ m_nCount

◆ m_nNumMatchings

◆ m_nStack

◆ m_nTop

◆ m_nToS