Classes | Public Types | Public Member Functions | Protected Types | Protected Member Functions | Protected Attributes | List of all members
Ogre::RadixSort< TContainer, TContainerValueType, TCompValueType > Class Template Reference

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

#include <OgreRadixSort.h>

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. More...
 

Protected Types

typedef std::vector< SortEntry, STLAllocator< SortEntry, GeneralAllocPolicy > > SortVector
 Temp sort storage. More...
 

Protected Member Functions

void finalPass (int byteIndex, float val)
 
void finalPass (int byteIndex, int val)
 
template<typename T >
void finalPass (int byteIndex, T val)
 
unsigned char getByte (int byteIndex, TCompValueType val)
 
void sortPass (int byteIndex)
 

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. More...
 
SortVectormDest
 
int mNumPasses
 Number of passes for this type. More...
 
int mOffsets [256]
 Beta-pass offsets. More...
 
SortVector mSortArea1
 
SortVector mSortArea2
 
int mSortSize
 Sort area size. More...
 
SortVectormSrc
 
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

◆ ContainerIter

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

Definition at line 91 of file OgreRadixSort.h.

◆ SortVector

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

◆ RadixSort()

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

Definition at line 237 of file OgreRadixSort.h.

◆ ~RadixSort()

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

Definition at line 238 of file OgreRadixSort.h.

Member Function Documentation

◆ finalPass() [1/3]

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.

◆ finalPass() [2/3]

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.

◆ finalPass() [3/3]

template<class TContainer , class TContainerValueType , typename TCompValueType >
template<typename T >
void Ogre::RadixSort< TContainer, TContainerValueType, TCompValueType >::finalPass ( int  byteIndex,
val 
)
protected

◆ getByte()

template<class TContainer , class TContainerValueType , typename TCompValueType >
unsigned char Ogre::RadixSort< TContainer, TContainerValueType, TCompValueType >::getByte ( int  byteIndex,
TCompValueType  val 
)
protected

◆ sort()

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
containerA container of the type you declared when declaring
funcA functor which returns the value for comparison when given a container value

Definition at line 246 of file OgreRadixSort.h.

◆ sortPass()

template<class TContainer , class TContainerValueType , typename TCompValueType >
void Ogre::RadixSort< TContainer, TContainerValueType, TCompValueType >::sortPass ( int  byteIndex)
protected

Member Data Documentation

◆ mCounters

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

◆ mDest

template<class TContainer , class TContainerValueType , typename TCompValueType >
SortVector* Ogre::RadixSort< TContainer, TContainerValueType, TCompValueType >::mDest
protected

◆ mNumPasses

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

◆ mOffsets

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

◆ mSortArea1

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

◆ mSortArea2

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

◆ mSortSize

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

◆ mSrc

template<class TContainer , class TContainerValueType , typename TCompValueType >
SortVector* Ogre::RadixSort< TContainer, TContainerValueType, TCompValueType >::mSrc
protected

◆ mTmpContainer

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

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

Copyright © 2012 Torus Knot Software Ltd
Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License.
Last modified Tue Apr 13 2021 08:53:15