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

#include <creaImageIOIndexedHeap.h>

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

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

Public Member Functions
	IndexedHeap ()
	Constructor. More...

	IndexedHeap (const Comparator &comp, const Indexer &ind)
	Constructor. More...

	~IndexedHeap ()
	Destructor. More...

void	set (const Comparator &comp)
	Sets the comparator. More...

void	set (const Indexer &ind)
	Sets the Index. More...

int	insert (T)
	inserts an element in the Heap and returns its position More...

T &	top ()
	return a reference on the first element of the Heap More...

const T &	top () const
	return a constant reference on the first element of the Heap More...

T	remove_top ()
	removes and returns the first element of the Heap More...

T	remove (int n)
	removes and returns the nth element More...

int	size () const
	returns the size of the Heap More...

void	clear ()
	empties the Heap More...

const std::vector< T > &	stack () const
	returns a constant on the stack of elements More...

T &	operator[] (int i)
	returns a reference to the ith element of the stack More...

const T &	operator[] (int i) const
	returns a constant reference to the ith element of the stack More...

int	index (T &t)
	returns the index (position) of t More...

int	father (int i) const
	returns the position of the father of i More...

int	rightson (int i) const
	returns the position of the right son of i More...

int	leftson (int i) const
	returns the position of the leftson of i More...

void	swap (int i, int j)
	swaps ith and jth elements More...

int	upsort (int)

int	downsort (int)

Protected Attributes
std::vector< T >	m_p
	binary tree handled by a vector More...

const Comparator *	m_c
	comparator pointer More...

const Indexer *	m_i
	Index pointer. More...

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 48 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 84 of file creaImageIOIndexedHeap.h.

84 {}

template<class T , class CT, class IT>

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

Constructor.

Definition at line 50 of file creaImageIOIndexedHeap.h.

78 {

template<class T, class Comparator, class Indexer>

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

inline

Destructor.

Definition at line 88 of file creaImageIOIndexedHeap.h.

88 { }

Member Function Documentation

template<class T , class CT , class IT >

void IndexedHeap::clear ( )

empties the Heap

Definition at line 145 of file creaImageIOIndexedHeap.h.

template<class T , class CT , class IT >

int IndexedHeap::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 214 of file creaImageIOIndexedHeap.h.

template<class T , class CT , class IT >

int IndexedHeap::father ( int i ) const

inline

returns the position of the father of i

Definition at line 158 of file creaImageIOIndexedHeap.h.

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 120 of file creaImageIOIndexedHeap.h.

120 { return (*m_i)(t); }

template<class T, class CT , class IT >

int IndexedHeap::insert ( T t )

inserts an element in the Heap and returns its position

Definition at line 75 of file creaImageIOIndexedHeap.h.

   {
     //                  friend class SlicedIndexedHeap<T,Comparator,Index>;
   public :

template<class T , class CT , class IT >

int IndexedHeap::leftson ( int i ) const

inline

returns the position of the leftson of i

Definition at line 174 of file creaImageIOIndexedHeap.h.

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 116 of file creaImageIOIndexedHeap.h.

116 { 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 118 of file creaImageIOIndexedHeap.h.

118 { return m_p[i];}

template<class T , class CT , class IT >

T IndexedHeap::remove ( int n )

removes and returns the nth element

Definition at line 125 of file creaImageIOIndexedHeap.h.

141 :

template<class T , class CT , class IT >

T IndexedHeap::remove_top ( )

removes and returns the first element of the Heap

Definition at line 104 of file creaImageIOIndexedHeap.h.

                             {return (int)m_p.size(); }
         void clear();
     //======================================================================
         
     //======================================================================
     const std::vector<T> & stack() const {return m_p;}
     T& operator [] (int i) { return m_p[i];}
     const T& operator [] (int i) const { return m_p[i];}

template<class T , class CT , class IT >

int IndexedHeap::rightson ( int i ) const

inline

returns the position of the right son of i

Definition at line 166 of file creaImageIOIndexedHeap.h.

template<class T , class CT, class IT >

void creaImageIO::IndexedHeap< T, CT, IT >::set ( const CT & comp )

Sets the comparator.

Definition at line 58 of file creaImageIOIndexedHeap.h.

78 {

template<class T , class CT , class IT>

void creaImageIO::IndexedHeap< T, CT, IT >::set ( const IT & ind )

Sets the Index.

Definition at line 66 of file creaImageIOIndexedHeap.h.

78 {

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 107 of file creaImageIOIndexedHeap.h.

107 {return (int)m_p.size(); }

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 114 of file creaImageIOIndexedHeap.h.

114 {return m_p;}

template<class T , class CT , class IT >

void IndexedHeap::swap	(	int	i,
		int	j
	)

inline

swaps ith and jth elements

Definition at line 182 of file creaImageIOIndexedHeap.h.

template<class T , class CT , class IT >

T & IndexedHeap::top ( )

return a reference on the first element of the Heap

Definition at line 85 of file creaImageIOIndexedHeap.h.

88 { }

template<class T , class CT , class IT >

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

return a constant reference on the first element of the Heap

Definition at line 95 of file creaImageIOIndexedHeap.h.

107 {return (int)m_p.size(); }

template<class T , class CT , class IT >

int IndexedHeap::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 197 of file creaImageIOIndexedHeap.h.

Member Data Documentation

template<class T, class Comparator, class Indexer>

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

protected

comparator pointer

Definition at line 145 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 147 of file creaImageIOIndexedHeap.h.

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

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 143 of file creaImageIOIndexedHeap.h.

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

/home/davila/Creatis/All/creatools_source/creaImageIO/src/creaImageIOIndexedHeap.h
/home/davila/Creatis/All/creatools_source/creaImageIO/src/creaImageIOIndexedHeap.txx

Public Member Functions

Protected Attributes

Detailed Description

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

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

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