HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
UT_PriorityQueue.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 template that implements a resizable array of
10  * arbitrary objects. The template parameter represents the type
11  * of object, and is called utPtr. You can instantiate this class
12  * with any object or pointer, such as:
13  * UT_ValArray<GeoPoint*> pObj;
14  * The utCompare class should be a class with a very simple constructor
15  * which provides a single method "isLess" which compares two utPtr's.
16  */
17 
18 #ifndef __UT_PriorityQueue_h__
19 #define __UT_PriorityQueue_h__
20 
21 #include "UT_Array.h"
22 
23 template <class utPtr, class utCompare=std::less<utPtr>,
24  bool need_changed_position=false>
26 {
27 public:
28  /// Trivial constructor and destructor:
29  explicit UT_PriorityQueue(unsigned int sz=0,
30  const utCompare &compare = utCompare())
31  : myArray(sz)
32  , comparator(compare)
33  { }
34  virtual ~UT_PriorityQueue() {}
35 
36  /// Copy constructor that uses operator '=' to assign each of a's Things
37  /// to this array.
38  UT_PriorityQueue(const UT_PriorityQueue<utPtr, utCompare,
39  need_changed_position> &a)
40  : myArray(a.myArray)
42  { }
43 
44  unsigned int insert(utPtr t)
45  {
46  unsigned int temp;
47  temp = myArray.append(t);
48  if (need_changed_position)
49  changedPosition(myArray[temp], temp);
50  return bubbleUp(temp);
51  }
52  unsigned int append(utPtr t)
53  {
54  return myArray.append(t);
55  }
56 
57 
58  /// calls remove before destroying
59  void destroy(unsigned int entry)
60  {
61  utPtr ptr = myArray[entry];
62  remove(entry);
63  delete ptr;
64  }
65 
66  void remove(unsigned int entry)
67  {
68  if (myArray.size() > 1)
69  {
70  myArray[entry] = myArray.last();
71  if (need_changed_position)
72  changedPosition(myArray[entry], entry);
74  bubbleDown(entry);
75  }
76  else
77  {
78  myArray.setSize(0);
79  }
80  }
81 
82  void clear()
83  {
84  myArray.clear();
85  }
86 
87  exint size() const { return myArray.size(); }
88  exint entries() const { return myArray.size(); }
89 
90  int64 getMemoryUsage(bool inclusive) const
91  {
92  int64 mem = inclusive ? sizeof(*this) : 0;
93  mem += myArray.getMemoryUsage(false);
94  return mem;
95  }
96 
97  bool isEmpty() const { return myArray.isEmpty(); }
98 
99  // make sure is queue is not empty
100  const utPtr &head() const { return myArray[0]; };
101 
102  // In almost all cases, you only want to pull from the head of the
103  // queue. But, to make the remove(unsigned int entry) sensible,
104  // you must be able to query.
105  const utPtr &getEntry(int idx) const { return myArray[idx]; };
106 
107 
108  // . allows nodes to keep track of where they are in the queue
109  // .. this way nodes can be placed in two queues and delete from both
110  // .. and allows deleting with just a node pointer
111  virtual void changedPosition(utPtr /*a*/,
112  unsigned int /*newposition*/ ) const
113  { }
114 
115  unsigned int bubbleDown(unsigned int entry)
116  {
117  for ( ;; )
118  {
119  unsigned int l = leftChild(entry);
120  unsigned int r = l+1;
121  unsigned int newplace;
122 
123  if (nodeExists(r)) // both children exist
124  {
125  if (comparator(myArray[entry], myArray[l]))
126  {
127  if (comparator(myArray[l], myArray[r]))
128  newplace = r;
129  else
130  newplace = l;
131  }
132  else if (comparator(myArray[entry],
133  myArray[r]))
134  {
135  newplace = r;
136  }
137  else break;
138 
139  }
140  else if(nodeExists(l)) // just left child
141  {
142  if (comparator(myArray[entry], myArray[l]))
143  newplace = l;
144  else break;
145  }
146  else // no children
147  {
148  break;
149  }
150 
151  swap(entry, newplace);
152  entry = newplace;
153  }
154  return entry;
155  }
156 
157  unsigned int bubbleUp(unsigned int entry)
158  {
159  while (entry) // while not root
160  {
161  int nextentry = parent(entry);
162  if (!comparator(myArray[entry],
163  myArray[nextentry]))
164  {
165  swap(entry, nextentry);
166  entry = nextentry;
167  }
168  else
169  {
170  break;
171  }
172  }
173  return entry;
174  }
175 
176 private:
177  static unsigned int parent(unsigned int node)
178  {
179  return (node-1)>>1;
180  }
181 
182  static unsigned int leftChild(unsigned int node)
183  {
184  return (node<<1) + 1;
185  }
186 
187  static unsigned int rightChild(unsigned int node)
188  {
189  return (node<<1) + 2;
190  }
191 
192  bool nodeExists(unsigned int node)
193  {
194  return node < myArray.size();
195  }
196 
197  void swap(unsigned int a, unsigned int b)
198  {
199  utPtr temp = myArray[a];
200  myArray[a] = myArray[b];
201  myArray[b] = temp;
202 
203  if (need_changed_position)
204  {
205  changedPosition(myArray[a], a);
206  changedPosition(myArray[b], b);
207  }
208  }
209 
210 protected:
211  // In almost all cases, you probably want to extract the queue in sorted
212  // order. However, some sub-classes may not require this, so we make this
213  // protected so that the sub-classes can access the queue without the
214  // sorting requirement (see IMG3D_Photon).
216  const utCompare comparator;
217 };
218 
219 /// Based on ut_KDPQueueType (UT_KDTree.C)
220 /// This class is a priority queue ordered so that entries are always pulled
221 /// off in increasing order of a float parameter.
222 template <typename T>
224 {
225 private:
226  class QEntry
227  {
228  public:
229  QEntry() {}
230  QEntry(T node, float d)
231  : myNode(node)
232  , myDistance(d) {}
233 
234  T myNode;
235  float myDistance;
236 
237  bool operator<(const QEntry &b) const
238  {
239  return myDistance > b.myDistance;
240  }
241  };
242 
243  class QCompare {
244  public:
245  bool operator()(const QEntry &a, const QEntry &b) const
246  { return a < b; }
247  };
248 
249 public:
250  // Add an entry to the queue
251  void insert(T node, float d)
252  {
253  myQueue.insert(QEntry(node, d));
254  }
255 
256  // Pull of the min entry
257  bool pullOff(T &node, float &d)
258  {
259  if (myQueue.size())
260  {
261  node = myQueue.getEntry(0).myNode;
262  d = myQueue.getEntry(0).myDistance;
263  myQueue.remove(0);
264  return true;
265  }
266  return false;
267  }
268 
269  void clear()
270  { myQueue.clear(); }
271 
272 private:
274 };
275 
276 #endif
T & last()
Definition: UT_Array.h:584
const utPtr & getEntry(int idx) const
void remove(unsigned int entry)
exint size() const
int64 getMemoryUsage(bool inclusive) const
png_voidp ptr
Definition: png.h:2145
int64 getMemoryUsage(bool inclusive=false) const
Definition: UT_Array.h:455
GLboolean GLboolean GLboolean GLboolean a
Definition: glcorearb.h:1221
virtual void changedPosition(utPtr, unsigned int) const
UT_Array< utPtr > myArray
unsigned int append(utPtr t)
exint size() const
Definition: UT_Array.h:444
void setSize(exint newsize)
Definition: UT_Array.h:462
long long int64
Definition: SYS_Types.h:100
virtual ~UT_PriorityQueue()
int64 exint
Definition: SYS_Types.h:109
UT_PriorityQueue(const UT_PriorityQueue< utPtr, utCompare, need_changed_position > &a)
bool isEmpty() const
bool pullOff(T &node, float &d)
bool operator<(const GU_TetrahedronFacet &a, const GU_TetrahedronFacet &b)
GLboolean GLboolean GLboolean b
Definition: glcorearb.h:1221
unsigned int bubbleUp(unsigned int entry)
unsigned int bubbleDown(unsigned int entry)
const utPtr & head() const
UT_PriorityQueue(unsigned int sz=0, const utCompare &compare=utCompare())
Trivial constructor and destructor:
exint append(void)
Definition: UT_Array.h:95
GLboolean r
Definition: glcorearb.h:1221
void destroy(unsigned int entry)
calls remove before destroying
void clear()
Resets list to an empty list.
Definition: UT_Array.h:506
unsigned int insert(utPtr t)
exint entries() const
const utCompare comparator
void insert(T node, float d)
bool isEmpty() const
Returns true iff there are no occupied elements in the array.
Definition: UT_Array.h:448