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
22 /** @file PriorityQueue_Heap.h
23
24 Heap-based implementation of PriorityQueue algorithm based on
25 Robert Sedgewick's "Algorithms in C++", Ch. 11.
26 */
27
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; /// Array of queued pointers
57 size_t m_size; /// Array's size
58 size_t m_curr; /// Next free slot in array
59 size_t m_lwm; /// Low water mark
60 };
61
62 template< class T, class Compare>
63 inline
64 PriorityQueue_Heap<T, Compare>::
PriorityQueue_Heap(size_t maxsz_)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>::
PriorityQueue_Heap(size_t maxsz_,const Compare & x_)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>::
allocate(size_t s_)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>::
PriorityQueue_Heap(const PriorityQueue_Heap & h_)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>::
~PriorityQueue_Heap()119 ~PriorityQueue_Heap ()
120 {
121 delete [] m_queue;
122 }
123
124 template< class T, class Compare>
125 void
126 PriorityQueue_Heap<T, Compare>::
insert(const T & t_)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>::
upheap(size_t k_)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>::
pop()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>::
top()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>::
downheap(size_t k_)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>::
remove(T t_)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>::
size()222 size ()
223 {
224 return m_curr-1;
225 }
226
227 template< class T, class Compare>
228 bool
229 PriorityQueue_Heap<T, Compare>::
resize(size_t newsz_)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 */
254