OgreRadixSort.h

Go to the documentation of this file.
00001 /*
00002 -----------------------------------------------------------------------------
00003 This source file is part of OGRE
00004     (Object-oriented Graphics Rendering Engine)
00005 For the latest info, see http://www.ogre3d.org/
00006 
00007 Copyright (c) 2000-2006 Torus Knot Software Ltd
00008 Also see acknowledgements in Readme.html
00009 
00010 This program is free software; you can redistribute it and/or modify it under
00011 the terms of the GNU Lesser General Public License as published by the Free Software
00012 Foundation; either version 2 of the License, or (at your option) any later
00013 version.
00014 
00015 This program is distributed in the hope that it will be useful, but WITHOUT
00016 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
00017 FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.
00018 
00019 You should have received a copy of the GNU Lesser General Public License along with
00020 this program; if not, write to the Free Software Foundation, Inc., 59 Temple
00021 Place - Suite 330, Boston, MA 02111-1307, USA, or go to
00022 http://www.gnu.org/copyleft/lesser.txt.
00023 
00024 You may alternatively use this source under the terms of a specific version of
00025 the OGRE Unrestricted License provided you have obtained such a license from
00026 Torus Knot Software Ltd.
00027 -----------------------------------------------------------------------------
00028 */
00029 #ifndef __RadixSort_H__
00030 #define __RadixSort_H__
00031 
00032 #include "OgrePrerequisites.h"
00033 
00034 namespace Ogre {
00035 
00082     template <class TContainer, class TContainerValueType, typename TCompValueType>
00083     class RadixSort
00084     {
00085     public:
00086         typedef typename TContainer::iterator ContainerIter;
00087     protected:
00090         int mCounters[4][256];
00092         int mOffsets[256];
00094         int mSortSize;
00096         int mNumPasses;
00097 
00098         struct SortEntry
00099         {
00100             TCompValueType key;
00101             ContainerIter iter;
00102             SortEntry() {}
00103             SortEntry(TCompValueType k, ContainerIter it)
00104                 : key(k), iter(it) {}
00105 
00106         };
00108         std::vector<SortEntry> mSortArea1;
00109         std::vector<SortEntry> mSortArea2;
00110         std::vector<SortEntry>* mSrc;
00111         std::vector<SortEntry>* mDest;
00112         TContainer mTmpContainer; // initial copy
00113 
00114 
00115         void sortPass(int byteIndex)
00116         {
00117             // Calculate offsets
00118             // Basically this just leaves gaps for duplicate entries to fill
00119             mOffsets[0] = 0;
00120             for (int i = 1; i < 256; ++i)
00121             {
00122                 mOffsets[i] = mOffsets[i-1] + mCounters[byteIndex][i-1];
00123             }
00124 
00125             // Sort pass
00126             for (int i = 0; i < mSortSize; ++i)
00127             {
00128                 unsigned char byteVal = getByte(byteIndex, (*mSrc)[i].key);
00129                 (*mDest)[mOffsets[byteVal]++] = (*mSrc)[i];
00130             }
00131 
00132         }
00133         template <typename T>
00134         void finalPass(int byteIndex, T val)
00135         {
00136             // default is to do normal pass
00137             sortPass(byteIndex);
00138         }
00139         
00140         // special case signed int
00141         void finalPass(int byteIndex, int val)
00142         {
00143             int numNeg = 0;
00144             // all negative values are in entries 128+ in most significant byte
00145             for (int i = 128; i < 256; ++i)
00146             {
00147                 numNeg += mCounters[byteIndex][i];
00148             }
00149             // Calculate offsets - positive ones start at the number of negatives
00150             // do positive numbers
00151             mOffsets[0] = numNeg;
00152             for (int i = 1; i < 128; ++i)
00153             {
00154                 mOffsets[i] = mOffsets[i-1] + mCounters[byteIndex][i-1];
00155             }
00156             // Do negative numbers (must start at zero)
00157             // No need to invert ordering, already correct (-1 is highest number)
00158             mOffsets[128] = 0;
00159             for (int i = 129; i < 256; ++i)
00160             {
00161                 mOffsets[i] = mOffsets[i-1] + mCounters[byteIndex][i-1];
00162             }
00163 
00164             // Sort pass
00165             for (int i = 0; i < mSortSize; ++i)
00166             {
00167                 unsigned char byteVal = getByte(byteIndex, (*mSrc)[i].key);
00168                 (*mDest)[mOffsets[byteVal]++] = (*mSrc)[i];
00169             }
00170         }
00171         
00172 
00173         // special case float
00174         void finalPass(int byteIndex, float val)
00175         {
00176             // floats need to be special cased since negative numbers will come
00177             // after positives (high bit = sign) and will be in reverse order
00178             // (no ones-complement of the +ve value)
00179             int numNeg = 0;
00180             // all negative values are in entries 128+ in most significant byte
00181             for (int i = 128; i < 256; ++i)
00182             {
00183                 numNeg += mCounters[byteIndex][i];
00184             }
00185             // Calculate offsets - positive ones start at the number of negatives
00186             // do positive numbers normally
00187             mOffsets[0] = numNeg;
00188             for (int i = 1; i < 128; ++i)
00189             {
00190                 mOffsets[i] = mOffsets[i-1] + mCounters[byteIndex][i-1];
00191             }
00192             // Do negative numbers (must start at zero)
00193             // Also need to invert ordering
00194             // In order to preserve the stability of the sort (essential since
00195             // we rely on previous bytes already being sorted) we have to count
00196             // backwards in our offsets from 
00197             mOffsets[255] = mCounters[byteIndex][255];
00198             for (int i = 254; i > 127; --i)
00199             {
00200                 mOffsets[i] = mOffsets[i+1] + mCounters[byteIndex][i];
00201             }
00202 
00203             // Sort pass
00204             for (int i = 0; i < mSortSize; ++i)
00205             {
00206                 unsigned char byteVal = getByte(byteIndex, (*mSrc)[i].key);
00207                 if (byteVal > 127)
00208                 {
00209                     // -ve; pre-decrement since offsets set to count
00210                     (*mDest)[--mOffsets[byteVal]] = (*mSrc)[i];
00211                 }
00212                 else
00213                 {
00214                     // +ve
00215                     (*mDest)[mOffsets[byteVal]++] = (*mSrc)[i];
00216                 }
00217             }
00218         }
00219 
00220         inline unsigned char getByte(int byteIndex, TCompValueType val)
00221         {
00222 #if OGRE_ENDIAN == OGRE_ENDIAN_LITTLE
00223             return ((unsigned char*)(&val))[byteIndex];
00224 #else
00225             return ((unsigned char*)(&val))[mNumPasses - byteIndex - 1];
00226 #endif
00227         }
00228 
00229     public:
00230 
00231         RadixSort() {}
00232         ~RadixSort() {}
00233 
00239         template <class TFunction>
00240         void sort(TContainer& container, TFunction func)
00241         {
00242             if (container.empty())
00243                 return;
00244 
00245             // Set up the sort areas
00246             mSortSize = static_cast<int>(container.size());
00247             mSortArea1.resize(container.size());
00248             mSortArea2.resize(container.size());
00249 
00250             // Copy data now (we need constant iterators for sorting)
00251             mTmpContainer = container;
00252 
00253             mNumPasses = sizeof(TCompValueType);
00254 
00255             // Counter pass
00256             // Initialise the counts
00257             int p;
00258             for (p = 0; p < mNumPasses; ++p)
00259                 memset(mCounters[p], 0, sizeof(int) * 256);
00260 
00261             // Perform alpha pass to count
00262             ContainerIter i = mTmpContainer.begin();
00263             TCompValueType prevValue = func.operator()(*i); 
00264             bool needsSorting = false;
00265             for (int u = 0; i != mTmpContainer.end(); ++i, ++u)
00266             {
00267                 // get sort value
00268                 TCompValueType val = func.operator()(*i);
00269                 // cheap check to see if needs sorting (temporal coherence)
00270                 if (!needsSorting && val < prevValue)
00271                     needsSorting = true;
00272 
00273                 // Create a sort entry
00274                 mSortArea1[u].key = val;
00275                 mSortArea1[u].iter = i;
00276 
00277                 // increase counters
00278                 for (p = 0; p < mNumPasses; ++p)
00279                 {
00280                     unsigned char byteVal = getByte(p, val);
00281                     mCounters[p][byteVal]++;
00282                 }
00283 
00284                 prevValue = val;
00285 
00286             }
00287 
00288             // early exit if already sorted
00289             if (!needsSorting)
00290                 return;
00291 
00292 
00293             // Sort passes
00294             mSrc = &mSortArea1;
00295             mDest = &mSortArea2;
00296 
00297             for (p = 0; p < mNumPasses - 1; ++p)
00298             {
00299                 sortPass(p);
00300                 // flip src/dst
00301                 std::vector<SortEntry>* tmp = mSrc;
00302                 mSrc = mDest;
00303                 mDest = tmp;
00304             }
00305             // Final pass may differ, make polymorphic
00306             finalPass(p, prevValue);
00307 
00308             // Copy everything back
00309             int c = 0;
00310             for (i = container.begin(); 
00311                 i != container.end(); ++i, ++c)
00312             {
00313                 *i = *((*mDest)[c].iter);
00314             }
00315         }
00316 
00317     };
00318 
00319 
00320 }
00321 #endif
00322 

Copyright © 2008 Torus Knot Software Ltd
Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 2.5 License.
Last modified Sun Sep 27 22:02:25 2009