Ogre::RadixSort< TContainer, TContainerValueType, TCompValueType > Class Template Reference
[General]

Class for performing a radix sort (fast comparison-less sort based on byte value) on various standard STL containers. More...

#include <OgreRadixSort.h>

List of all members.

Classes
struct	SortEntry
Public Types
typedef TContainer::iterator	ContainerIter
Public Member Functions
	RadixSort ()
	~RadixSort ()
template<class TFunction >
void	sort (TContainer &container, TFunction func)
	Main sort function.
Protected Types
typedef std::vector< SortEntry, STLAllocator< SortEntry, GeneralAllocPolicy > >	SortVector
	Temp sort storage.
Protected Member Functions
void	sortPass (int byteIndex)
template<typename T >
void	finalPass (int byteIndex, T val)
void	finalPass (int byteIndex, int val)
void	finalPass (int byteIndex, float val)
unsigned char	getByte (int byteIndex, TCompValueType val)
Protected Attributes
int	mCounters [4][256]
	Alpha-pass counters of values (histogram) 4 of them so we can radix sort a maximum of a 32bit value.
int	mOffsets [256]
	Beta-pass offsets.
int	mSortSize
	Sort area size.
int	mNumPasses
	Number of passes for this type.
SortVector	mSortArea1
SortVector	mSortArea2
SortVector *	mSrc
SortVector *	mDest
TContainer	mTmpContainer

---

Detailed Description

template<class TContainer, class TContainerValueType, typename TCompValueType>
class Ogre::RadixSort< TContainer, TContainerValueType, TCompValueType >

Class for performing a radix sort (fast comparison-less sort based on byte value) on various standard STL containers.

Remarks:

A radix sort is a very fast sort algorithm. It doesn't use comparisons and thus is able to break the theoretical minimum O(N*logN) complexity. Radix sort is complexity O(k*N), where k is a constant. Note that radix sorting is not in-place, it requires additional storage, so it trades memory for speed. The overhead of copying means that it is only faster for fairly large datasets, so you are advised to only use it for collections of at least a few hundred items.

This is a template class to allow it to deal with a variety of containers, and a variety of value types to sort on. In addition to providing the container and value type on construction, you also need to supply a functor object which will retrieve the value to compare on for each item in the list. For example, if you had an std::vector of by-value instances of an object of class 'Bibble', and you wanted to sort on Bibble::getDoobrie(), you'd have to firstly create a functor like this:

        struct BibbleSortFunctor
        {
            float operator()(const Bibble& val) const
            {
                return val.getDoobrie();
            }
        }

Then, you need to declare a RadixSort class which names the container type, the value type in the container, and the type of the value you want to sort by. You can then call the sort function. E.g.

        RadixSort<BibbleList, Bibble, float> radixSorter;
        BibbleSortFunctor functor;

        radixSorter.sort(myBibbleList, functor);

You should try to reuse RadixSort instances, since repeated allocation of the internal storage is then avoided.

Note:

Radix sorting is often associated with just unsigned integer values. Our implementation can handle both unsigned and signed integers, as well as floats (which are often not supported by other radix sorters). doubles are not supported; you will need to implement your functor object to convert to float if you wish to use this sort routine.

Definition at line 88 of file OgreRadixSort.h.

---

Member Typedef Documentation

template<class TContainer, class TContainerValueType, typename TCompValueType>

typedef TContainer::iterator Ogre::RadixSort< TContainer, TContainerValueType, TCompValueType >::ContainerIter

Definition at line 91 of file OgreRadixSort.h.

template<class TContainer, class TContainerValueType, typename TCompValueType>

typedef std::vector<SortEntry, STLAllocator<SortEntry, GeneralAllocPolicy> > Ogre::RadixSort< TContainer, TContainerValueType, TCompValueType >::SortVector [protected]

Temp sort storage.

Definition at line 113 of file OgreRadixSort.h.

---

Constructor & Destructor Documentation

template<class TContainer, class TContainerValueType, typename TCompValueType>

Ogre::RadixSort< TContainer, TContainerValueType, TCompValueType >::RadixSort

(

)

Definition at line 237 of file OgreRadixSort.h.

template<class TContainer, class TContainerValueType, typename TCompValueType>

Ogre::RadixSort< TContainer, TContainerValueType, TCompValueType >::~RadixSort

(

)

Definition at line 238 of file OgreRadixSort.h.

---

Member Function Documentation

template<class TContainer, class TContainerValueType, typename TCompValueType>

void Ogre::RadixSort< TContainer, TContainerValueType, TCompValueType >::finalPass	(	int	byteIndex,
		float	val
	)			[protected]

Definition at line 180 of file OgreRadixSort.h.

template<class TContainer, class TContainerValueType, typename TCompValueType>

void Ogre::RadixSort< TContainer, TContainerValueType, TCompValueType >::finalPass	(	int	byteIndex,
		int	val
	)			[protected]

Definition at line 147 of file OgreRadixSort.h.

template<class TContainer, class TContainerValueType, typename TCompValueType>

template<typename T >

void Ogre::RadixSort< TContainer, TContainerValueType, TCompValueType >::finalPass	(	int	byteIndex,
		T	val
	)			[protected]

Definition at line 140 of file OgreRadixSort.h.

Referenced by Ogre::RadixSort< RenderablePassList, RenderablePass, uint32 >::sort().

template<class TContainer, class TContainerValueType, typename TCompValueType>

unsigned char Ogre::RadixSort< TContainer, TContainerValueType, TCompValueType >::getByte	(	int	byteIndex,
		TCompValueType	val
	)			[protected]

Definition at line 226 of file OgreRadixSort.h.

Referenced by Ogre::RadixSort< RenderablePassList, RenderablePass, uint32 >::finalPass(), Ogre::RadixSort< RenderablePassList, RenderablePass, uint32 >::sort(), and Ogre::RadixSort< RenderablePassList, RenderablePass, uint32 >::sortPass().

template<class TContainer, class TContainerValueType, typename TCompValueType>

template<class TFunction >

void Ogre::RadixSort< TContainer, TContainerValueType, TCompValueType >::sort	(	TContainer &	container,
		TFunction	func
	)

Main sort function.

Parameters:

	container	A container of the type you declared when declaring
	func	A functor which returns the value for comparison when given a container value

Definition at line 246 of file OgreRadixSort.h.

template<class TContainer, class TContainerValueType, typename TCompValueType>

void Ogre::RadixSort< TContainer, TContainerValueType, TCompValueType >::sortPass

(

int

byteIndex

)

[protected]

Definition at line 121 of file OgreRadixSort.h.

Referenced by Ogre::RadixSort< RenderablePassList, RenderablePass, uint32 >::finalPass(), and Ogre::RadixSort< RenderablePassList, RenderablePass, uint32 >::sort().

---

Member Data Documentation

template<class TContainer, class TContainerValueType, typename TCompValueType>

int Ogre::RadixSort< TContainer, TContainerValueType, TCompValueType >::mCounters[4][256] [protected]

Alpha-pass counters of values (histogram) 4 of them so we can radix sort a maximum of a 32bit value.

Definition at line 95 of file OgreRadixSort.h.

Referenced by Ogre::RadixSort< RenderablePassList, RenderablePass, uint32 >::finalPass(), Ogre::RadixSort< RenderablePassList, RenderablePass, uint32 >::sort(), and Ogre::RadixSort< RenderablePassList, RenderablePass, uint32 >::sortPass().

template<class TContainer, class TContainerValueType, typename TCompValueType>

SortVector* Ogre::RadixSort< TContainer, TContainerValueType, TCompValueType >::mDest [protected]

Definition at line 117 of file OgreRadixSort.h.

Referenced by Ogre::RadixSort< RenderablePassList, RenderablePass, uint32 >::sort().

template<class TContainer, class TContainerValueType, typename TCompValueType>

int Ogre::RadixSort< TContainer, TContainerValueType, TCompValueType >::mNumPasses [protected]

Number of passes for this type.

Definition at line 101 of file OgreRadixSort.h.

Referenced by Ogre::RadixSort< RenderablePassList, RenderablePass, uint32 >::getByte(), and Ogre::RadixSort< RenderablePassList, RenderablePass, uint32 >::sort().

template<class TContainer, class TContainerValueType, typename TCompValueType>

int Ogre::RadixSort< TContainer, TContainerValueType, TCompValueType >::mOffsets[256] [protected]

Beta-pass offsets.

Definition at line 97 of file OgreRadixSort.h.

Referenced by Ogre::RadixSort< RenderablePassList, RenderablePass, uint32 >::finalPass(), and Ogre::RadixSort< RenderablePassList, RenderablePass, uint32 >::sortPass().

template<class TContainer, class TContainerValueType, typename TCompValueType>

SortVector Ogre::RadixSort< TContainer, TContainerValueType, TCompValueType >::mSortArea1 [protected]

Definition at line 114 of file OgreRadixSort.h.

Referenced by Ogre::RadixSort< RenderablePassList, RenderablePass, uint32 >::sort().

template<class TContainer, class TContainerValueType, typename TCompValueType>

SortVector Ogre::RadixSort< TContainer, TContainerValueType, TCompValueType >::mSortArea2 [protected]

Definition at line 115 of file OgreRadixSort.h.

Referenced by Ogre::RadixSort< RenderablePassList, RenderablePass, uint32 >::sort().

template<class TContainer, class TContainerValueType, typename TCompValueType>

int Ogre::RadixSort< TContainer, TContainerValueType, TCompValueType >::mSortSize [protected]

Sort area size.

Definition at line 99 of file OgreRadixSort.h.

Referenced by Ogre::RadixSort< RenderablePassList, RenderablePass, uint32 >::finalPass(), Ogre::RadixSort< RenderablePassList, RenderablePass, uint32 >::sort(), and Ogre::RadixSort< RenderablePassList, RenderablePass, uint32 >::sortPass().

template<class TContainer, class TContainerValueType, typename TCompValueType>

SortVector* Ogre::RadixSort< TContainer, TContainerValueType, TCompValueType >::mSrc [protected]

Definition at line 116 of file OgreRadixSort.h.

Referenced by Ogre::RadixSort< RenderablePassList, RenderablePass, uint32 >::finalPass(), Ogre::RadixSort< RenderablePassList, RenderablePass, uint32 >::sort(), and Ogre::RadixSort< RenderablePassList, RenderablePass, uint32 >::sortPass().

template<class TContainer, class TContainerValueType, typename TCompValueType>

TContainer Ogre::RadixSort< TContainer, TContainerValueType, TCompValueType >::mTmpContainer [protected]

Definition at line 118 of file OgreRadixSort.h.

Referenced by Ogre::RadixSort< RenderablePassList, RenderablePass, uint32 >::sort().

---

The documentation for this class was generated from the following file:

• OgreRadixSort.h