Aleph::GenBinHeap< NodeType, Key, Compare > Class Template Reference

Generic heap of nodes. More...

#include <tpl_binHeap.H>

Inheritance diagram for Aleph::GenBinHeap< NodeType, Key, Compare >:

Collaboration diagram for Aleph::GenBinHeap< NodeType, Key, Compare >:

Classes
class	Iterator

Public Types
using	Node = NodeType< Key >

Public Member Functions
Compare &	key_comp () noexcept
Compare &	get_compare () noexcept
void	swap (GenBinHeap &h) noexcept
Node *	getRoot () noexcept
Node *	getRoot () const noexcept
template<class Operation >
bool	preorder_traverse (Operation op) const
template<class Operation >
void	for_each_in_preorder (Operation &operation) const
template<class Operation >
void	for_each_in_preorder (Operation &&operation=Operation()) const
template<class Operation >
void	for_each_in_inorder (Operation &operation) const
template<class Operation >
void	for_each_in_inorder (Operation &&operation=Operation()) const
template<class Op >
bool	level_traverse (Op operation=Op()) const
	GenBinHeap (Compare __cmp=Compare()) noexcept
virtual	~GenBinHeap () noexcept
Node *	insert (Node *p) noexcept
	Inserts a node into a heap.
Node *	getMin_ne () noexcept
Node *	getMin ()
	Removes the node with the lowest priority from the heap.
Node *	getMax ()
void	update (Node *p) noexcept
	Updates the priority of a node contained in the heap.
Node *	remove (Node *node)
	Removes node from the heap.
void	remove_all_and_delete () noexcept
	Deletes all the nodes of the heap, invokes the destructors of the removed nodes, and frees all the memory.
Node *	top ()
	Returns the node with the lowest priority according to the comparison criterion specified in the declaration.
Node *	top () const
const size_t &	size () const noexcept
bool	is_empty () const noexcept
bool	verify_heap () const

Protected Member Functions
virtual bool	verify_heap (Node *p) const

Static Protected Member Functions
static Node *	advance_left (Node *p) noexcept
static Node *	advance_right (Node *p) noexcept

Protected Attributes
Compare	cmp

Private Member Functions
void	swap_with_parent (Node *p) noexcept
virtual void	sift_up (Node *p) noexcept
virtual void	sift_down (Node *p) noexcept
void	swap_root_with_last () noexcept
Node *	remove_last () noexcept
void	replace_node (Node *node, Node *new_node) noexcept
template<class Operation >
bool	preorder_traverse (Node *p, Operation op) const
template<class Op >
bool	__level_traverse (Node *root, Op &operation) const

Static Private Member Functions
static bool	is_in_list (Node *p) noexcept
static bool	has_sibling (Node *p) noexcept
static void	__postorder_delete (Node *p, Node *incomplete_node) noexcept
template<class Operation >
static void	__for_each_in_preorder (Node *p, Operation &operation)
template<class Operation >
static void	__for_each_in_inorder (Node *p, Operation &operation)

Private Attributes
Node	head_node
Node *	head
Node *&	root
Node *	last
size_t	num_nodes

Detailed Description

template<template< class > class NodeType, typename Key, class Compare = Aleph::less<Key>>
requires StrictWeakOrder<Compare, Key>
class Aleph::GenBinHeap< NodeType, Key, Compare >

Generic heap of nodes.

The GenBinHeap class instruments a node heap. This team doesn't is implemented by array, but with a binary tree. This provides the great advantage of being highly dynamic. The memory used is therefore proportional to the amount of nodes of the HEAP.

This class is not intended for public use. Its purpose is to provide basic functionality to the BinHeap, BinHeapVtl, and DynBinHeap.

Parameters

NodeType	the type of node the HEAP uses; this will be with or without a virtual destroyer.
Key	the key that each node keeps.
Compare	the criterion of comparison between the keys of the Nodes.

See also

BinHeap BinHeapVtl DynBinHeap

Definition at line 174 of file tpl_binHeap.H.

Member Typedef Documentation

Node

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>

using Aleph::GenBinHeap< NodeType, Key, Compare >::Node = NodeType<Key>

Definition at line 180 of file tpl_binHeap.H.

Constructor & Destructor Documentation

GenBinHeap()

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>

Aleph::GenBinHeap< NodeType, Key, Compare >::GenBinHeap ( Compare  __cmp = Compare() )

inlinenoexcept

Definition at line 634 of file tpl_binHeap.H.

~GenBinHeap()

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>

virtual Aleph::GenBinHeap< NodeType, Key, Compare >::~GenBinHeap ( )

inlinevirtualnoexcept

Definition at line 641 of file tpl_binHeap.H.

Member Function Documentation

__for_each_in_inorder()

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>

template<class Operation >

static void Aleph::GenBinHeap< NodeType, Key, Compare >::__for_each_in_inorder ( Node *  p, Operation &  operation  )

inlinestaticprivate

Definition at line 543 of file tpl_binHeap.H.

References Aleph::GenBinHeap< NodeType, Key, Compare >::__for_each_in_inorder(), Aleph::GenBinHeap< NodeType, Key, Compare >::advance_left(), Aleph::GenBinHeap< NodeType, Key, Compare >::advance_right(), and Aleph::blossom_maximum_cardinality_matching().

Referenced by Aleph::GenBinHeap< NodeType, Key, Compare >::__for_each_in_inorder().

__for_each_in_preorder()

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>

template<class Operation >

static void Aleph::GenBinHeap< NodeType, Key, Compare >::__for_each_in_preorder ( Node *  p, Operation &  operation  )

inlinestaticprivate

Definition at line 531 of file tpl_binHeap.H.

References Aleph::GenBinHeap< NodeType, Key, Compare >::__for_each_in_preorder(), Aleph::GenBinHeap< NodeType, Key, Compare >::advance_left(), Aleph::GenBinHeap< NodeType, Key, Compare >::advance_right(), and Aleph::blossom_maximum_cardinality_matching().

Referenced by Aleph::GenBinHeap< NodeType, Key, Compare >::__for_each_in_preorder().

__level_traverse()

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>

template<class Op >

bool Aleph::GenBinHeap< NodeType, Key, Compare >::__level_traverse ( Node *  root, Op &  operation  ) const

inlineprivate

Definition at line 598 of file tpl_binHeap.H.

References Aleph::GenBinHeap< NodeType, Key, Compare >::advance_left(), Aleph::GenBinHeap< NodeType, Key, Compare >::advance_right(), Aleph::blossom_maximum_cardinality_matching(), Aleph::DynListQueue< T >::get(), Aleph::DynListQueue< T >::is_empty(), Aleph::DynListQueue< T >::put(), and Aleph::GenBinHeap< NodeType, Key, Compare >::root.

Referenced by Aleph::GenBinHeap< NodeType, Key, Compare >::level_traverse().

__postorder_delete()

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>

static void Aleph::GenBinHeap< NodeType, Key, Compare >::__postorder_delete ( Node *  p, Node *  incomplete_node  )

inlinestaticprivatenoexcept

Definition at line 507 of file tpl_binHeap.H.

References Aleph::GenBinHeap< NodeType, Key, Compare >::__postorder_delete(), Aleph::blossom_maximum_cardinality_matching(), IS_LEAF, LLINK, and RLINK.

Referenced by Aleph::GenBinHeap< NodeType, Key, Compare >::__postorder_delete(), and Aleph::GenBinHeap< NodeType, Key, Compare >::remove_all_and_delete().

advance_left()

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>

static Node * Aleph::GenBinHeap< NodeType, Key, Compare >::advance_left ( Node *  p )

inlinestaticprotectednoexcept

Definition at line 836 of file tpl_binHeap.H.

References IS_LEAF, and LLINK.

Referenced by Aleph::GenBinHeap< NodeType, Key, Compare >::__for_each_in_inorder(), Aleph::GenBinHeap< NodeType, Key, Compare >::__for_each_in_preorder(), Aleph::GenBinHeap< NodeType, Key, Compare >::__level_traverse(), Aleph::GenBinHeap< NodeType, Key, Compare >::Iterator::next_ne(), Aleph::GenBinHeap< NodeType, Key, Compare >::preorder_traverse(), and Aleph::GenBinHeap< NodeType, Key, Compare >::verify_heap().

advance_right()

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>

static Node * Aleph::GenBinHeap< NodeType, Key, Compare >::advance_right ( Node *  p )

inlinestaticprotectednoexcept

Definition at line 844 of file tpl_binHeap.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::GenBinHeap< NodeType, Key, Compare >::has_sibling(), IS_LEAF, LLINK, and RLINK.

Referenced by Aleph::GenBinHeap< NodeType, Key, Compare >::__for_each_in_inorder(), Aleph::GenBinHeap< NodeType, Key, Compare >::__for_each_in_preorder(), Aleph::GenBinHeap< NodeType, Key, Compare >::__level_traverse(), Aleph::GenBinHeap< NodeType, Key, Compare >::Iterator::next_ne(), Aleph::GenBinHeap< NodeType, Key, Compare >::preorder_traverse(), Aleph::GenBinHeap< NodeType, Key, Compare >::Iterator::reset_last(), and Aleph::GenBinHeap< NodeType, Key, Compare >::verify_heap().

for_each_in_inorder() [1/2]

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>

template<class Operation >

void Aleph::GenBinHeap< NodeType, Key, Compare >::for_each_in_inorder ( Operation &&  operation = Operation() ) const

inline

Definition at line 591 of file tpl_binHeap.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::GenBinHeap< NodeType, Key, Compare >::for_each_in_inorder().

for_each_in_inorder() [2/2]

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>

template<class Operation >

void Aleph::GenBinHeap< NodeType, Key, Compare >::for_each_in_inorder ( Operation &  operation ) const

inline

Definition at line 585 of file tpl_binHeap.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::GenBinHeap< NodeType, Key, Compare >::getRoot().

Referenced by Aleph::GenBinHeap< NodeType, Key, Compare >::for_each_in_inorder().

for_each_in_preorder() [1/2]

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>

template<class Operation >

void Aleph::GenBinHeap< NodeType, Key, Compare >::for_each_in_preorder ( Operation &&  operation = Operation() ) const

inline

Definition at line 579 of file tpl_binHeap.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::GenBinHeap< NodeType, Key, Compare >::for_each_in_preorder().

for_each_in_preorder() [2/2]

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>

template<class Operation >

void Aleph::GenBinHeap< NodeType, Key, Compare >::for_each_in_preorder ( Operation &  operation ) const

inline

Definition at line 573 of file tpl_binHeap.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::GenBinHeap< NodeType, Key, Compare >::getRoot().

Referenced by Aleph::DynBinHeap< T, Compare >::copy(), and Aleph::GenBinHeap< NodeType, Key, Compare >::for_each_in_preorder().

get_compare()

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>

Compare & Aleph::GenBinHeap< NodeType, Key, Compare >::get_compare ( )

inlinenoexcept

Definition at line 184 of file tpl_binHeap.H.

References Aleph::GenBinHeap< NodeType, Key, Compare >::cmp.

getMax()

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>

Node * Aleph::GenBinHeap< NodeType, Key, Compare >::getMax ( )

inline

Definition at line 735 of file tpl_binHeap.H.

References Aleph::GenBinHeap< NodeType, Key, Compare >::getMin().

getMin()

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>

Aleph::GenBinHeap< NodeType, Key, Compare >::getMin ( )

inline

Removes the node with the lowest priority from the heap.

getMIn() extracts from this heap the node that holds the lowest priority value according to the comparison criterion defined in the declaration.

Returns

pointer to the removed node.

Exceptions

underflow_error

if the heap is empty.

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Definition at line 728 of file tpl_binHeap.H.

References ah_underflow_error_if, Aleph::GenBinHeap< NodeType, Key, Compare >::getMin_ne(), and Aleph::GenBinHeap< NodeType, Key, Compare >::root.

Referenced by TimeoutQueue::clear_all(), Aleph::Huffman_Encoder_Engine::generate_huffman_tree(), ArcHeap< GT, Distance, Access_Heap_Node >::get_min_arc(), Aleph::GenBinHeap< NodeType, Key, Compare >::getMax(), Aleph::DynBinHeap< T, Compare >::getMin(), main(), and TimeoutQueue::triggerEvent().

getMin_ne()

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>

Node * Aleph::GenBinHeap< NodeType, Key, Compare >::getMin_ne ( )

inlinenoexcept

Definition at line 699 of file tpl_binHeap.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::GenBinHeap< NodeType, Key, Compare >::num_nodes, Aleph::GenBinHeap< NodeType, Key, Compare >::remove_last(), Aleph::GenBinHeap< NodeType, Key, Compare >::root, Aleph::GenBinHeap< NodeType, Key, Compare >::sift_down(), and Aleph::GenBinHeap< NodeType, Key, Compare >::swap_root_with_last().

Referenced by Aleph::Huffman_Encoder_Engine::clear_build_state(), Aleph::GenBinHeap< NodeType, Key, Compare >::getMin(), Aleph::GenBinHeap< NodeType, Key, Compare >::remove(), and Aleph::GenBinHeap< NodeType, Key, Compare >::remove_all_and_delete().

getRoot() [1/2]

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>

Node * Aleph::GenBinHeap< NodeType, Key, Compare >::getRoot ( ) const

inlinenoexcept

Definition at line 526 of file tpl_binHeap.H.

References Aleph::GenBinHeap< NodeType, Key, Compare >::root.

getRoot() [2/2]

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>

Node * Aleph::GenBinHeap< NodeType, Key, Compare >::getRoot ( )

inlinenoexcept

Definition at line 524 of file tpl_binHeap.H.

References Aleph::GenBinHeap< NodeType, Key, Compare >::root.

Referenced by Aleph::GenBinHeap< NodeType, Key, Compare >::for_each_in_inorder(), Aleph::GenBinHeap< NodeType, Key, Compare >::for_each_in_preorder(), Aleph::GenBinHeap< NodeType, Key, Compare >::level_traverse(), and Aleph::GenBinHeap< NodeType, Key, Compare >::preorder_traverse().

has_sibling()

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>

static bool Aleph::GenBinHeap< NodeType, Key, Compare >::has_sibling ( Node *  p )

inlinestaticprivatenoexcept

Definition at line 211 of file tpl_binHeap.H.

References RLINK, and ULINK.

Referenced by Aleph::GenBinHeap< NodeType, Key, Compare >::advance_right(), Aleph::GenBinHeap< NodeType, Key, Compare >::sift_down(), and Aleph::GenBinHeap< NodeType, Key, Compare >::swap_with_parent().

insert()

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>

Node * Aleph::GenBinHeap< NodeType, Key, Compare >::insert ( Node *  p )

inlinenoexcept

Inserts a node into a heap.

insert(p) inserts node p into this heap.

Parameters

[in]

p

the node to insert.

Returns

pointer to the inserted node.

Definition at line 652 of file tpl_binHeap.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::GenBinHeap< NodeType, Key, Compare >::head, IS_LEAF, IS_LEFT, Aleph::GenBinHeap< NodeType, Key, Compare >::last, LLINK, Aleph::GenBinHeap< NodeType, Key, Compare >::num_nodes, RLINK, Aleph::GenBinHeap< NodeType, Key, Compare >::root, Aleph::GenBinHeap< NodeType, Key, Compare >::sift_up(), and ULINK.

Referenced by Aleph::DynBinHeap< T, Compare >::__insert(), Aleph::Huffman_Encoder_Engine::generate_huffman_tree(), Aleph::Huffman_Encoder_Engine::insert_end_symbol_node(), main(), ArcHeap< GT, Distance, Access_Heap_Node >::put_arc(), Aleph::GenBinHeap< NodeType, Key, Compare >::remove(), TimeoutQueue::reschedule_event(), TimeoutQueue::schedule_event(), Aleph::Huffman_Encoder_Engine::set_freq(), and Aleph::Huffman_Encoder_Engine::update_freq().

is_empty()

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>

bool Aleph::GenBinHeap< NodeType, Key, Compare >::is_empty ( ) const

inlinenoexcept

Definition at line 833 of file tpl_binHeap.H.

References Aleph::GenBinHeap< NodeType, Key, Compare >::size().

Referenced by Aleph::Huffman_Encoder_Engine::clear_build_state(), demo_binary_heap(), demo_performance_comparison(), Aleph::Huffman_Encoder_Engine::generate_huffman_tree(), Aleph::Prim_Min_Spanning_Tree< GT, Distance, SA >::min_spanning_tree(), Aleph::Prim_Min_Spanning_Tree< GT, Distance, SA >::paint_min_spanning_tree(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::pop_best_pair(), Aleph::DynBinHeap< T, Compare >::remove(), Aleph::GenBinHeap< NodeType, Key, Compare >::remove_all_and_delete(), Aleph::GenBinHeap< NodeType, Key, Compare >::Iterator::reset_first(), Aleph::GenBinHeap< NodeType, Key, Compare >::Iterator::reset_last(), Aleph::VisvalingamWhyattSimplification::simplify_open_array(), Aleph::VisvalingamWhyattSimplification::simplify_polygon(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and Aleph::VoronoiDiagramFortune::triangulate_sweep().

is_in_list()

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>

static bool Aleph::GenBinHeap< NodeType, Key, Compare >::is_in_list ( Node *  p )

inlinestaticprivatenoexcept

Definition at line 203 of file tpl_binHeap.H.

References IS_LEAF, LLINK, RLINK, and ULINK.

Referenced by Aleph::GenBinHeap< NodeType, Key, Compare >::swap_with_parent().

key_comp()

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>

Compare & Aleph::GenBinHeap< NodeType, Key, Compare >::key_comp ( )

inlinenoexcept

Definition at line 182 of file tpl_binHeap.H.

References Aleph::GenBinHeap< NodeType, Key, Compare >::cmp.

level_traverse()

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>

template<class Op >

bool Aleph::GenBinHeap< NodeType, Key, Compare >::level_traverse ( Op  operation = Op() ) const

inline

Definition at line 629 of file tpl_binHeap.H.

References Aleph::GenBinHeap< NodeType, Key, Compare >::__level_traverse(), Aleph::blossom_maximum_cardinality_matching(), and Aleph::GenBinHeap< NodeType, Key, Compare >::getRoot().

preorder_traverse() [1/2]

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>

template<class Operation >

bool Aleph::GenBinHeap< NodeType, Key, Compare >::preorder_traverse ( Node *  p, Operation  op  ) const

inlineprivate

Definition at line 554 of file tpl_binHeap.H.

References Aleph::GenBinHeap< NodeType, Key, Compare >::advance_left(), Aleph::GenBinHeap< NodeType, Key, Compare >::advance_right(), Aleph::blossom_maximum_cardinality_matching(), and Aleph::GenBinHeap< NodeType, Key, Compare >::preorder_traverse().

Referenced by Aleph::GenBinHeap< NodeType, Key, Compare >::preorder_traverse(), Aleph::GenBinHeap< NodeType, Key, Compare >::preorder_traverse(), Aleph::DynBinHeap< T, Compare >::traverse(), and Aleph::DynBinHeap< T, Compare >::traverse().

preorder_traverse() [2/2]

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>

template<class Operation >

bool Aleph::GenBinHeap< NodeType, Key, Compare >::preorder_traverse ( Operation  op ) const

inline

Definition at line 567 of file tpl_binHeap.H.

References Aleph::GenBinHeap< NodeType, Key, Compare >::getRoot(), and Aleph::GenBinHeap< NodeType, Key, Compare >::preorder_traverse().

remove()

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>

Node * Aleph::GenBinHeap< NodeType, Key, Compare >::remove ( Node *  node )

inline

Removes node from the heap.

remove(node) removes node from this heap.

Parameters

[in]

node

pointer to the node to remove.

Exceptions

underflow_error

if the heap is empty

Returns

pointer to the removed node

Note

It is not verified whether node belongs to the heap.

Definition at line 765 of file tpl_binHeap.H.

References ah_underflow_error_if, Aleph::GenBinHeap< NodeType, Key, Compare >::getMin_ne(), Aleph::GenBinHeap< NodeType, Key, Compare >::insert(), Aleph::GenBinHeap< NodeType, Key, Compare >::last, Aleph::GenBinHeap< NodeType, Key, Compare >::remove_last(), Aleph::GenBinHeap< NodeType, Key, Compare >::replace_node(), Aleph::GenBinHeap< NodeType, Key, Compare >::root, and Aleph::GenBinHeap< NodeType, Key, Compare >::update().

Referenced by TimeoutQueue::cancel_by_id(), TimeoutQueue::cancel_delete_event(), TimeoutQueue::cancel_event(), main(), Aleph::DynBinHeap< T, Compare >::remove(), and TimeoutQueue::reschedule_event().

remove_all_and_delete()

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>

void Aleph::GenBinHeap< NodeType, Key, Compare >::remove_all_and_delete ( )

inlinenoexcept

Deletes all the nodes of the heap, invokes the destructors of the removed nodes, and frees all the memory.

Definition at line 793 of file tpl_binHeap.H.

References Aleph::GenBinHeap< NodeType, Key, Compare >::__postorder_delete(), Aleph::blossom_maximum_cardinality_matching(), Aleph::GenBinHeap< NodeType, Key, Compare >::getMin_ne(), Aleph::GenBinHeap< NodeType, Key, Compare >::head_node, Aleph::GenBinHeap< NodeType, Key, Compare >::is_empty(), IS_LEFT, Aleph::GenBinHeap< NodeType, Key, Compare >::last, Aleph::GenBinHeap< NodeType, Key, Compare >::num_nodes, Aleph::GenBinHeap< NodeType, Key, Compare >::root, and ULINK.

Referenced by ArcHeap< GT, Distance, Access_Heap_Node >::empty(), Aleph::DynBinHeap< T, Compare >::empty(), and main().

remove_last()

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>

Node * Aleph::GenBinHeap< NodeType, Key, Compare >::remove_last ( )

inlineprivatenoexcept

Definition at line 429 of file tpl_binHeap.H.

References Aleph::and, Aleph::blossom_maximum_cardinality_matching(), IS_LEAF, IS_LEFT, Aleph::GenBinHeap< NodeType, Key, Compare >::last, LLINK, Aleph::GenBinHeap< NodeType, Key, Compare >::num_nodes, RLINK, Aleph::GenBinHeap< NodeType, Key, Compare >::root, and ULINK.

Referenced by Aleph::GenBinHeap< NodeType, Key, Compare >::getMin_ne(), and Aleph::GenBinHeap< NodeType, Key, Compare >::remove().

replace_node()

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>

void Aleph::GenBinHeap< NodeType, Key, Compare >::replace_node ( Node *  node, Node *  new_node  )

inlineprivatenoexcept

Definition at line 457 of file tpl_binHeap.H.

References Aleph::blossom_maximum_cardinality_matching(), CTRL_BITS, IS_LEAF, IS_LEFT, Aleph::GenBinHeap< NodeType, Key, Compare >::last, LLINK, RLINK, and ULINK.

Referenced by Aleph::GenBinHeap< NodeType, Key, Compare >::remove().

sift_down()

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>

virtual void Aleph::GenBinHeap< NodeType, Key, Compare >::sift_down ( Node *  p )

inlineprivatevirtualnoexcept

Definition at line 341 of file tpl_binHeap.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::GenBinHeap< NodeType, Key, Compare >::cmp, Aleph::GenBinHeap< NodeType, Key, Compare >::has_sibling(), IS_LEAF, KEY, LLINK, RLINK, and Aleph::GenBinHeap< NodeType, Key, Compare >::swap_with_parent().

Referenced by Aleph::GenBinHeap< NodeType, Key, Compare >::getMin_ne(), and Aleph::GenBinHeap< NodeType, Key, Compare >::update().

sift_up()

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>

virtual void Aleph::GenBinHeap< NodeType, Key, Compare >::sift_up ( Node *  p )

inlineprivatevirtualnoexcept

Definition at line 335 of file tpl_binHeap.H.

References Aleph::and, Aleph::GenBinHeap< NodeType, Key, Compare >::cmp, KEY, Aleph::GenBinHeap< NodeType, Key, Compare >::root, Aleph::GenBinHeap< NodeType, Key, Compare >::swap_with_parent(), and ULINK.

Referenced by Aleph::GenBinHeap< NodeType, Key, Compare >::insert(), and Aleph::GenBinHeap< NodeType, Key, Compare >::update().

size()

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>

const size_t & Aleph::GenBinHeap< NodeType, Key, Compare >::size ( ) const

inlinenoexcept

Definition at line 831 of file tpl_binHeap.H.

References Aleph::GenBinHeap< NodeType, Key, Compare >::num_nodes.

Referenced by TimeoutQueue::cancel_by_id(), TimeoutQueue::cancel_delete_event(), TimeoutQueue::cancel_event(), TimeoutQueue::clear_all(), demo_binary_heap(), Aleph::Huffman_Encoder_Engine::generate_huffman_tree(), TimeoutQueue::is_empty(), Aleph::GenBinHeap< NodeType, Key, Compare >::is_empty(), main(), TimeoutQueue::next_event_time(), TimeoutQueue::size(), TEST(), TEST(), TEST(), TimeoutQueue::triggerEvent(), and TimeoutQueue::wait_until_empty().

swap()

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>

void Aleph::GenBinHeap< NodeType, Key, Compare >::swap ( GenBinHeap< NodeType, Key, Compare > &  h )

inlinenoexcept

Definition at line 194 of file tpl_binHeap.H.

References Aleph::GenBinHeap< NodeType, Key, Compare >::cmp, h, Aleph::GenBinHeap< NodeType, Key, Compare >::last, Aleph::GenBinHeap< NodeType, Key, Compare >::num_nodes, and Aleph::GenBinHeap< NodeType, Key, Compare >::root.

swap_root_with_last()

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>

void Aleph::GenBinHeap< NodeType, Key, Compare >::swap_root_with_last ( )

inlineprivatenoexcept

Definition at line 357 of file tpl_binHeap.H.

References Aleph::and, Aleph::blossom_maximum_cardinality_matching(), CTRL_BITS, Aleph::GenBinHeap< NodeType, Key, Compare >::head, IS_LEAF, Aleph::GenBinHeap< NodeType, Key, Compare >::last, LLINK, NEXT, Aleph::GenBinHeap< NodeType, Key, Compare >::num_nodes, PREV, RLINK, Aleph::GenBinHeap< NodeType, Key, Compare >::root, and ULINK.

Referenced by Aleph::GenBinHeap< NodeType, Key, Compare >::getMin_ne().

swap_with_parent()

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>

void Aleph::GenBinHeap< NodeType, Key, Compare >::swap_with_parent ( Node *  p )

inlineprivatenoexcept

Definition at line 216 of file tpl_binHeap.H.

References Aleph::blossom_maximum_cardinality_matching(), CTRL_BITS, Aleph::GenBinHeap< NodeType, Key, Compare >::has_sibling(), Aleph::GenBinHeap< NodeType, Key, Compare >::is_in_list(), IS_LEAF, Aleph::GenBinHeap< NodeType, Key, Compare >::last, LLINK, Aleph::GenBinHeap< NodeType, Key, Compare >::num_nodes, RLINK, Aleph::GenBinHeap< NodeType, Key, Compare >::root, and ULINK.

Referenced by Aleph::GenBinHeap< NodeType, Key, Compare >::sift_down(), and Aleph::GenBinHeap< NodeType, Key, Compare >::sift_up().

top() [1/2]

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>

Node * Aleph::GenBinHeap< NodeType, Key, Compare >::top ( )

inline

Returns the node with the lowest priority according to the comparison criterion specified in the declaration.

Definition at line 817 of file tpl_binHeap.H.

References ah_underflow_error_if, and Aleph::GenBinHeap< NodeType, Key, Compare >::root.

Referenced by TimeoutQueue::next_event_time(), Aleph::DynBinHeap< T, Compare >::top(), and TimeoutQueue::triggerEvent().

top() [2/2]

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>

Node * Aleph::GenBinHeap< NodeType, Key, Compare >::top ( ) const

inline

Definition at line 824 of file tpl_binHeap.H.

References ah_underflow_error_if, and Aleph::GenBinHeap< NodeType, Key, Compare >::root.

update()

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>

void Aleph::GenBinHeap< NodeType, Key, Compare >::update ( Node *  p )

inlinenoexcept

Updates the priority of a node contained in the heap.

update(p) takes a node of the heap whose priority has been modified and updates its priority within the heap. The idea is that if for some reason a priority must be modified, then the extraction order can be updated.

Parameters

[in]

p

pointer to the node to update

See also

insert()

Definition at line 750 of file tpl_binHeap.H.

References Aleph::GenBinHeap< NodeType, Key, Compare >::sift_down(), and Aleph::GenBinHeap< NodeType, Key, Compare >::sift_up().

Referenced by ArcHeap< GT, Distance, Access_Heap_Node >::put_arc(), Aleph::GenBinHeap< NodeType, Key, Compare >::remove(), Aleph::DynBinHeap< T, Compare >::update(), and Aleph::Huffman_Encoder_Engine::update_freq().

verify_heap() [1/2]

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>

bool Aleph::GenBinHeap< NodeType, Key, Compare >::verify_heap ( ) const

inline

Definition at line 878 of file tpl_binHeap.H.

References Aleph::GenBinHeap< NodeType, Key, Compare >::root, and Aleph::GenBinHeap< NodeType, Key, Compare >::verify_heap().

Referenced by Aleph::GenBinHeap< NodeType, Key, Compare >::verify_heap(), and Aleph::GenBinHeap< NodeType, Key, Compare >::verify_heap().

verify_heap() [2/2]

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>

virtual bool Aleph::GenBinHeap< NodeType, Key, Compare >::verify_heap ( Node *  p ) const

inlineprotectedvirtual

Definition at line 855 of file tpl_binHeap.H.

References Aleph::GenBinHeap< NodeType, Key, Compare >::advance_left(), Aleph::GenBinHeap< NodeType, Key, Compare >::advance_right(), Aleph::blossom_maximum_cardinality_matching(), Aleph::GenBinHeap< NodeType, Key, Compare >::cmp, IS_LEAF, KEY, and Aleph::GenBinHeap< NodeType, Key, Compare >::verify_heap().

Referenced by main().

Member Data Documentation

cmp

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>

Compare Aleph::GenBinHeap< NodeType, Key, Compare >::cmp

protected

Definition at line 177 of file tpl_binHeap.H.

Referenced by Aleph::GenBinHeap< NodeType, Key, Compare >::get_compare(), Aleph::GenBinHeap< NodeType, Key, Compare >::key_comp(), Aleph::GenBinHeap< NodeType, Key, Compare >::sift_down(), Aleph::GenBinHeap< NodeType, Key, Compare >::sift_up(), Aleph::GenBinHeap< NodeType, Key, Compare >::swap(), and Aleph::GenBinHeap< NodeType, Key, Compare >::verify_heap().

head

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>

Node* Aleph::GenBinHeap< NodeType, Key, Compare >::head

private

Definition at line 188 of file tpl_binHeap.H.

Referenced by Aleph::GenBinHeap< NodeType, Key, Compare >::insert(), and Aleph::GenBinHeap< NodeType, Key, Compare >::swap_root_with_last().

head_node

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>

Node Aleph::GenBinHeap< NodeType, Key, Compare >::head_node

private

Definition at line 187 of file tpl_binHeap.H.

Referenced by Aleph::GenBinHeap< NodeType, Key, Compare >::remove_all_and_delete().

last

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>

Node* Aleph::GenBinHeap< NodeType, Key, Compare >::last

private

Definition at line 190 of file tpl_binHeap.H.

Referenced by Aleph::GenBinHeap< NodeType, Key, Compare >::insert(), Aleph::GenBinHeap< NodeType, Key, Compare >::remove(), Aleph::GenBinHeap< NodeType, Key, Compare >::remove_all_and_delete(), Aleph::GenBinHeap< NodeType, Key, Compare >::remove_last(), Aleph::GenBinHeap< NodeType, Key, Compare >::replace_node(), Aleph::GenBinHeap< NodeType, Key, Compare >::swap(), Aleph::GenBinHeap< NodeType, Key, Compare >::swap_root_with_last(), and Aleph::GenBinHeap< NodeType, Key, Compare >::swap_with_parent().

num_nodes

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>

size_t Aleph::GenBinHeap< NodeType, Key, Compare >::num_nodes

private

Definition at line 191 of file tpl_binHeap.H.

Referenced by Aleph::GenBinHeap< NodeType, Key, Compare >::Iterator::end(), Aleph::GenBinHeap< NodeType, Key, Compare >::getMin_ne(), Aleph::GenBinHeap< NodeType, Key, Compare >::insert(), Aleph::GenBinHeap< NodeType, Key, Compare >::remove_all_and_delete(), Aleph::GenBinHeap< NodeType, Key, Compare >::remove_last(), Aleph::GenBinHeap< NodeType, Key, Compare >::Iterator::reset_last(), Aleph::GenBinHeap< NodeType, Key, Compare >::size(), Aleph::GenBinHeap< NodeType, Key, Compare >::swap(), Aleph::GenBinHeap< NodeType, Key, Compare >::swap_root_with_last(), and Aleph::GenBinHeap< NodeType, Key, Compare >::swap_with_parent().

root

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>

Node*& Aleph::GenBinHeap< NodeType, Key, Compare >::root

private

Definition at line 189 of file tpl_binHeap.H.

Referenced by Aleph::GenBinHeap< NodeType, Key, Compare >::__level_traverse(), Aleph::GenBinHeap< NodeType, Key, Compare >::getMin(), Aleph::GenBinHeap< NodeType, Key, Compare >::getMin_ne(), Aleph::GenBinHeap< NodeType, Key, Compare >::getRoot(), Aleph::GenBinHeap< NodeType, Key, Compare >::getRoot(), Aleph::GenBinHeap< NodeType, Key, Compare >::insert(), Aleph::GenBinHeap< NodeType, Key, Compare >::remove(), Aleph::GenBinHeap< NodeType, Key, Compare >::remove_all_and_delete(), Aleph::GenBinHeap< NodeType, Key, Compare >::remove_last(), Aleph::GenBinHeap< NodeType, Key, Compare >::Iterator::reset_first(), Aleph::GenBinHeap< NodeType, Key, Compare >::Iterator::reset_last(), Aleph::GenBinHeap< NodeType, Key, Compare >::sift_up(), Aleph::GenBinHeap< NodeType, Key, Compare >::swap(), Aleph::GenBinHeap< NodeType, Key, Compare >::swap_root_with_last(), Aleph::GenBinHeap< NodeType, Key, Compare >::swap_with_parent(), Aleph::GenBinHeap< NodeType, Key, Compare >::top(), Aleph::GenBinHeap< NodeType, Key, Compare >::top(), and Aleph::GenBinHeap< NodeType, Key, Compare >::verify_heap().

---

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

• tpl_binHeap.H