Public Types | Public Member Functions | Private Types | Private Member Functions | Private Attributes

mln::util::soft_heap< T, R > Class Template Reference
[Utilities]

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

Definition at line 178 of file soft_heap.hh.

Member Typedef Documentation

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

Definition at line 174 of file object.hh.

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

Element associated type.

Definition at line 185 of file soft_heap.hh.

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

Definition at line 173 of file object.hh.

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

Definition at line 180 of file soft_heap.hh.

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.

Definition at line 619 of file soft_heap.hh.

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.

Definition at line 631 of file soft_heap.hh.

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.

Definition at line 771 of file soft_heap.hh.

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|

Definition at line 1009 of file soft_heap.hh.

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.

Definition at line 1052 of file soft_heap.hh.

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|

Definition at line 1025 of file soft_heap.hh.

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.

Definition at line 884 of file soft_heap.hh.

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.

Definition at line 812 of file soft_heap.hh.

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.

Definition at line 753 of file soft_heap.hh.

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.

Definition at line 744 of file soft_heap.hh.

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

Definition at line 821 of file soft_heap.hh.

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.

Definition at line 762 of file soft_heap.hh.

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.

Definition at line 675 of file soft_heap.hh.

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.

Definition at line 1086 of file soft_heap.hh.

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.

Definition at line 646 of file soft_heap.hh.

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.

Definition at line 658 of file soft_heap.hh.

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.

Definition at line 905 of file soft_heap.hh.

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

Definition at line 798 of file soft_heap.hh.

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]

Definition at line 278 of file soft_heap.hh.

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]

Definition at line 284 of file soft_heap.hh.

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.

Definition at line 282 of file soft_heap.hh.

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]

Definition at line 279 of file soft_heap.hh.

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().

Generated on Tue Oct 4 2011 15:30:45 for Milena (Olena) by  doxygen 1.7.1