GRASS 8 Programmer's Manual 8.6.0dev(2026)-f6f2c534ea
Loading...
Searching...
No Matches
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
42template <class T>
43class queue {
44private:
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
52public:
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
63template <class T>
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
76template <class T>
78{
79 delete[] data;
80}
81
82template <class T>
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
94template <class T>
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
106template <class T>
107bool 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
117template <class T>
118void 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:291