Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | File List | Namespace Members | Class Members | File Members | Related Pages

TLArrayHeap< T, _OP > Class Template Reference

Standard array-based heap template. More...

#include <tlarrayheap.h>

Inheritance diagram for TLArrayHeap< T, _OP >:

Inheritance graph
[legend]
Collaboration diagram for TLArrayHeap< T, _OP >:

Collaboration graph
[legend]
List of all members.

Public Member Functions

 TLArrayHeap (const _OP &op=_OP())
 Create empty heap.

 ~TLArrayHeap ()
 Destroy heap clearing it.

T & operator[] (size_t idx)
 Get number of elements in heap: Get element with passed index as reference.

const T & operator[] (size_t idx) const
 See non-const version.

void clear (bool keep_memory=0)
 Clear the whole heap.

T * first ()
const T * first () const
void DownHeapFirst ()
 See first().

void ReHeap (size_t idx, int size_change=0)
 Re-order heap after change of specified element.

void insert (const T &e)
 Insert element into the heap.
.

int ReplaceFirst (const T &e)
 Replace first (=largest) element by new one.

int PopFirst (T *e=NULL)
 Remove first (=largest) element.

template<typename K> ssize_t LinSearch (const K &key)
 Linearly search element in heap.

template<typename K> ssize_t RecSearch (const K &key)
 Recursively search element in heap.

template<typename K> int remove (const K &key, T *e=NULL)
 Remove element with passed key.

int RemoveIdx (size_t idx, T *e=NULL)
 Like remove() but with index instead of key.

template<typename K> int replace (const K &key, const T &new_ent)
 Find element and replace it.

int ReplaceIdx (size_t idx, const T &new_ent)
 Like replace() but with index instead of key.

size_t CheckHeap ()
 Debugging: check heap condition for all entries.


Private Member Functions

T & heap (size_t idx)
T * heapP (size_t idx)
void _realloc (size_t new_asize)
 Perform reallocation operation to change array size.

void _clearall ()
 Clear all elements in the array using OP.clr().

void _UpHeap (size_t idx)
void _DownHeap (size_t idx)
template<typename K> size_t _RecSearch (const K &key, size_t idx)
template<typename K> size_t _LinSearch (const K &key)
void _ReHeap (size_t idx, int size_change=0)
void _RemoveIdx (size_t idx, T *e=NULL)
 TLArrayHeap (const TLArrayHeap &)
 Do not use these:.

void operator= (const TLArrayHeap &)

Detailed Description

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>
class TLArrayHeap< T, _OP >

Standard array-based heap template.

Author:
Wolfgang Wieser ] wwieser (a) gmx <*> de [
Implements standard array-based heap. Heaps allow operations insert() and remove() in O(log(n)), GetLargest() in O(1) and search() in O(n). They are suitable for implementation of waiting queues and similar things where you need quick access to the largest element but do not need to search through the elements.

This heap implementation uses an array to store the elements. The array is resized as needed using reallocation (OP.realloc()). Note that there is nothing which hinders you to store several identical elements in this heap (i.e. several equally large elements).

WHAT TO USE FOR <T>: (Standard text from tlbtree.h:) This class is probably most useful for T being a simple type (integer, unique pointers to a class or small data-only structures). You may use any POD type or any struct/class which is a "plain data type" (PDT; see defop.h) and even for "complex data types" as long as you can provide the required operator plugin OP and it has a working default constructor and a working copy constructor (both for temporaries).

Thread safety: The complete heap must be protected by a mutex for all "write" operations.

This class is NOT "C++-safe", i.e. do not use the assignment operator or the copy constructor (these are private).

Definition at line 62 of file tlarrayheap.h.

Constructor & Destructor Documentation

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>
TLArrayHeap< T, _OP >::TLArrayHeap (  const TLArrayHeap< T, _OP > &   )  [private]
 

Do not use these:.

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>
TLArrayHeap< T, _OP >::TLArrayHeap (  const _OP &  op = _OP()  )  [inline]
 

Create empty heap.

Definition at line 173 of file tlarrayheap.h.

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>
TLArrayHeap< T, _OP >::~TLArrayHeap (   )  [inline]
 

Destroy heap clearing it.

Definition at line 175 of file tlarrayheap.h.

Member Function Documentation

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>
void TLArrayHeap< T, _OP >::_clearall (   )  [inline, private]
 

Clear all elements in the array using OP.clr().

Reimplemented from TLArray< T, _OP >.

Definition at line 94 of file tlarrayheap.h.

Referenced by TLArrayHeap< RJumpEntry, RJumpEntry_Operators >::clear(), and TLArrayHeap< RJumpEntry, RJumpEntry_Operators >::~TLArrayHeap().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>
void TLArrayHeap< T, _OP >::_DownHeap (  size_t  idx  )  [inline, private]
 

For internal use only.

Move element with internal index [idx] down in heap.

Definition at line 112 of file tlarrayheap.h.

Referenced by TLArrayHeap< RJumpEntry, RJumpEntry_Operators >::_ReHeap(), TLArrayHeap< RJumpEntry, RJumpEntry_Operators >::DownHeapFirst(), TLArrayHeap< RJumpEntry, RJumpEntry_Operators >::PopFirst(), and TLArrayHeap< RJumpEntry, RJumpEntry_Operators >::ReplaceFirst().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>
template<typename K>
size_t TLArrayHeap< T, _OP >::_LinSearch (  const K &  key  )  [inline, private]
 

For internal use only.

Linearly find element in heap; internal idx with value 0 if not found.

Definition at line 142 of file tlarrayheap.h.

Referenced by TLArrayHeap< RJumpEntry, RJumpEntry_Operators >::LinSearch(), TLArrayHeap< RJumpEntry, RJumpEntry_Operators >::remove(), and TLArrayHeap< RJumpEntry, RJumpEntry_Operators >::replace().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>
void TLArrayHeap< T, _OP >::_realloc (  size_t  new_asize  )  [inline, private, virtual]
 

Perform reallocation operation to change array size.

Reimplemented from TLArray< T, _OP >.

Definition at line 86 of file tlarrayheap.h.

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>
template<typename K>
size_t TLArrayHeap< T, _OP >::_RecSearch (  const K &  key,
size_t  idx
)  [inline, private]
 

For internal use only.

Recursively find element in heap; internal idx with value 0 if not found.

Definition at line 129 of file tlarrayheap.h.

Referenced by TLArrayHeap< RJumpEntry, RJumpEntry_Operators >::_RecSearch(), and TLArrayHeap< RJumpEntry, RJumpEntry_Operators >::RecSearch().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>
void TLArrayHeap< T, _OP >::_ReHeap (  size_t  idx,
int  size_change = 0
)  [inline, private]
 

For internal use only.

Move element with internal index [idx] up or down in heap.

Todo:
#warning "Optimize me..."

Definition at line 151 of file tlarrayheap.h.

Referenced by TLArrayHeap< RJumpEntry, RJumpEntry_Operators >::_RemoveIdx(), TLArrayHeap< RJumpEntry, RJumpEntry_Operators >::ReHeap(), TLArrayHeap< RJumpEntry, RJumpEntry_Operators >::replace(), and TLArrayHeap< RJumpEntry, RJumpEntry_Operators >::ReplaceIdx().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>
void TLArrayHeap< T, _OP >::_RemoveIdx (  size_t  idx,
T *  e = NULL
)  [inline, private]
 

For internal use only.

Remove element with internal index [idx].

Definition at line 160 of file tlarrayheap.h.

Referenced by TLArrayHeap< RJumpEntry, RJumpEntry_Operators >::remove(), and TLArrayHeap< RJumpEntry, RJumpEntry_Operators >::RemoveIdx().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>
void TLArrayHeap< T, _OP >::_UpHeap (  size_t  idx  )  [inline, private]
 

For internal use only.

Move element with internal index [idx] up in heap.

Definition at line 102 of file tlarrayheap.h.

Referenced by TLArrayHeap< RJumpEntry, RJumpEntry_Operators >::_ReHeap(), and TLArrayHeap< RJumpEntry, RJumpEntry_Operators >::insert().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>
size_t TLArrayHeap< T, _OP >::CheckHeap (   )  [inline]
 

Debugging: check heap condition for all entries.

Returns:
number of errors

Definition at line 370 of file tlarrayheap.h.

Referenced by main().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>
void TLArrayHeap< T, _OP >::clear (  bool  keep_memory = 0  )  [inline]
 

Clear the whole heap.

Reimplemented from TLArray< T, _OP >.

Definition at line 211 of file tlarrayheap.h.

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>
void TLArrayHeap< T, _OP >::DownHeapFirst (   )  [inline]
 

See first().

Definition at line 221 of file tlarrayheap.h.

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>
const T* TLArrayHeap< T, _OP >::first (   )  const [inline]
 

Definition at line 218 of file tlarrayheap.h.

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>
T* TLArrayHeap< T, _OP >::first (   )  [inline]
 

Get first (=largest) element in the heap (or NULL): Do not modify; if you did, call DownHeapFirst(). Runtime is O(1).

Definition at line 217 of file tlarrayheap.h.

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>
T& TLArrayHeap< T, _OP >::heap (  size_t  idx  )  [inline, private]
 

Use this for array subscript:

NOTE about indices: All user-visible indices are in range 0..NElem()-1. Internally, indices 1..NElem() are used with 0 being special.

Definition at line 80 of file tlarrayheap.h.

Referenced by TLArrayHeap< RJumpEntry, RJumpEntry_Operators >::_DownHeap(), TLArrayHeap< RJumpEntry, RJumpEntry_Operators >::_LinSearch(), TLArrayHeap< RJumpEntry, RJumpEntry_Operators >::_RecSearch(), TLArrayHeap< RJumpEntry, RJumpEntry_Operators >::_RemoveIdx(), TLArrayHeap< RJumpEntry, RJumpEntry_Operators >::_UpHeap(), TLArrayHeap< RJumpEntry, RJumpEntry_Operators >::CheckHeap(), TLArrayHeap< RJumpEntry, RJumpEntry_Operators >::operator[](), TLArrayHeap< RJumpEntry, RJumpEntry_Operators >::PopFirst(), TLArrayHeap< RJumpEntry, RJumpEntry_Operators >::replace(), TLArrayHeap< RJumpEntry, RJumpEntry_Operators >::ReplaceFirst(), and TLArrayHeap< RJumpEntry, RJumpEntry_Operators >::ReplaceIdx().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>
T* TLArrayHeap< T, _OP >::heapP (  size_t  idx  )  [inline, private]
 

Definition at line 82 of file tlarrayheap.h.

Referenced by TLArrayHeap< RJumpEntry, RJumpEntry_Operators >::_clearall(), TLArrayHeap< RJumpEntry, RJumpEntry_Operators >::_DownHeap(), TLArrayHeap< RJumpEntry, RJumpEntry_Operators >::_RemoveIdx(), TLArrayHeap< RJumpEntry, RJumpEntry_Operators >::_UpHeap(), TLArrayHeap< RJumpEntry, RJumpEntry_Operators >::first(), TLArrayHeap< RJumpEntry, RJumpEntry_Operators >::insert(), and TLArrayHeap< RJumpEntry, RJumpEntry_Operators >::PopFirst().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>
void TLArrayHeap< T, _OP >::insert (  const T &  e  )  [inline]
 

Insert element into the heap.
.

Runtime is O(log(n)).

Definition at line 244 of file tlarrayheap.h.

Referenced by main().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>
template<typename K>
ssize_t TLArrayHeap< T, _OP >::LinSearch (  const K &  key  )  [inline]
 

Linearly search element in heap.

Return index of element or -1 if not found. If there are more than one identical entries, the first one which is found, is returned.
Runtime is O(n).

This implements linear serach in the array.

Definition at line 287 of file tlarrayheap.h.

Referenced by main().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>
void TLArrayHeap< T, _OP >::operator= (  const TLArrayHeap< T, _OP > &   )  [private]
 

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>
const T& TLArrayHeap< T, _OP >::operator[] (  size_t  idx  )  const [inline]
 

See non-const version.

Reimplemented from TLArray< T, _OP >.

Definition at line 207 of file tlarrayheap.h.

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>
T& TLArrayHeap< T, _OP >::operator[] (  size_t  idx  )  [inline]
 

Get number of elements in heap: Get element with passed index as reference.

NO RANGE CHECK! Range: 0..NElem()-1.
IN CASE YOU MODIFY THE ELEMENT IN A WAY THAT IT HAS AN INCORRECT POSITION IN THE HEAP, CALL ReHeap() IMMEDIATELY.

Runtime is O(1).

Note: Probably only useful if you need to iterate through the elements or obtained an index via some function.

Reimplemented from TLArray< T, _OP >.

Definition at line 205 of file tlarrayheap.h.

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>
int TLArrayHeap< T, _OP >::PopFirst (  T *  e = NULL  )  [inline]
 

Remove first (=largest) element.

If e is non-NULL, store that element there (using OP::ass()) before removing it.

Returns:
1 -> Nothing done: heap empty.
0 -> OK

Definition at line 269 of file tlarrayheap.h.

Referenced by main().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>
template<typename K>
ssize_t TLArrayHeap< T, _OP >::RecSearch (  const K &  key  )  [inline]
 

Recursively search element in heap.

Return index of element or -1 if not found. If there are more than one identical entries, the first one which is found, is returned.
Runtime is O(n).

This function will not descend into sub-trees where the element can surely not be found, hence the smaller the element the longer the operation will take.

NOTE that this function uses TWO as much compare operations per processed element and cannot be inlined as it is recursive, so LinSearch() IS faster in most of the cases.
And hey, for simple types, this turned out to be REALLY slow!

Definition at line 307 of file tlarrayheap.h.

Referenced by main().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>
void TLArrayHeap< T, _OP >::ReHeap (  size_t  idx,
int  size_change = 0
)  [inline]
 

Re-order heap after change of specified element.

See operator[]: Make sure element with passed index is at the correct position in the heap (Re-order).

Runtime is O(log(n)).

  • Use size_change=+1, if the element was made larger.
  • Use size_change=-1, if the element was made smaller.
  • Use size_change=0, if you do not know.

Definition at line 236 of file tlarrayheap.h.

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>
template<typename K>
int TLArrayHeap< T, _OP >::remove (  const K &  key,
T *  e = NULL
)  [inline]
 

Remove element with passed key.

If e is non-NULL, store that element there (using OP::ass()) before removing it. IF there is more than one element matching the key, only the first one which is found, is removed.
Runtime is O(n) (-> LinSearch())

Returns:
1 -> Element not found.
0 -> OK

Definition at line 322 of file tlarrayheap.h.

Referenced by main().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>
int TLArrayHeap< T, _OP >::RemoveIdx (  size_t  idx,
T *  e = NULL
)  [inline]
 

Like remove() but with index instead of key.

Runtime is O(log(n))

Returns:
1 -> Index out of range.
0 -> OK

Definition at line 336 of file tlarrayheap.h.

Referenced by main().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>
template<typename K>
int TLArrayHeap< T, _OP >::replace (  const K &  key,
const T &  new_ent
)  [inline]
 

Find element and replace it.

Just like remove() but instead of removing the element, replace it with new_ent. Same behavior and return value.
Runtime is O(n) (-> LinSearch())

Definition at line 346 of file tlarrayheap.h.

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>
int TLArrayHeap< T, _OP >::ReplaceFirst (  const T &  e  )  [inline]
 

Replace first (=largest) element by new one.

Returns:
1 -> Nothing done: heap empty.
0 -> OK

Definition at line 254 of file tlarrayheap.h.

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>
int TLArrayHeap< T, _OP >::ReplaceIdx (  size_t  idx,
const T &  new_ent
)  [inline]
 

Like replace() but with index instead of key.

Runtime is O(log(n))

Returns:
1 -> Index out of range.
0 -> OK

Definition at line 360 of file tlarrayheap.h.

Referenced by main().

The documentation for this class was generated from the following file:
Generated on Sat Feb 19 22:35:46 2005 for Ray by doxygen 1.3.5