28#ifndef __RadixSort_H__
29#define __RadixSort_H__
87 template <
class TContainer,
class TContainerValueType,
typename TCompValueType>
113 typedef std::vector<SortEntry, STLAllocator<SortEntry, GeneralAllocPolicy> >
SortVector;
126 for (
int i = 1; i < 256; ++i)
134 unsigned char byteVal =
getByte(byteIndex, (*
mSrc)[i].key);
135 (*mDest)[
mOffsets[byteVal]++] = (*mSrc)[i];
139 template <
typename T>
151 for (
int i = 128; i < 256; ++i)
158 for (
int i = 1; i < 128; ++i)
165 for (
int i = 129; i < 256; ++i)
173 unsigned char byteVal =
getByte(byteIndex, (*
mSrc)[i].key);
174 (*mDest)[
mOffsets[byteVal]++] = (*mSrc)[i];
187 for (
int i = 128; i < 256; ++i)
194 for (
int i = 1; i < 128; ++i)
204 for (
int i = 254; i > 127; --i)
212 unsigned char byteVal =
getByte(byteIndex, (*
mSrc)[i].key);
216 (*mDest)[--
mOffsets[byteVal]] = (*mSrc)[i];
221 (*mDest)[
mOffsets[byteVal]++] = (*mSrc)[i];
226 inline unsigned char getByte(
int byteIndex, TCompValueType val)
228#if OGRE_ENDIAN == OGRE_ENDIAN_LITTLE
229 return ((
unsigned char*)(&val))[byteIndex];
231 return ((
unsigned char*)(&val))[
mNumPasses - byteIndex - 1];
245 template <
class TFunction>
246 void sort(TContainer& container, TFunction func)
248 if (container.empty())
252 mSortSize =
static_cast<int>(container.size());
265 memset(
mCounters[p], 0,
sizeof(
int) * 256);
269 TCompValueType prevValue = func.operator()(*i);
270 bool needsSorting =
false;
274 TCompValueType val = func.operator()(*i);
276 if (!needsSorting && val < prevValue)
286 unsigned char byteVal =
getByte(p, val);
316 for (i = container.begin();
317 i != container.end(); ++i, ++c)
319 *i = *((*mDest)[c].iter);
Class for performing a radix sort (fast comparison-less sort based on byte value) on various standard...
int mNumPasses
Number of passes for this type.
int mOffsets[256]
Beta-pass offsets.
void sortPass(int byteIndex)
void sort(TContainer &container, TFunction func)
Main sort function.
std::vector< SortEntry, STLAllocator< SortEntry, GeneralAllocPolicy > > SortVector
Temp sort storage.
void finalPass(int byteIndex, float val)
int mSortSize
Sort area size.
void finalPass(int byteIndex, int val)
unsigned char getByte(int byteIndex, TCompValueType val)
int mCounters[4][256]
Alpha-pass counters of values (histogram) 4 of them so we can radix sort a maximum of a 32bit value.
void finalPass(int byteIndex, T val)
TContainer::iterator ContainerIter
SortEntry(TCompValueType k, ContainerIter it)