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