__gnu_pbds::detail::thin_heap< Value_Type, Cmp_Fn, _Alloc > Class Template Reference

#include <ext/pb_ds/detail/thin_heap_/thin_heap_.hpp>

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

Public Types
typedef Value_Type	value_type
typedef Cmp_Fn	cmp_fn
typedef _Alloc	allocator_type
typedef _Alloc::size_type	size_type
typedef _Alloc::difference_type	difference_type
typedef __rebind_a::pointer	pointer
typedef __rebind_a::const_pointer	const_pointer
typedef __rebind_a::reference	reference
typedef __rebind_a::const_reference	const_reference
typedef base_type::point_iterator	point_iterator
typedef base_type::point_const_iterator	point_const_iterator
typedef base_type::iterator	iterator
typedef base_type::const_iterator	const_iterator

Public Member Functions
point_iterator	push (const_reference)
void	modify (point_iterator, const_reference)
const_reference	top () const
void	pop ()
void	erase (point_iterator)
void	clear ()
template<typename Pred >
size_type	erase_if (Pred)
template<typename Pred >
void	split (Pred, PB_DS_CLASS_C_DEC &)
void	join (PB_DS_CLASS_C_DEC &)

Protected Types
typedef base_type::node	node
typedef base_type::node_pointer	node_pointer
typedef base_type::node_const_pointer	node_const_pointer

Protected Member Functions
	thin_heap ()
	thin_heap (const Cmp_Fn &)
	thin_heap (const PB_DS_CLASS_C_DEC &)
void	swap (PB_DS_CLASS_C_DEC &)
	~thin_heap ()
template<typename It >
void	copy_from_range (It, It)

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 PB_DS_BASE_T_P	base_type

Private Member Functions
void	initialize ()
void	update_max (node_pointer)
void	fix (node_pointer)
void	fix_root (node_pointer)
void	fix_sibling_rank_1_unmarked (node_pointer)
void	fix_sibling_rank_1_marked (node_pointer)
void	fix_sibling_general_unmarked (node_pointer)
void	fix_sibling_general_marked (node_pointer)
void	fix_child (node_pointer)
void	make_root_and_link (node_pointer)
void	remove_max_node ()
void	to_aux_except_max ()
void	add_to_aux (node_pointer)
void	make_from_aux ()
size_type	rank_bound ()
void	make_child_of (node_pointer, node_pointer)
void	remove_node (node_pointer)
node_pointer	join (node_pointer, node_pointer) const

Static Private Member Functions
static void	make_root (node_pointer)

Private Attributes
node_pointer	m_p_max
node_pointer	m_a_aux [max_rank]

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 PB_DS_BASE_T_P __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

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

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

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

Member Enumeration Documentation

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

anonymous enum

private

Enumerator
max_rank

    {
      max_rank = (sizeof(size_type) << 4) + 2
    };

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 PB_DS_CLASS_C_DEC &  )

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

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

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

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

inline

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

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

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

(

PB_DS_CLASS_C_DEC &

)

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

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
	)

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

void __gnu_pbds::detail::thin_heap< Value_Type, Cmp_Fn, _Alloc >::pop

(

)

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

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	,
		PB_DS_CLASS_C_DEC &
	)

template<typename Value_Type , typename Cmp_Fn , typename _Alloc >

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

protected

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

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

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

---

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

• GCC4/inc/ext/pb_ds/detail/thin_heap_/thin_heap_.hpp