Milena (Olena): mln::util::soft_heap< T, R > Class Template Reference

Soft heap. More...

#include <soft_heap.hh>

Inheritance diagram for mln::util::soft_heap< T, R >:

Inheritance graph

List of all members.

Public Types
typedef Object< void >	category
typedef T	element
	Element associated type.
typedef soft_heap< T, R >	exact_t
Public Member Functions
void	clear ()
	Clear the heap.
head< T, R > *	head_hook_ () const
	Internal use only.
bool	is_empty () const
	Return true if there is at least one element.
bool	is_valid () const
	Return true if there is at least one element.
int	nelements () const
	Return the number of element in the heap.
T	pop_front ()
	Returns the element with the lowest priority and remove it from the heap.
void	push (const T &element)
	Add a new element `element`.
void	push (soft_heap< T, R > &sh)
	Merge `sh` with this heap.
void	soft_clear_ ()
	Reset the heap to an empty heap.
	soft_heap (unsigned r=20)
	Default constructor.
	~soft_heap ()
	Destructor.
Private Types
typedef util::tracked_ptr < ilcell< T > >	ilcell_t
Private Member Functions
template<typename L >
void	clear_list (L begin, L end=0)
	Delete all element in a C-list from `begin` to `end`.
void	debug_head_list () const
	Print which node is part of which head.
template<typename L >
void	deep_clear_list (L *n)
	Delete all element in a 2 dimensional C-list.
void	fix_minlist (head< T, R > *h)
	Update suffix_min pointer according to the new values inserted in the item lists.
void	meld (node< T, R > *q)
	Merge a node `q` to this heap.
void	println_ () const
	Display the heap, preserving the hierarchy of the elements.
node< T, R > *	sift (node< T, R > *v)
	After the deletion of an element, this function move/update item lists in the proper nodes.
Private Attributes
head< T, R > *	header_
int	nelements_
unsigned	r_
	Corruption threshold. Must be set once through the constructor.
head< T, R > *	tail_

Detailed Description

template<typename T, typename R>
class mln::util::soft_heap< T, R >

Soft heap.

T key, the data to store in the heap. For instance a point 2d. R rank, for instance int_u8

Member Typedef Documentation

typedef Object<void> mln::Object< soft_heap< T, R > >::category [inherited]

template<typename T, typename R>

typedef T mln::util::soft_heap< T, R >::element

Element associated type.

typedef soft_heap< T, R > mln::Object< soft_heap< T, R > >::exact_t [inherited]

template<typename T, typename R>

typedef util::tracked_ptr< ilcell<T> > mln::util::soft_heap< T, R >::ilcell_t [private]

Constructor & Destructor Documentation

template<typename T , typename R >

mln::util::soft_heap< T, R >::soft_heap ( unsigned r = 20 ) [inline]

Default constructor.

A corruption threshold r can be specified. This threshold means that if nodes have a rank higher than this threshold they can be "corrupted" and therefore their rank can be reduced.

References mln::util::soft_heap< T, R >::header_, mln::util::soft_heap< T, R >::nelements_, mln::util::soft_heap< T, R >::r_, and mln::util::soft_heap< T, R >::tail_.

template<typename T , typename R >

mln::util::soft_heap< T, R >::~soft_heap ( ) [inline]

Destructor.

References mln::util::soft_heap< T, R >::clear_list(), mln::util::soft_heap< T, R >::deep_clear_list(), mln::util::soft_heap< T, R >::header_, mln::util::head< T, R >::next(), mln::util::head< T, R >::queue(), and mln::util::soft_heap< T, R >::tail_.

Member Function Documentation

template<typename T , typename R >

void mln::util::soft_heap< T, R >::clear ( ) [inline]

Clear the heap.

References mln::util::soft_heap< T, R >::clear_list(), mln::util::soft_heap< T, R >::deep_clear_list(), mln::util::soft_heap< T, R >::header_, mln::util::soft_heap< T, R >::nelements_, mln::util::head< T, R >::next(), mln::util::head< T, R >::queue(), mln::util::head< T, R >::set_next(), mln::util::head< T, R >::set_prev(), and mln::util::soft_heap< T, R >::tail_.

template<typename T , typename R >

template<typename L >

void mln::util::soft_heap< T, R >::clear_list	(	L *	begin,
		L *	end = `0`
	)			`[inline, private]`

Delete all element in a C-list from begin to end.

end is not deleted. The type L must provide 'L *next()'.

next

|x| -> |x| -> |x|

Referenced by mln::util::soft_heap< T, R >::clear(), mln::util::soft_heap< T, R >::soft_clear_(), and mln::util::soft_heap< T, R >::~soft_heap().

template<typename T , typename R >

void mln::util::soft_heap< T, R >::debug_head_list ( ) const [inline, private]

Print which node is part of which head.

References mln::util::node< T, R >::child(), mln::util::soft_heap< T, R >::header_, mln::util::head< T, R >::next(), mln::util::node< T, R >::next(), and mln::util::head< T, R >::queue().

template<typename T , typename R >

template<typename L >

void mln::util::soft_heap< T, R >::deep_clear_list ( L * n ) [inline, private]

Delete all element in a 2 dimensional C-list.

The type L must provide 'L *next()' and 'L *child()'.

next

|x| -> |x| -> |x| | child v |x| -> |x|

Referenced by mln::util::soft_heap< T, R >::clear(), mln::util::soft_heap< T, R >::pop_front(), mln::util::soft_heap< T, R >::sift(), and mln::util::soft_heap< T, R >::~soft_heap().

template<typename T , typename R >

void mln::util::soft_heap< T, R >::fix_minlist ( head< T, R > * h ) [inline, private]

Update suffix_min pointer according to the new values inserted in the item lists.

References mln::util::soft_heap< T, R >::header_, mln::util::head< T, R >::next(), mln::util::ord_strict(), mln::util::head< T, R >::prev(), mln::util::head< T, R >::queue(), mln::util::head< T, R >::set_suffix_min(), and mln::util::soft_heap< T, R >::tail_.

Referenced by mln::util::soft_heap< T, R >::meld(), and mln::util::soft_heap< T, R >::pop_front().

template<typename T , typename R >

head< T, R > * mln::util::soft_heap< T, R >::head_hook_ ( ) const [inline]

Internal use only.

Return a pointer to the first header struct of this heap.

References mln::util::soft_heap< T, R >::header_.

Referenced by mln::util::soft_heap< T, R >::push().

template<typename T , typename R >

bool mln::util::soft_heap< T, R >::is_empty ( ) const [inline]

Return true if there is at least one element.

References mln::util::soft_heap< T, R >::nelements_.

template<typename T , typename R >

bool mln::util::soft_heap< T, R >::is_valid ( ) const [inline]

Return true if there is at least one element.

References mln::util::soft_heap< T, R >::header_, and mln::util::soft_heap< T, R >::tail_.

Referenced by mln::util::soft_heap< T, R >::pop_front().

template<typename T , typename R >

void mln::util::soft_heap< T, R >::meld ( node< T, R > * q ) [inline, private]

Merge a node q to this heap.

See also:: push

References mln::util::node< T, R >::ckey(), mln::util::soft_heap< T, R >::fix_minlist(), mln::util::soft_heap< T, R >::header_, mln::util::node< T, R >::il(), mln::util::node< T, R >::il_tail(), mln::util::node< T, R >::next(), mln::util::head< T, R >::next(), mln::util::ord_strict(), mln::util::head< T, R >::prev(), mln::util::head< T, R >::queue(), mln::util::head< T, R >::rank(), mln::util::node< T, R >::rank(), mln::util::head< T, R >::set_next(), mln::util::head< T, R >::set_prev(), mln::util::head< T, R >::set_queue(), and mln::util::head< T, R >::set_rank().

Referenced by mln::util::soft_heap< T, R >::pop_front(), and mln::util::soft_heap< T, R >::push().

template<typename T , typename R >

int mln::util::soft_heap< T, R >::nelements ( ) const [inline]

Return the number of element in the heap.

References mln::util::soft_heap< T, R >::nelements_.

Referenced by mln::util::soft_heap< T, R >::push().

template<typename T , typename R >

T mln::util::soft_heap< T, R >::pop_front ( ) [inline]

Returns the element with the lowest priority and remove it from the heap.

References mln::util::soft_heap< T, R >::deep_clear_list(), mln::util::soft_heap< T, R >::fix_minlist(), mln::util::soft_heap< T, R >::header_, mln::util::soft_heap< T, R >::is_valid(), mln::util::soft_heap< T, R >::meld(), mln::util::soft_heap< T, R >::nelements_, mln::util::head< T, R >::next(), mln::util::node< T, R >::next(), mln::util::head< T, R >::prev(), mln::util::head< T, R >::queue(), mln::util::head< T, R >::set_queue(), and mln::util::soft_heap< T, R >::sift().

template<typename T , typename R >

void mln::util::soft_heap< T, R >::println_ ( ) const [inline, private]

Display the heap, preserving the hierarchy of the elements.

References mln::util::node< T, R >::child(), mln::util::soft_heap< T, R >::header_, mln::util::node< T, R >::il(), mln::util::head< T, R >::next(), mln::util::node< T, R >::next(), and mln::util::head< T, R >::queue().

template<typename T , typename R >

void mln::util::soft_heap< T, R >::push ( const T & element ) [inline]

Add a new element element.

References mln::util::soft_heap< T, R >::meld(), and mln::util::soft_heap< T, R >::nelements_.

template<typename T , typename R >

void mln::util::soft_heap< T, R >::push ( soft_heap< T, R > & sh ) [inline]

Merge sh with this heap.

Be ware that after this call, sh will be empty. This heap will hold the elements which were part of sh.

References mln::util::soft_heap< T, R >::head_hook_(), mln::util::soft_heap< T, R >::meld(), mln::util::soft_heap< T, R >::nelements(), mln::util::soft_heap< T, R >::nelements_, mln::util::head< T, R >::next(), mln::util::head< T, R >::queue(), and mln::util::soft_heap< T, R >::soft_clear_().

template<typename T , typename R >

node< T, R > * mln::util::soft_heap< T, R >::sift ( node< T, R > * v ) [inline, private]

After the deletion of an element, this function move/update item lists in the proper nodes.

References mln::util::node< T, R >::child(), mln::util::soft_heap< T, R >::deep_clear_list(), mln::util::node< T, R >::il(), mln::util::node< T, R >::il_tail(), mln::util::node< T, R >::next(), mln::util::ord_strict(), mln::util::soft_heap< T, R >::r_, mln::util::node< T, R >::rank(), mln::util::node< T, R >::set_child(), mln::util::node< T, R >::set_ckey(), mln::util::node< T, R >::set_il(), mln::util::node< T, R >::set_il_tail(), and mln::util::node< T, R >::set_next().

Referenced by mln::util::soft_heap< T, R >::pop_front().

template<typename T , typename R >

void mln::util::soft_heap< T, R >::soft_clear_ ( ) [inline]

Reset the heap to an empty heap.

Do *NOT* delete element which may have been inserted.

See also:: push

References mln::util::soft_heap< T, R >::clear_list(), mln::util::soft_heap< T, R >::header_, mln::util::soft_heap< T, R >::nelements_, and mln::util::soft_heap< T, R >::tail_.

Referenced by mln::util::soft_heap< T, R >::push().

Member Data Documentation

template<typename T, typename R>

head<T,R>* mln::util::soft_heap< T, R >::header_ [private]

Referenced by mln::util::soft_heap< T, R >::clear(), mln::util::soft_heap< T, R >::debug_head_list(), mln::util::soft_heap< T, R >::fix_minlist(), mln::util::soft_heap< T, R >::head_hook_(), mln::util::soft_heap< T, R >::is_valid(), mln::util::soft_heap< T, R >::meld(), mln::util::soft_heap< T, R >::pop_front(), mln::util::soft_heap< T, R >::println_(), mln::util::soft_heap< T, R >::soft_clear_(), mln::util::soft_heap< T, R >::soft_heap(), and mln::util::soft_heap< T, R >::~soft_heap().

template<typename T, typename R>

int mln::util::soft_heap< T, R >::nelements_ [private]

Referenced by mln::util::soft_heap< T, R >::clear(), mln::util::soft_heap< T, R >::is_empty(), mln::util::soft_heap< T, R >::nelements(), mln::util::soft_heap< T, R >::pop_front(), mln::util::soft_heap< T, R >::push(), mln::util::soft_heap< T, R >::soft_clear_(), and mln::util::soft_heap< T, R >::soft_heap().

template<typename T, typename R>

unsigned mln::util::soft_heap< T, R >::r_ [private]

Corruption threshold. Must be set once through the constructor.

Referenced by mln::util::soft_heap< T, R >::sift(), and mln::util::soft_heap< T, R >::soft_heap().

template<typename T, typename R>

head<T,R>* mln::util::soft_heap< T, R >::tail_ [private]

Referenced by mln::util::soft_heap< T, R >::clear(), mln::util::soft_heap< T, R >::fix_minlist(), mln::util::soft_heap< T, R >::is_valid(), mln::util::soft_heap< T, R >::soft_clear_(), mln::util::soft_heap< T, R >::soft_heap(), and mln::util::soft_heap< T, R >::~soft_heap().