28 #ifndef __RadixSort_H__ 29 #define __RadixSort_H__ 87 template <
class TContainer,
class TContainerValueType,
typename TCompValueType>
109 : key(k), iter(it) {}
113 typedef std::vector<SortEntry, STLAllocator<SortEntry, GeneralAllocPolicy> >
SortVector;
126 for (
int i = 1; i < 256; ++i)
128 mOffsets[i] = mOffsets[i-1] + mCounters[byteIndex][i-1];
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)
153 numNeg += mCounters[byteIndex][i];
157 mOffsets[0] = numNeg;
158 for (
int i = 1; i < 128; ++i)
160 mOffsets[i] = mOffsets[i-1] + mCounters[byteIndex][i-1];
165 for (
int i = 129; i < 256; ++i)
167 mOffsets[i] = mOffsets[i-1] + mCounters[byteIndex][i-1];
173 unsigned char byteVal =
getByte(byteIndex, (*mSrc)[i].
key);
174 (*mDest)[mOffsets[byteVal]++] = (*mSrc)[i];
187 for (
int i = 128; i < 256; ++i)
189 numNeg += mCounters[byteIndex][i];
193 mOffsets[0] = numNeg;
194 for (
int i = 1; i < 128; ++i)
196 mOffsets[i] = mOffsets[i-1] + mCounters[byteIndex][i-1];
203 mOffsets[255] = mCounters[byteIndex][255];
204 for (
int i = 254; i > 127; --i)
206 mOffsets[i] = mOffsets[i+1] + mCounters[byteIndex][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());
253 mSortArea1.resize(container.size());
254 mSortArea2.resize(container.size());
257 mTmpContainer = container;
259 mNumPasses =
sizeof(TCompValueType);
265 memset(mCounters[p], 0,
sizeof(
int) * 256);
268 ContainerIter i = mTmpContainer.begin();
269 TCompValueType prevValue = func.operator()(*i);
270 bool needsSorting =
false;
271 for (
int u = 0; i != mTmpContainer.end(); ++i, ++u)
274 TCompValueType val = func.operator()(*i);
276 if (!needsSorting && val < prevValue)
280 mSortArea1[u].key = val;
281 mSortArea1[u].iter = i;
286 unsigned char byteVal =
getByte(p, val);
287 mCounters[p][byteVal]++;
303 for (p = 0; p < mNumPasses - 1; ++p)
307 SortVector* tmp =
mSrc;
316 for (i = container.begin();
317 i != container.end(); ++i, ++c)
319 *i = *((*mDest)[c].iter);
std::vector< SortEntry, STLAllocator< SortEntry, GeneralAllocPolicy > > SortVector
Temp sort storage.
void finalPass(int byteIndex, int val)
int mSortSize
Sort area size.
TContainer::iterator ContainerIter
void sortPass(int byteIndex)
int mNumPasses
Number of passes for this type.
unsigned char getByte(int byteIndex, TCompValueType val)
SortEntry(TCompValueType k, ContainerIter it)
void sort(TContainer &container, TFunction func)
Main sort function.
void finalPass(int byteIndex, float val)
Class for performing a radix sort (fast comparison-less sort based on byte value) on various standard...
void finalPass(int byteIndex, T 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...
int mOffsets[256]
Beta-pass offsets.