Batcher's odd-even sorting network. More...

#include <OddEven.h>

Inheritance diagram for COddEvenSort:

Public Member Functions
	COddEvenSort (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 ()
	Create comparators. More...

Private Attributes
UINT	m_nLog2n = 0
	Log base 2 of the number of inputs. 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...

Detailed Description

Batcher's odd-even sorting network has number of inputs a power of 2. It sorts by recursively sorting each half of the channels, then applying odd-even 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.

Definition at line 40 of file OddEven.h.

Constructor & Destructor Documentation

◆ COddEvenSort()

COddEvenSort::COddEvenSort ( const UINT log2n )

Construct an odd-even sorting network with number of inputs a power of 2.

Parameters

log2n Log base 2 of the number of inputs.

Definition at line 32 of file OddEven.cpp.

Member Function Documentation

◆ CreateComparators()

void COddEvenSort::CreateComparators ( )

private

Create the comparators for odd-even sort. Assumes that m_nLog2n has been set to log base 2 of the number of inputs, 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 odd-even mergesort Wikipedia page https://en.wikipedia.org/wiki/Batcher_odd-even_mergesort.

Definition at line 54 of file OddEven.cpp.

◆ GetName()

const std::wstring COddEvenSort::GetName ( ) const

Construct a wide string name from the type of sorting network and the number of inputs.

Returns: A wide string name.

Definition at line 81 of file OddEven.cpp.

Member Data Documentation

◆ m_nLog2n

UINT COddEvenSort::m_nLog2n = 0

private

Definition at line 42 of file OddEven.h.

Public Member Functions

Private Member Functions

Private Attributes

Additional Inherited Members