| 1 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
|---|
| 2 | /** |
|---|
| 3 | * Contains source code from the article "Radix Sort Revisited". |
|---|
| 4 | * \file IceRevisitedRadix.h |
|---|
| 5 | * \author Pierre Terdiman |
|---|
| 6 | * \date April, 4, 2000 |
|---|
| 7 | */ |
|---|
| 8 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
|---|
| 9 | |
|---|
| 10 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
|---|
| 11 | // Include Guard |
|---|
| 12 | #ifndef __ICERADIXSORT_H__ |
|---|
| 13 | #define __ICERADIXSORT_H__ |
|---|
| 14 | |
|---|
| 15 | //! Allocate histograms & offsets locally |
|---|
| 16 | #define RADIX_LOCAL_RAM |
|---|
| 17 | |
|---|
| 18 | enum RadixHint |
|---|
| 19 | { |
|---|
| 20 | RADIX_SIGNED, //!< Input values are signed |
|---|
| 21 | RADIX_UNSIGNED, //!< Input values are unsigned |
|---|
| 22 | |
|---|
| 23 | RADIX_FORCE_DWORD = 0x7fffffff |
|---|
| 24 | }; |
|---|
| 25 | |
|---|
| 26 | class ICECORE_API RadixSort |
|---|
| 27 | { |
|---|
| 28 | public: |
|---|
| 29 | // Constructor/Destructor |
|---|
| 30 | RadixSort(); |
|---|
| 31 | ~RadixSort(); |
|---|
| 32 | // Sorting methods |
|---|
| 33 | RadixSort& Sort(const udword* input, udword nb, RadixHint hint=RADIX_SIGNED); |
|---|
| 34 | RadixSort& Sort(const float* input, udword nb); |
|---|
| 35 | |
|---|
| 36 | //! Access to results. mRanks is a list of indices in sorted order, i.e. in the order you may further process your data |
|---|
| 37 | inline_ const udword* GetRanks() const { return mRanks; } |
|---|
| 38 | |
|---|
| 39 | //! mIndices2 gets trashed on calling the sort routine, but otherwise you can recycle it the way you want. |
|---|
| 40 | inline_ udword* GetRecyclable() const { return mRanks2; } |
|---|
| 41 | |
|---|
| 42 | // Stats |
|---|
| 43 | udword GetUsedRam() const; |
|---|
| 44 | //! Returns the total number of calls to the radix sorter. |
|---|
| 45 | inline_ udword GetNbTotalCalls() const { return mTotalCalls; } |
|---|
| 46 | //! Returns the number of eraly exits due to temporal coherence. |
|---|
| 47 | inline_ udword GetNbHits() const { return mNbHits; } |
|---|
| 48 | |
|---|
| 49 | private: |
|---|
| 50 | #ifndef RADIX_LOCAL_RAM |
|---|
| 51 | udword* mHistogram; //!< Counters for each byte |
|---|
| 52 | udword* mOffset; //!< Offsets (nearly a cumulative distribution function) |
|---|
| 53 | #endif |
|---|
| 54 | udword mCurrentSize; //!< Current size of the indices list |
|---|
| 55 | udword* mRanks; //!< Two lists, swapped each pass |
|---|
| 56 | udword* mRanks2; |
|---|
| 57 | // Stats |
|---|
| 58 | udword mTotalCalls; //!< Total number of calls to the sort routine |
|---|
| 59 | udword mNbHits; //!< Number of early exits due to coherence |
|---|
| 60 | // Internal methods |
|---|
| 61 | void CheckResize(udword nb); |
|---|
| 62 | bool Resize(udword nb); |
|---|
| 63 | }; |
|---|
| 64 | |
|---|
| 65 | #endif // __ICERADIXSORT_H__ |
|---|
