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-2012 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