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
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>
77
queue<T>::~queue
()
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
AMI_STREAM
Definition
ami_stream.h:153
AMI_STREAM::AMI_STREAM
AMI_STREAM()
Definition
ami_stream.h:227
queue
Definition
queue.h:43
queue::queue
queue(int size=4096)
Definition
queue.h:64
queue::~queue
~queue()
Definition
queue.h:77
queue::dequeue
bool dequeue(T *)
Definition
queue.h:95
queue::length
unsigned int length() const
Definition
queue.h:60
queue::peek
bool peek(int offset, T *)
Definition
queue.h:107
queue::enqueue
bool enqueue(T &)
Definition
queue.h:83
queue::isEmpty
bool isEmpty() const
Definition
queue.h:58
assert
#define assert(condition)
Definition
lz4.c:291
include
grass
iostream
queue.h
Generated on Sun Apr 12 2026 06:59:13 for GRASS 8 Programmer's Manual by
1.9.8