# OpenGraph DrawingFramework

v.2012.07

MinHeap.h
Go to the documentation of this file.
1 /*
2  * $Revision: 2583$
3  *
4  * last checkin:
5  * $Author: gutwenger$
6  * $Date: 2012-07-12 01:02:21 +0200 (Do, 12. Jul 2012)$
7  ***************************************************************/
8
43 #ifdef _MSC_VER
44 #pragma once
45 #endif
46
47 #ifndef OGDF_MIN_HEAP_H
48 #define OGDF_MIN_HEAP_H
49
50 #include<ogdf/basic/Array.h>
51
52 namespace ogdf {
53
55
59 template<class X, class Priority=double> class Prioritized {
60  X x;
61  Priority p;
62 public:
64  Prioritized() : x(0), p(0) { }
66  Prioritized(X xt, Priority pt) : x(xt),p(pt) { }
68  Prioritized(const Prioritized& P) : x(P.x),p(P.p) { }
70  Priority priority() const { return p; }
72  X item() const { return x;}
74  bool operator<(const Prioritized<X,Priority>& P) const { return p<P.p; }
76  bool operator<=(const Prioritized<X,Priority>& P) const { return p<=P.p; }
78  bool operator>(const Prioritized<X,Priority>& P) const { return p>P.p; }
80  bool operator>=(const Prioritized<X,Priority>& P) const { return p>=P.p; }
82  bool operator==(const Prioritized<X,Priority>& P) const { return p==P.p; }
84  bool operator!=(const Prioritized<X,Priority>& P) const { return p!=P.p; }
85 };
86
87
89
102 template<class X, class INDEX = int>
104 private:
105  Array<X,INDEX> data; // array starts at index 1
106  INDEX num;
107 public:
109  BinaryHeapSimple(INDEX size) : data(1, size), num(0) {}
110
112  bool empty() const { return num == 0; }
114  INDEX size() const { return num; }
115
117  void clear() { num = 0; }
118
120  const X& top() const {
121  return data[1];
122  }
124  inline const X& getMin() const {
126  }
127
129  void push(X& x) {
130  X y;
131  if(num == capacity())
132  data.grow(capacity(),y); // double the size & init with nulls
133  data[++num] = x;
134  heapup(num);
135  }
137  inline void insert(X& x) {
138  push(x);
139  }
140
142  X pop() {
143  data.swap(1, num--);
144  heapdown();
145  return data[num+1];
146  }
148  inline X extractMin() {
149  return pop();
150  }
151
153  const X& operator[](INDEX idx) const {
154  return data[idx+1];
155  }
156
157
158 protected:
160  INDEX capacity() const { return data.size(); }
161
162  void heapup(INDEX idx) {
163  INDEX papa;
164  while( (papa = idx/2) > 0) {
165  if( data[papa] > data[idx] ) {
166  data.swap(papa, idx);
167  idx = papa;
168  } else return; //done
169  }
170  }
171
172  void heapdown() {
173  INDEX papa = 1;
174  INDEX son;
175  while(true) {
176  if( (son = 2*papa) < num && data[son+1] < data[son] )
177  son++;
178  if( son <= num && data[son] < data[papa]) {
179  data.swap(papa, son);
180  papa = son;
181  } else return;
182  }
183  }
184 };
185
187
195 template<class X, class INDEX = int>
196 class Top10Heap : protected BinaryHeapSimple<X,INDEX> { // favors the 10 highest values...
197 public:
200
202  static bool successful(PushResult r) { return r != Rejected; }
204  static bool returnedSomething(PushResult r) { return r != Accepted; }
205
207  Top10Heap() : BinaryHeapSimple<X,INDEX>(10) {}
209  Top10Heap(INDEX size) : BinaryHeapSimple<X,INDEX>(size) {}
210
212  bool empty() const { return BinaryHeapSimple<X,INDEX>::empty(); }
214  bool full() const { return size() == capacity(); }
216  INDEX size() const { return BinaryHeapSimple<X,INDEX>::size(); }
218  INDEX capacity() const { return BinaryHeapSimple<X,INDEX>::capacity(); }
219
222
224
240  PushResult push(X& x, X& out) { // returns element that got kicked out - out is uninitialized if heap wasn't full (i.e. PushResult equals Accepted)
241  PushResult ret = Accepted;
242  if(capacity() == size()) {
243  if(BinaryHeapSimple<X,INDEX>::top() >= x) {// reject new item since it's too bad
244  out = x;
245  return Rejected;
246  }
247  out = BinaryHeapSimple<X,INDEX>::pop(); // remove worst first
248  ret = Swapped;
249  }
251  return ret;
252  }
254  inline PushResult insert(X& x, X& out) {
255  return push(x, out);
256  }
257
259
262  void pushBlind(X& x) {
263  if(capacity() == size()) {
264  if(BinaryHeapSimple<X,INDEX>::top() >= x) // reject new item since it's too bad
265  return;
266  BinaryHeapSimple<X,INDEX>::pop(); // remove worst first
267  }
269  }
271  inline void insertBlind(X& x, X& out) {
272  return pushBlind(x, out);
273  }
274
276
280  const X& operator[](INDEX idx) const { // ATTN: simulate index starting at 0, to be "traditional" to the outside!!!
282  }
283 };
284
286
294 template<class X, class Priority=double, class STATICCOMPARER=StdComparer<X>, class INDEX = int >
295 class DeletingTop10Heap : public Top10Heap<Prioritized<X*,Priority>,INDEX > {
296 public:
298  DeletingTop10Heap(int size) : Top10Heap<Prioritized<X*, Priority>,INDEX >(size) {}
300
305  void pushAndDelete(X* x, Priority p) {
307  Prioritized<X*, Priority> nv(x, p);
309  delete vo.item();
310  }
312  inline void insertAndDelete(X* x, Priority p) {
313  pushAndDelete(x, p);
314  }
316
320  void pushAndDeleteNoRedundancy(X* x, Priority p) {
321  for(INDEX i = Top10Heap<Prioritized<X*,Priority>,INDEX >::size(); i-->0;) {
322  X* k = Top10Heap<Prioritized<X*,Priority>,INDEX >::operator[](i).item();
323 // OGDF_ASSERT( x )
324 // OGDF_ASSERT( k )
326  delete x;
327  return;
328  }
329  }
330  pushAndDelete(x, p);
331  }
333  inline void insertAndDeleteNoRedundancy(X* x, Priority p) {
335  }
336 };
337
338 } // end namespace ogdf
339
340
341 #endif