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