Thin heap. More...

#include <thin_heap_.hpp>

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

Collaboration diagram for __gnu_pbds::detail::thin_heap< 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_a::const_pointer	const_pointer

typedef __rebind_a::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_a::pointer	pointer

typedef __rebind_a::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 (thin_heap< 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, thin_heap< 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
	thin_heap ()

	thin_heap (const Cmp_Fn &)

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

	~thin_heap ()

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)

node_pointer	get_new_node_for_insert (const_reference)

node_pointer	prune (Pred)

void	swap (thin_heap< 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 node_pointer	parent (node_pointer)

Protected Attributes
node_pointer	m_p_root

size_type	m_size

Private Types
enum	{ max_rank = (sizeof(size_type) << 4) + 2 }

typedef _Alloc::template rebind< Value_Type >::other	__rebind_a

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

Private Member Functions
void	add_to_aux (node_pointer)

void	fix (node_pointer)

void	fix_child (node_pointer)

void	fix_root (node_pointer)

void	fix_sibling_general_marked (node_pointer)

void	fix_sibling_general_unmarked (node_pointer)

void	fix_sibling_rank_1_marked (node_pointer)

void	fix_sibling_rank_1_unmarked (node_pointer)

void	initialize ()

node_pointer	join (node_pointer, node_pointer) const

void	make_child_of (node_pointer, node_pointer)

void	make_from_aux ()

void	make_root_and_link (node_pointer)

size_type	rank_bound ()

void	remove_max_node ()

void	remove_node (node_pointer)

void	to_aux_except_max ()

void	update_max (node_pointer)

Static Private Member Functions
static void	make_root (node_pointer)

Private Attributes
node_pointer	m_a_aux [max_rank]

node_pointer	m_p_max

Detailed Description

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

Thin heap.

See Tarjan and Kaplan.

Member Typedef Documentation

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

typedef _Alloc::template rebind<Value_Type>::other __gnu_pbds::detail::thin_heap< Value_Type, Cmp_Fn, _Alloc >::__rebind_a

private

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

typedef _Alloc __gnu_pbds::detail::thin_heap< 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::thin_heap< Value_Type, Cmp_Fn, _Alloc >::base_type

private

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

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

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

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

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

typedef __rebind_a::const_pointer __gnu_pbds::detail::thin_heap< Value_Type, Cmp_Fn, _Alloc >::const_pointer

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

typedef __rebind_a::const_reference __gnu_pbds::detail::thin_heap< Value_Type, Cmp_Fn, _Alloc >::const_reference

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

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

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

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

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

typedef base_type::node __gnu_pbds::detail::thin_heap< 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::thin_heap< 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::thin_heap< 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::thin_heap< 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::thin_heap< Value_Type, Cmp_Fn, _Alloc >::point_iterator

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

typedef __rebind_a::pointer __gnu_pbds::detail::thin_heap< Value_Type, Cmp_Fn, _Alloc >::pointer

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

typedef __rebind_a::reference __gnu_pbds::detail::thin_heap< Value_Type, Cmp_Fn, _Alloc >::reference

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

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

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

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

Constructor & Destructor Documentation

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

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

protected

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

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

protected

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

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

protected

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

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

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

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

void __gnu_pbds::detail::thin_heap< Value_Type, Cmp_Fn, _Alloc >::add_to_aux ( node_pointer )

inlineprivate

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::thin_heap< 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::thin_heap< 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::thin_heap< 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::thin_heap< Value_Type, Cmp_Fn, _Alloc >::erase_if ( Pred )

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

void __gnu_pbds::detail::thin_heap< Value_Type, Cmp_Fn, _Alloc >::fix ( node_pointer )

inlineprivate

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

void __gnu_pbds::detail::thin_heap< Value_Type, Cmp_Fn, _Alloc >::fix_child ( node_pointer )

inlineprivate

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

void __gnu_pbds::detail::thin_heap< Value_Type, Cmp_Fn, _Alloc >::fix_root ( node_pointer )

inlineprivate

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

void __gnu_pbds::detail::thin_heap< Value_Type, Cmp_Fn, _Alloc >::fix_sibling_general_marked ( node_pointer )

inlineprivate

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

void __gnu_pbds::detail::thin_heap< Value_Type, Cmp_Fn, _Alloc >::fix_sibling_general_unmarked ( node_pointer )

inlineprivate

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

void __gnu_pbds::detail::thin_heap< Value_Type, Cmp_Fn, _Alloc >::fix_sibling_rank_1_marked ( node_pointer )

inlineprivate

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

void __gnu_pbds::detail::thin_heap< Value_Type, Cmp_Fn, _Alloc >::fix_sibling_rank_1_unmarked ( node_pointer )

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::thin_heap< Value_Type, Cmp_Fn, _Alloc >::initialize ( )

private

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

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

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

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

inlineprivate

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

void __gnu_pbds::detail::thin_heap< Value_Type, Cmp_Fn, _Alloc >::make_child_of	(	node_pointer	,
		node_pointer
	)

inlineprivate

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

void __gnu_pbds::detail::thin_heap< Value_Type, Cmp_Fn, _Alloc >::make_from_aux ( )

inlineprivate

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

static void __gnu_pbds::detail::thin_heap< Value_Type, Cmp_Fn, _Alloc >::make_root ( node_pointer )

inlinestaticprivate

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

void __gnu_pbds::detail::thin_heap< Value_Type, Cmp_Fn, _Alloc >::make_root_and_link ( node_pointer )

inlineprivate

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::thin_heap< 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::thin_heap< 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::thin_heap< Value_Type, Cmp_Fn, _Alloc >::push ( const_reference )

inline

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

size_type __gnu_pbds::detail::thin_heap< Value_Type, Cmp_Fn, _Alloc >::rank_bound ( )

inlineprivate

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

void __gnu_pbds::detail::thin_heap< Value_Type, Cmp_Fn, _Alloc >::remove_max_node ( )

inlineprivate

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

void __gnu_pbds::detail::thin_heap< Value_Type, Cmp_Fn, _Alloc >::remove_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::thin_heap< Value_Type, Cmp_Fn, _Alloc >::split	(	Pred	,
		thin_heap< 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::thin_heap< Value_Type, Cmp_Fn, _Alloc >::swap ( thin_heap< 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

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

void __gnu_pbds::detail::thin_heap< Value_Type, Cmp_Fn, _Alloc >::to_aux_except_max ( )

private

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::thin_heap< Value_Type, Cmp_Fn, _Alloc >::top ( ) const

inline

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

void __gnu_pbds::detail::thin_heap< Value_Type, Cmp_Fn, _Alloc >::update_max ( node_pointer )

inlineprivate

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::thin_heap< Value_Type, Cmp_Fn, _Alloc >::m_a_aux[max_rank]

private

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

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

private

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/thin_heap_/thin_heap_.hpp

Public Types

Public Member Functions

Protected Types

Protected Member Functions

Static Protected Member Functions

Protected Attributes

Private Types

Private Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

template<typename Value_Type, typename Cmp_Fn, typename _Alloc> class __gnu_pbds::detail::thin_heap< 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::thin_heap< Value_Type, Cmp_Fn, _Alloc >