#include <PriorityQueue_Heap.h>

Inheritance diagram for ASSA::PriorityQueue_Heap< 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_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)
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.
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.

    : m_curr (1), m_lwm (20)
{
    trace("PriorityQueue_Heap::PriorityQueue_Heap");
    allocate (maxsz_);
}

References allocate(), m_curr, m_lwm, and trace.

Referenced by operator=(), and PriorityQueue_Heap().

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

    : m_comp (x_), m_curr (1), m_lwm (20)
{
    allocate (maxsz_);
}

References allocate(), m_comp, m_curr, and m_lwm.

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

    : m_comp (h_.m_comp), m_size (h_.m_size), m_curr (h_.m_curr),
      m_lwm (h_.m_lwm)
{
    allocate (m_size);
    ::memcpy (m_queue, h_.m_queue, sizeof(T)*m_curr);
}

References allocate(), m_comp, m_curr, m_lwm, m_queue, m_size, and PriorityQueue_Heap().

◆ ~PriorityQueue_Heap()

template<class T, class Compare>

ASSA::PriorityQueue_Heap< T, Compare >::~PriorityQueue_Heap ( )

inline

Definition at line 118 of file PriorityQueue_Heap.h.

{
    delete [] m_queue;
}

References m_queue.

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.

{
    m_size = s_ > m_lwm ? s_ : m_lwm;
    m_queue = new T [m_size];
}

References m_lwm, m_queue, and m_size.

Referenced by operator=(), PriorityQueue_Heap(), PriorityQueue_Heap(), and 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.

{
    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;
}

References m_comp, m_curr, and m_queue.

Referenced by pop(), and remove().

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

{
    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++;
}

References m_curr, m_queue, m_size, resize(), and upheap().

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

{
    delete [] m_queue;
    m_comp = h_.m_comp;
    m_size = h_.m_size;
    m_curr = h_.m_curr;
    m_lwm  = h_.m_lwm;
    allocate (m_size);
    ::memcpy (m_queue, h_.m_queue, sizeof(T)*m_curr);
    return *this;
}

References allocate(), m_comp, m_curr, m_lwm, m_queue, m_size, and PriorityQueue_Heap().

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

{
    return m_queue[idx+1];
}

References m_queue.

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

{
    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;
}

References downheap(), m_curr, m_lwm, m_queue, m_size, and resize().

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

{
    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;
}

References downheap(), m_curr, and m_queue.

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

{
    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;
}

References m_curr, m_queue, and m_size.

Referenced by insert(), and pop().

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

{
    return m_curr-1;
}

References m_curr.

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

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

References m_queue.

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

{
    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;
}

References m_comp, and m_queue.

Referenced by insert().

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.

Referenced by downheap(), operator=(), PriorityQueue_Heap(), PriorityQueue_Heap(), and upheap().

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

◆ 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 allocate(), operator=(), pop(), PriorityQueue_Heap(), PriorityQueue_Heap(), and PriorityQueue_Heap().

◆ m_queue

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 allocate(), downheap(), insert(), operator=(), operator[](), pop(), PriorityQueue_Heap(), remove(), resize(), top(), upheap(), and ~PriorityQueue_Heap().

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

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

PriorityQueue_Heap.h

Public Member Functions

Protected Member Functions

Protected Attributes

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ PriorityQueue_Heap() [1/3]

◆ PriorityQueue_Heap() [2/3]

◆ PriorityQueue_Heap() [3/3]

◆ ~PriorityQueue_Heap()

Member Function Documentation

◆ allocate()

◆ downheap()

◆ insert()

◆ operator=()

◆ operator[]()

◆ pop()

◆ remove()

◆ resize()

◆ size()

◆ top()

◆ upheap()

Member Data Documentation

◆ m_comp

◆ m_curr

◆ m_lwm

◆ m_queue

◆ m_size