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);