OgreRadixSort.h
Go to the documentation of this file.
/*
-----------------------------------------------------------------------------
This source file is part of OGRE
(Object-oriented Graphics Rendering Engine)
For the latest info, see http://www.ogre3d.org/
Copyright (c) 2000-2013 Torus Knot Software Ltd
Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.
-----------------------------------------------------------------------------
*/
#ifndef __RadixSort_H__
#define __RadixSort_H__
#include "OgrePrerequisites.h"
namespace Ogre {
template <class TContainer, class TContainerValueType, typename TCompValueType>
class RadixSort
{
public:
typedef typename TContainer::iterator ContainerIter;
protected:
int mCounters[4][256];
int mOffsets[256];
int mSortSize;
int mNumPasses;
struct SortEntry
{
TCompValueType key;
ContainerIter iter;
SortEntry() {}
SortEntry(TCompValueType k, ContainerIter it)
: key(k), iter(it) {}
};
typedef std::vector<SortEntry, STLAllocator<SortEntry, GeneralAllocPolicy> > SortVector;
SortVector mSortArea1;
SortVector mSortArea2;
SortVector* mSrc;
SortVector* mDest;
TContainer mTmpContainer; // initial copy
void sortPass(int byteIndex)
{
// Calculate offsets
// Basically this just leaves gaps for duplicate entries to fill
mOffsets[0] = 0;
for (int i = 1; i < 256; ++i)
{
mOffsets[i] = mOffsets[i-1] + mCounters[byteIndex][i-1];
}
// Sort pass
for (int i = 0; i < mSortSize; ++i)
{
unsigned char byteVal = getByte(byteIndex, (*mSrc)[i].key);
(*mDest)[mOffsets[byteVal]++] = (*mSrc)[i];
}
}
template <typename T>
void finalPass(int byteIndex, T val)
{
// default is to do normal pass
sortPass(byteIndex);
}
// special case signed int
void finalPass(int byteIndex, int val)
{
int numNeg = 0;
// all negative values are in entries 128+ in most significant byte
for (int i = 128; i < 256; ++i)
{
numNeg += mCounters[byteIndex][i];
}
// Calculate offsets - positive ones start at the number of negatives
// do positive numbers
mOffsets[0] = numNeg;
for (int i = 1; i < 128; ++i)
{
mOffsets[i] = mOffsets[i-1] + mCounters[byteIndex][i-1];
}
// Do negative numbers (must start at zero)
// No need to invert ordering, already correct (-1 is highest number)
mOffsets[128] = 0;
for (int i = 129; i < 256; ++i)
{
mOffsets[i] = mOffsets[i-1] + mCounters[byteIndex][i-1];
}
// Sort pass
for (int i = 0; i < mSortSize; ++i)
{
unsigned char byteVal = getByte(byteIndex, (*mSrc)[i].key);
(*mDest)[mOffsets[byteVal]++] = (*mSrc)[i];
}
}
// special case float
void finalPass(int byteIndex, float val)
{
// floats need to be special cased since negative numbers will come
// after positives (high bit = sign) and will be in reverse order
// (no ones-complement of the +ve value)
int numNeg = 0;
// all negative values are in entries 128+ in most significant byte
for (int i = 128; i < 256; ++i)
{
numNeg += mCounters[byteIndex][i];
}
// Calculate offsets - positive ones start at the number of negatives
// do positive numbers normally
mOffsets[0] = numNeg;
for (int i = 1; i < 128; ++i)
{
mOffsets[i] = mOffsets[i-1] + mCounters[byteIndex][i-1];
}
// Do negative numbers (must start at zero)
// Also need to invert ordering
// In order to preserve the stability of the sort (essential since
// we rely on previous bytes already being sorted) we have to count
// backwards in our offsets from
mOffsets[255] = mCounters[byteIndex][255];
for (int i = 254; i > 127; --i)
{
mOffsets[i] = mOffsets[i+1] + mCounters[byteIndex][i];
}
// Sort pass
for (int i = 0; i < mSortSize; ++i)
{
unsigned char byteVal = getByte(byteIndex, (*mSrc)[i].key);
if (byteVal > 127)
{
// -ve; pre-decrement since offsets set to count
(*mDest)[--mOffsets[byteVal]] = (*mSrc)[i];
}
else
{
// +ve
(*mDest)[mOffsets[byteVal]++] = (*mSrc)[i];
}
}
}
inline unsigned char getByte(int byteIndex, TCompValueType val)
{
#if OGRE_ENDIAN == OGRE_ENDIAN_LITTLE
return ((unsigned char*)(&val))[byteIndex];
#else
return ((unsigned char*)(&val))[mNumPasses - byteIndex - 1];
#endif
}
public:
RadixSort() {}
~RadixSort() {}
template <class TFunction>
void sort(TContainer& container, TFunction func)
{
if (container.empty())
return;
// Set up the sort areas
mSortSize = static_cast<int>(container.size());
mSortArea1.resize(container.size());
mSortArea2.resize(container.size());
// Copy data now (we need constant iterators for sorting)
mTmpContainer = container;
mNumPasses = sizeof(TCompValueType);
// Counter pass
// Initialise the counts
int p;
for (p = 0; p < mNumPasses; ++p)
memset(mCounters[p], 0, sizeof(int) * 256);
// Perform alpha pass to count
ContainerIter i = mTmpContainer.begin();
TCompValueType prevValue = func.operator()(*i);
bool needsSorting = false;
for (int u = 0; i != mTmpContainer.end(); ++i, ++u)
{
// get sort value
TCompValueType val = func.operator()(*i);
// cheap check to see if needs sorting (temporal coherence)
if (!needsSorting && val < prevValue)
needsSorting = true;
// Create a sort entry
mSortArea1[u].key = val;
mSortArea1[u].iter = i;
// increase counters
for (p = 0; p < mNumPasses; ++p)
{
unsigned char byteVal = getByte(p, val);
mCounters[p][byteVal]++;
}
prevValue = val;
}
// early exit if already sorted
if (!needsSorting)
return;
// Sort passes
mSrc = &mSortArea1;
mDest = &mSortArea2;
for (p = 0; p < mNumPasses - 1; ++p)
{
sortPass(p);
// flip src/dst
SortVector* tmp = mSrc;
mSrc = mDest;
mDest = tmp;
}
// Final pass may differ, make polymorphic
finalPass(p, prevValue);
// Copy everything back
int c = 0;
for (i = container.begin();
i != container.end(); ++i, ++c)
{
*i = *((*mDest)[c].iter);
}
}
};
}
#endif
Ogre::RadixSort::SortVector
std::vector< SortEntry, STLAllocator< SortEntry, GeneralAllocPolicy > > SortVector
Temp sort storage.
Definition: OgreRadixSort.h:113
Ogre::RadixSort::finalPass
void finalPass(int byteIndex, int val)
Definition: OgreRadixSort.h:147
Ogre::RadixSort::mSortSize
int mSortSize
Sort area size.
Definition: OgreRadixSort.h:99
Ogre::RadixSort::ContainerIter
TContainer::iterator ContainerIter
Definition: OgreRadixSort.h:91
Ogre::RadixSort::RadixSort
RadixSort()
Definition: OgreRadixSort.h:237
Ogre::RadixSort::sortPass
void sortPass(int byteIndex)
Definition: OgreRadixSort.h:121
Ogre::RadixSort::mSrc
SortVector * mSrc
Definition: OgreRadixSort.h:116
Ogre::RadixSort::mNumPasses
int mNumPasses
Number of passes for this type.
Definition: OgreRadixSort.h:101
Ogre::RadixSort::SortEntry::SortEntry
SortEntry()
Definition: OgreRadixSort.h:107
Ogre::RadixSort::getByte
unsigned char getByte(int byteIndex, TCompValueType val)
Definition: OgreRadixSort.h:226
Ogre::RadixSort::SortEntry::SortEntry
SortEntry(TCompValueType k, ContainerIter it)
Definition: OgreRadixSort.h:108
Ogre::RadixSort::~RadixSort
~RadixSort()
Definition: OgreRadixSort.h:238
Ogre::RadixSort::mSortArea1
SortVector mSortArea1
Definition: OgreRadixSort.h:114
Ogre::RadixSort::sort
void sort(TContainer &container, TFunction func)
Main sort function.
Definition: OgreRadixSort.h:246
OgrePrerequisites.h
Ogre::RadixSort::mTmpContainer
TContainer mTmpContainer
Definition: OgreRadixSort.h:118
Ogre::RadixSort::SortEntry
Definition: OgreRadixSort.h:103
Ogre::RadixSort::finalPass
void finalPass(int byteIndex, float val)
Definition: OgreRadixSort.h:180
Ogre::RadixSort::mDest
SortVector * mDest
Definition: OgreRadixSort.h:117
Ogre::RadixSort
Class for performing a radix sort (fast comparison-less sort based on byte value) on various standard...
Definition: OgreRadixSort.h:88
Ogre::RadixSort::SortEntry::key
TCompValueType key
Definition: OgreRadixSort.h:105
Ogre::RadixSort::SortEntry::iter
ContainerIter iter
Definition: OgreRadixSort.h:106
Ogre
Definition: OgreAndroidLogListener.h:34
Ogre::RadixSort::finalPass
void finalPass(int byteIndex, T val)
Definition: OgreRadixSort.h:140
Ogre::RadixSort::mCounters
int mCounters[4][256]
Alpha-pass counters of values (histogram) 4 of them so we can radix sort a maximum of a 32bit value...
Definition: OgreRadixSort.h:95
Ogre::RadixSort::mOffsets
int mOffsets[256]
Beta-pass offsets.
Definition: OgreRadixSort.h:97
Ogre::RadixSort::mSortArea2
SortVector mSortArea2
Definition: OgreRadixSort.h:115

Copyright © 2012 Torus Knot Software Ltd
This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License.