[216] | 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__ |
---|