HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
UT_QuickSort.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  */
7 
8 #ifndef __UT_QuickSort__
9 #define __UT_QuickSort__
10 
11 #include "UT_API.h"
12 #include <stddef.h> // For definition of size_t
13 #include "UT_IntArray.h"
14 
15 #if 0
16 typedef int UTcompareFunc(void * /*userdata*/, const void *, const void *);
17 #endif
18 
19 /// This is a bare bones implementation of the Quick Sort,
20 /// so those who don't believe in Radix sort have something to use.
22 {
23 public:
24  UT_QuickSort();
25  virtual ~UT_QuickSort();
26 
27  /// Sorting methods
28  /// After sorting, use the getIndices() method to get the
29  /// list of indices in sorted order.
30  /// NB: Unlike the UT_RadixSort, the input array IS sorted
31  /// with this quick sort.
32  // @{
33  UT_QuickSort& sort(unsigned int *input, unsigned int nb,
34  int useindex = 1,
35  bool signedvalues=true);
36  UT_QuickSort& sort(fpreal32 *input, unsigned int nb,
37  int useindex = 1);
38  UT_QuickSort& sort(fpreal64 *input, unsigned int nb,
39  int useindex = 1);
40  // @}
41 
42  enum compareType {
45  COMPARE_FLOAT
46  };
47 
48  /// The following sort method is used to sort arbitrary structures.
49  /// The first element of the structure must be an int, unsigned, or
50  /// a float depending on the compareType chosen.
51  UT_QuickSort& sort(void *input, size_t size, unsigned int nb,
52  compareType type);
53 
54 #if 0
55  /// The following sort method is used to sort arbitrary structures.
56  static void sort(void *input, size_t size, unsigned int nb,
57  void *userdata, UTcompareFunc *cmp);
58 #endif
59 
60  /// Return a pointer to the list of indices in sorted order.
61  /// This list is internally stored in myIndices.
62  int* getIndices() { return &myIndices(0); }
63 
64  int operator()(int idx) { return myIndices((unsigned)idx); }
65 
66  /// Reset the internal indices. Note that the list of indices
67  /// in sorted order is kept internally and is checked at the
68  /// beginning of the sort routine to check if the list is
69  /// already sorted.
70  UT_QuickSort& resetIndices() { myIndices.setCapacity(0); return *this; }
71 
72  /// Return the amount of ram used by this particular object.
73  int64 getUsedRam() const
74  { return myIndices.getMemoryUsage(); }
75 protected:
77 
78  /// These are the unsigned, signed, and float sort routines.
79  /// The ones without an index variable don't sort an index array
80  /// along with the main array.
81  // @{
82  static void uisort(unsigned int *input, int *index, int len);
83  static void sisort(int *input, int *index, int len);
84  static void fisort(fpreal32 *input, int *index, int len);
85  static void fisort(fpreal32 *input, int len);
86  static void disort(fpreal64 *input, int *index, int len);
87  static void disort(fpreal64 *input, int len);
88  static void sisort(int *input, int len);
89  static void uisort(unsigned int *input, int len);
90  static void disort(void *input, size_t size, int len, char *tinput);
91  static void fisort(void *input, size_t size, int len, char *tinput);
92  static void sisort(void *input, size_t size, int len, char *tinput);
93  static void uisort(void *input, size_t size, int len, char *tinput);
94  // @}
95 
96  static void urecurse(unsigned int *input, int *index, int len);
97  static void srecurse(int *input, int *index, int len);
98  static void frecurse(fpreal32 *input, int *index, int len);
99  static void drecurse(fpreal64 *input, int *index, int len);
100 
101  static void frecurse(fpreal32 *input, int len);
102  static void drecurse(fpreal64 *input, int len);
103  static void srecurse(int *input, int len);
104  static void urecurse(unsigned int *input, int len);
105 
106  static void drecurse(void *input, size_t size, int len,
107  char *tinput);
108  static void frecurse(void *input, size_t size, int len,
109  char *tinput);
110  static void srecurse(void *input, size_t size, int len,
111  char *tinput);
112  static void urecurse(void *input, size_t size, int len,
113  char *tinput);
114 };
115 
116 #endif
UT_QuickSort & resetIndices()
Definition: UT_QuickSort.h:70
#define UT_API
Definition: UT_API.h:12
GLsizeiptr size
Definition: glcorearb.h:663
long long int64
Definition: SYS_Types.h:100
double fpreal64
Definition: SYS_Types.h:185
int cmp(T a, T b)
Definition: ImathFun.h:119
int64 getUsedRam() const
Return the amount of ram used by this particular object.
Definition: UT_QuickSort.h:73
GLuint index
Definition: glcorearb.h:785
int operator()(int idx)
Definition: UT_QuickSort.h:64
UT_IntArray myIndices
Definition: UT_QuickSort.h:76
GLint GLint GLsizei GLint GLenum GLenum type
Definition: glcorearb.h:107
int * getIndices()
Definition: UT_QuickSort.h:62
float fpreal32
Definition: SYS_Types.h:184