creaImageIO::IndexedHeap< T, Comparator, Indexer > Class Template Reference

Indexed priority queues handled by binary trees. More...

#include <creaImageIOIndexedHeap.h>

Inheritance diagram for creaImageIO::IndexedHeap< T, Comparator, Indexer >:

[legend]

Collaboration diagram for creaImageIO::IndexedHeap< T, Comparator, Indexer >:

[legend]

List of all members.

Public Member Functions
	IndexedHeap ()
	Constructor.
	IndexedHeap (const Comparator &comp, const Indexer &ind)
	Constructor.
	~IndexedHeap ()
	Destructor.
void	set (const Comparator &comp)
	Sets the comparator.
void	set (const Indexer &ind)
	Sets the Index.
int	insert (T)
	inserts an element in the Heap and returns its position
T &	top ()
	return a reference on the first element of the Heap
const T &	top () const
	return a constant reference on the first element of the Heap
T	remove_top ()
	removes and returns the first element of the Heap
T	remove (int n)
	removes and returns the nth element
int	size () const
	returns the size of the Heap
void	clear ()
	empties the Heap
const std::vector< T > &	stack () const
	returns a constant on the stack of elements
T &	operator[] (int i)
	returns a reference to the ith element of the stack
const T &	operator[] (int i) const
	returns a constant reference to the ith element of the stack
int	index (T &t)
	returns the index (position) of t
int	father (int i) const
	returns the position of the father of i
int	rightson (int i) const
	returns the position of the right son of i
int	leftson (int i) const
	returns the position of the leftson of i
void	swap (int i, int j)
	swaps ith and jth elements
int	upsort (int)
int	downsort (int)
Protected Attributes
std::vector< T >	m_p
	binary tree handled by a vector
const Comparator *	m_c
	comparator pointer
const Indexer *	m_i
	Index pointer.

---

Detailed Description

template<class T, class Comparator, class Indexer>
class creaImageIO::IndexedHeap< T, Comparator, Indexer >

Indexed priority queues handled by binary trees.

Heap Allows :

• log(n) insertion
• constant time acces to the first element
• log(n) removal of the first element
• log(n) priority change of a random element Indexation Allows :
• constant time access to a random element (for priority change)

The Indexer is an unary_function<T,int&> whose operator()(T& t) returns a reference on an integer which is maintained by the IndexedHeap in order to provide at any time the position of the object t in the Heap (hence allowing constant time random access to an object).

Definition at line 49 of file creaImageIOIndexedHeap.h.

---

Constructor & Destructor Documentation

template<class T, class Comparator, class Indexer>

creaImageIO::IndexedHeap< T, Comparator, Indexer >::IndexedHeap

(

)

[inline]

Constructor.

Definition at line 56 of file creaImageIOIndexedHeap.h.

{}

template<class T, class CT, class IT>

creaImageIO::IndexedHeap< T, CT, IT >::IndexedHeap	(	const CT &	comp,
		const IT &	ind
	)			[inline]

Constructor.

Definition at line 146 of file creaImageIOIndexedHeap.h.

template<class T, class Comparator, class Indexer>

creaImageIO::IndexedHeap< T, Comparator, Indexer >::~IndexedHeap

(

)

[inline]

Destructor.

Definition at line 60 of file creaImageIOIndexedHeap.h.

{ }

---

Member Function Documentation

template<class T, class CT, class IT>

void creaImageIO::IndexedHeap< T, CT, IT >::set

(

const CT &

comp

)

[inline]

Sets the comparator.

Definition at line 154 of file creaImageIOIndexedHeap.h.

template<class T, class CT, class IT>

void creaImageIO::IndexedHeap< T, CT, IT >::set

(

const IT &

ind

)

[inline]

Sets the Index.

Definition at line 162 of file creaImageIOIndexedHeap.h.

template<class T, class CT, class IT>

int creaImageIO::IndexedHeap< T, CT, IT >::insert

(

T

t

)

[inline]

inserts an element in the Heap and returns its position

Definition at line 171 of file creaImageIOIndexedHeap.h.

template<class T, class CT, class IT>

T & creaImageIO::IndexedHeap< T, CT, IT >::top

(

)

[inline]

return a reference on the first element of the Heap

Definition at line 181 of file creaImageIOIndexedHeap.h.

template<class T, class CT, class IT>

const T & creaImageIO::IndexedHeap< T, CT, IT >::top

(

)

const [inline]

return a constant reference on the first element of the Heap

Definition at line 191 of file creaImageIOIndexedHeap.h.

template<class T, class CT, class IT>

T creaImageIO::IndexedHeap< T, CT, IT >::remove_top

(

)

[inline]

removes and returns the first element of the Heap

Definition at line 200 of file creaImageIOIndexedHeap.h.

template<class T, class CT, class IT>

T creaImageIO::IndexedHeap< T, CT, IT >::remove

(

int

n

)

[inline]

removes and returns the nth element

Definition at line 221 of file creaImageIOIndexedHeap.h.

template<class T, class Comparator, class Indexer>

int creaImageIO::IndexedHeap< T, Comparator, Indexer >::size

(

)

const [inline]

returns the size of the Heap

Definition at line 79 of file creaImageIOIndexedHeap.h.

{return m_p.size(); }

template<class T, class CT, class IT>

void creaImageIO::IndexedHeap< T, CT, IT >::clear

(

)

[inline]

empties the Heap

Definition at line 241 of file creaImageIOIndexedHeap.h.

template<class T, class Comparator, class Indexer>

const std::vector<T>& creaImageIO::IndexedHeap< T, Comparator, Indexer >::stack

(

)

const [inline]

returns a constant on the stack of elements

Definition at line 86 of file creaImageIOIndexedHeap.h.

{return m_p;}

template<class T, class Comparator, class Indexer>

T& creaImageIO::IndexedHeap< T, Comparator, Indexer >::operator[]

(

int

i

)

[inline]

returns a reference to the ith element of the stack

Definition at line 88 of file creaImageIOIndexedHeap.h.

{ return m_p[i];}

template<class T, class Comparator, class Indexer>

const T& creaImageIO::IndexedHeap< T, Comparator, Indexer >::operator[]

(

int

i

)

const [inline]

returns a constant reference to the ith element of the stack

Definition at line 90 of file creaImageIOIndexedHeap.h.

{ return m_p[i];}

template<class T, class Comparator, class Indexer>

int creaImageIO::IndexedHeap< T, Comparator, Indexer >::index

(

T &

t

)

[inline]

returns the index (position) of t

Definition at line 92 of file creaImageIOIndexedHeap.h.

{ return (*m_i)(t); }

template<class T, class CT, class IT>

int creaImageIO::IndexedHeap< T, CT, IT >::father

(

int

i

)

const [inline]

returns the position of the father of i

Definition at line 254 of file creaImageIOIndexedHeap.h.

template<class T, class CT, class IT>

int creaImageIO::IndexedHeap< T, CT, IT >::rightson

(

int

i

)

const [inline]

returns the position of the right son of i

Definition at line 262 of file creaImageIOIndexedHeap.h.

template<class T, class CT, class IT>

int creaImageIO::IndexedHeap< T, CT, IT >::leftson

(

int

i

)

const [inline]

returns the position of the leftson of i

Definition at line 270 of file creaImageIOIndexedHeap.h.

template<class T, class CT, class IT>

void creaImageIO::IndexedHeap< T, CT, IT >::swap	(	int	i,
		int	j
	)			[inline]

swaps ith and jth elements

Definition at line 278 of file creaImageIOIndexedHeap.h.

template<class T, class CT, class IT>

int creaImageIO::IndexedHeap< T, CT, IT >::upsort

(

int

i

)

[inline]

remonte un element dans le tas tant qu'il n'est pas a sa place. renvoie la position finale

Definition at line 293 of file creaImageIOIndexedHeap.h.

template<class T, class CT, class IT>

int creaImageIO::IndexedHeap< T, CT, IT >::downsort

(

int

i

)

[inline]

descend un element dans le tas tant qu'il n'est pas a sa place. renvoie la position finale

Definition at line 310 of file creaImageIOIndexedHeap.h.

---

Member Data Documentation

template<class T, class Comparator, class Indexer>

std::vector<T> creaImageIO::IndexedHeap< T, Comparator, Indexer >::m_p [protected]

binary tree handled by a vector

Definition at line 115 of file creaImageIOIndexedHeap.h.

Referenced by creaImageIO::IndexedHeap< creaImageIO::MultiThreadImageReader::ImageToLoad, creaImageIO::MultiThreadImageReader::ImageToLoadPtrPriorityComparator, creaImageIO::MultiThreadImageReader::ImageToLoadPtrIndexer >::operator[](), creaImageIO::IndexedHeap< creaImageIO::MultiThreadImageReader::ImageToLoad, creaImageIO::MultiThreadImageReader::ImageToLoadPtrPriorityComparator, creaImageIO::MultiThreadImageReader::ImageToLoadPtrIndexer >::size(), and creaImageIO::IndexedHeap< creaImageIO::MultiThreadImageReader::ImageToLoad, creaImageIO::MultiThreadImageReader::ImageToLoadPtrPriorityComparator, creaImageIO::MultiThreadImageReader::ImageToLoadPtrIndexer >::stack().

template<class T, class Comparator, class Indexer>

const Comparator* creaImageIO::IndexedHeap< T, Comparator, Indexer >::m_c [protected]

comparator pointer

Definition at line 117 of file creaImageIOIndexedHeap.h.

template<class T, class Comparator, class Indexer>

const Indexer* creaImageIO::IndexedHeap< T, Comparator, Indexer >::m_i [protected]

Index pointer.

Definition at line 119 of file creaImageIOIndexedHeap.h.

Referenced by creaImageIO::IndexedHeap< creaImageIO::MultiThreadImageReader::ImageToLoad, creaImageIO::MultiThreadImageReader::ImageToLoadPtrPriorityComparator, creaImageIO::MultiThreadImageReader::ImageToLoadPtrIndexer >::index().

---

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

• C:/Creatis/creaImageIO/src2/creaImageIOIndexedHeap.h

---