nevrax.org : docs

00001 
+00007 /* Copyright, 2001 Nevrax Ltd.
+00008  *
+00009  * This file is part of NEVRAX NEL.
+00010  * NEVRAX NEL is free software; you can redistribute it and/or modify
+00011  * it under the terms of the GNU General Public License as published by
+00012  * the Free Software Foundation; either version 2, or (at your option)
+00013  * any later version.
+00014 
+00015  * NEVRAX NEL is distributed in the hope that it will be useful, but
+00016  * WITHOUT ANY WARRANTY; without even the implied warranty of
+00017  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+00018  * General Public License for more details.
+00019 
+00020  * You should have received a copy of the GNU General Public License
+00021  * along with NEVRAX NEL; see the file COPYING. If not, write to the
+00022  * Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
+00023  * MA 02111-1307, USA.
+00024  */
+00025 
+00026 #ifndef NL_RADIX_SORT_H
+00027 #define NL_RADIX_SORT_H
+00028 
+00029 #include "nel/misc/types_nl.h"
+00030 #include "nel/misc/common.h"
+00031 
+00032 
+00033 namespace NL3D {
+00034 
+00035 
+00036 // ***************************************************************************
+00049 template<class T> class CRadixSort
+00050 {
+00051 public:
+00052 
+00062         CRadixSort(uint keyDepth= 32, uint digitDepth= 8)
+00063         {
+00064                 // setup
+00065                 _KeyDepth= keyDepth;
+00066                 NLMISC::clamp(_KeyDepth, 1U, 32U);
+00067                 _DigitDepth= digitDepth;
+00068                 NLMISC::clamp(_DigitDepth, 1U, 16U);
+00069                 _DigitDepth= std::min(_DigitDepth, _KeyDepth);
+00070 
+00071                 // resize the array of digits.
+00072                 _DigitSize= 1<<_DigitDepth;
+00073                 _SortDigits.resize(_DigitSize);
+00074         }
+00075 
+00084         T                               *sort(T *array0, T *array1, uint size) {return doSort(array0, array1, size, true);}
+00085 
+00086 
+00090         T                               *reverse_sort(T *array0, T *array1, uint size) {return doSort(array0, array1, size, false);}
+00091 
+00092 
+00093 // ***********************
+00094 private:
+00095 
+00096         struct  CSortDigit
+00097         {
+00098                 // For a digit, how many elements it has in the array.
+00099                 uint    Count;
+00100                 // current ptr where to write in destArray
+00101                 T               *Ptr;
+00102         };
+00103 
+00104         // setup
+00105         uint                    _KeyDepth;
+00106         uint                    _DigitDepth;
+00107         uint                    _DigitSize;
+00108         // We sort digits per digit (default is byte per byte)
+00109         std::vector<CSortDigit>         _SortDigits;
+00110 
+00111 
+00113         T                               *doSort(T *arraySrc, T *arrayDst, uint size, bool increasingOrder)
+00114         {
+00115                 if(size==0)
+00116                         return arraySrc;
+00117 
+00118                 // for all digits.
+00119                 for(uint        digit=0; digit< _KeyDepth; digit+=_DigitDepth )
+00120                 {
+00121                         sint    i;
+00122                         // how many bits do we shift?
+00123                         uint    digitShift= digit;
+00124                         uint    digitMask= _DigitSize - 1;
+00125 
+00126                         // Init digit count.
+00127                         for(i=0; i<(sint)_DigitSize; i++)
+00128                         {
+00129                                 _SortDigits[i].Count= 0;
+00130                         }
+00131 
+00132                         // for all elements in array, count the usage of current digit.
+00133                         T       *srcPtr= arraySrc;
+00134                         for(i=0; i<(sint)size; i++, srcPtr++)
+00135                         {
+00136                                 // get the key for this element
+00137                                 uint32  key= srcPtr->getRadixKey();
+00138                                 // get the actual digit of interest
+00139                                 key>>= digitShift;
+00140                                 key&= digitMask;
+00141                                 // increment the use of this digit.
+00142                                 _SortDigits[key].Count++;
+00143                         }
+00144 
+00145                         // for all digit, init start Ptr.
+00146                         T       *dstPtr= arrayDst;
+00147                         if(increasingOrder)
+00148                         {
+00149                                 for(i=0; i<(sint)_DigitSize; i++)
+00150                                 {
+00151                                         // setup the dest ptr for this digit.
+00152                                         _SortDigits[i].Ptr= dstPtr;
+00153                                         // increment the ptr of digit usage
+00154                                         dstPtr+= _SortDigits[i].Count;
+00155                                 }
+00156                         }
+00157                         else
+00158                         {
+00159                                 // reverse order of copy for digits, so the biggest one will 
+00160                                 // copy in the beginning of the array
+00161                                 for(i=_DigitSize-1; i>=0; i--)
+00162                                 {
+00163                                         // setup the dest ptr for this digit.
+00164                                         _SortDigits[i].Ptr= dstPtr;
+00165                                         // increment the ptr of digit usage
+00166                                         dstPtr+= _SortDigits[i].Count;
+00167                                 }
+00168                         }
+00169 
+00170                         // for all elements, sort for this digit, by copying from src to dest.
+00171                         srcPtr= arraySrc;
+00172                         for(i=0; i<(sint)size; i++, srcPtr++)
+00173                         {
+00174                                 // get the key for this element
+00175                                 uint32  key= srcPtr->getRadixKey();
+00176                                 // get the actual digit of interest
+00177                                 key>>= digitShift;
+00178                                 key&= digitMask;
+00179                                 // copy to good digit dst, and increment dest ptr.
+00180                                 *(_SortDigits[key].Ptr++)= *srcPtr;
+00181                         }
+00182 
+00183                         // arraDst has now values of arraySrc sorted for the current digit.
+00184                         // now, restart with next digit, so swap src / dst
+00185                         std::swap(arraySrc, arrayDst);
+00186                 }
+00187 
+00188                 // return the array correctly sorted. because of last swap, this is arraySrc
+00189                 return arraySrc;
+00190         }
+00191 
+00192 };
+00193 
+00194 
+00195 } // NL3D
+00196 
+00197 
+00198 #endif // NL_RADIX_SORT_H
+00199 
+00200 /* End of radix_sort.h */
+