Loading...
Searching...
No Matches
ASSA::PriorityQueue_Heap< T, Compare > Class Template Reference

`#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_);
}
trace
#define trace(s)
trace() is used to trace function call chain in C++ program.
Definition Logger.h:429
ASSA::PriorityQueue_Heap::m_curr
size_t m_curr
Array's size.
Definition PriorityQueue_Heap.h:58
ASSA::PriorityQueue_Heap::allocate
void allocate(size_t)
Definition PriorityQueue_Heap.h:84
ASSA::PriorityQueue_Heap::m_lwm
size_t m_lwm
Next free slot in array.
Definition PriorityQueue_Heap.h:59

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.

: m_comp (x_), m_curr (1), m_lwm (20)
{
allocate (maxsz_);
}
ASSA::PriorityQueue_Heap::m_comp
Compare m_comp
Definition PriorityQueue_Heap.h:51

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.

: 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);
}
ASSA::PriorityQueue_Heap::m_queue
T * m_queue
Definition PriorityQueue_Heap.h:56
ASSA::PriorityQueue_Heap::m_size
size_t m_size
Array of queued pointers.
Definition PriorityQueue_Heap.h:57

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.

{
delete [] m_queue;
}

## Member Function Documentation

## allocate()

template<class T , class Compare >

void ASSA::PriorityQueue_Heap< T, Compare >::allocate | ( | size_t | s_ | ) |

inline private

Definition at line 83 of file PriorityQueue_Heap.h.

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

Referenced by ASSA::PriorityQueue_Heap< T, Compare >::PriorityQueue_Heap(), ASSA::PriorityQueue_Heap< T, Compare >::PriorityQueue_Heap(), and 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.

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

## 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++;
}
ASSA::PriorityQueue_Heap::resize
bool resize(size_t)
Definition PriorityQueue_Heap.h:230
ASSA::PriorityQueue_Heap::upheap
void upheap(size_t)
Definition PriorityQueue_Heap.h:140

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

## 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];
}

## 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;
}
ASSA::PriorityQueue_Heap::downheap
void downheap(size_t)
Definition PriorityQueue_Heap.h:178

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

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

## size()

template<class T , class Compare >

size_t ASSA::PriorityQueue_Heap< T, Compare >::size | ( |  | ) |

inline virtual

Implements ASSA::PriorityQueue_Impl< T, Compare >.

Definition at line 221 of file PriorityQueue_Heap.h.

{
return m_curr-1;
}

## top()

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 169 of file PriorityQueue_Heap.h.

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

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

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

Definition at line 56 of file PriorityQueue_Heap.h.

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

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

- PriorityQueue_Heap.h