 |
Sorting Network Verify and Draw
Check Whether Comparator Networks Sort and Draw Them
|
|
Sorting Network Verify and Draw
Check Whether Comparator Networks Sort and Draw Them
|
Batcher's bitonic sorting network. More...
#include <Bitonic.h>
Public Member Functions | |
| CBitonicSort (const UINT) | |
| Constructor. More... | |
| const std::wstring | GetName () const |
| Get name. More... | |
 Public Member Functions inherited from CSortingNetwork | |
| ~CSortingNetwork () | |
| Destructor. More... | |
| bool | Read (LPWSTR) |
| Read from file. More... | |
| bool | sorts () |
| Does it sort? More... | |
| const UINT | GetUnused () const |
| Get number of unused comparators. More... | |
| Public Member Functions inherited from CRenderableComparatorNet | |
| ~CRenderableComparatorNet () | |
| Destructor. More... | |
| void | Draw (const eDrawStyle) |
Draw to a Gdiplus::Bitmap. More... | |
| HRESULT | ExportToPNG (LPWSTR) |
| Export in PNG format. More... | |
| HRESULT | ExportToTex (LPWSTR) |
| Export in TeX format. More... | |
| HRESULT | ExportToSVG (LPWSTR) |
| Export in SVG format. More... | |
| Gdiplus::Bitmap * | GetBitmap () |
| Get bitmap pointer. More... | |
| Public Member Functions inherited from CComparatorNetwork | |
| ~CComparatorNetwork () | |
| Destructor. More... | |
| virtual bool | Read (LPWSTR) |
| Read from file. More... | |
| void | Prune (const UINT) |
| Prune down number of inputs. More... | |
| const UINT | GetNumInputs () const |
| Get number of inputs. More... | |
| const UINT | GetDepth () const |
| Get depth. More... | |
| const UINT | GetSize () const |
| Get size. More... | |
| const bool | FirstNormalForm () const |
| Test for first normal form. More... | |
Private Member Functions | |
| void | CreateComparators (std::vector< CComparator > *) |
| Create comparators. More... | |
| void | MakeAllMinMax (std::vector< CComparator > *) |
| Make all comparators min-max. More... | |
| void | Twist (std::vector< CComparator > *, UINT, UINT, UINT) |
| Twist channels. More... | |
| void | CreateMatchArray (std::vector< CComparator > *) |
| Create match array. More... | |
Additional Inherited Members | |
| Protected Member Functions inherited from CSortingNetwork | |
| void | initSortingTest () |
| Initialize the sorting test. More... | |
| bool | stillsorts (const int delta) |
| Does it still sort when a bit is changed? More... | |
| UINT | flipinput (UINT j, const UINT firstlayer, const UINT lastlayer) |
| Recompute network values when a bit is changed. More... | |
| void | initValues (const UINT firstlayer, const UINT lastlayer) |
| Initialize the network values to the all zero input. More... | |
| void | initUsage () |
| Initialize usage array. More... | |
| void | CreateValueArray () |
| Make value array. More... | |
| void | CreateUsageArray () |
| Make usage array. More... | |
| Protected Member Functions inherited from CRenderableComparatorNet | |
| Gdiplus::REAL | ComputeBitmapHeight () |
| Compute bitmap height. More... | |
| void | DrawChannels (const float fLen) |
| Draw channels. More... | |
| void | DrawComparator (const UINT, const UINT, const float, bool=false) |
| Draw a comparator. More... | |
| void | DrawComparators () |
| Draw all comparators. More... | |
| Protected Member Functions inherited from CComparatorNetwork | |
| void | InsertComparator (UINT, UINT, UINT) |
| Insert comparator. More... | |
| void | CreateMatchArray (UINT, UINT) |
| Create match array. More... | |
| void | ComputeSize () |
| Compute size. More... | |
| Protected Attributes inherited from CSortingNetwork | |
| CBinaryGrayCode * | m_pGrayCode = nullptr |
| Gray code generator. More... | |
| UINT ** | m_nValue = nullptr |
| Values at each level when sorting. More... | |
| Protected Attributes inherited from CRenderableComparatorNet | |
| const Gdiplus::REAL | m_fPenWidth = 2.0f |
| Pen width in pixels. More... | |
| const Gdiplus::REAL | m_fXDelta = 24.0f |
| Gap between channels in pixels. More... | |
| const Gdiplus::REAL | m_fYDelta = 16.0f |
| Vertical comparator gap in pixels. More... | |
| const Gdiplus::REAL | m_fYDelta2 = 8.0f |
| Extra vertical gap between layers in pixels. More... | |
| const Gdiplus::REAL | m_fDiameter = 8.0f |
| Diameter of circles in pixels. More... | |
| Gdiplus::Bitmap * | m_pBitmap = nullptr |
| Pointer to a bitmap image. More... | |
| eDrawStyle | m_eDrawStyle = eDrawStyle::Horizontal |
| Drawing style. More... | |
| Gdiplus::Graphics * | m_pGraphics = nullptr |
| Pointer to graphics object. More... | |
| Gdiplus::Pen * | m_pPen = nullptr |
| Pointer to graphics pen. More... | |
| Gdiplus::Pen * | m_pRedPen = nullptr |
| Pointer to graphics pen. More... | |
| Gdiplus::SolidBrush * | m_pBrush = nullptr |
| Pointer to graphics brush. More... | |
| Gdiplus::SolidBrush * | m_pRedBrush = nullptr |
| Pointer to graphics brush. More... | |
| FILE * | m_pOutput = nullptr |
| File pointer. More... | |
| eExport | m_eExportType = eExport::Png |
| Export type. More... | |
| Protected Attributes inherited from CComparatorNetwork | |
| UINT ** | m_nMatch = nullptr |
| Matchings at each level. More... | |
| bool ** | m_bUsed = nullptr |
| Whether comparators are used when sorting. More... | |
| UINT | m_nInputs = 0 |
| Number of inputs. More... | |
| UINT | m_nDepth = 0 |
| Depth. More... | |
| UINT | m_nSize = 0 |
| Size. More... | |
| bool | m_bSorts = false |
| True if it sorts, false if it doesn't or unknown. More... | |
Batcher's bitonic sorting network has number of inputs a power of 2. It sorts by recursively sorting each half of the channels, one upward (min to max) and one downward (max to min) and then using bitonic merge to merge the results. From
K. E. Batcher, "Sorting networks and their applications", In Proc. AFIPS Spring Joint Computer Conference, Vol. 32, pp. 307-314, 1968.
| CBitonicSort::CBitonicSort | ( | const UINT | log2n | ) |
Construct a bitonic sorting network with number of inputs a power of 2. This involves dabbling in max-min comparators, which we will have to twist into min-max comparators before we're finished.
| log2n | Log base 2 of the number of inputs. |
Definition at line 33 of file Bitonic.cpp.
|
private |
Create an array of std::vectors of CComparator with one entry for each level. The comparators may be min-max or max-min comparators. Assumes that m_nInputs has been set to the number of inputs and is a power of 2 and that the matching array m_nMatch has been created and initialized. This code was appropriated from the bitonic sorter Wikipedia page https://en.wikipedia.org/wiki/Bitonic_sorter.
| vecLevel | [OUT] Array of std::vectors of CComparator. |
Definition at line 60 of file Bitonic.cpp.
|
private |
Create the matching array and populate it with comparators from an array of std::vectors of CComparator. Assumes that m_nInputs and m_nDepth have been set.
| vecLevel | Array of std::vectors of min-max CComparators. |
Definition at line 120 of file Bitonic.cpp.
| const std::wstring CBitonicSort::GetName | ( | ) | const |
Construct a wide string name from the type of sorting network and the number of inputs.
Definition at line 132 of file Bitonic.cpp.
|
private |
Make all comparators in an array of std::vectors of CComparator into min-max comparators. Assumes that m_nDepth has been set and that the array has exactly this number of entries.
| vecLevel | [IN, OUT] Array of std::vectors of CComparator. |
Definition at line 82 of file Bitonic.cpp.
|
private |
Swap two channels below a certain depth in an array of std::vectors of CComparator. That is, every comparator that is attached to one of the channels gets attached to the other instead. Assumes that m_nDepth has been set and that the array has exactly this number of entries.
| vecLevel | [IN, OUT] Array of std::vectors of CComparator. |
| nLevel | Swap channels at this level and below. |
| nMin | One channel to swap. |
| nMax | The other channel to swap. |
Definition at line 100 of file Bitonic.cpp.
1.9.4