GRASS GIS 7 Programmer's Manual  7.9.dev(2021)-e5379bbd7
queue.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 QUEUE_H
37 #define QUEUE_H
38 
39 #include <assert.h>
40 #include <iostream>
41 
42 template<class T>
43 class queue {
44 private:
45  T *data;
46  int size;
47  int head; // first valid location (if data)
48  int tail; // next free location
49  int len;
50  void grow();
51 public:
52  queue(int size=4096);
53  ~queue();
54  bool enqueue(T &);
55  bool dequeue(T *);
56  bool peek(int offset, T *);
57  bool isEmpty() const { return len==0; };
58  //int length() const { return len; };
59  unsigned int length() const { return (unsigned int)len; };
60 };
61 
62 
63 template<class T>
64 queue<T>::queue(int vsize) : size(vsize) {
65 
66  if(size <= 0) size = 64; /* default */
67 
68  data = new T[size];
69  head = 0;
70  tail = 0;
71  len = 0;
72 }
73 
74 
75 template<class T>
77  delete [] data;
78 }
79 
80 
81 template<class T>
82 bool
84  if(len==size) grow();
85  assert(len<size);
86  data[tail] = elt;
87  tail = (tail+1)%size;
88  len++;
89  return true;
90 }
91 
92 template<class T>
93 bool
95  if(len>0) {
96  *elt = data[head];
97  head = (head+1)%size;
98  len--;
99  return true;
100  }
101  return false;
102 }
103 
104 
105 template<class T>
106 bool
107 queue<T>::peek(int offset, T *elt) {
108  if(len>offset) {
109  int pos = (head+offset)%size;
110  *elt = data[pos];
111  return true;
112  }
113  return false;
114 }
115 
116 template<class T>
117 void
118 queue<T>::grow() {
119  T *data2 = new T[size*2];
120  int k=head;
121  for(int i=0; i<len; i++) {
122  data2[i] = data[k];
123  k = (k+1)%size;
124  }
125  head = 0;
126  tail = len;
127  delete [] data;
128  data = data2;
129  size *= 2;
130 }
131 
132 
133 #endif // QUEUE_H
~queue()
Definition: queue.h:76
unsigned int length() const
Definition: queue.h:59
Definition: queue.h:43
#define assert(condition)
Definition: lz4.c:324
bool peek(int offset, T *)
Definition: queue.h:107
bool isEmpty() const
Definition: queue.h:57
bool enqueue(T &)
Definition: queue.h:83
queue(int size=4096)
Definition: queue.h:64
bool dequeue(T *)
Definition: queue.h:94