prophet::Heap< UnitType, Sequence, Compare, UpdateElem > Class Template Reference

#include <Util.h>

List of all members.

Public Types

typedef Sequence::value_type value_type
typedef Sequence::size_type size_type
typedef Sequence::iterator iterator
typedef Sequence::const_reference const_reference

Public Member Functions

 Heap ()
 Default constructor.
 Heap (Compare *comp)
 Heap assumes ownership of comp.
virtual ~Heap ()
 Destructor.
const Compare * compare () const
 Constant reference to current compare.
void set_compare (Compare *comp)
 Change to new compare and reorder heap.
void update_elements ()
 Pass over entire sequence to ensure each element's heap pointer.
bool empty () const
 Return true if underlying sequence is empty.
size_type size () const
 Return number of elements in underlying sequence.
const_reference top () const
 Return read-only reference to top of heap.
void add (value_type x)
 Add data to heap, return index of insertion point.
void remove (size_t pos)
 Remove element from heap by position, re-heap remaining elements.
const Sequence & sequence () const
 Constant reference to underlying sequence.

Static Public Member Functions

static bool is_heap (const Sequence &list, Compare &comp)
 Verify heap order.

Protected Member Functions

size_type heap_down (size_type hole)
 Assuming left and right subtrees are in heap order, push hole down the tree until it reaches heap order.
size_type heap_up (size_type last)
 Assuming tree is heap order above last, bubble up last until the tree is in heap order.
void make_heap (size_type first)
 Begin with last node (a leaf, therefore a subtree of size 1, therefore a heap) and work upwards to build heap.
void swap (size_type a, size_type b)
 Swap function used by heap_up, heap_down.

Protected Attributes

Sequence seq_
Compare * comp_
UpdateElem upd_


Detailed Description

template<typename UnitType, typename Sequence = std::vector<UnitType>, typename Compare = std::less<typename Sequence::value_type>, typename UpdateElem = DoNothing<UnitType,typename Sequence::size_type>>
class prophet::Heap< UnitType, Sequence, Compare, UpdateElem >

Definition at line 54 of file Util.h.


Member Typedef Documentation

template<typename UnitType, typename Sequence = std::vector<UnitType>, typename Compare = std::less<typename Sequence::value_type>, typename UpdateElem = DoNothing<UnitType,typename Sequence::size_type>>
typedef Sequence::const_reference prophet::Heap< UnitType, Sequence, Compare, UpdateElem >::const_reference

Definition at line 60 of file Util.h.

template<typename UnitType, typename Sequence = std::vector<UnitType>, typename Compare = std::less<typename Sequence::value_type>, typename UpdateElem = DoNothing<UnitType,typename Sequence::size_type>>
typedef Sequence::iterator prophet::Heap< UnitType, Sequence, Compare, UpdateElem >::iterator

Definition at line 59 of file Util.h.

template<typename UnitType, typename Sequence = std::vector<UnitType>, typename Compare = std::less<typename Sequence::value_type>, typename UpdateElem = DoNothing<UnitType,typename Sequence::size_type>>
typedef Sequence::size_type prophet::Heap< UnitType, Sequence, Compare, UpdateElem >::size_type

Definition at line 58 of file Util.h.

template<typename UnitType, typename Sequence = std::vector<UnitType>, typename Compare = std::less<typename Sequence::value_type>, typename UpdateElem = DoNothing<UnitType,typename Sequence::size_type>>
typedef Sequence::value_type prophet::Heap< UnitType, Sequence, Compare, UpdateElem >::value_type

Definition at line 57 of file Util.h.


Constructor & Destructor Documentation

template<typename UnitType, typename Sequence = std::vector<UnitType>, typename Compare = std::less<typename Sequence::value_type>, typename UpdateElem = DoNothing<UnitType,typename Sequence::size_type>>
prophet::Heap< UnitType, Sequence, Compare, UpdateElem >::Heap (  )  [inline]

Default constructor.

Definition at line 65 of file Util.h.

template<typename UnitType, typename Sequence = std::vector<UnitType>, typename Compare = std::less<typename Sequence::value_type>, typename UpdateElem = DoNothing<UnitType,typename Sequence::size_type>>
prophet::Heap< UnitType, Sequence, Compare, UpdateElem >::Heap ( Compare *  comp  )  [inline]

Heap assumes ownership of comp.

Definition at line 73 of file Util.h.

template<typename UnitType, typename Sequence = std::vector<UnitType>, typename Compare = std::less<typename Sequence::value_type>, typename UpdateElem = DoNothing<UnitType,typename Sequence::size_type>>
virtual prophet::Heap< UnitType, Sequence, Compare, UpdateElem >::~Heap (  )  [inline, virtual]

Destructor.

Definition at line 81 of file Util.h.


Member Function Documentation

template<typename UnitType, typename Sequence = std::vector<UnitType>, typename Compare = std::less<typename Sequence::value_type>, typename UpdateElem = DoNothing<UnitType,typename Sequence::size_type>>
void prophet::Heap< UnitType, Sequence, Compare, UpdateElem >::add ( value_type  x  )  [inline]

Add data to heap, return index of insertion point.

Definition at line 145 of file Util.h.

Referenced by prophet::Table::heap_add().

template<typename UnitType, typename Sequence = std::vector<UnitType>, typename Compare = std::less<typename Sequence::value_type>, typename UpdateElem = DoNothing<UnitType,typename Sequence::size_type>>
const Compare* prophet::Heap< UnitType, Sequence, Compare, UpdateElem >::compare (  )  const [inline]

Constant reference to current compare.

Definition at line 87 of file Util.h.

template<typename UnitType, typename Sequence = std::vector<UnitType>, typename Compare = std::less<typename Sequence::value_type>, typename UpdateElem = DoNothing<UnitType,typename Sequence::size_type>>
bool prophet::Heap< UnitType, Sequence, Compare, UpdateElem >::empty (  )  const [inline]

Return true if underlying sequence is empty.

Definition at line 129 of file Util.h.

Referenced by prophet::Table::enforce_quota(), and prophet::Table::truncate().

template<typename UnitType, typename Sequence = std::vector<UnitType>, typename Compare = std::less<typename Sequence::value_type>, typename UpdateElem = DoNothing<UnitType,typename Sequence::size_type>>
size_type prophet::Heap< UnitType, Sequence, Compare, UpdateElem >::heap_down ( size_type  hole  )  [inline, protected]

Assuming left and right subtrees are in heap order, push hole down the tree until it reaches heap order.

Definition at line 180 of file Util.h.

Referenced by prophet::Heap< Node *, std::vector< Node * >, struct heap_compare, struct heap_pos >::make_heap(), and prophet::Heap< Node *, std::vector< Node * >, struct heap_compare, struct heap_pos >::remove().

template<typename UnitType, typename Sequence = std::vector<UnitType>, typename Compare = std::less<typename Sequence::value_type>, typename UpdateElem = DoNothing<UnitType,typename Sequence::size_type>>
size_type prophet::Heap< UnitType, Sequence, Compare, UpdateElem >::heap_up ( size_type  last  )  [inline, protected]

Assuming tree is heap order above last, bubble up last until the tree is in heap order.

Definition at line 214 of file Util.h.

Referenced by prophet::Heap< Node *, std::vector< Node * >, struct heap_compare, struct heap_pos >::add().

template<typename UnitType, typename Sequence = std::vector<UnitType>, typename Compare = std::less<typename Sequence::value_type>, typename UpdateElem = DoNothing<UnitType,typename Sequence::size_type>>
static bool prophet::Heap< UnitType, Sequence, Compare, UpdateElem >::is_heap ( const Sequence &  list,
Compare &  comp 
) [inline, static]

Verify heap order.

Definition at line 104 of file Util.h.

template<typename UnitType, typename Sequence = std::vector<UnitType>, typename Compare = std::less<typename Sequence::value_type>, typename UpdateElem = DoNothing<UnitType,typename Sequence::size_type>>
void prophet::Heap< UnitType, Sequence, Compare, UpdateElem >::make_heap ( size_type  first  )  [inline, protected]

Begin with last node (a leaf, therefore a subtree of size 1, therefore a heap) and work upwards to build heap.

Definition at line 237 of file Util.h.

Referenced by prophet::Heap< Node *, std::vector< Node * >, struct heap_compare, struct heap_pos >::set_compare().

template<typename UnitType, typename Sequence = std::vector<UnitType>, typename Compare = std::less<typename Sequence::value_type>, typename UpdateElem = DoNothing<UnitType,typename Sequence::size_type>>
void prophet::Heap< UnitType, Sequence, Compare, UpdateElem >::remove ( size_t  pos  )  [inline]

Remove element from heap by position, re-heap remaining elements.

Definition at line 159 of file Util.h.

Referenced by prophet::Table::heap_del(), and prophet::Table::truncate().

template<typename UnitType, typename Sequence = std::vector<UnitType>, typename Compare = std::less<typename Sequence::value_type>, typename UpdateElem = DoNothing<UnitType,typename Sequence::size_type>>
const Sequence& prophet::Heap< UnitType, Sequence, Compare, UpdateElem >::sequence (  )  const [inline]

Constant reference to underlying sequence.

Definition at line 172 of file Util.h.

Referenced by prophet::Table::heap_begin(), prophet::Table::heap_del(), and prophet::Table::heap_end().

template<typename UnitType, typename Sequence = std::vector<UnitType>, typename Compare = std::less<typename Sequence::value_type>, typename UpdateElem = DoNothing<UnitType,typename Sequence::size_type>>
void prophet::Heap< UnitType, Sequence, Compare, UpdateElem >::set_compare ( Compare *  comp  )  [inline]

Change to new compare and reorder heap.

Definition at line 93 of file Util.h.

template<typename UnitType, typename Sequence = std::vector<UnitType>, typename Compare = std::less<typename Sequence::value_type>, typename UpdateElem = DoNothing<UnitType,typename Sequence::size_type>>
size_type prophet::Heap< UnitType, Sequence, Compare, UpdateElem >::size (  )  const [inline]

template<typename UnitType, typename Sequence = std::vector<UnitType>, typename Compare = std::less<typename Sequence::value_type>, typename UpdateElem = DoNothing<UnitType,typename Sequence::size_type>>
void prophet::Heap< UnitType, Sequence, Compare, UpdateElem >::swap ( size_type  a,
size_type  b 
) [inline, protected]

template<typename UnitType, typename Sequence = std::vector<UnitType>, typename Compare = std::less<typename Sequence::value_type>, typename UpdateElem = DoNothing<UnitType,typename Sequence::size_type>>
const_reference prophet::Heap< UnitType, Sequence, Compare, UpdateElem >::top (  )  const [inline]

template<typename UnitType, typename Sequence = std::vector<UnitType>, typename Compare = std::less<typename Sequence::value_type>, typename UpdateElem = DoNothing<UnitType,typename Sequence::size_type>>
void prophet::Heap< UnitType, Sequence, Compare, UpdateElem >::update_elements (  )  [inline]

Pass over entire sequence to ensure each element's heap pointer.

Definition at line 120 of file Util.h.

Referenced by prophet::Heap< Node *, std::vector< Node * >, struct heap_compare, struct heap_pos >::set_compare().


Member Data Documentation

template<typename UnitType, typename Sequence = std::vector<UnitType>, typename Compare = std::less<typename Sequence::value_type>, typename UpdateElem = DoNothing<UnitType,typename Sequence::size_type>>
Compare* prophet::Heap< UnitType, Sequence, Compare, UpdateElem >::comp_ [protected]

template<typename UnitType, typename Sequence = std::vector<UnitType>, typename Compare = std::less<typename Sequence::value_type>, typename UpdateElem = DoNothing<UnitType,typename Sequence::size_type>>
Sequence prophet::Heap< UnitType, Sequence, Compare, UpdateElem >::seq_ [protected]

template<typename UnitType, typename Sequence = std::vector<UnitType>, typename Compare = std::less<typename Sequence::value_type>, typename UpdateElem = DoNothing<UnitType,typename Sequence::size_type>>
UpdateElem prophet::Heap< UnitType, Sequence, Compare, UpdateElem >::upd_ [protected]


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

Generated on Fri Jan 30 09:43:16 2009 for DTN Reference Implementation by  doxygen 1.5.8