libassa  3.5.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
Public Member Functions | Protected Member Functions | Protected Attributes | Private Member Functions | Private Attributes
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 >

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_Heapoperator= (const PriorityQueue_Heap &)
void insert (const 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.

    : m_curr (1), m_lwm (20)
{
    trace("PriorityQueue_Heap::PriorityQueue_Heap");
    allocate (maxsz_);
}
template<class T , class Compare >
ASSA::PriorityQueue_Heap< T, Compare >::PriorityQueue_Heap ( size_t  maxsz_,
const Compare &  x_ 
) [inline]

Definition at line 75 of file PriorityQueue_Heap.h.

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

    : m_comp (x_), m_curr (1), m_lwm (20)
{
    allocate (maxsz_);
}
template<class T , class Compare >
ASSA::PriorityQueue_Heap< T, Compare >::PriorityQueue_Heap ( const PriorityQueue_Heap< T, Compare > &  h_) [inline]
template<class T , class Compare >
ASSA::PriorityQueue_Heap< T, Compare >::~PriorityQueue_Heap ( ) [inline]

Definition at line 119 of file PriorityQueue_Heap.h.

{
    delete [] m_queue;
}

Member Function Documentation

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

Definition at line 84 of file PriorityQueue_Heap.h.

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

{
    m_size = s_ > m_lwm ? s_ : m_lwm;
    m_queue = new T [m_size];
}
template<class T , class Compare >
void ASSA::PriorityQueue_Heap< T, Compare >::downheap ( size_t  k_) [protected]

Definition at line 178 of file PriorityQueue_Heap.h.

{
    register size_t j;
    T v = m_queue[k_];

    while (k_ <= m_curr/2) {
        j = 2*k_;
        if (j < m_curr && m_comp (m_queue[j+1], m_queue[j])) 
            j++;
        if (m_comp (v, m_queue[j])) 
            break;
        m_queue[k_] = m_queue[j];
        k_ = j;
    }
    m_queue[k_] = v;
}
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 127 of file PriorityQueue_Heap.h.

{
    if (m_curr+1 == m_size)  // if array filled up 
        resize (m_size*2); // then resize array

    m_queue [m_curr] = t_;
    upheap (m_curr);
    m_curr++;
}
template<class T , class Compare >
PriorityQueue_Heap< T, Compare > & ASSA::PriorityQueue_Heap< T, Compare >::operator= ( const PriorityQueue_Heap< T, Compare > &  h_)
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.

{
    return m_queue[idx+1];
}
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.

{
    T v = m_queue[1];
    m_queue[1] = m_queue[--m_curr];
    
    downheap (1);
    if (m_curr*3 <= m_size && m_curr*2 > m_lwm) {
        resize (m_curr*2);
    }
    return v;
}
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.

{
    register size_t i;

    for (i=1; i < m_curr; i++) 
        if (m_queue[i] == t_)
            break;

    if (i == m_curr)    // not found
        return false;

    m_curr--;
    if (i == m_curr)    // last element in queue
        return true;

    m_queue[i] = m_queue[m_curr];
    downheap (i);

    return true;
}
template<class T , class Compare >
bool ASSA::PriorityQueue_Heap< T, Compare >::resize ( size_t  newsz_) [protected]

Definition at line 230 of file PriorityQueue_Heap.h.

{
    if (m_size == newsz_)
        return true;

    T* new_chunk = new T[newsz_];
    ::memcpy (new_chunk, m_queue, m_curr * sizeof(T));
    delete [] m_queue;
    m_queue = new_chunk;
    m_size = newsz_;
    return true;
}
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.

{
    return m_curr-1;
}
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.

{
    return (const T&) m_queue[1];
}
template<class T , class Compare >
void ASSA::PriorityQueue_Heap< T, Compare >::upheap ( size_t  k_) [protected]

Definition at line 140 of file PriorityQueue_Heap.h.

{
    T v = m_queue[k_];
    m_queue[0] = 0;

    while ( k_/2 != 0 && m_comp (v, m_queue[k_/2]) ) {
        m_queue[k_] = m_queue[k_/2];
        k_ = k_/2;
    }
    m_queue[k_] = v;
}

Member Data Documentation

template<class T, class Compare>
Compare ASSA::PriorityQueue_Heap< T, Compare >::m_comp [protected]
template<class T, class Compare>
size_t ASSA::PriorityQueue_Heap< T, Compare >::m_curr [private]
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=().

template<class T, class Compare>
T* ASSA::PriorityQueue_Heap< T, Compare >::m_queue [private]
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:
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines