GRASS GIS 8 Programmer's Manual  8.5.0dev(2024)-ee9fa48798
imbuffer.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 __IMBUFFER_H
37 #define __IMBUFFER_H
38 
39 #include <stdio.h>
40 #include <assert.h>
41 #include <stdlib.h>
42 
43 #include "ami_config.h" //for SAVE_MEMORY
44 #include "ami_stream.h"
45 #include "mm.h"
46 #include "mm_utils.h"
47 #include "pqheap.h"
48 
49 /* to do: - iterative sort */
50 
51 /*****************************************************************
52  *****************************************************************
53  *****************************************************************
54 
55  in memory buffer (level-0 buffer):
56 
57  Functionality:
58 
59  Stores an array of data in memory; when it becomes full, sorts the
60  data and copies it on secondary storage in a level-1 buffer; data is
61  stored contiguously from left to right;
62 
63  assume: class T supports < and getPriority and getValue; elements in
64  buffer are sorted according to < relation
65 
66  *****************************************************************
67  *****************************************************************
68  *****************************************************************/
69 
70 template <class T>
71 class im_buffer {
72 
73 private:
74  // maximum capacity of buffer
75  unsigned long maxsize;
76 
77  // index of next empty entry in buffer; between 0 and maxsize;
78  // initialized to 0
79  unsigned long size;
80 
81  // stored data
82  T *data;
83 
84  bool sorted; // true if it is sorted; set when the buffer is sorted
85  // to prevent sorting it twice
86 
87 public:
88  // create a buffer of maxsize n
89  im_buffer(long n) : maxsize(n), size(0), sorted(false)
90  {
91  assert(n >= 0);
92 
93  char str[100];
94  snprintf(str, sizeof(str), "im_buffer: allocate %ld\n",
95  (long)(maxsize * sizeof(T)));
96  MEMORY_LOG(str);
97 
98  data = new T[maxsize];
99  assert(data);
100  }
101 
102  // copy constructor
103  im_buffer(const im_buffer &b);
104 
105  // free memory
107  {
108  if (data)
109  delete[] data;
110  }
111 
112  // insert an item in buffer in next free position; fail if buffer full
113  bool insert(T &x);
114 
115  // insert n items in buffer; return the number of items actually inserted
116  unsigned long insert(T *x, unsigned long n);
117 
118  //(quick)sort (ascending order) the buffer (in place);
119  // the buffer is overwritten; recursive for the time being..
120  void sort();
121 
122  // return maxsize of the buffer (number of elements);
123  unsigned long get_buf_maxlen() const { return maxsize; }
124 
125  // return current size of the buffer(number of elements);
126  unsigned long get_buf_len() const { return size; }
127 
128  // return true if buffer full
129  bool is_full() const { return (size == maxsize); }
130 
131  // return true if buffer empty
132  bool is_empty() const { return (size == 0); }
133 
134  // return i'th item in buffer
135  T get_item(unsigned long i) const
136  {
137  assert(i < size);
138  return data[i];
139  }
140 
141  // return data
142  T *get_array() const { return data; }
143 
144  // write buffer to a stream; create the stream and return it
145  AMI_STREAM<T> *save2str() const;
146 
147  // set i'th item in buffer
148  void set_item(unsigned long i, T &item)
149  {
150  assert((i >= 0) && (i < size));
151  data[i] = item;
152  sorted = false;
153  }
154 
155  // reset buffer (delete all data); if SAVE_MEMORY is on, free also the space
156  void reset()
157  {
158  size = 0;
159  sorted = false;
160 #ifdef SAVE_MEMORY
161  delete[] data;
162  data = NULL;
163 #endif
164  }
165 
166  // reset buffer (delete all data); don't delete memory
167  void clear()
168  {
169  size = 0;
170  sorted = false;
171  }
172 
173  // reset buffer: keep n elements starting at position start
174  void reset(unsigned long start, unsigned long n);
175 
176  // shift n items to the left: in effect this deletes the first n items
177  void shift_left(unsigned long n);
178 
179  // print the elements in the buffer
180  friend ostream &operator<<(ostream &s, const im_buffer &b)
181  {
182  s << "(buffer:) [";
183  for (int i = 0; i < b.size; i++) {
184  s << b.data[i] << ", ";
185  }
186  return s << "]";
187  }
188 
189  // print range: prints the range of the items in buffer
190  void print_range() const;
191 
192  // print
193  void print() const;
194 
195 private:
196  // sort the buffer (recursively)
197  void sort_rec(unsigned long start, unsigned long end);
198 
199  // partition the buffer and return the the position of the pivot
200  unsigned long partition(unsigned long start, unsigned long end);
201 };
202 
203 /************************************************************/
204 // copy constructor
205 template <class T>
207 {
208 
209  MEMORY_LOG("im_buffer: copy constructor start\n");
210  maxsize = b.maxsize;
211  size = b.size;
212  sorted = b.sorted;
213  assert(data);
214  for (unsigned long i = 0; i < size; i++) {
215  data[i] = b.data[i];
216  }
217  MEMORY_LOG("im_buffer: copy constructor end\n");
218 }
219 
220 /************************************************************/
221 // insert an item in buffer; fail if buffer full
222 template <class T>
224 {
225 
226  if (size == maxsize) {
227  return false; // buffer full
228  }
229 #ifdef SAVE_MEMORY
230  if (!data) {
231  data = new T[maxsize];
232  }
233 #endif
234  assert(data);
235  assert(size < maxsize);
236  data[size] = x;
237  size++;
238  sorted = false; // not worth checking..
239  return true;
240 }
241 
242 /************************************************************/
243 // insert n items in buffer; return the number of items actually inserted
244 template <class T>
245 unsigned long im_buffer<T>::insert(T *x, unsigned long n)
246 {
247 
248  assert(x);
249  for (unsigned long i = 0; i < n; i++) {
250  if (!insert(x[i])) {
251  return i;
252  }
253  }
254  assert(sorted == false);
255  return n;
256 }
257 
258 /************************************************************/
259 //(quick)sort (ascending order) the buffer (in place);
260 // the buffer is overwritten; recursive for the time being..
261 template <class T>
263 {
264  if (!is_empty()) {
265  if (!sorted) {
266  // use my quicksort - eventually must be iterative
267  // sort_rec(0, size-1);
268 
269  // use system quicksort
270  qsort((T *)data, size, sizeof(T), T::qscompare);
271  }
272  }
273  sorted = true;
274 }
275 
276 /************************************************************/
277 template <class T>
278 void im_buffer<T>::sort_rec(unsigned long start, unsigned long end)
279 {
280  unsigned long q;
281  if (start < end) {
282  q = partition(start, end);
283  sort_rec(start, q);
284  sort_rec(q + 1, end);
285  }
286 }
287 
288 /************************************************************/
289 // partition the buffer in place and return the the position of the
290 // pivot
291 template <class T>
292 unsigned long im_buffer<T>::partition(unsigned long start, unsigned long end)
293 {
294  assert((start <= end) && (end < size) && (start >= 0));
295  if (start == end) {
296  return start;
297  }
298  T pivot = get_item(start), lit, rit;
299  unsigned long l = start - 1, r = end + 1;
300 
301  while (1) {
302 
303  do {
304  r = r - 1;
305  } while (get_item(r) > pivot);
306 
307  do {
308  l = l + 1;
309  } while (get_item(l) < pivot);
310 
311  if (l < r) {
312  lit = get_item(l);
313  rit = get_item(r);
314  set_item(l, rit);
315  set_item(r, lit);
316  }
317  else {
318  // printf("partition (%ld,%ld) return %ld\n", start, end, r);
319  return r;
320  }
321  }
322 }
323 
324 /************************************************************/
325 // reset buffer: keep n elements starting at position start
326 template <class T>
327 void im_buffer<T>::reset(unsigned long start, unsigned long n)
328 {
329 
330  if (start >= size) {
331  // buffer is completely reset
332  assert(n == 0);
333  size = 0;
334  sorted = false;
335  return;
336  }
337  assert(start + n <= size);
338  size = n;
339  if (n) {
340  memmove(data, data + start, n * sizeof(T));
341  }
342  // remains sorted
343 }
344 
345 /************************************************************/
346 // shift n items to the left: in effect this deletes the first n items
347 template <class T>
348 void im_buffer<T>::shift_left(unsigned long n)
349 {
350  assert(n <= size);
351  // remains sorted
352  if (n) {
353  memmove(data, data + n, (size - n) * sizeof(T));
354  size -= n;
355  }
356 }
357 
358 /************************************************************/
359 // print range of the (priority of) items in the buffer
360 template <class T>
362 {
363 
364  if (size == 0) {
365  cout << "[]";
366  }
367  else {
368 #ifdef SAVE_MEMORY
369  if (!data) {
370  data = new T[maxsize];
371  }
372 #endif
373  assert(data);
374 
375  // determine min and max
376  T min, max;
377  min = data[0];
378  if (sorted) {
379  max = data[size];
380  }
381  else {
382  max = data[0];
383  for (int i = 1; i < size; i++) {
384  if (data[i] < min) {
385  min = data[i];
386  }
387  if (data[i] > max) {
388  max = data[i];
389  }
390  }
391  }
392  // print min and max
393  cout << "[";
394  cout << min.getPriority() << ".." << max.getPriority();
395  cout << " (sz=" << size << ")"; // print also bufsize
396  cout << "]";
397  } // else (size==0)
398 }
399 
400 /************************************************************/
401 // print (priority of) all items in buffer
402 template <class T>
404 {
405  cout << "[";
406  for (unsigned long i = 0; i < size; i++) {
407  cout << data[i].getPriority() << ",";
408  }
409  cout << "]";
410 }
411 
412 /************************************************************/
413 // write buffer to a stream; create the stream and return it;
414 // buffer must be sorted prior to saving (functionality of empq)
415 template <class T>
417 {
418 
419  AMI_err ae;
420 
421  AMI_STREAM<T> *amis = new AMI_STREAM<T>();
422  assert(amis);
423 
424  assert(sorted); // buffer must be sorted prior to saving;
425  for (unsigned long i = 0; i < size; i++) {
426  ae = amis->write_item(data[i]);
427  assert(ae == AMI_ERROR_NO_ERROR);
428  }
429  return amis;
430 }
431 
432 #endif
AMI_err
Definition: ami_stream.h:83
@ AMI_ERROR_NO_ERROR
Definition: ami_stream.h:84
#define NULL
Definition: ccmath.h:32
AMI_err write_item(const T &elt)
Definition: ami_stream.h:588
void print_range() const
Definition: imbuffer.h:361
im_buffer(long n)
Definition: imbuffer.h:89
bool is_empty() const
Definition: imbuffer.h:132
void sort()
Definition: imbuffer.h:262
bool is_full() const
Definition: imbuffer.h:129
bool insert(T &x)
Definition: imbuffer.h:223
void reset()
Definition: imbuffer.h:156
void clear()
Definition: imbuffer.h:167
void set_item(unsigned long i, T &item)
Definition: imbuffer.h:148
void shift_left(unsigned long n)
Definition: imbuffer.h:348
AMI_STREAM< T > * save2str() const
Definition: imbuffer.h:416
T get_item(unsigned long i) const
Definition: imbuffer.h:135
unsigned long get_buf_maxlen() const
Definition: imbuffer.h:123
T * get_array() const
Definition: imbuffer.h:142
friend ostream & operator<<(ostream &s, const im_buffer &b)
Definition: imbuffer.h:180
~im_buffer()
Definition: imbuffer.h:106
unsigned long get_buf_len() const
Definition: imbuffer.h:126
void print() const
Definition: imbuffer.h:403
#define min(x, y)
Definition: draw2.c:29
#define max(x, y)
Definition: draw2.c:30
#define assert(condition)
Definition: lz4.c:393
void MEMORY_LOG(const std::string &str)
Definition: mm_utils.cpp:59
void partition(T *data, size_t n, size_t &pivot, CMPR &cmp)
Definition: quicksort.h:50
double b
Definition: r_raster.c:39
double l
Definition: r_raster.c:39
double r
Definition: r_raster.c:39
#define x