libassa 3.5.1
Loading...
Searching...
No Matches
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 &)
 
T pop ()
 
const Ttop () const
 
bool remove (T)
 
size_t size ()
 
Toperator[] (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

Tm_queue
 
size_t m_size
 Array of queued pointers.
 
size_t m_curr
 Array's size.
 
size_t m_lwm
 Next free slot in array.
 

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

◆ ~PriorityQueue_Heap()

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

◆ 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=()

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;
112 ::memcpy (m_queue, h_.m_queue, sizeof(T)*m_curr);
113 return *this;
114}

◆ 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  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 ( ) const
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

Definition at line 51 of file PriorityQueue_Heap.h.

◆ m_curr

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

Array's size.

Definition at line 58 of file PriorityQueue_Heap.h.

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

◆ 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.

◆ 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

Array of queued pointers.

Definition at line 57 of file PriorityQueue_Heap.h.

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


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