source: OGRE/trunk/ogrenew/OgreMain/include/OgreRadixSort.h @ 692

/*
-----------------------------------------------------------------------------
This source file is part of OGRE
    (Object-oriented Graphics Rendering Engine)
For the latest info, see http://www.ogre3d.org/

Copyright (c) 2000-2005 The OGRE Team
Also see acknowledgements in Readme.html

This program is free software; you can redistribute it and/or modify it under
the terms of the GNU Lesser General Public License as published by the Free Software
Foundation; either version 2 of the License, or (at your option) any later
version.

This program is distributed in the hope that it will be useful, but WITHOUT
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along with
this program; if not, write to the Free Software Foundation, Inc., 59 Temple
Place - Suite 330, Boston, MA 02111-1307, USA, or go to
http://www.gnu.org/copyleft/lesser.txt.
-----------------------------------------------------------------------------
*/
#ifndef __RadixSort_H__
#define __RadixSort_H__

#include "OgrePrerequisites.h"

namespace Ogre {

        /** 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
                std::vector<SortEntry> mSortArea1;
                std::vector<SortEntry> mSortArea2;
                std::vector<SortEntry>* mSrc;
                std::vector<SortEntry>* 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
                                std::vector<SortEntry>* 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