GRASS GIS 8 Programmer's Manual  8.2.2dev(2023)-3d2c704037
pqheap.h
Go to the documentation of this file.
1 /****************************************************************************
2  *
3  * MODULE: iostream
4  *
5 
6  * COPYRIGHT (C) 2007 Laura Toma
7  *
8  *
9 
10  * Iostream is a library that implements streams, external memory
11  * sorting on streams, and an external memory priority queue on
12  * streams. These are the fundamental components used in external
13  * memory algorithms.
14 
15  * Credits: The library was developed by Laura Toma. The kernel of
16  * class STREAM is based on the similar class existent in the GPL TPIE
17  * project developed at Duke University. The sorting and priority
18  * queue have been developed by Laura Toma based on communications
19  * with Rajiv Wickremesinghe. The library was developed as part of
20  * porting Terraflow to GRASS in 2001. PEARL upgrades in 2003 by
21  * Rajiv Wickremesinghe as part of the Terracost project.
22 
23  *
24  * This program is free software; you can redistribute it and/or modify
25  * it under the terms of the GNU General Public License as published by
26  * the Free Software Foundation; either version 2 of the License, or
27  * (at your option) any later version.
28  *
29 
30  * This program is distributed in the hope that it will be useful,
31  * but WITHOUT ANY WARRANTY; without even the implied warranty of
32  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
33  * General Public License for more details. *
34  * **************************************************************************/
35 
36 
37 #ifndef _PQHEAP_H
38 #define _PQHEAP_H
39 
40 #include <assert.h>
41 #include <stdlib.h>
42 
43 #define PQHEAP_MEM_DEBUG if(0)
44 
45 
46 //HEAPSTATUS can be defined at compile time
47 
48 
49 
50 //this flag is currently off; we used it at some point for checking
51 //how many times is each element in the heap accessed or something
52 //like that
53 #ifdef HEAPSTATUS
54 static const int PAGESIZE = 1024;
55 #endif
56 
57 
58 // Helper functions for navigating through a binary heap.
59 /* for simplicity the heap structure is slightly modified as:
60  0
61  |
62  1
63  /\
64  2 3
65  /\ /\
66 4 5 6 7
67 
68 */
69 
70 // The children of an element of the heap.
71 static inline unsigned int heap_lchild(unsigned int index) {
72  return 2 * index;
73 }
74 
75 static inline unsigned int heap_rchild(unsigned int index) {
76  return 2 * index + 1;
77 }
78 
79 // The parent of an element.
80 static inline unsigned int heap_parent(unsigned int index) {
81  return index >> 1;
82 }
83 
84 
85 // return minimum of two integers
86 static unsigned int mymin(unsigned int a, unsigned int b) {
87  return (a<=b)? a:b;
88 }
89 
90 
91 
92 /**************************************************************
93 ***************************************************************
94 ***************************************************************
95 
96 Priority queue templated on a single type
97 
98 assume T to be a class with getPriority() and getValue() implemented;
99 
100 Supported operations: min, extract_min, insert in O(lg n)
101 
102 
103 ***************************************************************
104 ***************************************************************
105 ***************************************************************/
106 template <class T>
107 class pqheap_t1 {
108  // A pointer to an array of elements
109  T* elements;
110 
111  // The number of elements currently in the queue.
112  unsigned int cur_elts;
113 
114  // The maximum number the queue can hold.
115  unsigned int max_elts;
116 
117 private:
118  void heapify(unsigned int root);
119 
120 public:
121  inline pqheap_t1(unsigned int size);
122 
123  //build heap from an array of elements; array a is REUSED, and NOT
124  //COPIED, for efficiency; it'd better not be used after this
125  //outside!!!
126  inline pqheap_t1(T* a, unsigned int size);
127 
128  inline ~pqheap_t1(void);
129 
130  //build a heap from an array of elements;
131  //if size > max_elts, insert first maxsize elements from array;
132  //return nb of elements that did not fit;
133  unsigned int fill(T* a, unsigned int size);
134 
135  // Is it full?
136  inline bool full(void);
137 
138  //Is it empty?
139  inline bool empty(void);
140  inline bool is_empty() { return empty(); };
141 
142  // How many elements?
143  inline unsigned int num_elts(void);
144 
145  // How many elements? sorry - i could never remember num_elts
146  inline unsigned int size(void) const { return cur_elts; };
147 
148  // Min
149  inline bool min(T& elt);
150  T min();
151 
152  // Extract min and set elt = min
153  inline bool extract_min(T& elt);
154 
155  //extract all elts with min key, add them and return their sum
156  inline bool extract_all_min(T& elt);
157 
158  //delete min; same as extract_min, but ignore the value extracted
159  inline bool delete_min();
160 
161  // Insert
162  inline bool insert(const T& elt);
163 
164  //Delete the current minimum and insert the new item x;
165  //the minimum item is lost (i.e. not returned to user);
166  //needed to optimize merge
167  inline void delete_min_and_insert(const T &x);
168 
169  //this function is a dirty way to allow building faster the heap
170  //in case we build it from a sorted array; in that case we dont need
171  //to 'insert' and then 'heapify', but it is enough to 'set'
172  void set(long i, T& elt);
173 
174  //print
175  inline friend ostream& operator<<(ostream& s, const pqheap_t1<T> &pq) {
176  s << "PQ: "; s.flush();
177  for (unsigned int i=0; i< mymin(10, pq.cur_elts); i++) {
178  s << "["
179  //<< pq.elements[i].getPriority() << ","
180  //<< pq.elements[i].getValue()
181  << pq.elements[i]
182  << "]";
183  }
184  return s;
185  }
186  //print
187  void print();
188 
189  //print
190  void print_range();
191 
192 
193 #ifdef HEAPSTATUS
194  inline void heapstatus(int d);
195  inline void heaptouch(unsigned int pos);
196  unsigned int *numtouch;
197 #endif
198 };
199 
200 
201 //************************************************************/
202 template <class T>
203 inline
205 
206 
207  elements = new T [size];
208  cout << "pqheap_t1: register memory\n";
209  cout.flush();
210  PQHEAP_MEM_DEBUG cout << "pqheap_t1::pq_heap_t1: allocate\n";
211  // PQHEAP_MEM_DEBUG MMmanager.print();
212 
213 
214  if (!elements) {
215  cerr << "could not allocate priority queue: insufficient memory..\n";
216  exit(1);
217  }
218  assert(elements);
219 
220  max_elts = size;
221  cur_elts = 0;
222 
223 #ifdef HEAPSTATUS
224  numtouch = new unsigned int[size/PAGESIZE];
225  assert(numtouch);
226  for(int i=0; i<size/PAGESIZE; i++) {
227  numtouch[i] = 0;
228  }
229 #endif
230 }
231 
232 
233 //************************************************************/
234 /* (this constructor is a bit nasty) Build heap from an array of
235  elements; array a is reused, and not copied, for efficiency; it'd
236  better not be used after this outside!!! */
237 template <class T>
238 inline
239 pqheap_t1<T>::pqheap_t1(T* a, unsigned int size) {
240  {
241  static int flag = 0;
242  if(!flag) {
243  cerr << "Using slow build in pqheap_t1" << endl;
244  flag = 1;
245  }
246  }
247 
248  elements = a;
249  max_elts = size;
250  cur_elts = size;
251 
252  if (max_elts) {
253  for (int i = heap_parent(max_elts-1); i>=0; i--) {
254  //cout << "heapify i=" << i<<"\n";
255  heapify(i);
256  }
257  }
258 }
259 
260 //************************************************************/
261 template <class T>
262 inline
264 #ifdef HEAPSTATUS
265  cout << endl << "pagesize = " << PAGESIZE << endl;
266  cout << "max_elts = " << max_elts << endl;
267  unsigned int n = max_elts / PAGESIZE;
268  for(unsigned int i=0; i<n; i++) {
269  cout << form("PQTEMP %d\t%d", i, numtouch[i]) << endl;
270  }
271  delete [] numtouch;
272 #endif
273 
274  delete [] elements;
275  cur_elts = 0;
276  max_elts = 0;
277  return;
278 }
279 
280 
281 //************************************************************/
282 //build a heap from an array of elements;
283 //if size > max_elts, insert first maxsize elements from array;
284 //return nb of elements that did not fit;
285 template <class T>
286 inline unsigned int
287 pqheap_t1<T>::fill(T* a, unsigned int size) {
288  unsigned int i;
289  assert(cur_elts == 0);
290  for (i = 0; i<size; i++) {
291  if (!insert(a[i])) {
292  break;
293  }
294  }
295  if (i < size) {
296  assert(i == max_elts);
297  return size - i;
298  } else {
299  return 0;
300  }
301 }
302 
303 
304 
305 //************************************************************/
306 template <class T>
307 inline bool
309  return cur_elts == max_elts;
310 }
311 
312 //************************************************************/
313 template <class T>
314 inline bool
316  return cur_elts == 0;
317 }
318 
319 //************************************************************/
320 template <class T>
321 inline unsigned int
323  return cur_elts;
324 }
325 
326 //************************************************************/
327 template <class T>
328 inline bool
330  if (!cur_elts) {
331  return false;
332  }
333  elt = elements[0];
334  return true;
335 }
336 
337 
338 //************************************************************/
339 template <class T>
340 T
342  T elt;
343  if(min(elt)) {
344  return elt;
345  } else {
346  cerr << "unguarded min failed" << endl;
347  assert(0);
348  exit(1);
349  }
350  return elt;
351 }
352 
353 
354 
355 
356 //************************************************************/
357 //this function is a dirty hack to allow building faster the heap
358 //in case we build it from a sorted array; in thiat case we dont need
359 //to 'insert' and then 'heapify', but it is enough to 'set'
360 template <class T>
361 inline void
362 pqheap_t1<T>::set(long i, T& elt) {
363  //must always set precisely the next element
364  assert(i == cur_elts);
365  elements[i] = elt;
366  cur_elts++;
367 }
368 
369 
370 //************************************************************/
371 #ifdef HEAPSTATUS
372 template <class T>
373 inline void pqheap_t1<T>::heaptouch(unsigned int pos) {
374  numtouch[pos/PAGESIZE]++;
375  assert(numtouch[pos/PAGESIZE] > 0);
376 }
377 #endif
378 
379 #ifdef HEAPSTATUS
380 template <class T>
381 inline void pqheap_t1<T>::heapstatus(int d) {
382  static int count = 0;
383  static int delta = 0;
384 
385  delta += d;
386  count++;
387 
388  if((count % 10000) == 0) {
389  cout << endl << form("PQHEAP %d\t%d", cur_elts, delta) << endl;
390  count = 0;
391  delta = 0;
392  }
393 }
394 #endif
395 
396 
397 
398 //************************************************************/
399 template <class T>
400 inline bool
402  if (!cur_elts) {
403  return false;
404  }
405  elt = elements[0];
406  elements[0] = elements[--cur_elts];
407  heapify(0);
408 
409 #ifdef HEAPSTATUS
410  heaptouch(cur_elts);
411  heaptouch(0);
412  heapstatus(-1);
413 #endif
414 
415  return true;
416 }
417 
418 //************************************************************/
419 //extract all elts with min key, add them and return their sum
420 template <class T>
421 inline bool
423 
424  T next_elt;
425  bool done = false;
426 
427  //extract first elt
428  if (!extract_min(elt)) {
429  return false;
430  } else {
431  while (!done) {
432  //peek at the next min elt to see if matches
433  if ((!min(next_elt)) ||
434  !(next_elt.getPriority() == elt.getPriority())) {
435  done = true;
436  } else {
437  extract_min(next_elt);
438  elt = elt + next_elt;
439  }
440  }
441  }
442  return true;
443 }
444 
445 
446 
447 
448 //************************************************************/
449 template <class T>
450 inline bool
452  T dummy;
453  return extract_min(dummy);
454 }
455 
456 
457 //************************************************************/
458 template <class T>
459 inline bool
460 pqheap_t1<T>::insert(const T& elt) {
461  unsigned int ii;
462 
463  if (full()) {
464  return false;
465  }
466 
467  for (ii = cur_elts++;
468  ii && (elements[heap_parent(ii)].getPriority() > elt.getPriority());
469  ii = heap_parent(ii)) {
470  elements[ii] = elements[heap_parent(ii)];
471  }
472  elements[ii] = elt;
473 
474 #ifdef HEAPSTATUS
475  heaptouch(ii);
476  heapstatus(+1);
477 #endif
478 
479  return true;
480 }
481 
482 
483 //************************************************************/
484 template <class T>
485 inline void
486 pqheap_t1<T>::heapify(unsigned int root) {
487  unsigned int min_index = root;
488  unsigned int lc = heap_lchild(root);
489  unsigned int rc = heap_rchild(root);
490 
491 #ifdef HEAPSTATUS
492  // already did the root, so dont do it again
493  if(lc < cur_elts) {
494  heaptouch(lc);
495  }
496  if(rc < cur_elts) {
497  heaptouch(rc);
498  }
499 #endif
500  if ((lc < cur_elts) &&
501  ((elements[lc].getPriority()) < elements[min_index].getPriority())) {
502  min_index = lc;
503  }
504  if ((rc < cur_elts) &&
505  ((elements[rc].getPriority()) < elements[min_index].getPriority())) {
506  min_index = rc;
507  }
508 
509  if (min_index != root) {
510  T tmp_q = elements[min_index];
511 
512  elements[min_index] = elements[root];
513  elements[root] = tmp_q;
514 
515  heapify(min_index);
516  }
517 }
518 
519 
520 //************************************************************/
521 //Delete the current minimum and insert the new item;
522 //the minimum item is lost (i.e. not returned to user);
523 //needed to optimize merge
524 template <class T>
525 inline void
527  assert(cur_elts);
528  elements[0] = x;
529  heapify(0);
530 }
531 
532 
533 
534 
535 /************************************************************/
536 template <class T>
538  cout << "[";
539  for (unsigned int i=0; i<cur_elts; i++) {
540  cout << elements[i].getPriority().field1() <<",";
541  }
542  cout << "]";
543 }
544 
545 
546 /************************************************************/
547 template <class T>
549  cout << "[";
550  T a, b;
551  min(a);
552  max(b);
553  if (cur_elts) {
554  cout << a.getPriority().field1() << ".."
555  << b.getPriority().field1();
556  }
557  cout << " (" << cur_elts << ")]";
558 }
559 
560 
561 
562 
563 
564 
565 
566 #endif // _PQUEUE_HEAP_H
bool empty(void)
Definition: pqheap.h:315
unsigned int num_elts(void)
Definition: pqheap.h:322
bool extract_min(T &elt)
Definition: pqheap.h:401
pqheap_t1(unsigned int size)
Definition: pqheap.h:204
int count
void print()
Definition: pqheap.h:537
#define x
#define max(x, y)
Definition: draw2.c:32
unsigned int size(void) const
Definition: pqheap.h:146
void delete_min_and_insert(const T &x)
Definition: pqheap.h:526
#define PQHEAP_MEM_DEBUG
Definition: pqheap.h:43
#define assert(condition)
Definition: lz4.c:324
double b
Definition: r_raster.c:39
bool extract_all_min(T &elt)
Definition: pqheap.h:422
bool is_empty()
Definition: pqheap.h:140
void set(long i, T &elt)
Definition: pqheap.h:362
bool delete_min()
Definition: pqheap.h:451
T min()
Definition: pqheap.h:341
void print_range()
Definition: pqheap.h:548
unsigned int fill(T *a, unsigned int size)
Definition: pqheap.h:287
bool insert(const T &elt)
Definition: pqheap.h:460
~pqheap_t1(void)
Definition: pqheap.h:263
bool full(void)
Definition: pqheap.h:308