#include <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_ |
Definition at line 54 of file Util.h.
| typedef Sequence::const_reference prophet::Heap< UnitType, Sequence, Compare, UpdateElem >::const_reference |
| typedef Sequence::iterator prophet::Heap< UnitType, Sequence, Compare, UpdateElem >::iterator |
| typedef Sequence::size_type prophet::Heap< UnitType, Sequence, Compare, UpdateElem >::size_type |
| typedef Sequence::value_type prophet::Heap< UnitType, Sequence, Compare, UpdateElem >::value_type |
| 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] |
| 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().
| const Compare* prophet::Heap< UnitType, Sequence, Compare, UpdateElem >::compare | ( | ) | const [inline] |
| 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 >::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().
| 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().
| static bool prophet::Heap< UnitType, Sequence, Compare, UpdateElem >::is_heap | ( | const Sequence & | list, | |
| Compare & | comp | |||
| ) | [inline, static] |
| 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().
| 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().
| void prophet::Heap< UnitType, Sequence, Compare, UpdateElem >::set_compare | ( | Compare * | comp | ) | [inline] |
| 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< Node *, std::vector< Node * >, struct heap_compare, struct heap_pos >::add(), prophet::Table::heap_del(), prophet::Heap< Node *, std::vector< Node * >, struct heap_compare, struct heap_pos >::heap_down(), prophet::Heap< Node *, std::vector< Node * >, struct heap_compare, struct heap_pos >::make_heap(), prophet::Heap< Node *, std::vector< Node * >, struct heap_compare, struct heap_pos >::remove(), prophet::Table::truncate(), and prophet::Heap< Node *, std::vector< Node * >, struct heap_compare, struct heap_pos >::update_elements().
| 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< Node *, std::vector< Node * >, struct heap_compare, struct heap_pos >::heap_down(), and prophet::Heap< Node *, std::vector< Node * >, struct heap_compare, struct heap_pos >::heap_up().
| 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< Node *, std::vector< Node * >, struct heap_compare, struct heap_pos >::heap_down(), and prophet::Table::truncate().
| 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().
Compare* prophet::Heap< UnitType, Sequence, Compare, UpdateElem >::comp_ [protected] |
Definition at line 266 of file Util.h.
Referenced by prophet::Heap< Node *, std::vector< Node * >, struct heap_compare, struct heap_pos >::compare(), prophet::Heap< Node *, std::vector< Node * >, struct heap_compare, struct heap_pos >::Heap(), prophet::Heap< Node *, std::vector< Node * >, struct heap_compare, struct heap_pos >::heap_down(), prophet::Heap< Node *, std::vector< Node * >, struct heap_compare, struct heap_pos >::heap_up(), prophet::Heap< Node *, std::vector< Node * >, struct heap_compare, struct heap_pos >::set_compare(), and prophet::Heap< Node *, std::vector< Node * >, struct heap_compare, struct heap_pos >::~Heap().
Sequence prophet::Heap< UnitType, Sequence, Compare, UpdateElem >::seq_ [protected] |
Definition at line 265 of file Util.h.
Referenced by prophet::Heap< Node *, std::vector< Node * >, struct heap_compare, struct heap_pos >::add(), prophet::Heap< Node *, std::vector< Node * >, struct heap_compare, struct heap_pos >::empty(), prophet::Heap< Node *, std::vector< Node * >, struct heap_compare, struct heap_pos >::heap_down(), prophet::Heap< Node *, std::vector< Node * >, struct heap_compare, struct heap_pos >::heap_up(), prophet::Heap< Node *, std::vector< Node * >, struct heap_compare, struct heap_pos >::remove(), prophet::Heap< Node *, std::vector< Node * >, struct heap_compare, struct heap_pos >::sequence(), prophet::Heap< Node *, std::vector< Node * >, struct heap_compare, struct heap_pos >::size(), prophet::Heap< Node *, std::vector< Node * >, struct heap_compare, struct heap_pos >::swap(), prophet::Heap< Node *, std::vector< Node * >, struct heap_compare, struct heap_pos >::top(), and prophet::Heap< Node *, std::vector< Node * >, struct heap_compare, struct heap_pos >::update_elements().
UpdateElem prophet::Heap< UnitType, Sequence, Compare, UpdateElem >::upd_ [protected] |
Definition at line 267 of file Util.h.
Referenced by prophet::Heap< Node *, std::vector< Node * >, struct heap_compare, struct heap_pos >::add(), prophet::Heap< Node *, std::vector< Node * >, struct heap_compare, struct heap_pos >::remove(), prophet::Heap< Node *, std::vector< Node * >, struct heap_compare, struct heap_pos >::swap(), and prophet::Heap< Node *, std::vector< Node * >, struct heap_compare, struct heap_pos >::update_elements().
1.6.3