libassa
3.5.1
Loading...
Searching...
No Matches
assa
PriorityQueue_Heap.h
Go to the documentation of this file.
1
// -*- c++ -*-
2
//------------------------------------------------------------------------------
3
// PriorityQueue_Heap.h
4
//------------------------------------------------------------------------------
5
// Copyright (c) 1999 by Vladislav Grinchenko
6
//
7
// This library is free software; you can redistribute it and/or
8
// modify it under the terms of the GNU Library General Public
9
// License as published by the Free Software Foundation; either
10
// version 2 of the License, or (at your option) any later version.
11
//------------------------------------------------------------------------------
12
#ifndef PRIORITY_QUEUE_HEAP_H
13
#define PRIORITY_QUEUE_HEAP_H
14
15
#include <sys/types.h>
16
#include <string.h>
17
18
#include "
assa/PriorityQueue_Impl.h
"
19
20
namespace
ASSA
{
21
28
template
<
class
T,
class
Compare >
29
class
PriorityQueue_Heap
:
public
PriorityQueue_Impl
< T, Compare >
30
{
31
public
:
32
PriorityQueue_Heap
(
size_t
max_
= 0);
33
PriorityQueue_Heap
(
size_t
,
const
Compare
&);
34
PriorityQueue_Heap
(
const
PriorityQueue_Heap
&);
35
~PriorityQueue_Heap
();
36
37
PriorityQueue_Heap
&
operator=
(
const
PriorityQueue_Heap
&);
38
39
void
insert
(
const
T
&);
40
T
pop
();
41
const
T
&
top
()
const
;
42
bool
remove
(
T
);
43
size_t
size
();
44
T
&
operator[]
(
int
idx
);
45
46
protected
:
47
void
upheap
(
size_t
);
48
void
downheap
(
size_t
);
49
bool
resize
(
size_t
);
50
51
Compare
m_comp
;
52
53
private
:
54
void
allocate
(
size_t
);
55
56
T
*
m_queue
;
57
size_t
m_size
;
58
size_t
m_curr
;
59
size_t
m_lwm
;
60
};
61
62
template
<
class
T,
class
Compare>
63
inline
64
PriorityQueue_Heap<T, Compare>::
65
PriorityQueue_Heap
(
size_t
maxsz_
)
66
: m_curr (1), m_lwm (20)
67
{
68
trace
(
"PriorityQueue_Heap::PriorityQueue_Heap"
);
69
allocate
(
maxsz_
);
70
}
71
72
template
<
class
T,
class
Compare>
73
inline
74
PriorityQueue_Heap<T, Compare>::
75
PriorityQueue_Heap
(
size_t
maxsz_
,
const
Compare
&
x_
)
76
: m_comp (
x_
), m_curr (1), m_lwm (20)
77
{
78
allocate
(
maxsz_
);
79
}
80
81
template
<
class
T,
class
Compare>
82
inline
void
83
PriorityQueue_Heap<T, Compare>::
84
allocate
(
size_t
s_
)
85
{
86
m_size =
s_
> m_lwm ?
s_
: m_lwm;
87
m_queue =
new
T
[m_size];
88
}
89
90
template
<
class
T,
class
Compare>
91
inline
92
PriorityQueue_Heap<T, Compare>::
93
PriorityQueue_Heap
(
const
PriorityQueue_Heap
&
h_
)
94
: m_comp (
h_
.m_comp), m_size (
h_
.m_size), m_curr (
h_
.m_curr),
95
m_lwm (
h_
.m_lwm)
96
{
97
allocate
(
m_size
);
98
::memcpy (
m_queue
,
h_
.m_queue,
sizeof
(
T
)*
m_curr
);
99
}
100
101
template
<
class
T,
class
Compare>
102
PriorityQueue_Heap<T, Compare>
&
103
PriorityQueue_Heap<T, Compare>::
104
operator=
(
const
PriorityQueue_Heap
&
h_
)
105
{
106
delete
[] m_queue;
107
m_comp =
h_
.m_comp;
108
m_size =
h_
.m_size;
109
m_curr =
h_
.m_curr;
110
m_lwm =
h_
.m_lwm;
111
allocate (m_size);
112
::memcpy (m_queue,
h_
.m_queue,
sizeof
(
T
)*m_curr);
113
return
*
this
;
114
}
115
116
template
<
class
T,
class
Compare>
117
inline
118
PriorityQueue_Heap<T, Compare>::
119
~PriorityQueue_Heap
()
120
{
121
delete
[] m_queue;
122
}
123
124
template
<
class
T,
class
Compare>
125
void
126
PriorityQueue_Heap<T, Compare>::
127
insert
(
const
T
&
t_
)
128
{
129
if
(m_curr+1 == m_size)
// if array filled up
130
resize (m_size*2);
// then resize array
131
132
m_queue [m_curr] =
t_
;
133
upheap (m_curr);
134
m_curr++;
135
}
136
137
template
<
class
T,
class
Compare>
138
void
139
PriorityQueue_Heap<T, Compare>::
140
upheap
(
size_t
k_
)
141
{
142
T
v
= m_queue[
k_
];
143
m_queue[0] = 0;
144
145
while
(
k_
/2 != 0 && m_comp (
v
, m_queue[
k_
/2]) ) {
146
m_queue[
k_
] = m_queue[
k_
/2];
147
k_
=
k_
/2;
148
}
149
m_queue[
k_
] =
v
;
150
}
151
152
template
<
class
T,
class
Compare>
153
T
154
PriorityQueue_Heap<T, Compare>::
155
pop
()
156
{
157
T
v
= m_queue[1];
158
m_queue[1] = m_queue[--m_curr];
159
160
downheap (1);
161
if
(m_curr*3 <= m_size && m_curr*2 > m_lwm) {
162
resize (m_curr*2);
163
}
164
return
v
;
165
}
166
167
template
<
class
T,
class
Compare>
168
inline
const
T
&
169
PriorityQueue_Heap<T, Compare>::
170
top
()
const
171
{
172
return
(
const
T
&) m_queue[1];
173
}
174
175
template
<
class
T,
class
Compare>
176
void
177
PriorityQueue_Heap<T, Compare>::
178
downheap
(
size_t
k_
)
179
{
180
register
size_t
j
;
181
T
v
= m_queue[
k_
];
182
183
while
(
k_
<= m_curr/2) {
184
j
= 2*
k_
;
185
if
(
j
< m_curr && m_comp (m_queue[
j
+1], m_queue[
j
]))
186
j
++;
187
if
(m_comp (
v
, m_queue[
j
]))
188
break
;
189
m_queue[
k_
] = m_queue[
j
];
190
k_
=
j
;
191
}
192
m_queue[
k_
] =
v
;
193
}
194
195
template
<
class
T,
class
Compare>
196
bool
197
PriorityQueue_Heap<T, Compare>::
198
remove
(
T
t_
)
199
{
200
register
size_t
i
;
201
202
for
(
i
=1;
i
< m_curr;
i
++)
203
if
(m_queue[
i
] ==
t_
)
204
break
;
205
206
if
(
i
== m_curr)
// not found
207
return
false
;
208
209
m_curr--;
210
if
(
i
== m_curr)
// last element in queue
211
return
true
;
212
213
m_queue[
i
] = m_queue[m_curr];
214
downheap (
i
);
215
216
return
true
;
217
}
218
219
template
<
class
T,
class
Compare>
220
inline
size_t
221
PriorityQueue_Heap<T, Compare>::
222
size
()
223
{
224
return
m_curr-1;
225
}
226
227
template
<
class
T,
class
Compare>
228
bool
229
PriorityQueue_Heap<T, Compare>::
230
resize
(
size_t
newsz_
)
231
{
232
if
(m_size ==
newsz_
)
233
return
true
;
234
235
T
*
new_chunk
=
new
T
[
newsz_
];
236
::memcpy (
new_chunk
, m_queue, m_curr *
sizeof
(
T
));
237
delete
[] m_queue;
238
m_queue =
new_chunk
;
239
m_size =
newsz_
;
240
return
true
;
241
}
242
243
template
<
class
T,
class
Compare>
244
T
&
245
PriorityQueue_Heap<T, Compare>::
246
operator[]
(
int
idx
)
247
{
248
return
m_queue[
idx
+1];
249
}
250
251
}
// end namespace ASSA
252
253
#endif
/* PRIORITY_QUEUE_HEAP_H */
trace
#define trace(s)
trace() is used to trace function call chain in C++ program.
Definition
Logger.h:429
PriorityQueue_Impl.h
Interface class that defines Implementor of the Bridge pattern.
ASSA::AutoPtrRef
A wrapper class to provide AutoPtr with reference semantics.
Definition
AutoPtr.h:32
ASSA::PriorityQueue_Heap
Definition
PriorityQueue_Heap.h:30
ASSA::PriorityQueue_Heap::resize
bool resize(size_t)
Definition
PriorityQueue_Heap.h:230
ASSA::PriorityQueue_Heap::operator=
PriorityQueue_Heap & operator=(const PriorityQueue_Heap &)
Definition
PriorityQueue_Heap.h:104
ASSA::PriorityQueue_Heap::m_queue
T * m_queue
Definition
PriorityQueue_Heap.h:56
ASSA::PriorityQueue_Heap::m_curr
size_t m_curr
Array's size.
Definition
PriorityQueue_Heap.h:58
ASSA::PriorityQueue_Heap::downheap
void downheap(size_t)
Definition
PriorityQueue_Heap.h:178
ASSA::PriorityQueue_Heap::m_size
size_t m_size
Array of queued pointers.
Definition
PriorityQueue_Heap.h:57
ASSA::PriorityQueue_Heap::insert
void insert(const T &)
Definition
PriorityQueue_Heap.h:127
ASSA::PriorityQueue_Heap::top
const T & top() const
Definition
PriorityQueue_Heap.h:170
ASSA::PriorityQueue_Heap::upheap
void upheap(size_t)
Definition
PriorityQueue_Heap.h:140
ASSA::PriorityQueue_Heap::remove
bool remove(T)
Definition
PriorityQueue_Heap.h:198
ASSA::PriorityQueue_Heap::pop
T pop()
Definition
PriorityQueue_Heap.h:155
ASSA::PriorityQueue_Heap::~PriorityQueue_Heap
~PriorityQueue_Heap()
Definition
PriorityQueue_Heap.h:119
ASSA::PriorityQueue_Heap::allocate
void allocate(size_t)
Definition
PriorityQueue_Heap.h:84
ASSA::PriorityQueue_Heap::size
size_t size()
Definition
PriorityQueue_Heap.h:222
ASSA::PriorityQueue_Heap::m_lwm
size_t m_lwm
Next free slot in array.
Definition
PriorityQueue_Heap.h:59
ASSA::PriorityQueue_Heap::PriorityQueue_Heap
PriorityQueue_Heap(size_t max_=0)
Definition
PriorityQueue_Heap.h:65
ASSA::PriorityQueue_Heap::operator[]
T & operator[](int idx)
Definition
PriorityQueue_Heap.h:246
ASSA::PriorityQueue_Heap::m_comp
Compare m_comp
Definition
PriorityQueue_Heap.h:51
ASSA::PriorityQueue_Impl
Class PriorityQueue_Impl.
Definition
PriorityQueue_Impl.h:54
ASSA
Definition
Acceptor.h:40
Generated by
1.9.8