Aleph-w 3.0
A C++ Library for Data Structures and Algorithms
Loading...
Searching...
No Matches
Public Types | Public Member Functions | Private Types | Private Member Functions | Private Attributes | List of all members
ArcFibonacciHeap< GT, Distance, Access_Heap_Node > Class Template Reference

#include <archeap.H>

Collaboration diagram for ArcFibonacciHeap< GT, Distance, Access_Heap_Node >:
[legend]

Public Types

using handle_type = typename Heap::handle_type
 

Public Member Functions

Distance & get_distance ()
 Return the distance functor used to compare arcs in this heap.
 
 ArcFibonacciHeap (Distance __dist=Distance(), Access_Heap_Node acc=Access_Heap_Node())
 Construct an empty Fibonacci arc heap with the given distance functor and heap-node access policy.
 
 ArcFibonacciHeap (const ArcFibonacciHeap &)=delete
 Copying is disabled (heap manages internal node memory)
 
ArcFibonacciHeap & operator= (const ArcFibonacciHeap &)=delete
 
 ArcFibonacciHeap (ArcFibonacciHeap &&other) noexcept
 Move construction transfers ownership of heap nodes.
 
ArcFibonacciHeap & operator= (ArcFibonacciHeap &&other) noexcept
 Move assignment transfers ownership of heap nodes.
 
void put_arc (typename GT::Arc *arc, typename GT::Node *tgt)
 Insert or update an arc associated with a target node, keeping the smallest-distance arc per node in the heap.
 
GT::Arc * get_min_arc ()
 Extract the arc with minimum distance from the heap and clear its node-to-heap mapping.
 
bool is_empty () const noexcept
 Return true if the heap is empty.
 
void empty ()
 Remove all heap nodes and delete their memory.
 
void clear ()
 Empties the container.
 
 ~ArcFibonacciHeap ()
 Destructor. Clears all remaining heap nodes.
 

Private Types

using Compare = Distance_Compare< GT, Distance >
 
using Heap = Fibonacci_Heap< typename GT::Arc *, Compare >
 

Private Member Functions

handle_type & handle_ref (typename GT::Node *p)
 

Private Attributes

Distance dist
 
Access_Heap_Node access_node
 
Compare dist_cmp
 
Heap heap
 

Detailed Description

template<class GT, class Distance, class Access_Heap_Node>
class ArcFibonacciHeap< GT, Distance, Access_Heap_Node >

Definition at line 184 of file archeap.H.

Member Typedef Documentation

◆ Compare

template<class GT , class Distance , class Access_Heap_Node >
using ArcFibonacciHeap< GT, Distance, Access_Heap_Node >::Compare = Distance_Compare<GT, Distance>
private

Definition at line 186 of file archeap.H.

◆ handle_type

template<class GT , class Distance , class Access_Heap_Node >
using ArcFibonacciHeap< GT, Distance, Access_Heap_Node >::handle_type = typename Heap::handle_type

Definition at line 190 of file archeap.H.

◆ Heap

template<class GT , class Distance , class Access_Heap_Node >
using ArcFibonacciHeap< GT, Distance, Access_Heap_Node >::Heap = Fibonacci_Heap<typename GT::Arc *, Compare>
private

Definition at line 187 of file archeap.H.

Constructor & Destructor Documentation

◆ ArcFibonacciHeap() [1/3]

template<class GT , class Distance , class Access_Heap_Node >
ArcFibonacciHeap< GT, Distance, Access_Heap_Node >::ArcFibonacciHeap ( Distance  __dist = Distance(),
Access_Heap_Node  acc = Access_Heap_Node() 
)
inline

Construct an empty Fibonacci arc heap with the given distance functor and heap-node access policy.

Definition at line 209 of file archeap.H.

◆ ArcFibonacciHeap() [2/3]

template<class GT , class Distance , class Access_Heap_Node >
ArcFibonacciHeap< GT, Distance, Access_Heap_Node >::ArcFibonacciHeap ( const ArcFibonacciHeap< GT, Distance, Access_Heap_Node > &  )
delete

Copying is disabled (heap manages internal node memory)

◆ ArcFibonacciHeap() [3/3]

template<class GT , class Distance , class Access_Heap_Node >
ArcFibonacciHeap< GT, Distance, Access_Heap_Node >::ArcFibonacciHeap ( ArcFibonacciHeap< GT, Distance, Access_Heap_Node > &&  other)
inlinenoexcept

Move construction transfers ownership of heap nodes.

Definition at line 221 of file archeap.H.

◆ ~ArcFibonacciHeap()

template<class GT , class Distance , class Access_Heap_Node >
ArcFibonacciHeap< GT, Distance, Access_Heap_Node >::~ArcFibonacciHeap ( )
inline

Destructor. Clears all remaining heap nodes.

Definition at line 303 of file archeap.H.

References ArcFibonacciHeap< GT, Distance, Access_Heap_Node >::empty().

Member Function Documentation

◆ clear()

template<class GT , class Distance , class Access_Heap_Node >
void ArcFibonacciHeap< GT, Distance, Access_Heap_Node >::clear ( )
inline

Empties the container.

Exceptions
none
See also
empty()

Definition at line 300 of file archeap.H.

References ArcFibonacciHeap< GT, Distance, Access_Heap_Node >::empty().

◆ empty()

template<class GT , class Distance , class Access_Heap_Node >
void ArcFibonacciHeap< GT, Distance, Access_Heap_Node >::empty ( )
inline

Remove all heap nodes and delete their memory.

Definition at line 290 of file archeap.H.

References Aleph::Fibonacci_Heap< T, Compare >::clear(), and ArcFibonacciHeap< GT, Distance, Access_Heap_Node >::heap.

Referenced by ArcFibonacciHeap< GT, Distance, Access_Heap_Node >::~ArcFibonacciHeap(), and ArcFibonacciHeap< GT, Distance, Access_Heap_Node >::clear().

◆ get_distance()

template<class GT , class Distance , class Access_Heap_Node >
Distance & ArcFibonacciHeap< GT, Distance, Access_Heap_Node >::get_distance ( )
inline

Return the distance functor used to compare arcs in this heap.

Definition at line 205 of file archeap.H.

References ArcFibonacciHeap< GT, Distance, Access_Heap_Node >::dist.

◆ get_min_arc()

template<class GT , class Distance , class Access_Heap_Node >
GT::Arc * ArcFibonacciHeap< GT, Distance, Access_Heap_Node >::get_min_arc ( )
inline

Extract the arc with minimum distance from the heap and clear its node-to-heap mapping.

Definition at line 263 of file archeap.H.

References ah_underflow_error_if, Aleph::divide_and_conquer_partition_dp(), Aleph::Fibonacci_Heap< T, Compare >::extract_min(), Aleph::Fibonacci_Heap< T, Compare >::get_min_node(), ArcFibonacciHeap< GT, Distance, Access_Heap_Node >::handle_ref(), ArcFibonacciHeap< GT, Distance, Access_Heap_Node >::heap, and Aleph::Fibonacci_Heap< T, Compare >::is_empty().

◆ handle_ref()

template<class GT , class Distance , class Access_Heap_Node >
handle_type & ArcFibonacciHeap< GT, Distance, Access_Heap_Node >::handle_ref ( typename GT::Node *  p)
inlineprivate

Definition at line 198 of file archeap.H.

References ArcFibonacciHeap< GT, Distance, Access_Heap_Node >::access_node.

Referenced by ArcFibonacciHeap< GT, Distance, Access_Heap_Node >::get_min_arc(), and ArcFibonacciHeap< GT, Distance, Access_Heap_Node >::put_arc().

◆ is_empty()

template<class GT , class Distance , class Access_Heap_Node >
bool ArcFibonacciHeap< GT, Distance, Access_Heap_Node >::is_empty ( ) const
inlinenoexcept

Return true if the heap is empty.

Definition at line 287 of file archeap.H.

References ArcFibonacciHeap< GT, Distance, Access_Heap_Node >::heap, and Aleph::Fibonacci_Heap< T, Compare >::is_empty().

◆ operator=() [1/2]

template<class GT , class Distance , class Access_Heap_Node >
ArcFibonacciHeap & ArcFibonacciHeap< GT, Distance, Access_Heap_Node >::operator= ( ArcFibonacciHeap< GT, Distance, Access_Heap_Node > &&  other)
inlinenoexcept

Move assignment transfers ownership of heap nodes.

Definition at line 227 of file archeap.H.

References ArcFibonacciHeap< GT, Distance, Access_Heap_Node >::access_node, ArcFibonacciHeap< GT, Distance, Access_Heap_Node >::dist, ArcFibonacciHeap< GT, Distance, Access_Heap_Node >::dist_cmp, Aleph::divide_and_conquer_partition_dp(), and ArcFibonacciHeap< GT, Distance, Access_Heap_Node >::heap.

◆ operator=() [2/2]

template<class GT , class Distance , class Access_Heap_Node >
ArcFibonacciHeap & ArcFibonacciHeap< GT, Distance, Access_Heap_Node >::operator= ( const ArcFibonacciHeap< GT, Distance, Access_Heap_Node > &  )
delete

◆ put_arc()

template<class GT , class Distance , class Access_Heap_Node >
void ArcFibonacciHeap< GT, Distance, Access_Heap_Node >::put_arc ( typename GT::Arc *  arc,
typename GT::Node *  tgt 
)
inline

Insert or update an arc associated with a target node, keeping the smallest-distance arc per node in the heap.

Definition at line 241 of file archeap.H.

References Aleph::Fibonacci_Heap< T, Compare >::decrease_key(), ArcFibonacciHeap< GT, Distance, Access_Heap_Node >::dist_cmp, Aleph::divide_and_conquer_partition_dp(), ArcFibonacciHeap< GT, Distance, Access_Heap_Node >::handle_ref(), ArcFibonacciHeap< GT, Distance, Access_Heap_Node >::heap, and Aleph::Fibonacci_Heap< T, Compare >::insert().

Member Data Documentation

◆ access_node

template<class GT , class Distance , class Access_Heap_Node >
Access_Heap_Node ArcFibonacciHeap< GT, Distance, Access_Heap_Node >::access_node
private

Definition at line 194 of file archeap.H.

Referenced by ArcFibonacciHeap< GT, Distance, Access_Heap_Node >::handle_ref(), and ArcFibonacciHeap< GT, Distance, Access_Heap_Node >::operator=().

◆ dist

template<class GT , class Distance , class Access_Heap_Node >
Distance ArcFibonacciHeap< GT, Distance, Access_Heap_Node >::dist
private

Definition at line 193 of file archeap.H.

Referenced by ArcFibonacciHeap< GT, Distance, Access_Heap_Node >::get_distance(), and ArcFibonacciHeap< GT, Distance, Access_Heap_Node >::operator=().

◆ dist_cmp

template<class GT , class Distance , class Access_Heap_Node >
Compare ArcFibonacciHeap< GT, Distance, Access_Heap_Node >::dist_cmp
private

Definition at line 195 of file archeap.H.

Referenced by ArcFibonacciHeap< GT, Distance, Access_Heap_Node >::operator=(), and ArcFibonacciHeap< GT, Distance, Access_Heap_Node >::put_arc().

◆ heap

template<class GT , class Distance , class Access_Heap_Node >
Heap ArcFibonacciHeap< GT, Distance, Access_Heap_Node >::heap
private

Definition at line 196 of file archeap.H.

Referenced by ArcFibonacciHeap< GT, Distance, Access_Heap_Node >::empty(), ArcFibonacciHeap< GT, Distance, Access_Heap_Node >::get_min_arc(), ArcFibonacciHeap< GT, Distance, Access_Heap_Node >::is_empty(), ArcFibonacciHeap< GT, Distance, Access_Heap_Node >::operator=(), and ArcFibonacciHeap< GT, Distance, Access_Heap_Node >::put_arc().

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