GRASS GIS 8 Programmer's Manual  8.4.0dev(2024)-6c790bf5c0
replacementHeap.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 REPLACEMENT_QUEUE_H
37 #define REPLACEMENT_QUEUE_H
38 
39 #include <assert.h>
40 
41 #include "queue.h"
42 
43 #define RHEAP_DEBUG if (0)
44 
45 /*****************************************************************/
46 /* encapsulation of the element and the run it comes from;
47  */
48 template <class T>
49 class HeapElement {
50 public:
51  T value;
53 
55 
56  friend ostream &operator<<(ostream &s, const HeapElement &p)
57  {
58  return s << "[" << p.value << "]";
59  };
60 };
61 
62 /*****************************************************************/
63 /*
64 This is a heap of HeapElements, i.e. elements which come from streams;
65 when an element is consumed, the heap knows how to replace it with the
66 next element from the same stream.
67 
68 Compare is a class that has a member function called "compare" which
69 is used to compare two elements of type T
70 */
71 template <class T, class Compare>
73 private:
74  HeapElement<T> *mergeHeap; // the heap;
75  size_t arity; // max size
76  size_t size; // represents actual size, i.e. the nb of (non-empty)
77  // runs; they are stored contigously in the first
78  //<size> positions of mergeHeap; once a run becomes
79  // empty, it is deleted and size is decremented. size
80  // stores the next position where a HeapElement can be
81  // added.
82 
83 protected:
84  void heapify(size_t i);
85 
86  void buildheap();
87 
88  /* for each run in the heap, read an element from the run into the heap */
89  void init();
90 
91  /* add a run; make sure total nb of runs does not exceed heap arity */
92  void addRun(AMI_STREAM<T> *run);
93 
94  /* delete the i-th run (and the element); that is, swap the ith run
95  with the last one, and decrement size; just like in a heap, but
96  no heapify. Note: this function messes up the heap order. If the
97  user wants to maintain heap property should call heapify
98  specifically.
99  */
100  void deleteRun(size_t i);
101 
102 public:
103  // allocate array mergeHeap and the runs in runList
104  ReplacementHeap<T, Compare>(size_t arity, queue<char *> *runList);
105 
106  // delete array mergeHeap
108 
109  // is heap empty?
110  int empty() const { return (size == 0); }
111 
112  // delete mergeHeap[0].value, replace it with the next element from
113  // the same stream, and re-heapify
114  T extract_min();
115 
116  ostream &print(ostream &s) const
117  {
118  char *runname;
119  off_t runlen;
120  s << "Replacementheap " << this << ": " << size << " runs";
121  for (size_t i = 0; i < size; i++) {
122  s << endl << " <- i=" << i << ": " << mergeHeap[i].run;
123  assert(mergeHeap[i].run);
124  mergeHeap[i].run->name(&runname);
125  runlen = mergeHeap[i].run->stream_len();
126  s << ", " << runname << ", len=" << runlen;
127  delete runname; // this should be safe
128  }
129  s << endl;
130  return s;
131  }
132 };
133 
134 /*****************************************************************/
135 template <class T, class Compare>
137  queue<char *> *runList)
138 {
139  char *name = NULL;
140 
141  assert(runList && g_arity > 0);
142 
143  RHEAP_DEBUG cerr << "ReplacementHeap arity=" << g_arity << "\n";
144 
145  arity = g_arity;
146  size = 0; // no run yet
147 
148  mergeHeap = new HeapElement<T>[arity];
149  for (unsigned int i = 0; i < arity; i++) {
150  // pop a stream from the list and add it to heap
151  runList->dequeue(&name);
152  AMI_STREAM<T> *str = new AMI_STREAM<T>(name);
153  assert(str);
154  delete name; // str makes its own copy
155  addRun(str);
156  }
157  init();
158 }
159 
160 /*****************************************************************/
161 template <class T, class Compare>
163 {
164 
165  if (!empty()) {
166  cerr << "warning: ~ReplacementHeap: heap not empty!\n";
167  }
168  // delete the runs first
169  for (size_t i = 0; i < size; i++) {
170  if (mergeHeap[i].run)
171  delete mergeHeap[i].run;
172  }
173  delete[] mergeHeap;
174 }
175 
176 /*****************************************************************/
177 /* add a run; make sure total nb of runs does not exceed heap arity
178  */
179 template <class T, class Compare>
181 {
182 
183  assert(r);
184 
185  if (size == arity) {
186  cerr << "ReplacementHeap::addRun size =" << size << ",arity=" << arity
187  << " full, cannot add another run.\n";
188  assert(0);
189  exit(1);
190  }
191  assert(size < arity);
192 
193  mergeHeap[size].run = r;
194  size++;
195 
197  {
198  char *strname;
199  r->name(&strname);
200  cerr << "ReplacementHeap::addRun added run " << strname
201  << " (rheap size=" << size << ")" << endl;
202  delete strname;
203  cerr.flush();
204  }
205 }
206 
207 /*****************************************************************/
208 /* delete the i-th run (and the value); that is, swap ith element with
209  the last one, and decrement size; just like in a heap, but no
210  heapify. Note: this function messes up the heap order. If the user
211  wants to maintain heap property should call heapify specifically.
212  */
213 template <class T, class Compare>
215 {
216 
217  assert(i < size && mergeHeap[i].run);
218 
220  {
221  cerr << "ReplacementHeap::deleteRun deleting run " << i << ", "
222  << mergeHeap[i].run << endl;
223  print(cerr);
224  }
225 
226  // delete it
227  delete mergeHeap[i].run;
228  // and replace it with
229  if (size > 1) {
230  mergeHeap[i].value = mergeHeap[size - 1].value;
231  mergeHeap[i].run = mergeHeap[size - 1].run;
232  }
233  size--;
234 }
235 
236 /*****************************************************************/
237 /* for each run in the heap, read an element from the run into the
238  heap; if ith run is empty, delete it
239 */
240 template <class T, class Compare>
242 {
243  AMI_err err;
244  T *elt;
245  size_t i;
246 
247  RHEAP_DEBUG cerr << "ReplacementHeap::init ";
248 
249  i = 0;
250  while (i < size) {
251 
252  assert(mergeHeap[i].run);
253 
254  // Rewind run i
255  err = mergeHeap[i].run->seek(0);
256  if (err != AMI_ERROR_NO_ERROR) {
257  cerr << "ReplacementHeap::Init(): cannot seek run " << i << "\n";
258  assert(0);
259  exit(1);
260  }
261  // read first item from run i
262  err = mergeHeap[i].run->read_item(&elt);
263  if (err != AMI_ERROR_NO_ERROR) {
264  if (err == AMI_ERROR_END_OF_STREAM) {
265  deleteRun(i);
266  // need to iterate one more time with same i;
267  }
268  else {
269  cerr << "ReplacementHeap::Init(): cannot read run " << i
270  << "\n";
271  assert(0);
272  exit(1);
273  }
274  }
275  else {
276  // copy.... can this be avoided? xxx
277  mergeHeap[i].value = *elt;
278 
279  i++;
280  }
281  }
282  buildheap();
283 }
284 
285 // Helper functions for navigating through a binary heap.
286 /* for simplicity the heap structure is slightly modified as:
287  0
288  |
289  1
290  /\
291  2 3
292  /\ /\
293 4 5 6 7
294 
295 */
296 
297 // The children of an element of the heap.
298 static inline size_t rheap_lchild(size_t index)
299 {
300  return 2 * index;
301 }
302 
303 static inline size_t rheap_rchild(size_t index)
304 {
305  return 2 * index + 1;
306 }
307 
308 // The parent of an element.
309 static inline size_t rheap_parent(size_t index)
310 {
311  return index >> 1;
312 }
313 // this functions are duplicated in pqheap.H...XXX
314 
315 /*****************************************************************/
316 template <class T, class Compare>
318 {
319  size_t min_index = i;
320  size_t lc = rheap_lchild(i);
321  size_t rc = rheap_rchild(i);
322 
323  Compare cmpobj;
324  assert(i < size);
325  if ((lc < size) && (cmpobj.compare(mergeHeap[lc].value,
326  mergeHeap[min_index].value) == -1)) {
327  min_index = lc;
328  }
329  if ((rc < size) && (cmpobj.compare(mergeHeap[rc].value,
330  mergeHeap[min_index].value) == -1)) {
331  min_index = rc;
332  }
333 
334  if (min_index != i) {
335  HeapElement<T> tmp = mergeHeap[min_index];
336 
337  mergeHeap[min_index] = mergeHeap[i];
338  mergeHeap[i] = tmp;
339 
340  heapify(min_index);
341  }
342 
343  return;
344 }
345 
346 /*****************************************************************/
347 template <class T, class Compare>
349 {
350 
351  if (size > 1) {
352  for (int i = rheap_parent(size - 1); i >= 0; i--) {
353  heapify(i);
354  }
355  }
356  RHEAP_DEBUG cerr << "Buildheap done\n";
357  return;
358 }
359 
360 /*****************************************************************/
361 template <class T, class Compare>
363 {
364  T *elt, min;
365  AMI_err err;
366 
367  assert(!empty()); // user's job to check first if it's empty
368  min = mergeHeap[0].value;
369 
370  // read a new element from the same run
371  assert(mergeHeap[0].run);
372  err = mergeHeap[0].run->read_item(&elt);
373  if (err != AMI_ERROR_NO_ERROR) {
374  // if run is empty, delete it
375  if (err == AMI_ERROR_END_OF_STREAM) {
376  RHEAP_DEBUG cerr << "rheap extract_min: run " << mergeHeap[0].run
377  << " empty. deleting\n ";
378  deleteRun(0);
379  }
380  else {
381  cerr << "ReplacementHeap::extract_min: cannot read\n";
382  assert(0);
383  exit(1);
384  }
385  }
386  else {
387  // copy...can this be avoided?
388  mergeHeap[0].value = *elt;
389  }
390 
391  // restore heap
392  if (size > 0)
393  heapify(0);
394 
395  return min;
396 }
397 
398 #endif
AMI_err
Definition: ami_stream.h:83
@ AMI_ERROR_END_OF_STREAM
Definition: ami_stream.h:86
@ AMI_ERROR_NO_ERROR
Definition: ami_stream.h:84
void init(double work[])
Definition: as177.c:61
#define NULL
Definition: ccmath.h:32
friend ostream & operator<<(ostream &s, const HeapElement &p)
AMI_STREAM< T > * run
int empty() const
ReplacementHeap(size_t arity, queue< char * > *runList)
ostream & print(ostream &s) const
void addRun(AMI_STREAM< T > *run)
void heapify(size_t i)
void deleteRun(size_t i)
Definition: queue.h:43
bool dequeue(T *)
Definition: queue.h:95
#define min(x, y)
Definition: draw2.c:29
#define assert(condition)
Definition: lz4.c:393
const char * name
Definition: named_colr.c:6
double r
Definition: r_raster.c:39
#define RHEAP_DEBUG
SYMBOL * err(FILE *fp, SYMBOL *s, char *msg)
Definition: symbol/read.c:216