ASSA::PriorityQueue_Heap

ASSA::PriorityQueue_Heap< T, Compare > Class Template Reference

#include <PriorityQueue_Heap.h>

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

Inheritance graph
[legend]
Collaboration diagram for ASSA::PriorityQueue_Heap< T, Compare >:

Collaboration graph
[legend]
List of all members.

Public Member Functions

 PriorityQueue_Heap (size_t max_=0)
 PriorityQueue_Heap (size_t, const Compare &)
 PriorityQueue_Heap (const PriorityQueue_Heap &)
 ~PriorityQueue_Heap ()
PriorityQueue_Heap & operator= (const PriorityQueue_Heap &)
void insert (const T &)
T pop ()
const T & top () const
bool remove (T)
size_t size ()
T & operator[] (int idx)

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

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

Definition at line 65 of file PriorityQueue_Heap.h.

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

00066     : m_curr (1), m_lwm (20)
00067 {
00068     trace("PriorityQueue_Heap::PriorityQueue_Heap");
00069     allocate (maxsz_);
00070 }

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

Definition at line 75 of file PriorityQueue_Heap.h.

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

00076     : m_comp (x_), m_curr (1), m_lwm (20)
00077 {
00078     allocate (maxsz_);
00079 }

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

Definition at line 93 of file PriorityQueue_Heap.h.

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.

00094     : m_comp (h_.m_comp), m_size (h_.m_size), m_curr (h_.m_curr),
00095       m_lwm (h_.m_lwm)
00096 {
00097     allocate (m_size);
00098     ::memcpy (m_queue, h_.m_queue, sizeof(T)*m_curr);
00099 }

template<class T, class Compare>
ASSA::PriorityQueue_Heap< T, Compare >::~PriorityQueue_Heap (   )  [inline]
 

Definition at line 119 of file PriorityQueue_Heap.h.

References ASSA::PriorityQueue_Heap< T, Compare >::m_queue.

00120 {
00121     delete [] m_queue;
00122 }

Member Function Documentation

template<class T, class Compare>
void ASSA::PriorityQueue_Heap< T, Compare >::allocate (  size_t   )  [inline, private]
 

Definition at line 84 of file PriorityQueue_Heap.h.

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

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

00085 {
00086     m_size = s_ > m_lwm ? s_ : m_lwm;
00087     m_queue = new T [m_size];
00088 }

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

Definition at line 178 of file PriorityQueue_Heap.h.

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

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

00179 {
00180     register size_t j;
00181     T v = m_queue[k_];
00182 
00183     while (k_ <= m_curr/2) {
00184         j = 2*k_;
00185         if (j < m_curr && m_comp (m_queue[j+1], m_queue[j])) 
00186             j++;
00187         if (m_comp (v, m_queue[j])) 
00188             break;
00189         m_queue[k_] = m_queue[j];
00190         k_ = j;
00191     }
00192     m_queue[k_] = v;
00193 }

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

Implements ASSA::PriorityQueue_Impl< T, Compare >.

Definition at line 127 of file PriorityQueue_Heap.h.

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

00128 {
00129     if (m_curr+1 == m_size)  // if array filled up 
00130         resize (m_size*2); // then resize array
00131 
00132     m_queue [m_curr] = t_;
00133     upheap (m_curr);
00134     m_curr++;
00135 }

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

Definition at line 104 of file PriorityQueue_Heap.h.

References ASSA::PriorityQueue_Heap< T, Compare >::allocate(), 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.

00105 {
00106     delete [] m_queue;
00107     m_comp = h_.m_comp;
00108     m_size = h_.m_size;
00109     m_curr = h_.m_curr;
00110     m_lwm  = h_.m_lwm;
00111     allocate (m_size);
00112     ::memcpy (m_queue, h_.m_queue, sizeof(T)*m_curr);
00113     return *this;
00114 }

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

Implements ASSA::PriorityQueue_Impl< T, Compare >.

Definition at line 246 of file PriorityQueue_Heap.h.

References ASSA::PriorityQueue_Heap< T, Compare >::m_queue.

00247 {
00248     return m_queue[idx+1];
00249 }

template<class T, class Compare>
T ASSA::PriorityQueue_Heap< T, Compare >::pop (   )  [virtual]
 

Implements ASSA::PriorityQueue_Impl< T, Compare >.

Definition at line 155 of file PriorityQueue_Heap.h.

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

00156 {
00157     T v = m_queue[1];
00158     m_queue[1] = m_queue[--m_curr];
00159     
00160     downheap (1);
00161     if (m_curr*3 <= m_size && m_curr*2 > m_lwm) {
00162         resize (m_curr*2);
00163     }
00164     return v;
00165 }

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

Implements ASSA::PriorityQueue_Impl< T, Compare >.

Definition at line 198 of file PriorityQueue_Heap.h.

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

00199 {
00200     register size_t i;
00201 
00202     for (i=1; i < m_curr; i++) 
00203         if (m_queue[i] == t_)
00204             break;
00205 
00206     if (i == m_curr)    // not found
00207         return false;
00208 
00209     m_curr--;
00210     if (i == m_curr)    // last element in queue
00211         return true;
00212 
00213     m_queue[i] = m_queue[m_curr];
00214     downheap (i);
00215 
00216     return true;
00217 }

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

Definition at line 230 of file PriorityQueue_Heap.h.

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

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

00231 {
00232     if (m_size == newsz_)
00233         return true;
00234 
00235     T* new_chunk = new T[newsz_];
00236     ::memcpy (new_chunk, m_queue, m_curr * sizeof(T));
00237     delete [] m_queue;
00238     m_queue = new_chunk;
00239     m_size = newsz_;
00240     return true;
00241 }

template<class T, class Compare>
size_t ASSA::PriorityQueue_Heap< T, Compare >::size (   )  [inline, virtual]
 

Implements ASSA::PriorityQueue_Impl< T, Compare >.

Definition at line 222 of file PriorityQueue_Heap.h.

References ASSA::PriorityQueue_Heap< T, Compare >::m_curr.

00223 {
00224     return m_curr-1;
00225 }

template<class T, class Compare>
const T & ASSA::PriorityQueue_Heap< T, Compare >::top (   )  const [inline, virtual]
 

Implements ASSA::PriorityQueue_Impl< T, Compare >.

Definition at line 170 of file PriorityQueue_Heap.h.

References ASSA::PriorityQueue_Heap< T, Compare >::m_queue.

00171 {
00172     return (const T&) m_queue[1];
00173 }

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

Definition at line 140 of file PriorityQueue_Heap.h.

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

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

00141 {
00142     T v = m_queue[k_];
00143     m_queue[0] = 0;
00144 
00145     while ( k_/2 != 0 && m_comp (v, m_queue[k_/2]) ) {
00146         m_queue[k_] = m_queue[k_/2];
00147         k_ = k_/2;
00148     }
00149     m_queue[k_] = v;
00150 }

Member Data Documentation

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

Definition at line 51 of file PriorityQueue_Heap.h.

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

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 >::downheap(), ASSA::PriorityQueue_Heap< T, Compare >::insert(), ASSA::PriorityQueue_Heap< T, Compare >::operator=(), ASSA::PriorityQueue_Heap< T, Compare >::pop(), ASSA::PriorityQueue_Heap< T, Compare >::PriorityQueue_Heap(), ASSA::PriorityQueue_Heap< T, Compare >::remove(), ASSA::PriorityQueue_Heap< T, Compare >::resize(), and ASSA::PriorityQueue_Heap< T, Compare >::size().

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 >::allocate(), ASSA::PriorityQueue_Heap< T, Compare >::operator=(), and ASSA::PriorityQueue_Heap< T, Compare >::pop().

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

Definition at line 56 of file PriorityQueue_Heap.h.

Referenced by ASSA::PriorityQueue_Heap< T, Compare >::allocate(), ASSA::PriorityQueue_Heap< T, Compare >::downheap(), ASSA::PriorityQueue_Heap< T, Compare >::insert(), ASSA::PriorityQueue_Heap< T, Compare >::operator=(), ASSA::PriorityQueue_Heap< T, Compare >::operator[](), ASSA::PriorityQueue_Heap< T, Compare >::pop(), ASSA::PriorityQueue_Heap< T, Compare >::PriorityQueue_Heap(), ASSA::PriorityQueue_Heap< T, Compare >::remove(), ASSA::PriorityQueue_Heap< T, Compare >::resize(), ASSA::PriorityQueue_Heap< T, Compare >::top(), ASSA::PriorityQueue_Heap< T, Compare >::upheap(), and ASSA::PriorityQueue_Heap< T, Compare >::~PriorityQueue_Heap().

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 >::allocate(), ASSA::PriorityQueue_Heap< T, Compare >::insert(), ASSA::PriorityQueue_Heap< T, Compare >::operator=(), ASSA::PriorityQueue_Heap< T, Compare >::pop(), ASSA::PriorityQueue_Heap< T, Compare >::PriorityQueue_Heap(), and ASSA::PriorityQueue_Heap< T, Compare >::resize().

The documentation for this class was generated from the following file:
Generated on Sun Aug 13 15:08:20 2006 for libassa by  doxygen 1.4.6