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