#include <Util.h>
Definition at line 54 of file Util.h.
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_ |
typedef Sequence::value_type prophet::Heap< UnitType, Sequence, Compare, UpdateElem >::value_type |
typedef Sequence::size_type prophet::Heap< UnitType, Sequence, Compare, UpdateElem >::size_type |
typedef Sequence::iterator prophet::Heap< UnitType, Sequence, Compare, UpdateElem >::iterator |
typedef Sequence::const_reference prophet::Heap< UnitType, Sequence, Compare, UpdateElem >::const_reference |
prophet::Heap< UnitType, Sequence, Compare, UpdateElem >::Heap | ( | ) | [inline] |
prophet::Heap< UnitType, Sequence, Compare, UpdateElem >::Heap | ( | Compare * | comp | ) | [inline] |
virtual prophet::Heap< UnitType, Sequence, Compare, UpdateElem >::~Heap | ( | ) | [inline, virtual] |
const Compare* prophet::Heap< UnitType, Sequence, Compare, UpdateElem >::compare | ( | ) | const [inline] |
void prophet::Heap< UnitType, Sequence, Compare, UpdateElem >::set_compare | ( | Compare * | comp | ) | [inline] |
static bool prophet::Heap< UnitType, Sequence, Compare, UpdateElem >::is_heap | ( | const Sequence & | list, | |
Compare & | comp | |||
) | [inline, static] |
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< prophet::Node *, std::vector< prophet::Node * >, struct prophet::heap_compare, struct prophet::heap_pos >::set_compare().
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().
size_type prophet::Heap< UnitType, Sequence, Compare, UpdateElem >::size | ( | ) | const [inline] |
Return number of elements in underlying sequence.
Definition at line 134 of file Util.h.
Referenced by prophet::Heap< prophet::Node *, std::vector< prophet::Node * >, struct prophet::heap_compare, struct prophet::heap_pos >::add(), prophet::Table::heap_del(), prophet::Heap< prophet::Node *, std::vector< prophet::Node * >, struct prophet::heap_compare, struct prophet::heap_pos >::heap_down(), prophet::Heap< prophet::Node *, std::vector< prophet::Node * >, struct prophet::heap_compare, struct prophet::heap_pos >::make_heap(), prophet::Heap< prophet::Node *, std::vector< prophet::Node * >, struct prophet::heap_compare, struct prophet::heap_pos >::remove(), prophet::Table::truncate(), and prophet::Heap< prophet::Node *, std::vector< prophet::Node * >, struct prophet::heap_compare, struct prophet::heap_pos >::update_elements().
const_reference prophet::Heap< UnitType, Sequence, Compare, UpdateElem >::top | ( | ) | const [inline] |
Return read-only reference to top of heap.
Definition at line 139 of file Util.h.
Referenced by prophet::Table::enforce_quota(), prophet::Heap< prophet::Node *, std::vector< prophet::Node * >, struct prophet::heap_compare, struct prophet::heap_pos >::heap_down(), and prophet::Table::truncate().
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().
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().
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().
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< prophet::Node *, std::vector< prophet::Node * >, struct prophet::heap_compare, struct prophet::heap_pos >::make_heap(), and prophet::Heap< prophet::Node *, std::vector< prophet::Node * >, struct prophet::heap_compare, struct prophet::heap_pos >::remove().
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< prophet::Node *, std::vector< prophet::Node * >, struct prophet::heap_compare, struct prophet::heap_pos >::add().
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< prophet::Node *, std::vector< prophet::Node * >, struct prophet::heap_compare, struct prophet::heap_pos >::set_compare().
void prophet::Heap< UnitType, Sequence, Compare, UpdateElem >::swap | ( | size_type | a, | |
size_type | b | |||
) | [inline, protected] |
Swap function used by heap_up, heap_down.
Definition at line 257 of file Util.h.
Referenced by prophet::Heap< prophet::Node *, std::vector< prophet::Node * >, struct prophet::heap_compare, struct prophet::heap_pos >::heap_down(), and prophet::Heap< prophet::Node *, std::vector< prophet::Node * >, struct prophet::heap_compare, struct prophet::heap_pos >::heap_up().
Sequence prophet::Heap< UnitType, Sequence, Compare, UpdateElem >::seq_ [protected] |
Definition at line 265 of file Util.h.
Referenced by prophet::Heap< prophet::Node *, std::vector< prophet::Node * >, struct prophet::heap_compare, struct prophet::heap_pos >::add(), prophet::Heap< prophet::Node *, std::vector< prophet::Node * >, struct prophet::heap_compare, struct prophet::heap_pos >::empty(), prophet::Heap< prophet::Node *, std::vector< prophet::Node * >, struct prophet::heap_compare, struct prophet::heap_pos >::heap_down(), prophet::Heap< prophet::Node *, std::vector< prophet::Node * >, struct prophet::heap_compare, struct prophet::heap_pos >::heap_up(), prophet::Heap< prophet::Node *, std::vector< prophet::Node * >, struct prophet::heap_compare, struct prophet::heap_pos >::remove(), prophet::Heap< prophet::Node *, std::vector< prophet::Node * >, struct prophet::heap_compare, struct prophet::heap_pos >::sequence(), prophet::Heap< prophet::Node *, std::vector< prophet::Node * >, struct prophet::heap_compare, struct prophet::heap_pos >::size(), prophet::Heap< prophet::Node *, std::vector< prophet::Node * >, struct prophet::heap_compare, struct prophet::heap_pos >::swap(), prophet::Heap< prophet::Node *, std::vector< prophet::Node * >, struct prophet::heap_compare, struct prophet::heap_pos >::top(), and prophet::Heap< prophet::Node *, std::vector< prophet::Node * >, struct prophet::heap_compare, struct prophet::heap_pos >::update_elements().
Compare* prophet::Heap< UnitType, Sequence, Compare, UpdateElem >::comp_ [protected] |
Definition at line 266 of file Util.h.
Referenced by prophet::Heap< prophet::Node *, std::vector< prophet::Node * >, struct prophet::heap_compare, struct prophet::heap_pos >::compare(), prophet::Heap< prophet::Node *, std::vector< prophet::Node * >, struct prophet::heap_compare, struct prophet::heap_pos >::Heap(), prophet::Heap< prophet::Node *, std::vector< prophet::Node * >, struct prophet::heap_compare, struct prophet::heap_pos >::heap_down(), prophet::Heap< prophet::Node *, std::vector< prophet::Node * >, struct prophet::heap_compare, struct prophet::heap_pos >::heap_up(), prophet::Heap< prophet::Node *, std::vector< prophet::Node * >, struct prophet::heap_compare, struct prophet::heap_pos >::set_compare(), and prophet::Heap< prophet::Node *, std::vector< prophet::Node * >, struct prophet::heap_compare, struct prophet::heap_pos >::~Heap().
UpdateElem prophet::Heap< UnitType, Sequence, Compare, UpdateElem >::upd_ [protected] |
Definition at line 267 of file Util.h.
Referenced by prophet::Heap< prophet::Node *, std::vector< prophet::Node * >, struct prophet::heap_compare, struct prophet::heap_pos >::add(), prophet::Heap< prophet::Node *, std::vector< prophet::Node * >, struct prophet::heap_compare, struct prophet::heap_pos >::remove(), prophet::Heap< prophet::Node *, std::vector< prophet::Node * >, struct prophet::heap_compare, struct prophet::heap_pos >::swap(), and prophet::Heap< prophet::Node *, std::vector< prophet::Node * >, struct prophet::heap_compare, struct prophet::heap_pos >::update_elements().