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