Home

nevrax.com

Nevrax.org News Mailing-list Documentation CVS Bugs License

Documentation                       Search   radix_sort.h Go to the documentation of this file. /* Copyright, 2001 Nevrax Ltd. * * This file is part of NEVRAX NEL. * NEVRAX NEL is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 2, or (at your option) * any later version. * NEVRAX NEL 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 * General Public License for more details. * You should have received a copy of the GNU General Public License * along with NEVRAX NEL; see the file COPYING. If not, write to the * Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, * MA 02111-1307, USA. */ #ifndef NL_RADIX_SORT_H #define NL_RADIX_SORT_H #include "nel/misc/types_nl.h" #include "nel/misc/common.h" namespace NL3D { // *************************************************************************** template<class T> class CRadixSort { public: CRadixSort(uint keyDepth= 32, uint digitDepth= 8) { // setup _KeyDepth= keyDepth; NLMISC::clamp(_KeyDepth, 1U, 32U); _DigitDepth= digitDepth; NLMISC::clamp(_DigitDepth, 1U, 16U); _DigitDepth= std::min(_DigitDepth, _KeyDepth); // resize the array of digits. _DigitSize= 1<<_DigitDepth; _SortDigits.resize(_DigitSize); } T *sort(T *array0, T *array1, uint size) {return doSort(array0, array1, size, true);} T *reverse_sort(T *array0, T *array1, uint size) {return doSort(array0, array1, size, false);} // *********************** private: struct CSortDigit { // For a digit, how many elements it has in the array. uint Count; // current ptr where to write in destArray T *Ptr; }; // setup uint _KeyDepth; uint _DigitDepth; uint _DigitSize; // We sort digits per digit (default is byte per byte) std::vector<CSortDigit> _SortDigits; T *doSort(T *arraySrc, T *arrayDst, uint size, bool increasingOrder) { if(size==0) return arraySrc; // for all digits. for(uint digit=0; digit< _KeyDepth; digit+=_DigitDepth ) { sint i; // how many bits do we shift? uint digitShift= digit; uint digitMask= _DigitSize - 1; // Init digit count. for(i=0; i<(sint)_DigitSize; i++) { _SortDigits[i].Count= 0; } // for all elements in array, count the usage of current digit. T *srcPtr= arraySrc; for(i=0; i<(sint)size; i++, srcPtr++) { // get the key for this element uint32 key= srcPtr->getRadixKey(); // get the actual digit of interest key>>= digitShift; key&= digitMask; // increment the use of this digit. _SortDigits[key].Count++; } // for all digit, init start Ptr. T *dstPtr= arrayDst; if(increasingOrder) { for(i=0; i<(sint)_DigitSize; i++) { // setup the dest ptr for this digit. _SortDigits[i].Ptr= dstPtr; // increment the ptr of digit usage dstPtr+= _SortDigits[i].Count; } } else { // reverse order of copy for digits, so the biggest one will // copy in the beginning of the array for(i=_DigitSize-1; i>=0; i--) { // setup the dest ptr for this digit. _SortDigits[i].Ptr= dstPtr; // increment the ptr of digit usage dstPtr+= _SortDigits[i].Count; } } // for all elements, sort for this digit, by copying from src to dest. srcPtr= arraySrc; for(i=0; i<(sint)size; i++, srcPtr++) { // get the key for this element uint32 key= srcPtr->getRadixKey(); // get the actual digit of interest key>>= digitShift; key&= digitMask; // copy to good digit dst, and increment dest ptr. *(_SortDigits[key].Ptr++)= *srcPtr; } // arraDst has now values of arraySrc sorted for the current digit. // now, restart with next digit, so swap src / dst std::swap(arraySrc, arrayDst); } // return the array correctly sorted. because of last swap, this is arraySrc return arraySrc; } }; } // NL3D #endif // NL_RADIX_SORT_H /* End of radix_sort.h */