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 GetRanks()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. GetRecyclable()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. GetNbTotalCalls()45 inline_ udword GetNbTotalCalls() const { return mTotalCalls; } 46 //! Returns the number of eraly exits due to temporal coherence. GetNbHits()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__ 66