 |
Sorting Network Search
Backtracking for Small Sorting Networks
|
|
Sorting Network Search
Backtracking for Small Sorting Networks
|
Second normal form searchable sorting network. More...
#include <2NF.h>
Public Member Functions | |
| 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 | 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 | |
| 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... | |
A first normal form sorting network that will be given its second level from a generator CLevel2Search that provides second level candidates unique up to symmetry.
| C2NF::C2NF | ( | CMatching & | L2Matching, |
| const size_t | index | ||
| ) |
|
virtual |
Initialize and then start a backtracking search for all sorting networks in Second Normal Form of given width and depth.
Reimplemented from CSearchable.
|
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, second level index, and order found. For example, an 8-input comparator network of depth 5 with second level index 99 that is the 20th sorting network found with that second level, would be saved to file w8d5x99n20.txt.
Reimplemented from CSearchable.
1.9.4