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