source: downloads/ogre_src_v1-9-0/OgreMain/include/OgreRadixSort.h

/*
-----------------------------------------------------------------------------
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 {

        /** \addtogroup Core
        *  @{
        */
        /** \addtogroup General
        *  @{
        */
        /** Class for performing a radix sort (fast comparison-less sort based on 
                byte value) on various standard STL containers. 
        @remarks
                A radix sort is a very fast sort algorithm. It doesn't use comparisons
                and thus is able to break the theoretical minimum O(N*logN) complexity. 
                Radix sort is complexity O(k*N), where k is a constant. Note that radix
                sorting is not in-place, it requires additional storage, so it trades
                memory for speed. The overhead of copying means that it is only faster
                for fairly large datasets, so you are advised to only use it for collections
                of at least a few hundred items.
        @par
                This is a template class to allow it to deal with a variety of containers, 
                and a variety of value types to sort on. In addition to providing the
                container and value type on construction, you also need to supply a 
                functor object which will retrieve the value to compare on for each item
                in the list. For example, if you had an std::vector of by-value instances
                of an object of class 'Bibble', and you wanted to sort on 
                Bibble::getDoobrie(), you'd have to firstly create a functor
                like this:
        @code
                struct BibbleSortFunctor
                {
                        float operator()(const Bibble& val) const
                        {
                                return val.getDoobrie();
                        }
                }
        @endcode
                Then, you need to declare a RadixSort class which names the container type, 
                the value type in the container, and the type of the value you want to 
                sort by. You can then call the sort function. E.g.
        @code
                RadixSort<BibbleList, Bibble, float> radixSorter;
                BibbleSortFunctor functor;

                radixSorter.sort(myBibbleList, functor);
        @endcode
                You should try to reuse RadixSort instances, since repeated allocation of the 
                internal storage is then avoided.
        @note
                Radix sorting is often associated with just unsigned integer values. Our
                implementation can handle both unsigned and signed integers, as well as
                floats (which are often not supported by other radix sorters). doubles
                are not supported; you will need to implement your functor object to convert
                to float if you wish to use this sort routine.
        */
        template <class TContainer, class TContainerValueType, typename TCompValueType>
        class RadixSort
        {
        public:
                typedef typename TContainer::iterator ContainerIter;
        protected:
                /// Alpha-pass counters of values (histogram)
                /// 4 of them so we can radix sort a maximum of a 32bit value
                int mCounters[4][256];
                /// Beta-pass offsets 
                int mOffsets[256];
                /// Sort area size
                int mSortSize;
                /// Number of passes for this type
                int mNumPasses;

                struct SortEntry
                {
                        TCompValueType key;
                        ContainerIter iter;
                        SortEntry() {}
                        SortEntry(TCompValueType k, ContainerIter it)
                                : key(k), iter(it) {}

                };
                /// Temp sort storage
                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() {}

                /** Main sort function
                @param container A container of the type you declared when declaring
                @param func A functor which returns the value for comparison when given
                        a container value
                */
                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