HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
UT_RadixSort.h
Go to the documentation of this file.
1 /*
2  * PROPRIETARY INFORMATION. This software is proprietary to
3  * Side Effects Software Inc., and is not to be reproduced,
4  * transmitted, or disclosed in any way without written permission.
5  *
6  * NAME: Utility Library (C++)
7  *
8  * COMMENTS:
9  * This is a class which implements a radix sort, but for 4 byte
10  * integer and (IEEE) floating point numbers. The sort algorithms
11  * take endianness into consideration so the user does not need to
12  * worry about it.
13  *
14  * This class is based off of the comments on Pierre Terdiman's
15  * web page "Radix Sort Revisted" as well as the provided source
16  * code.
17  *
18  * http://www.codercorner.com/RadixSortRevisited.htm
19  *
20  * Original code:
21  * Source code for "Radix Sort Revisited"
22  * (C) 2000, Pierre Terdiman (p.terdiman@wanadoo.fr)
23  */
24 
25 #ifndef __UT_RadixSort_h__
26 #define __UT_RadixSort_h__
27 
28 #include "UT_API.h"
29 #include <SYS/SYS_Types.h>
30 
32 {
33 public:
34  UT_RadixSort();
35  ~UT_RadixSort();
36 
37  // Sorting methods
38  // After sorting, use the getIndices() method to get the
39  // list of indices in sorted order.
40  // NB: The input array is NOT sorted by this routine,
41  // you must use the index array to figure out where
42  // each element belongs.
43  UT_RadixSort& sort(uint *input, uint nb,
44  bool signedvalues=true);
45  UT_RadixSort& sort(float *input, uint nb);
46 
47  // Return a pointer to the list of indices in sorted order.
48  // This list is internally stored in myIndices.
49  unsigned int *getIndices() { return myIndices; }
50 
51  // Reset the internal indices. Note that the list of indices
52  // in sorted order is kept internally and is checked at the
53  // beginning of the sort routine to check if the list is
54  // already sorted.
55  UT_RadixSort &resetIndices();
56 
57  // Return the amount of ram used by this particular object.
58  uint getUsedRam();
59 private:
60  void resizeIndices(unsigned int new_size);
61 
62  uint *myHistogram; // Counters for each byte
63  uint *myOffset; // Offsets (nearly a cumulative
64  // distribution function)
65 
66  uint myCurrentSize; // Current size of the indices list
67 
68  uint *myIndices; // Two lists, swapped each pass
69  uint *myIndices2;
70 };
71 
72 #endif // __UT_RadixSort_h__
#define UT_API
Definition: UT_API.h:12
unsigned int * getIndices()
Definition: UT_RadixSort.h:49
unsigned int uint
Definition: SYS_Types.h:39