Sorting network. More...

#include <SortingNetwork.h>

Inheritance diagram for CSortingNetwork:

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

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

Detailed Description

CSortingNetwork combines a renderable comparator network with a binary Gray code generator to test whether the comparator network sorts based on the Zero-One Principle, which says that a comparator network is a sorting network if and only if it sorts all inputs made up of only zeros and ones. See Knuth Volume 3 for the details. Using a Gray code generator instead of a standard binary string generator speeds up the test.

Definition at line 43 of file SortingNetwork.h.

Constructor & Destructor Documentation

◆ ~CSortingNetwork()

CSortingNetwork::~CSortingNetwork ( )

Delete the value table m_nValue, the usage array m_bUsed, and the Gray code generator.

Definition at line 31 of file SortingNetwork.cpp.

Member Function Documentation

◆ CreateUsageArray()

void CSortingNetwork::CreateUsageArray ( )

protected

Create and initialize usage array to all usde. Assumes that m_nInputs and m_nDepth have been set to the correct values.

Definition at line 166 of file SortingNetwork.cpp.

◆ CreateValueArray()

void CSortingNetwork::CreateValueArray ( )

protected

Create and initialize value array to all zeros. Assumes that m_nInputs and m_nDepth have been set to the correct values.

Definition at line 152 of file SortingNetwork.cpp.

◆ flipinput()

UINT CSortingNetwork::flipinput	(	UINT	j,
		const UINT	firstlayer,
		const UINT	lastlayer
	)

protected

Flip value and propagate down the comparator network.

Parameters

j	Flip value in this channel.
firstlayer	Flip value at this layer.
lastlayer	Propagate change down to this layer.

Returns: Channel whose value is flipped after the last layer.

Definition at line 90 of file SortingNetwork.cpp.

◆ GetUnused()

const UINT CSortingNetwork::GetUnused ( ) const

Get number of unused comparators. Assumes that function sorts() has already been run. Returns zero otherwise.

Returns: Number of unused comparators.

Definition at line 136 of file SortingNetwork.cpp.

◆ initSortingTest()

void CSortingNetwork::initSortingTest ( )

protected

Initialize the network for the sorting test, that is, make the Gray code word for input be all zeros, and the values on every channel at every level be zero.

Definition at line 75 of file SortingNetwork.cpp.

◆ initUsage()

void CSortingNetwork::initUsage ( )

protected

Set the usage flag on every channel to a fixed value.

Parameters

b	Value of flag.

Definition at line 60 of file SortingNetwork.cpp.

◆ initValues()

void CSortingNetwork::initValues	(	const UINT	firstlayer,
		const UINT	lastlayer
	)

protected

Set the values on every channel between two levels to zero.

Parameters

firstlayer	First level to set to zero.
lastlayer	Last level to set to zero.

Definition at line 51 of file SortingNetwork.cpp.

◆ Read()

bool CSortingNetwork::Read ( LPWSTR lpwstr )

virtual

Read a sorting network and create and initialize the value array m_nValue for use in sorting verification. Uses CComparatorNetwork::Read() to do the heavy lifting.

Parameters

lpwstr Null terminated wide file name.

Returns: true if the input succeeded.

Reimplemented from CComparatorNetwork.

Definition at line 183 of file SortingNetwork.cpp.

◆ sorts()

bool CSortingNetwork::sorts ( )

Check whether sorting network sorts all inputs. Set m_bSorts to true if it does.

Returns: true if it sorts.

Definition at line 119 of file SortingNetwork.cpp.

◆ stillsorts()

bool CSortingNetwork::stillsorts ( const int delta )

protected

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

Parameters

delta Index of channel to flip.

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

Definition at line 110 of file SortingNetwork.cpp.

Member Data Documentation

◆ m_nValue

UINT** CSortingNetwork::m_nValue = nullptr

protected

Definition at line 46 of file SortingNetwork.h.

◆ m_pGrayCode

CBinaryGrayCode* CSortingNetwork::m_pGrayCode = nullptr

protected

Definition at line 45 of file SortingNetwork.h.

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

Constructor & Destructor Documentation

◆ ~CSortingNetwork()

Member Function Documentation

◆ CreateUsageArray()

◆ CreateValueArray()

◆ flipinput()

◆ GetUnused()

◆ initSortingTest()

◆ initUsage()

◆ initValues()

◆ Read()

◆ sorts()

◆ stillsorts()

Member Data Documentation

◆ m_nValue

◆ m_pGrayCode