Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: code/branches/ode/ode-0.9/OPCODE/Ice/IceRevisitedRadix.h @ 216

Last change on this file since 216 was 216, checked in by mathiask, 17 years ago

[Physik] add ode-0.9

File size: 2.5 KB
Line 
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__
Note: See TracBrowser for help on using the repository browser.