OPCODE/Ice/IceRevisitedRadix.h

   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__