From 0ea5fc66924303d1bf73ba283a383e2aadee02f2 Mon Sep 17 00:00:00 2001 From: neodarz Date: Sat, 11 Aug 2018 20:21:34 +0200 Subject: Initial commit --- docs/doxygen/nel/a03300.html | 505 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 505 insertions(+) create mode 100644 docs/doxygen/nel/a03300.html (limited to 'docs/doxygen/nel/a03300.html') diff --git a/docs/doxygen/nel/a03300.html b/docs/doxygen/nel/a03300.html new file mode 100644 index 00000000..f80d84bd --- /dev/null +++ b/docs/doxygen/nel/a03300.html @@ -0,0 +1,505 @@ + + +NeL: TemplateNL3D::CRadixSort< T > class Reference + + + +
+Main Page | Namespace List | Class Hierarchy | Alphabetical List | Data Structures | File List | Namespace Members | Data Fields | Globals | Related Pages | Search for 
+

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: +

+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. +

+

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         }
+
+

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(). +

+

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         }
+
+

+ + + + +
+ + + + + + + + + + + + + + + + + + + + + + + + + + + + +
+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. +

+

00090 {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. +

+

00084 {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: +
Generated on Tue Mar 16 07:36:07 2004 for NeL by + +doxygen +1.3.6
+ + -- cgit v1.2.1