OpenTissue::containers::Heap< feature_type_, real_type_ > Class Template Reference

#include <containers_heap.h>

List of all members.

Classes
class	heap_element
Public Types
typedef real_type_	real_type
typedef feature_type_	feature_type
typedef heap_type::iterator	heap_iterator
Public Member Functions
	Heap ()
	~Heap ()
void	clear ()
std::size_t	size () const
heap_iterator	push (feature_type const &f)
bool	erase (feature_type const &f)
heap_iterator	get_heap_iterator (feature_type const &f)
void	heapify (heap_iterator i)
void	heapify ()
heap_iterator	top ()
heap_iterator	begin ()
heap_iterator	end ()
Protected Types
typedef std::list< heap_element >	heap_type
typedef std::map< feature_type, heap_iterator >	lut_type
typedef lut_type::iterator	lut_iterator
typedef lut_type::const_iterator	const_lut_iterator
Protected Attributes
heap_type	m_heap
	The heap storing the heap-elements.
lut_type	m_lut
	A heap iterator lookup table. This is used to quickly find the heap element corresponding to a given feature.

---

Detailed Description

template<typename feature_type_, typename real_type_>
class OpenTissue::containers::Heap< feature_type_, real_type_ >

Heap Utility Class.

NOTE: This heap keeps priorities in descending order. That means that the element with the largest priority is on top of the heap!!!

Often a priority heap is needed with the following properties:

1) Each priority value is coupled to some feature/element from another data structure. As an example one may store edges of a polygonal mesh in a priority queue. The priorites indicate the benefit of performing some operation on the edges.

Thus when extracting the top element one gets the ``edge'' which will result in the largest gain when performing some operation on it.

2) After having performed an operation on a coupled feature, one often need to recompute the priority value, the operation may even affects ``neighboring'' features, which also need to get their priority values updated.

Thus we are often faced with the problem of changing only a small number of heap values, destroying the heap-property.

Since the number of heap elements is low it would be more attractive to have a heapify functionality that exploits this fact.

This class was implemented to make it easy to deal with the priority-feature coupling and to be able to heapify single elements rather than the entire heap.

---

Member Typedef Documentation

template<typename feature_type_, typename real_type_>

typedef lut_type::const_iterator OpenTissue::containers::Heap< feature_type_, real_type_ >::const_lut_iterator [protected]

template<typename feature_type_, typename real_type_>

typedef feature_type_ OpenTissue::containers::Heap< feature_type_, real_type_ >::feature_type

template<typename feature_type_, typename real_type_>

typedef heap_type::iterator OpenTissue::containers::Heap< feature_type_, real_type_ >::heap_iterator

template<typename feature_type_, typename real_type_>

typedef std::list<heap_element> OpenTissue::containers::Heap< feature_type_, real_type_ >::heap_type [protected]

template<typename feature_type_, typename real_type_>

typedef lut_type::iterator OpenTissue::containers::Heap< feature_type_, real_type_ >::lut_iterator [protected]

template<typename feature_type_, typename real_type_>

typedef std::map<feature_type,heap_iterator> OpenTissue::containers::Heap< feature_type_, real_type_ >::lut_type [protected]

template<typename feature_type_, typename real_type_>

typedef real_type_ OpenTissue::containers::Heap< feature_type_, real_type_ >::real_type

---

Constructor & Destructor Documentation

template<typename feature_type_, typename real_type_>

OpenTissue::containers::Heap< feature_type_, real_type_ >::Heap

(

)

[inline]

template<typename feature_type_, typename real_type_>

OpenTissue::containers::Heap< feature_type_, real_type_ >::~Heap

(

)

[inline]

---

Member Function Documentation

template<typename feature_type_, typename real_type_>

heap_iterator OpenTissue::containers::Heap< feature_type_, real_type_ >::begin

(

)

[inline]

Get First Heap Element.

Returns:

An iterator to the first heap element.

template<typename feature_type_, typename real_type_>

void OpenTissue::containers::Heap< feature_type_, real_type_ >::clear

(

)

[inline]

template<typename feature_type_, typename real_type_>

heap_iterator OpenTissue::containers::Heap< feature_type_, real_type_ >::end

(

)

[inline]

Get End Heap Element.

Returns:

An iterator to the position one past the last heap element.

template<typename feature_type_, typename real_type_>

bool OpenTissue::containers::Heap< feature_type_, real_type_ >::erase

(

feature_type const &

f

)

[inline]

Erase Feature.

Parameters:

f

The feature indicating the corresponding heap element (if it exist) that be erased.

Returns:

If the heap element was succesfully deleted the return value is true otherwise it is false.

template<typename feature_type_, typename real_type_>

heap_iterator OpenTissue::containers::Heap< feature_type_, real_type_ >::get_heap_iterator

(

feature_type const &

f

)

[inline]

Get Heap Iterator.

Parameters:

f

The feature.

Returns:

An iterator pointing to the heap element that corresponds to the feature or the position one past the end of the heap.

template<typename feature_type_, typename real_type_>

void OpenTissue::containers::Heap< feature_type_, real_type_ >::heapify

(

)

[inline]

Heapify All of the Heap. This method has time-complexity o( n lg n), where n is the number of heap elements.

template<typename feature_type_, typename real_type_>

void OpenTissue::containers::Heap< feature_type_, real_type_ >::heapify

(

heap_iterator

i

)

[inline]

Heapify Single Element. This function assumes that only the specifed heap element has the wrong position in the heap. The method works by scanning first to the left and then to the right, to look for the correct position of the specified heap element. Worst case time-complexity is thus O(n), where n is the number of heap elements.

Notice that as an side-effect all iterators may change after having invoked the method.

template<typename feature_type_, typename real_type_>

heap_iterator OpenTissue::containers::Heap< feature_type_, real_type_ >::push

(

feature_type const &

f

)

[inline]

Push a new feature onto the heap.

Note that the new elements is not ``heapified''.

Parameters:

f

The feature that should be inserted.

Returns:

A heap iterator to the newly created heap element. This can for instance be used to heapify the new element.

template<typename feature_type_, typename real_type_>

std::size_t OpenTissue::containers::Heap< feature_type_, real_type_ >::size

(

)

const [inline]

Size.

Returns:

The number of heap elements in the heap.

template<typename feature_type_, typename real_type_>

heap_iterator OpenTissue::containers::Heap< feature_type_, real_type_ >::top

(

)

[inline]

Get Top Element.

Returns:

An iterator to the heap element with largest priority value.

---

Member Data Documentation

template<typename feature_type_, typename real_type_>

heap_type OpenTissue::containers::Heap< feature_type_, real_type_ >::m_heap [protected]

The heap storing the heap-elements.

template<typename feature_type_, typename real_type_>

lut_type OpenTissue::containers::Heap< feature_type_, real_type_ >::m_lut [protected]

A heap iterator lookup table. This is used to quickly find the heap element corresponding to a given feature.

---

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

• /home/hauberg/Dokumenter/Capture/humim-tracker-0.1/src/OpenTissue/OpenTissue/core/containers/containers_heap.h