libassa  3.5.1
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 
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&);
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 
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
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
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
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
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>
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
120 {
121  delete [] m_queue;
122 }
123 
124 template< class T, class Compare>
125 void
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
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
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&
170 top () const
171 {
172  return (const T&) m_queue[1];
173 }
174 
175 template< class T, class Compare>
176 void
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
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
222 size ()
223 {
224  return m_curr-1;
225 }
226 
227 template< class T, class Compare>
228 bool
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&
246 operator[] (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.
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.
PriorityQueue_Heap(size_t max_=0)
Class PriorityQueue_Impl.
Definition: Acceptor.h:40