NL3D::CRadixSort< T > Class Template Reference

#include <radix_sort.h>

---

Detailed Description

template<class T>
class NL3D::CRadixSort< T >

A class which sort elements T with radix sort algorithm. T must follow the following interface:

• uint32 getRadixKey() const;
• have a correct operator=()

getRadixKey() return the unsigned key for this element.

Author:

Lionel Berenguier

Nevrax France

Date:

2001

Definition at line 49 of file radix_sort.h.

Public Member Functions
	CRadixSort (uint keyDepth=32, uint digitDepth=8)
T *	reverse_sort (T *array0, T *array1, uint size)
T *	sort (T *array0, T *array1, uint size)
Private Member Functions
T *	doSort (T *arraySrc, T *arrayDst, uint size, bool increasingOrder)
	radix sort algorithm
Private Attributes
uint	_DigitDepth
uint	_DigitSize
uint	_KeyDepth
std::vector< CSortDigit >	_SortDigits

---

Constructor & Destructor Documentation

template<class T> NL3D::CRadixSort< T >::CRadixSort (  uint  keyDepth = 32, uint  digitDepth = 8 )  [inline]

Constructor Parameters: keyDepth  default is 32 bits, but if as example you're sure that you just use 14 bits, you can set keyDepth=14. Clamped to 1,32. digitDepth  default is 8 bits. The sort will do ceil(keyDepth/digitDepth) pass in Sort. But be aware that a CRadixSort object has a size of (1<<digitDepth) * 8 bytes. (2K for digitDepth=8). Be aware too that values>8 is not a really good idea because of cache, and random access... And this REALLY impact (eg: from 1 to 100 if you choose 16 instead than 8...) Clamped to 1,min(16, keyDepth). Definition at line 62 of file radix_sort.h. References NL3D::CRadixSort< T >::_DigitDepth, NL3D::CRadixSort< T >::_DigitSize, NL3D::CRadixSort< T >::_KeyDepth, NL3D::CRadixSort< T >::_SortDigits, NLMISC::clamp(), min, and uint. { // 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); }

---

Member Function Documentation

template<class T> T* NL3D::CRadixSort< T >::doSort (  T *  arraySrc, T *  arrayDst, uint  size, bool  increasingOrder )  [inline, private]

radix sort algorithm Definition at line 113 of file radix_sort.h. References NL3D::CRadixSort< T >::_DigitDepth, NL3D::CRadixSort< T >::_DigitSize, NL3D::CRadixSort< T >::_KeyDepth, NL3D::CRadixSort< T >::_SortDigits, sint, size, uint, and uint32. Referenced by NL3D::CRadixSort< T >::reverse_sort(), and NL3D::CRadixSort< T >::sort(). { 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; }

template<class T> T* NL3D::CRadixSort< T >::reverse_sort (  T *  array0, T *  array1, uint  size )  [inline]

same as sort(), but elements are reordered in decreasing order See also: sort() Definition at line 90 of file radix_sort.h. References NL3D::CRadixSort< T >::doSort(), size, and uint. {return doSort(array0, array1, size, false);}

template<class T> T* NL3D::CRadixSort< T >::sort (  T *  array0, T *  array1, uint  size )  [inline]

Sort an array of T, in (keyDepth/digitSize)*O(size). Elements are reordered in increasing order. Parameters: array0  ptr on elements to be sorted. array1  an array of T which must be allocated with same size. size  the number of elements. Returns: the array which have sorted elements. Actually return array0 if ceil(keyDepth/digitDepth) is pair, else return array1. The other array has elements in undefined order. Definition at line 84 of file radix_sort.h. References NL3D::CRadixSort< T >::doSort(), size, and uint. {return doSort(array0, array1, size, true);}

---

Field Documentation

template<class T> uint NL3D::CRadixSort< T >::_DigitDepth [private]

Definition at line 106 of file radix_sort.h. Referenced by NL3D::CRadixSort< T >::CRadixSort(), and NL3D::CRadixSort< T >::doSort().

template<class T> uint NL3D::CRadixSort< T >::_DigitSize [private]

Definition at line 107 of file radix_sort.h. Referenced by NL3D::CRadixSort< T >::CRadixSort(), and NL3D::CRadixSort< T >::doSort().

template<class T> uint NL3D::CRadixSort< T >::_KeyDepth [private]

Definition at line 105 of file radix_sort.h. Referenced by NL3D::CRadixSort< T >::CRadixSort(), and NL3D::CRadixSort< T >::doSort().

template<class T> std::vector<CSortDigit> NL3D::CRadixSort< T >::_SortDigits [private]

Definition at line 109 of file radix_sort.h. Referenced by NL3D::CRadixSort< T >::CRadixSort(), and NL3D::CRadixSort< T >::doSort().

---

The documentation for this class was generated from the following file:

• radix_sort.h

---