Aleph-w 3.0
A C++ Library for Data Structures and Algorithms
Loading...
Searching...
No Matches
Classes | Public Types | Public Member Functions | Protected Member Functions | Static Protected Member Functions | Protected Attributes | Private Member Functions | Static Private Member Functions | Private Attributes | List of all members
Aleph::GenBinHeap< NodeType, Key, Compare > Class Template Reference
Trees

Heap genérico de nodos. More...

#include <tpl_binHeap.H>

Inheritance diagram for Aleph::GenBinHeap< NodeType, Key, Compare >:
[legend]
Collaboration diagram for Aleph::GenBinHeap< NodeType, Key, Compare >:
[legend]

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
 Inserta un nodo en un heap.
 
Node * getMin_ne () noexcept
 
Node * getMin ()
 Elimina del heap el nodo de menor prioridad.
 
Node * getMax ()
 
void update (Node *p) noexcept
 Actualiza prioridad de un nodo contenido en el heap.
 
Node * remove (Node *node)
 Elimina del heap el nodo node.
 
void remove_all_and_delete () noexcept
 Borra todos los nodos del heap, invoca a los destructores de los nodos eliminados y libera toda la memoria.
 
Node * top ()
 Retorna el nodo con menor prioridad según el criterio de comparación especificado en la declaración.
 
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>>
class Aleph::GenBinHeap< NodeType, Key, Compare >

Heap genérico de nodos.

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
NodeTypethe type of node the HEAP uses; this will be with or without a virtual destroyer.
Keythe key that each node keeps.
Comparethe criterion of comparison between the keys of the Nodes.
See also
BinHeap BinHeapVtl DynBinHeap

Definition at line 172 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 178 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 632 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 639 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 541 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::maps().

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 529 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::maps().

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 596 of file tpl_binHeap.H.

References Aleph::GenBinHeap< NodeType, Key, Compare >::advance_left(), Aleph::GenBinHeap< NodeType, Key, Compare >::advance_right(), Aleph::DynListQueue< T >::get(), Aleph::DynListQueue< T >::is_empty(), Aleph::maps(), 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 505 of file tpl_binHeap.H.

References Aleph::GenBinHeap< NodeType, Key, Compare >::__postorder_delete(), IS_LEAF, Aleph::LLINK(), Aleph::maps(), and Aleph::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 834 of file tpl_binHeap.H.

References IS_LEAF, and Aleph::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 842 of file tpl_binHeap.H.

References Aleph::GenBinHeap< NodeType, Key, Compare >::has_sibling(), IS_LEAF, Aleph::LLINK(), Aleph::maps(), and Aleph::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 589 of file tpl_binHeap.H.

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

◆ 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 583 of file tpl_binHeap.H.

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

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 577 of file tpl_binHeap.H.

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

◆ 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 571 of file tpl_binHeap.H.

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

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 182 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 733 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

Elimina del heap el nodo de menor prioridad.

getMIn() extrae del heap this el nodo que contenga el menor valor de prioridad según el criterio de comparación definido en la declaración.

Returns
puntero al nodo eliminado.
Exceptions
underflow_errorsi el heap está vacío.

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 726 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(), 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 697 of file tpl_binHeap.H.

References Aleph::maps(), Aleph::GenBinHeap< NodeType, Key, Compare >::num_nodes, Aleph::GenBinHeap< NodeType, Key, Compare >::remove_last(), Aleph::HTList::reset(), 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 524 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 522 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 209 of file tpl_binHeap.H.

References Aleph::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

Inserta un nodo en un heap.

insert(p) inserta en el heap this el nodo p.

Parameters
[in]pel nodo a insertar.
Returns
puntero al nodo insertado.

Definition at line 650 of file tpl_binHeap.H.

References Aleph::GenBinHeap< NodeType, Key, Compare >::head, IS_LEAF, IS_LEFT, Aleph::GenBinHeap< NodeType, Key, Compare >::last, Aleph::LLINK(), Aleph::maps(), Aleph::GenBinHeap< NodeType, Key, Compare >::num_nodes, Aleph::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(), 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 831 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::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(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ 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 201 of file tpl_binHeap.H.

References IS_LEAF, Aleph::LLINK(), Aleph::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 180 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 627 of file tpl_binHeap.H.

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

◆ 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 552 of file tpl_binHeap.H.

References Aleph::GenBinHeap< NodeType, Key, Compare >::advance_left(), Aleph::GenBinHeap< NodeType, Key, Compare >::advance_right(), Aleph::maps(), 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 565 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

Elimina del heap el nodo node.

remove(node) elimina del heap el nodo node.

Parameters
[in]nodepuntero al nodo a eliminar.
Exceptions
underflow_errorsi el heap está vacío
Returns
puntero al nodo eliminado
Note
No se verifica si node pertenece al heap.

Definition at line 763 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(), 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

Borra todos los nodos del heap, invoca a los destructores de los nodos eliminados y libera toda la memoria.

Definition at line 791 of file tpl_binHeap.H.

References Aleph::GenBinHeap< NodeType, Key, Compare >::__postorder_delete(), 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::maps(), Aleph::GenBinHeap< NodeType, Key, Compare >::num_nodes, Aleph::GenBinHeap< NodeType, Key, Compare >::root, and ULINK.

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

◆ 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 427 of file tpl_binHeap.H.

References IS_LEAF, IS_LEFT, Aleph::GenBinHeap< NodeType, Key, Compare >::last, Aleph::LLINK(), Aleph::maps(), Aleph::GenBinHeap< NodeType, Key, Compare >::num_nodes, Aleph::HTList::reset(), Aleph::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 455 of file tpl_binHeap.H.

References CTRL_BITS, IS_LEAF, IS_LEFT, Aleph::GenBinHeap< NodeType, Key, Compare >::last, Aleph::LLINK(), Aleph::maps(), Aleph::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 339 of file tpl_binHeap.H.

References Aleph::GenBinHeap< NodeType, Key, Compare >::cmp, Aleph::GenBinHeap< NodeType, Key, Compare >::has_sibling(), IS_LEAF, KEY, Aleph::LLINK(), Aleph::maps(), Aleph::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 333 of file tpl_binHeap.H.

References Aleph::GenBinHeap< NodeType, Key, Compare >::cmp, KEY, Aleph::maps(), 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 829 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(), 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 192 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 355 of file tpl_binHeap.H.

References CTRL_BITS, Aleph::GenBinHeap< NodeType, Key, Compare >::head, IS_LEAF, Aleph::GenBinHeap< NodeType, Key, Compare >::last, Aleph::LLINK(), Aleph::maps(), NEXT, Aleph::GenBinHeap< NodeType, Key, Compare >::num_nodes, PREV, Aleph::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 214 of file tpl_binHeap.H.

References 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, Aleph::LLINK(), Aleph::maps(), Aleph::GenBinHeap< NodeType, Key, Compare >::num_nodes, Aleph::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

Retorna el nodo con menor prioridad según el criterio de comparación especificado en la declaración.

Definition at line 815 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 822 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

Actualiza prioridad de un nodo contenido en el heap.

update(p) toma un nodo del heap cuya prioridad haya sido modificada y actualiza su prioridad dentro del heap. La idea es que si por alguna razón una prioridad debe ser modificada, entonces el orden de extracción pueda actualizarse.

Parameters
[in]ppuntero al nodo que se desea actualizar
See also
insert()

Definition at line 748 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 876 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 853 of file tpl_binHeap.H.

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

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 175 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 186 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 185 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 188 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 189 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 187 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: