libassa  3.5.1
Public Member Functions | Protected Member Functions | Protected Attributes | Private Member Functions | Private Attributes | List of all members
ASSA::PriorityQueue_Heap< T, Compare > Class Template Reference

#include <PriorityQueue_Heap.h>

Inheritance diagram for ASSA::PriorityQueue_Heap< T, Compare >:
ASSA::PriorityQueue_Impl< T, Compare >

Public Member Functions

 PriorityQueue_Heap (size_t max_=0)
 
 PriorityQueue_Heap (size_t, const Compare &)
 
 PriorityQueue_Heap (const PriorityQueue_Heap &)
 
 ~PriorityQueue_Heap ()
 
PriorityQueue_Heapoperator= (const PriorityQueue_Heap &)
 
void insert (const T &)
 
pop ()
 
const T & top () const
 
bool remove (T)
 
size_t size ()
 
T & operator[] (int idx)
 
- Public Member Functions inherited from ASSA::PriorityQueue_Impl< T, Compare >
virtual ~PriorityQueue_Impl ()
 

Protected Member Functions

void upheap (size_t)
 
void downheap (size_t)
 
bool resize (size_t)
 

Protected Attributes

Compare m_comp
 

Private Member Functions

void allocate (size_t)
 

Private Attributes

T * m_queue
 
size_t m_size
 Array of queued pointers. More...
 
size_t m_curr
 Array's size. More...
 
size_t m_lwm
 Next free slot in array. More...
 

Detailed Description

template<class T, class Compare>
class ASSA::PriorityQueue_Heap< T, Compare >

Definition at line 29 of file PriorityQueue_Heap.h.

Constructor & Destructor Documentation

◆ PriorityQueue_Heap() [1/3]

template<class T , class Compare >
ASSA::PriorityQueue_Heap< T, Compare >::PriorityQueue_Heap ( size_t  max_ = 0)
inline

Definition at line 64 of file PriorityQueue_Heap.h.

66  : m_curr (1), m_lwm (20)
67 {
68  trace("PriorityQueue_Heap::PriorityQueue_Heap");
69  allocate (maxsz_);
70 }
#define trace(s)
trace() is used to trace function call chain in C++ program.
Definition: Logger.h:429
size_t m_curr
Array's size.
size_t m_lwm
Next free slot in array.

References ASSA::PriorityQueue_Heap< T, Compare >::allocate(), and trace.

◆ PriorityQueue_Heap() [2/3]

template<class T , class Compare >
ASSA::PriorityQueue_Heap< T, Compare >::PriorityQueue_Heap ( size_t  maxsz_,
const Compare &  x_ 
)
inline

Definition at line 74 of file PriorityQueue_Heap.h.

76  : m_comp (x_), m_curr (1), m_lwm (20)
77 {
78  allocate (maxsz_);
79 }

References ASSA::PriorityQueue_Heap< T, Compare >::allocate().

◆ PriorityQueue_Heap() [3/3]

template<class T , class Compare >
ASSA::PriorityQueue_Heap< T, Compare >::PriorityQueue_Heap ( const PriorityQueue_Heap< T, Compare > &  h_)
inline

Definition at line 92 of file 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 }
size_t m_size
Array of queued pointers.

References ASSA::PriorityQueue_Heap< T, Compare >::allocate(), ASSA::PriorityQueue_Heap< T, Compare >::m_curr, ASSA::PriorityQueue_Heap< T, Compare >::m_queue, and ASSA::PriorityQueue_Heap< T, Compare >::m_size.

◆ ~PriorityQueue_Heap()

template<class T , class Compare >
ASSA::PriorityQueue_Heap< T, Compare >::~PriorityQueue_Heap
inline

Definition at line 118 of file PriorityQueue_Heap.h.

120 {
121  delete [] m_queue;
122 }

Member Function Documentation

◆ allocate()

template<class T , class Compare >
void ASSA::PriorityQueue_Heap< T, Compare >::allocate ( size_t  s_)
inlineprivate

Definition at line 83 of file PriorityQueue_Heap.h.

85 {
86  m_size = s_ > m_lwm ? s_ : m_lwm;
87  m_queue = new T [m_size];
88 }

Referenced by ASSA::PriorityQueue_Heap< T, Compare >::PriorityQueue_Heap().

◆ downheap()

template<class T , class Compare >
void ASSA::PriorityQueue_Heap< T, Compare >::downheap ( size_t  k_)
protected

Definition at line 177 of file PriorityQueue_Heap.h.

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 }

◆ insert()

template<class T , class Compare >
void ASSA::PriorityQueue_Heap< T, Compare >::insert ( const T &  t_)
virtual

Implements ASSA::PriorityQueue_Impl< T, Compare >.

Definition at line 126 of file PriorityQueue_Heap.h.

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 }

◆ operator=()

template<class T , class Compare >
PriorityQueue_Heap< T, Compare > & ASSA::PriorityQueue_Heap< T, Compare >::operator= ( const PriorityQueue_Heap< T, Compare > &  h_)

Definition at line 103 of file 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 }

References ASSA::PriorityQueue_Heap< T, Compare >::m_comp, ASSA::PriorityQueue_Heap< T, Compare >::m_curr, ASSA::PriorityQueue_Heap< T, Compare >::m_lwm, ASSA::PriorityQueue_Heap< T, Compare >::m_queue, and ASSA::PriorityQueue_Heap< T, Compare >::m_size.

◆ operator[]()

template<class T , class Compare >
T & ASSA::PriorityQueue_Heap< T, Compare >::operator[] ( int  idx)
virtual

Implements ASSA::PriorityQueue_Impl< T, Compare >.

Definition at line 245 of file PriorityQueue_Heap.h.

247 {
248  return m_queue[idx+1];
249 }

◆ pop()

template<class T , class Compare >
T ASSA::PriorityQueue_Heap< T, Compare >::pop
virtual

Implements ASSA::PriorityQueue_Impl< T, Compare >.

Definition at line 154 of file PriorityQueue_Heap.h.

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 }

◆ remove()

template<class T , class Compare >
bool ASSA::PriorityQueue_Heap< T, Compare >::remove ( t_)
virtual

Implements ASSA::PriorityQueue_Impl< T, Compare >.

Definition at line 197 of file PriorityQueue_Heap.h.

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 }

◆ resize()

template<class T , class Compare >
bool ASSA::PriorityQueue_Heap< T, Compare >::resize ( size_t  newsz_)
protected

Definition at line 229 of file PriorityQueue_Heap.h.

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 }

◆ size()

template<class T , class Compare >
size_t ASSA::PriorityQueue_Heap< T, Compare >::size
inlinevirtual

Implements ASSA::PriorityQueue_Impl< T, Compare >.

Definition at line 221 of file PriorityQueue_Heap.h.

223 {
224  return m_curr-1;
225 }

◆ top()

template<class T , class Compare >
const T & ASSA::PriorityQueue_Heap< T, Compare >::top
inlinevirtual

Implements ASSA::PriorityQueue_Impl< T, Compare >.

Definition at line 169 of file PriorityQueue_Heap.h.

171 {
172  return (const T&) m_queue[1];
173 }

◆ upheap()

template<class T , class Compare >
void ASSA::PriorityQueue_Heap< T, Compare >::upheap ( size_t  k_)
protected

Definition at line 139 of file PriorityQueue_Heap.h.

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 }

Member Data Documentation

◆ m_comp

template<class T , class Compare >
Compare ASSA::PriorityQueue_Heap< T, Compare >::m_comp
protected

◆ m_curr

template<class T , class Compare >
size_t ASSA::PriorityQueue_Heap< T, Compare >::m_curr
private

◆ m_lwm

template<class T , class Compare >
size_t ASSA::PriorityQueue_Heap< T, Compare >::m_lwm
private

Next free slot in array.

Definition at line 59 of file PriorityQueue_Heap.h.

Referenced by ASSA::PriorityQueue_Heap< T, Compare >::operator=().

◆ m_queue

template<class T , class Compare >
T* ASSA::PriorityQueue_Heap< T, Compare >::m_queue
private

◆ m_size

template<class T , class Compare >
size_t ASSA::PriorityQueue_Heap< T, Compare >::m_size
private

The documentation for this class was generated from the following file: