Boost  v1.57.0
doxygen for www.boost.org
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
Public Member Functions | Protected Types | Protected Member Functions | Protected Attributes | List of all members
boost::fibonacci_heap< T, Compare, ID > Class Template Reference

#include <fibonacci_heap.hpp>

Collaboration diagram for boost::fibonacci_heap< T, Compare, ID >:
Collaboration graph
[legend]

Public Member Functions

 fibonacci_heap (size_type n, const Compare &cmp, const ID &id=identity_property_map())
 
void push (const T &d)
 
T & top ()
 
const T & top () const
 
void pop ()
 
void add_tree_to_new_roots (size_type v, LinkIter new_roots, int &h)
 
void make_child (size_type u, size_type v, size_type r)
 
void rebuild_root_list (LinkIter new_roots, int &h)
 
void update (const T &d)
 
size_type size () const
 
bool empty () const
 
void print (std::ostream &os)
 

Protected Types

typedef fibonacci_heap self
 
typedef std::vector< size_type > LinkVec
 
typedef LinkVec::iterator LinkIter
 

Protected Member Functions

void remove_from_family (size_type v, size_type p)
 
void insert_into_forest (size_type v, const T &d)
 
void print_recur (size_type x, std::ostream &os)
 
size_type nil () const
 

Protected Attributes

std::vector< T > _key
 
LinkVec _left
 
LinkVec _right
 
LinkVec _p
 
std::vector< bool > _mark
 
LinkVec _degree
 
size_type _n
 
size_type _root
 
ID _id
 
Compare _compare
 
LinkVec _child
 
LinkVec new_roots
 

Member Typedef Documentation

template<class T , class Compare = std::less<T>, class ID = identity_property_map>
typedef LinkVec::iterator boost::fibonacci_heap< T, Compare, ID >::LinkIter
protected
template<class T , class Compare = std::less<T>, class ID = identity_property_map>
typedef std::vector<size_type> boost::fibonacci_heap< T, Compare, ID >::LinkVec
protected
template<class T , class Compare = std::less<T>, class ID = identity_property_map>
typedef fibonacci_heap boost::fibonacci_heap< T, Compare, ID >::self
protected

Constructor & Destructor Documentation

template<class T , class Compare = std::less<T>, class ID = identity_property_map>
boost::fibonacci_heap< T, Compare, ID >::fibonacci_heap ( size_type  n,
const Compare &  cmp,
const ID &  id = identity_property_map() 
)
inline

Member Function Documentation

template<class T , class Compare = std::less<T>, class ID = identity_property_map>
void boost::fibonacci_heap< T, Compare, ID >::add_tree_to_new_roots ( size_type  v,
LinkIter  new_roots,
int &  h 
)
inline

References boost::fibonacci_heap< T, Compare, ID >::_compare, boost::fibonacci_heap< T, Compare, ID >::_degree, boost::fibonacci_heap< T, Compare, ID >::_key, boost::fibonacci_heap< T, Compare, ID >::_mark, boost::fibonacci_heap< T, Compare, ID >::make_child(), boost::fibonacci_heap< T, Compare, ID >::nil(), and boost::swap.

Referenced by boost::fibonacci_heap< T, Compare, ID >::pop().

template<class T , class Compare = std::less<T>, class ID = identity_property_map>
bool boost::fibonacci_heap< T, Compare, ID >::empty ( void  ) const
inline

References boost::fibonacci_heap< T, Compare, ID >::_n.

template<class T , class Compare = std::less<T>, class ID = identity_property_map>
void boost::fibonacci_heap< T, Compare, ID >::insert_into_forest ( size_type  v,
const T &  d 
)
inlineprotected

References boost::fibonacci_heap< T, Compare, ID >::_compare, boost::fibonacci_heap< T, Compare, ID >::_key, boost::fibonacci_heap< T, Compare, ID >::_left, boost::fibonacci_heap< T, Compare, ID >::_p, boost::fibonacci_heap< T, Compare, ID >::_right, boost::fibonacci_heap< T, Compare, ID >::_root, and boost::fibonacci_heap< T, Compare, ID >::nil().

Referenced by boost::fibonacci_heap< T, Compare, ID >::update().

template<class T , class Compare = std::less<T>, class ID = identity_property_map>
void boost::fibonacci_heap< T, Compare, ID >::make_child ( size_type  u,
size_type  v,
size_type  r 
)
inline

References boost::fibonacci_heap< T, Compare, ID >::_child, boost::fibonacci_heap< T, Compare, ID >::_left, boost::fibonacci_heap< T, Compare, ID >::_p, boost::fibonacci_heap< T, Compare, ID >::_right, and boost::flyweights::t.

Referenced by boost::fibonacci_heap< T, Compare, ID >::add_tree_to_new_roots().

template<class T , class Compare = std::less<T>, class ID = identity_property_map>
size_type boost::fibonacci_heap< T, Compare, ID >::nil ( ) const
inlineprotected

References boost::fibonacci_heap< T, Compare, ID >::_left.

Referenced by boost::fibonacci_heap< T, Compare, ID >::add_tree_to_new_roots(), boost::fibonacci_heap< T, Compare, ID >::insert_into_forest(), boost::fibonacci_heap< T, Compare, ID >::pop(), boost::fibonacci_heap< T, Compare, ID >::print(), boost::fibonacci_heap< T, Compare, ID >::print_recur(), boost::fibonacci_heap< T, Compare, ID >::push(), boost::fibonacci_heap< T, Compare, ID >::rebuild_root_list(), and boost::fibonacci_heap< T, Compare, ID >::update().

template<class T , class Compare = std::less<T>, class ID = identity_property_map>
void boost::fibonacci_heap< T, Compare, ID >::pop ( void  )
inline

References boost::fibonacci_heap< T, Compare, ID >::_child, boost::fibonacci_heap< T, Compare, ID >::_degree, boost::fibonacci_heap< T, Compare, ID >::_n, boost::fibonacci_heap< T, Compare, ID >::_p, boost::fibonacci_heap< T, Compare, ID >::_right, boost::fibonacci_heap< T, Compare, ID >::_root, boost::fibonacci_heap< T, Compare, ID >::add_tree_to_new_roots(), boost::fibonacci_heap< T, Compare, ID >::new_roots, boost::fibonacci_heap< T, Compare, ID >::nil(), and boost::fibonacci_heap< T, Compare, ID >::rebuild_root_list().

template<class T , class Compare = std::less<T>, class ID = identity_property_map>
void boost::fibonacci_heap< T, Compare, ID >::print ( std::ostream &  os)
inline

References boost::fibonacci_heap< T, Compare, ID >::_right, boost::fibonacci_heap< T, Compare, ID >::_root, boost::multiprecision::backends::i, boost::fibonacci_heap< T, Compare, ID >::nil(), and boost::fibonacci_heap< T, Compare, ID >::print_recur().

template<class T , class Compare = std::less<T>, class ID = identity_property_map>
void boost::fibonacci_heap< T, Compare, ID >::print_recur ( size_type  x,
std::ostream &  os 
)
inlineprotected

References boost::fibonacci_heap< T, Compare, ID >::_child, boost::fibonacci_heap< T, Compare, ID >::_degree, boost::fibonacci_heap< T, Compare, ID >::_right, boost::multiprecision::backends::i, boost::fibonacci_heap< T, Compare, ID >::nil(), and boost::flyweights::x.

Referenced by boost::fibonacci_heap< T, Compare, ID >::print().

template<class T , class Compare = std::less<T>, class ID = identity_property_map>
void boost::fibonacci_heap< T, Compare, ID >::push ( const T &  d)
inline

References boost::fibonacci_heap< T, Compare, ID >::_child, boost::fibonacci_heap< T, Compare, ID >::_compare, boost::fibonacci_heap< T, Compare, ID >::_degree, boost::fibonacci_heap< T, Compare, ID >::_id, boost::fibonacci_heap< T, Compare, ID >::_key, boost::fibonacci_heap< T, Compare, ID >::_left, boost::fibonacci_heap< T, Compare, ID >::_mark, boost::fibonacci_heap< T, Compare, ID >::_n, boost::fibonacci_heap< T, Compare, ID >::_p, boost::fibonacci_heap< T, Compare, ID >::_right, boost::fibonacci_heap< T, Compare, ID >::_root, and boost::fibonacci_heap< T, Compare, ID >::nil().

template<class T , class Compare = std::less<T>, class ID = identity_property_map>
void boost::fibonacci_heap< T, Compare, ID >::rebuild_root_list ( LinkIter  new_roots,
int &  h 
)
inline

References boost::fibonacci_heap< T, Compare, ID >::_compare, boost::fibonacci_heap< T, Compare, ID >::_key, boost::fibonacci_heap< T, Compare, ID >::_left, boost::fibonacci_heap< T, Compare, ID >::_right, boost::fibonacci_heap< T, Compare, ID >::_root, boost::fibonacci_heap< T, Compare, ID >::nil(), and T.

Referenced by boost::fibonacci_heap< T, Compare, ID >::pop().

template<class T , class Compare = std::less<T>, class ID = identity_property_map>
void boost::fibonacci_heap< T, Compare, ID >::remove_from_family ( size_type  v,
size_type  p 
)
inlineprotected

References boost::fibonacci_heap< T, Compare, ID >::_child, boost::fibonacci_heap< T, Compare, ID >::_left, boost::fibonacci_heap< T, Compare, ID >::_right, and boost::multiprecision::backends::p.

Referenced by boost::fibonacci_heap< T, Compare, ID >::update().

template<class T , class Compare = std::less<T>, class ID = identity_property_map>
size_type boost::fibonacci_heap< T, Compare, ID >::size ( void  ) const
inline

References boost::fibonacci_heap< T, Compare, ID >::_n.

template<class T , class Compare = std::less<T>, class ID = identity_property_map>
T& boost::fibonacci_heap< T, Compare, ID >::top ( void  )
inline

References boost::fibonacci_heap< T, Compare, ID >::_key, and boost::fibonacci_heap< T, Compare, ID >::_root.

template<class T , class Compare = std::less<T>, class ID = identity_property_map>
const T& boost::fibonacci_heap< T, Compare, ID >::top ( void  ) const
inline

References boost::fibonacci_heap< T, Compare, ID >::_key, and boost::fibonacci_heap< T, Compare, ID >::_root.

template<class T , class Compare = std::less<T>, class ID = identity_property_map>
void boost::fibonacci_heap< T, Compare, ID >::update ( const T &  d)
inline

References boost::fibonacci_heap< T, Compare, ID >::_compare, boost::fibonacci_heap< T, Compare, ID >::_degree, boost::fibonacci_heap< T, Compare, ID >::_id, boost::fibonacci_heap< T, Compare, ID >::_key, boost::fibonacci_heap< T, Compare, ID >::_mark, boost::fibonacci_heap< T, Compare, ID >::_p, boost::fibonacci_heap< T, Compare, ID >::_root, boost::fibonacci_heap< T, Compare, ID >::insert_into_forest(), boost::fibonacci_heap< T, Compare, ID >::nil(), boost::multiprecision::backends::p, and boost::fibonacci_heap< T, Compare, ID >::remove_from_family().

Member Data Documentation

template<class T , class Compare = std::less<T>, class ID = identity_property_map>
LinkVec boost::fibonacci_heap< T, Compare, ID >::_child
protected

Referenced by boost::fibonacci_heap< T, Compare, ID >::make_child(), boost::fibonacci_heap< T, Compare, ID >::pop(), boost::fibonacci_heap< T, Compare, ID >::print_recur(), boost::fibonacci_heap< T, Compare, ID >::push(), and boost::fibonacci_heap< T, Compare, ID >::remove_from_family().

template<class T , class Compare = std::less<T>, class ID = identity_property_map>
Compare boost::fibonacci_heap< T, Compare, ID >::_compare
protected

Referenced by boost::fibonacci_heap< T, Compare, ID >::add_tree_to_new_roots(), boost::fibonacci_heap< T, Compare, ID >::insert_into_forest(), boost::fibonacci_heap< T, Compare, ID >::push(), boost::fibonacci_heap< T, Compare, ID >::rebuild_root_list(), and boost::fibonacci_heap< T, Compare, ID >::update().

template<class T , class Compare = std::less<T>, class ID = identity_property_map>
LinkVec boost::fibonacci_heap< T, Compare, ID >::_degree
protected

Referenced by boost::fibonacci_heap< T, Compare, ID >::add_tree_to_new_roots(), boost::fibonacci_heap< T, Compare, ID >::pop(), boost::fibonacci_heap< T, Compare, ID >::print_recur(), boost::fibonacci_heap< T, Compare, ID >::push(), and boost::fibonacci_heap< T, Compare, ID >::update().

template<class T , class Compare = std::less<T>, class ID = identity_property_map>
ID boost::fibonacci_heap< T, Compare, ID >::_id
protected

Referenced by boost::fibonacci_heap< T, Compare, ID >::push(), and boost::fibonacci_heap< T, Compare, ID >::update().

template<class T , class Compare = std::less<T>, class ID = identity_property_map>
std::vector<T> boost::fibonacci_heap< T, Compare, ID >::_key
protected

Referenced by boost::fibonacci_heap< T, Compare, ID >::add_tree_to_new_roots(), boost::fibonacci_heap< T, Compare, ID >::insert_into_forest(), boost::fibonacci_heap< T, Compare, ID >::push(), boost::fibonacci_heap< T, Compare, ID >::rebuild_root_list(), boost::fibonacci_heap< T, Compare, ID >::top(), and boost::fibonacci_heap< T, Compare, ID >::update().

template<class T , class Compare = std::less<T>, class ID = identity_property_map>
LinkVec boost::fibonacci_heap< T, Compare, ID >::_left
protected

Referenced by boost::fibonacci_heap< T, Compare, ID >::insert_into_forest(), boost::fibonacci_heap< T, Compare, ID >::make_child(), boost::fibonacci_heap< T, Compare, ID >::nil(), boost::fibonacci_heap< T, Compare, ID >::push(), boost::fibonacci_heap< T, Compare, ID >::rebuild_root_list(), and boost::fibonacci_heap< T, Compare, ID >::remove_from_family().

template<class T , class Compare = std::less<T>, class ID = identity_property_map>
std::vector<bool> boost::fibonacci_heap< T, Compare, ID >::_mark
protected

Referenced by boost::fibonacci_heap< T, Compare, ID >::add_tree_to_new_roots(), boost::fibonacci_heap< T, Compare, ID >::push(), and boost::fibonacci_heap< T, Compare, ID >::update().

template<class T , class Compare = std::less<T>, class ID = identity_property_map>
size_type boost::fibonacci_heap< T, Compare, ID >::_n
protected

Referenced by boost::fibonacci_heap< T, Compare, ID >::empty(), boost::fibonacci_heap< T, Compare, ID >::pop(), boost::fibonacci_heap< T, Compare, ID >::push(), and boost::fibonacci_heap< T, Compare, ID >::size().

template<class T , class Compare = std::less<T>, class ID = identity_property_map>
LinkVec boost::fibonacci_heap< T, Compare, ID >::_p
protected

Referenced by boost::fibonacci_heap< T, Compare, ID >::insert_into_forest(), boost::fibonacci_heap< T, Compare, ID >::make_child(), boost::fibonacci_heap< T, Compare, ID >::pop(), boost::fibonacci_heap< T, Compare, ID >::push(), and boost::fibonacci_heap< T, Compare, ID >::update().

template<class T , class Compare = std::less<T>, class ID = identity_property_map>
LinkVec boost::fibonacci_heap< T, Compare, ID >::_right
protected

Referenced by boost::fibonacci_heap< T, Compare, ID >::insert_into_forest(), boost::fibonacci_heap< T, Compare, ID >::make_child(), boost::fibonacci_heap< T, Compare, ID >::pop(), boost::fibonacci_heap< T, Compare, ID >::print(), boost::fibonacci_heap< T, Compare, ID >::print_recur(), boost::fibonacci_heap< T, Compare, ID >::push(), boost::fibonacci_heap< T, Compare, ID >::rebuild_root_list(), and boost::fibonacci_heap< T, Compare, ID >::remove_from_family().

template<class T , class Compare = std::less<T>, class ID = identity_property_map>
size_type boost::fibonacci_heap< T, Compare, ID >::_root
protected

Referenced by boost::fibonacci_heap< T, Compare, ID >::insert_into_forest(), boost::fibonacci_heap< T, Compare, ID >::pop(), boost::fibonacci_heap< T, Compare, ID >::print(), boost::fibonacci_heap< T, Compare, ID >::push(), boost::fibonacci_heap< T, Compare, ID >::rebuild_root_list(), boost::fibonacci_heap< T, Compare, ID >::top(), and boost::fibonacci_heap< T, Compare, ID >::update().

template<class T , class Compare = std::less<T>, class ID = identity_property_map>
LinkVec boost::fibonacci_heap< T, Compare, ID >::new_roots
protected

Referenced by boost::fibonacci_heap< T, Compare, ID >::pop().

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