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