CComparatorNetwork Class Reference

Comparator network. More...

#include <ComparatorNetwork.h>

Inheritance diagram for CComparatorNetwork:

Public Member Functions
	~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	InsertComparator (UINT, UINT, UINT)
	Insert comparator. More...
void	CreateMatchArray (UINT, UINT)
	Create match array. More...
void	ComputeSize ()
	Compute size. More...

Protected Attributes
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

CComparatorNetwork implements a comparator network, which may or may not sort. Each level of the comparator network is represented by a matching stored in an array m_nMatch. There is a comparator between channels j and k at level i iff m_nMatch[i][j] == k && m_nMatch[i][k] == j. If there is no comparator on channel j at level i, then m_nMatch[i][j] == j. This will allow for fast verification of whether a comparator network is a sorting network.

Definition at line 41 of file ComparatorNetwork.h.

Constructor & Destructor Documentation

~CComparatorNetwork()

CComparatorNetwork::~CComparatorNetwork

(

)

Delete the memory used for the 2D array m_nMatch.

Definition at line 36 of file ComparatorNetwork.cpp.

Member Function Documentation

ComputeSize()

void CComparatorNetwork::ComputeSize ( )

protected

Compute the size, that is, number of comparators and stores it in m_nSize. Assumes that the matching array m_nMatch has been created and initialized, otherwise it sets m_nSize to zero.

Definition at line 183 of file ComparatorNetwork.cpp.

CreateMatchArray()

void CComparatorNetwork::CreateMatchArray ( UINT  nInputs, UINT  nDepth  )

protected

Set the number of inputs and the depth, then create a new matching array, taking care to delete any old one that may exist.

Parameters

nInputs	Number of inputs.
nDepth	Depth.

Definition at line 160 of file ComparatorNetwork.cpp.

FirstNormalForm()

const bool CComparatorNetwork::FirstNormalForm

(

)

const

First normal form test. A comparator network is in first normal form if the first layer consists of comparators between channels \(i\) and \(i + 1\) for all even \(0 \leq i < n\), where \(n\) is the number of inputs. This definition is from the following paper.

‍I. Parberry, "A computer-assisted optimal depth lower bound for nine-input sorting networks}, Mathematical Systems Theory, Vol. 24, No. 1, pp. 101-116, 1991.

Returns

True if in first normal form.

Definition at line 226 of file ComparatorNetwork.cpp.

GetDepth()

const UINT CComparatorNetwork::GetDepth

(

)

const

Reader function for the depth.

Returns

Depth.

Definition at line 204 of file ComparatorNetwork.cpp.

GetNumInputs()

const UINT CComparatorNetwork::GetNumInputs

(

)

const

Reader function for the number of inputs.

Returns

Number of inputs.

Definition at line 197 of file ComparatorNetwork.cpp.

GetSize()

const UINT CComparatorNetwork::GetSize

(

)

const

Reader function for the size (number of comparators).

Returns

Size.

Definition at line 211 of file ComparatorNetwork.cpp.

InsertComparator()

void CComparatorNetwork::InsertComparator ( UINT  nLevel, UINT  i, UINT  j  )

protected

Insert a comparator between two channels at a certain level.

Parameters

nLevel	Level number.
i	Channel index.
j	Channel index.

Definition at line 120 of file ComparatorNetwork.cpp.

Prune()

void CComparatorNetwork::Prune

(

const UINT

n

)

Prune down the number of inputs, deleting any comparators attached to the deleted channels. Does nothing if the desired number of inputs is less then 2 or greater than or equal to the current number of inputs.

Parameters

n	Number of inputs desired.

Definition at line 132 of file ComparatorNetwork.cpp.

Read()

bool CComparatorNetwork::Read ( LPWSTR  lpwstr )

virtual

Read a comparator network from file. Create and input the matching array m_nMatch and set m_nInputs to the number of inputs, m_nDepth to the depth, and m_nSize to the size (number of comparators). The input file must consist of a line of text for each layer of comparators. Each line must consist of an even number of unsigned integer channel numbers in which each consecutive pair \(i, j\) indicates a comparator between channels \(i\) and \(j\).

Parameters

lpwstr

Null terminated wide file name.

Returns

true if the input succeeded.

Reimplemented in CSortingNetwork.

Definition at line 54 of file ComparatorNetwork.cpp.

Member Data Documentation

m_bSorts

bool CComparatorNetwork::m_bSorts = false

protected

Definition at line 50 of file ComparatorNetwork.h.

m_bUsed

bool** CComparatorNetwork::m_bUsed = nullptr

protected

Definition at line 44 of file ComparatorNetwork.h.

m_nDepth

UINT CComparatorNetwork::m_nDepth = 0

protected

Definition at line 47 of file ComparatorNetwork.h.

m_nInputs

UINT CComparatorNetwork::m_nInputs = 0

protected

Definition at line 46 of file ComparatorNetwork.h.

m_nMatch

UINT** CComparatorNetwork::m_nMatch = nullptr

protected

Definition at line 43 of file ComparatorNetwork.h.

m_nSize

UINT CComparatorNetwork::m_nSize = 0

protected

Definition at line 48 of file ComparatorNetwork.h.