libassa 3.5.1
Loading...
Searching...
No Matches
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
19
20namespace ASSA {
21
28template< class T, class Compare >
29class PriorityQueue_Heap : public PriorityQueue_Impl< T, Compare >
30{
31public:
32 PriorityQueue_Heap (size_t max_ = 0);
33 PriorityQueue_Heap (size_t, const Compare&);
36
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
46protected:
47 void upheap (size_t);
48 void downheap (size_t);
49 bool resize (size_t);
50
52
53private:
54 void allocate (size_t);
55
57 size_t m_size;
58 size_t m_curr;
59 size_t m_lwm;
60};
61
62template< class T, class Compare>
63inline
66 : m_curr (1), m_lwm (20)
67{
68 trace("PriorityQueue_Heap::PriorityQueue_Heap");
70}
71
72template< class T, class Compare>
73inline
75PriorityQueue_Heap (size_t maxsz_, const Compare& x_)
76 : m_comp (x_), m_curr (1), m_lwm (20)
77{
79}
80
81template< class T, class Compare>
82inline void
84allocate (size_t s_)
85{
86 m_size = s_ > m_lwm ? s_ : m_lwm;
87 m_queue = new T [m_size];
88}
89
90template< class T, class Compare>
91inline
94 : m_comp (h_.m_comp), m_size (h_.m_size), m_curr (h_.m_curr),
95 m_lwm (h_.m_lwm)
96{
98 ::memcpy (m_queue, h_.m_queue, sizeof(T)*m_curr);
99}
100
101template< class T, class Compare>
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
116template< class T, class Compare>
117inline
120{
121 delete [] m_queue;
122}
123
124template< class T, class Compare>
125void
127insert (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
137template< class T, class Compare>
138void
140upheap (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
152template< class T, class Compare>
153T
155pop ()
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
167template< class T, class Compare>
168inline const T&
170top () const
171{
172 return (const T&) m_queue[1];
173}
174
175template< class T, class Compare>
176void
178downheap (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
195template< class T, class Compare>
196bool
198remove (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
219template< class T, class Compare>
220inline size_t
222size ()
223{
224 return m_curr-1;
225}
226
227template< class T, class Compare>
228bool
230resize (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
243template< class T, class Compare>
244T&
246operator[] (int idx)
247{
248 return m_queue[idx+1];
249}
250
251} // end namespace ASSA
252
253#endif /* PRIORITY_QUEUE_HEAP_H */
#define trace(s)
trace() is used to trace function call chain in C++ program.
Definition Logger.h:429
Interface class that defines Implementor of the Bridge pattern.
A wrapper class to provide AutoPtr with reference semantics.
Definition AutoPtr.h:32
PriorityQueue_Heap & operator=(const PriorityQueue_Heap &)
size_t m_curr
Array's size.
size_t m_size
Array of queued pointers.
size_t m_lwm
Next free slot in array.
Class PriorityQueue_Impl.