Base class for binomial heap. More...

#include <binomial_heap_base_.hpp>

Inheritance diagram for __gnu_pbds::detail::binomial_heap_base< Value_Type, Cmp_Fn, _Alloc >:

Collaboration diagram for __gnu_pbds::detail::binomial_heap_base< Value_Type, Cmp_Fn, _Alloc >:

Public Types
typedef _Alloc	allocator_type

typedef Cmp_Fn	cmp_fn

typedef base_type::const_iterator	const_iterator

typedef __rebind_v::const_pointer	const_pointer

typedef __rebind_v::const_reference	const_reference

typedef _Alloc::difference_type	difference_type

typedef base_type::iterator	iterator

typedef base_type::point_const_iterator	point_const_iterator

typedef base_type::point_iterator	point_iterator

typedef __rebind_v::pointer	pointer

typedef __rebind_v::reference	reference

typedef _Alloc::size_type	size_type

typedef Value_Type	value_type

Public Member Functions
iterator	begin ()

const_iterator	begin () const

void	clear ()

bool	empty () const

iterator	end ()

const_iterator	end () const

void	erase (point_iterator)

template<typename Pred >
size_type	erase_if (Pred)

Cmp_Fn &	get_cmp_fn ()

const Cmp_Fn &	get_cmp_fn () const

void	join (binomial_heap_base< Value_Type, Cmp_Fn, _Alloc > &)

size_type	max_size () const

void	modify (point_iterator, const_reference)

void	pop ()

point_iterator	push (const_reference)

size_type	size () const

template<typename Pred >
void	split (Pred, binomial_heap_base< Value_Type, Cmp_Fn, _Alloc > &)

void	swap (left_child_next_sibling_heap< Value_Type, Cmp_Fn, _Alloc::size_type, _Alloc > &)

const_reference	top () const

Protected Types
typedef base_type::node	node

typedef _Alloc::template rebind< left_child_next_sibling_heap_node_< Value_Type, _Alloc::size_type, _Alloc > >::other	node_allocator

typedef base_type::node_const_pointer	node_const_pointer

typedef _Alloc::size_type	node_metadata

typedef base_type::node_pointer	node_pointer

typedef std::pair< node_pointer, node_pointer >	node_pointer_pair

Protected Member Functions
	binomial_heap_base ()

	binomial_heap_base (const Cmp_Fn &)

	binomial_heap_base (const binomial_heap_base< Value_Type, Cmp_Fn, _Alloc > &)

	~binomial_heap_base ()

void	actual_erase_node (node_pointer)

void	bubble_to_top (node_pointer)

void	clear_imp (node_pointer)

template<typename It >
void	copy_from_range (It, It)

void	find_max ()

node_pointer	get_new_node_for_insert (const_reference)

node_pointer	prune (Pred)

void	swap (binomial_heap_base< Value_Type, Cmp_Fn, _Alloc > &)

void	swap_with_parent (node_pointer, node_pointer)

void	to_linked_list ()

void	value_swap (left_child_next_sibling_heap &)

Static Protected Member Functions
static void	make_child_of (node_pointer, node_pointer)

static node_pointer	parent (node_pointer)

Protected Attributes
node_pointer	m_p_max

node_pointer	m_p_root

size_type	m_size

Private Types
typedef _Alloc::template rebind< Value_Type >::other	__rebind_v

typedef left_child_next_sibling_heap< Value_Type, Cmp_Fn, typename _Alloc::size_type, _Alloc >	base_type

Private Member Functions
node_pointer	fix (node_pointer) const

void	insert_node (node_pointer)

node_pointer	join (node_pointer, node_pointer) const

void	remove_parentless_node (node_pointer)

Detailed Description

template<typename Value_Type, typename Cmp_Fn, typename _Alloc>
class __gnu_pbds::detail::binomial_heap_base< Value_Type, Cmp_Fn, _Alloc >

Base class for binomial heap.

Member Typedef Documentation

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

typedef _Alloc::template rebind<Value_Type>::other __gnu_pbds::detail::binomial_heap_base< Value_Type, Cmp_Fn, _Alloc >::__rebind_v

private

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

typedef _Alloc __gnu_pbds::detail::binomial_heap_base< Value_Type, Cmp_Fn, _Alloc >::allocator_type

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

typedef left_child_next_sibling_heap<Value_Type, Cmp_Fn, typename _Alloc::size_type, _Alloc> __gnu_pbds::detail::binomial_heap_base< Value_Type, Cmp_Fn, _Alloc >::base_type

private

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

typedef Cmp_Fn __gnu_pbds::detail::binomial_heap_base< Value_Type, Cmp_Fn, _Alloc >::cmp_fn

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

typedef base_type::const_iterator __gnu_pbds::detail::binomial_heap_base< Value_Type, Cmp_Fn, _Alloc >::const_iterator

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

typedef __rebind_v::const_pointer __gnu_pbds::detail::binomial_heap_base< Value_Type, Cmp_Fn, _Alloc >::const_pointer

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

typedef __rebind_v::const_reference __gnu_pbds::detail::binomial_heap_base< Value_Type, Cmp_Fn, _Alloc >::const_reference

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

typedef _Alloc::difference_type __gnu_pbds::detail::binomial_heap_base< Value_Type, Cmp_Fn, _Alloc >::difference_type

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

typedef base_type::iterator __gnu_pbds::detail::binomial_heap_base< Value_Type, Cmp_Fn, _Alloc >::iterator

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

typedef base_type::node __gnu_pbds::detail::binomial_heap_base< Value_Type, Cmp_Fn, _Alloc >::node

protected

typedef _Alloc::template rebind< left_child_next_sibling_heap_node_<Value_Type, _Alloc::size_type , _Alloc> >::other __gnu_pbds::detail::left_child_next_sibling_heap< Value_Type, Cmp_Fn, _Alloc::size_type , _Alloc >::node_allocator

protectedinherited

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

typedef base_type::node_const_pointer __gnu_pbds::detail::binomial_heap_base< Value_Type, Cmp_Fn, _Alloc >::node_const_pointer

protected

typedef _Alloc::size_type __gnu_pbds::detail::left_child_next_sibling_heap< Value_Type, Cmp_Fn, _Alloc::size_type , _Alloc >::node_metadata

protectedinherited

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

typedef base_type::node_pointer __gnu_pbds::detail::binomial_heap_base< Value_Type, Cmp_Fn, _Alloc >::node_pointer

protected

typedef std::pair< node_pointer, node_pointer> __gnu_pbds::detail::left_child_next_sibling_heap< Value_Type, Cmp_Fn, _Alloc::size_type , _Alloc >::node_pointer_pair

protectedinherited

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

typedef base_type::point_const_iterator __gnu_pbds::detail::binomial_heap_base< Value_Type, Cmp_Fn, _Alloc >::point_const_iterator

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

typedef base_type::point_iterator __gnu_pbds::detail::binomial_heap_base< Value_Type, Cmp_Fn, _Alloc >::point_iterator

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

typedef __rebind_v::pointer __gnu_pbds::detail::binomial_heap_base< Value_Type, Cmp_Fn, _Alloc >::pointer

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

typedef __rebind_v::reference __gnu_pbds::detail::binomial_heap_base< Value_Type, Cmp_Fn, _Alloc >::reference

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

typedef _Alloc::size_type __gnu_pbds::detail::binomial_heap_base< Value_Type, Cmp_Fn, _Alloc >::size_type

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

typedef Value_Type __gnu_pbds::detail::binomial_heap_base< Value_Type, Cmp_Fn, _Alloc >::value_type

Constructor & Destructor Documentation

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

__gnu_pbds::detail::binomial_heap_base< Value_Type, Cmp_Fn, _Alloc >::binomial_heap_base ( )

protected

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

__gnu_pbds::detail::binomial_heap_base< Value_Type, Cmp_Fn, _Alloc >::binomial_heap_base ( const Cmp_Fn & )

protected

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

__gnu_pbds::detail::binomial_heap_base< Value_Type, Cmp_Fn, _Alloc >::binomial_heap_base ( const binomial_heap_base< Value_Type, Cmp_Fn, _Alloc > & )

protected

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

__gnu_pbds::detail::binomial_heap_base< Value_Type, Cmp_Fn, _Alloc >::~binomial_heap_base ( )

protected

Member Function Documentation

void __gnu_pbds::detail::left_child_next_sibling_heap< Value_Type, Cmp_Fn, _Alloc::size_type , _Alloc >::actual_erase_node ( node_pointer )

inlineprotectedinherited

iterator __gnu_pbds::detail::left_child_next_sibling_heap< Value_Type, Cmp_Fn, _Alloc::size_type , _Alloc >::begin ( )

inlineinherited

const_iterator __gnu_pbds::detail::left_child_next_sibling_heap< Value_Type, Cmp_Fn, _Alloc::size_type , _Alloc >::begin ( ) const

inlineinherited

void __gnu_pbds::detail::left_child_next_sibling_heap< Value_Type, Cmp_Fn, _Alloc::size_type , _Alloc >::bubble_to_top ( node_pointer )

protectedinherited

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

void __gnu_pbds::detail::binomial_heap_base< Value_Type, Cmp_Fn, _Alloc >::clear ( )

inline

void __gnu_pbds::detail::left_child_next_sibling_heap< Value_Type, Cmp_Fn, _Alloc::size_type , _Alloc >::clear_imp ( node_pointer )

protectedinherited

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

template<typename It >

void __gnu_pbds::detail::binomial_heap_base< Value_Type, Cmp_Fn, _Alloc >::copy_from_range	(	It	,
		It
	)

protected

bool __gnu_pbds::detail::left_child_next_sibling_heap< Value_Type, Cmp_Fn, _Alloc::size_type , _Alloc >::empty ( ) const

inlineinherited

iterator __gnu_pbds::detail::left_child_next_sibling_heap< Value_Type, Cmp_Fn, _Alloc::size_type , _Alloc >::end ( )

inlineinherited

const_iterator __gnu_pbds::detail::left_child_next_sibling_heap< Value_Type, Cmp_Fn, _Alloc::size_type , _Alloc >::end ( ) const

inlineinherited

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

void __gnu_pbds::detail::binomial_heap_base< Value_Type, Cmp_Fn, _Alloc >::erase ( point_iterator )

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

template<typename Pred >

size_type __gnu_pbds::detail::binomial_heap_base< Value_Type, Cmp_Fn, _Alloc >::erase_if ( Pred )

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

void __gnu_pbds::detail::binomial_heap_base< Value_Type, Cmp_Fn, _Alloc >::find_max ( )

inlineprotected

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

node_pointer __gnu_pbds::detail::binomial_heap_base< Value_Type, Cmp_Fn, _Alloc >::fix ( node_pointer ) const

inlineprivate

Cmp_Fn& __gnu_pbds::detail::left_child_next_sibling_heap< Value_Type, Cmp_Fn, _Alloc::size_type , _Alloc >::get_cmp_fn ( )

inherited

const Cmp_Fn& __gnu_pbds::detail::left_child_next_sibling_heap< Value_Type, Cmp_Fn, _Alloc::size_type , _Alloc >::get_cmp_fn ( ) const

inherited

node_pointer __gnu_pbds::detail::left_child_next_sibling_heap< Value_Type, Cmp_Fn, _Alloc::size_type , _Alloc >::get_new_node_for_insert ( const_reference )

inlineprotectedinherited

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

void __gnu_pbds::detail::binomial_heap_base< Value_Type, Cmp_Fn, _Alloc >::insert_node ( node_pointer )

inlineprivate

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

void __gnu_pbds::detail::binomial_heap_base< Value_Type, Cmp_Fn, _Alloc >::join ( binomial_heap_base< Value_Type, Cmp_Fn, _Alloc > & )

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

node_pointer __gnu_pbds::detail::binomial_heap_base< Value_Type, Cmp_Fn, _Alloc >::join	(	node_pointer	,
		node_pointer
	)		const

inlineprivate

static void __gnu_pbds::detail::left_child_next_sibling_heap< Value_Type, Cmp_Fn, _Alloc::size_type , _Alloc >::make_child_of	(	node_pointer	,
		node_pointer
	)

inlinestaticprotectedinherited

size_type __gnu_pbds::detail::left_child_next_sibling_heap< Value_Type, Cmp_Fn, _Alloc::size_type , _Alloc >::max_size ( ) const

inlineinherited

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

void __gnu_pbds::detail::binomial_heap_base< Value_Type, Cmp_Fn, _Alloc >::modify	(	point_iterator	,
		const_reference
	)

static node_pointer __gnu_pbds::detail::left_child_next_sibling_heap< Value_Type, Cmp_Fn, _Alloc::size_type , _Alloc >::parent ( node_pointer )

inlinestaticprotectedinherited

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

void __gnu_pbds::detail::binomial_heap_base< Value_Type, Cmp_Fn, _Alloc >::pop ( )

node_pointer __gnu_pbds::detail::left_child_next_sibling_heap< Value_Type, Cmp_Fn, _Alloc::size_type , _Alloc >::prune ( Pred )

protectedinherited

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

point_iterator __gnu_pbds::detail::binomial_heap_base< Value_Type, Cmp_Fn, _Alloc >::push ( const_reference )

inline

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

void __gnu_pbds::detail::binomial_heap_base< Value_Type, Cmp_Fn, _Alloc >::remove_parentless_node ( node_pointer )

inlineprivate

size_type __gnu_pbds::detail::left_child_next_sibling_heap< Value_Type, Cmp_Fn, _Alloc::size_type , _Alloc >::size ( ) const

inlineinherited

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

template<typename Pred >

void __gnu_pbds::detail::binomial_heap_base< Value_Type, Cmp_Fn, _Alloc >::split	(	Pred	,
		binomial_heap_base< Value_Type, Cmp_Fn, _Alloc > &
	)

void __gnu_pbds::detail::left_child_next_sibling_heap< Value_Type, Cmp_Fn, _Alloc::size_type , _Alloc >::swap ( left_child_next_sibling_heap< Value_Type, Cmp_Fn, _Alloc::size_type , _Alloc > & )

inherited

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

void __gnu_pbds::detail::binomial_heap_base< Value_Type, Cmp_Fn, _Alloc >::swap ( binomial_heap_base< Value_Type, Cmp_Fn, _Alloc > & )

protected

void __gnu_pbds::detail::left_child_next_sibling_heap< Value_Type, Cmp_Fn, _Alloc::size_type , _Alloc >::swap_with_parent	(	node_pointer	,
		node_pointer
	)

inlineprotectedinherited

void __gnu_pbds::detail::left_child_next_sibling_heap< Value_Type, Cmp_Fn, _Alloc::size_type , _Alloc >::to_linked_list ( )

protectedinherited

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

const_reference __gnu_pbds::detail::binomial_heap_base< Value_Type, Cmp_Fn, _Alloc >::top ( ) const

inline

void __gnu_pbds::detail::left_child_next_sibling_heap< Value_Type, Cmp_Fn, _Alloc::size_type , _Alloc >::value_swap ( left_child_next_sibling_heap< Value_Type, Cmp_Fn, _Alloc::size_type, _Alloc > & )

protectedinherited

Member Data Documentation

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

node_pointer __gnu_pbds::detail::binomial_heap_base< Value_Type, Cmp_Fn, _Alloc >::m_p_max

protected

node_pointer __gnu_pbds::detail::left_child_next_sibling_heap< Value_Type, Cmp_Fn, _Alloc::size_type , _Alloc >::m_p_root

protectedinherited

size_type __gnu_pbds::detail::left_child_next_sibling_heap< Value_Type, Cmp_Fn, _Alloc::size_type , _Alloc >::m_size

protectedinherited

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

/usr/include/c++/5/ext/pb_ds/detail/binomial_heap_base_/binomial_heap_base_.hpp

Public Types

Public Member Functions

Protected Types

Protected Member Functions

Static Protected Member Functions

Protected Attributes

Private Types

Private Member Functions

Detailed Description

template<typename Value_Type, typename Cmp_Fn, typename _Alloc> class __gnu_pbds::detail::binomial_heap_base< Value_Type, Cmp_Fn, _Alloc >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<typename Value_Type, typename Cmp_Fn, typename _Alloc>
class __gnu_pbds::detail::binomial_heap_base< Value_Type, Cmp_Fn, _Alloc >