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)
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:759
const utPtr & getEntry(int idx) const
void remove(unsigned int entry)
GLboolean GLboolean GLboolean b
Definition: glcorearb.h:1222
exint size() const
int64 getMemoryUsage(bool inclusive) const
int64 exint
Definition: SYS_Types.h:125
int64 getMemoryUsage(bool inclusive=false) const
Definition: UT_Array.h:620
virtual void changedPosition(utPtr, unsigned int) const
UT_Array< utPtr > myArray
unsigned int append(utPtr t)
GLdouble GLdouble t
Definition: glew.h:1403
exint size() const
Definition: UT_Array.h:609
void setSize(exint newsize)
Definition: UT_Array.h:629
GLdouble l
Definition: glew.h:9164
CompareResults OIIO_API compare(const ImageBuf &A, const ImageBuf &B, float failthresh, float warnthresh, ROI roi={}, int nthreads=0)
virtual ~UT_PriorityQueue()
GLboolean GLboolean GLboolean GLboolean a
Definition: glcorearb.h:1222
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)
long long int64
Definition: SYS_Types.h:116
unsigned int bubbleUp(unsigned int entry)
unsigned int bubbleDown(unsigned int entry)
exint append()
Definition: UT_Array.h:137
const utPtr & head() const
UT_PriorityQueue(unsigned int sz=0, const utCompare &compare=utCompare())
Trivial constructor and destructor:
auto ptr(T p) -> const void *
Definition: format.h:2448
void destroy(unsigned int entry)
calls remove before destroying
void clear()
Resets list to an empty list.
Definition: UT_Array.h:679
unsigned int insert(utPtr t)
exint entries() const
GLboolean r
Definition: glcorearb.h:1222
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:613