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);
303 for (p = 0; p < mNumPasses - 1; ++p)
316 for (i = container.begin();
317 i != container.end(); ++i, ++c)
319 *i = *((*mDest)[c].iter);
SortEntry(TCompValueType k, ContainerIter it)
Class for performing a radix sort (fast comparison-less sort based on byte value) on various standard...
void sort(TContainer &container, TFunction func)
Main sort function.
unsigned char getByte(int byteIndex, TCompValueType val)
void finalPass(int byteIndex, float val)
int mSortSize
Sort area size.
void finalPass(int byteIndex, int val)
int mNumPasses
Number of passes for this type.
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 sortPass(int byteIndex)
int mOffsets[256]
Beta-pass offsets.
void finalPass(int byteIndex, T val)
TContainer::iterator ContainerIter
std::vector< SortEntry, STLAllocator< SortEntry, GeneralAllocPolicy > > SortVector
Temp sort storage.