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

Constructor.

Definition at line 22 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 >::clear ( )

empties the Heap

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

Referenced by creaImageIO::MultiThreadImageReader::UpdateUnloadPriority().

Here is the caller graph for this function:

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

{ return (*m_i)(t); }

template<class T, class CT , class IT >

int creaImageIO::IndexedHeap< T, CT, IT >::insert ( T t )

inserts an element in the Heap and returns its position

Definition at line 47 of file creaImageIOIndexedHeap.h.

Referenced by creaImageIO::MultiThreadImageReader::Request(), and creaImageIO::MultiThreadImageReader::SignalImageRead().

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

Here is the caller graph for this function:

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 146 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 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 CT , class IT >

T creaImageIO::IndexedHeap< T, CT, IT >::remove ( int n )

removes and returns the nth element

Definition at line 97 of file creaImageIOIndexedHeap.h.

template<class T , class CT , class IT >

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

removes and returns the first element of the Heap

Definition at line 76 of file creaImageIOIndexedHeap.h.

Referenced by creaImageIO::ThreadedImageReader::Entry(), and creaImageIO::MultiThreadImageReader::SignalImageRead().

                            {return 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];}

Here is the caller graph for this function:

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

template<class T , class CT , class IT>

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

Sets the Index.

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

Referenced by creaImageIO::MultiThreadImageReader::MultiThreadImageReader().

Here is the caller graph for this function:

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.

Referenced by creaImageIO::ThreadedImageReader::Entry(), creaImageIO::MultiThreadImageReader::GetMaximalPriorityWithoutLocking(), and creaImageIO::MultiThreadImageReader::SignalImageRead().

{return m_p.size(); }

Here is the caller graph for this function:

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 CT , class IT >

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

swaps ith and jth elements

Definition at line 154 of file creaImageIOIndexedHeap.h.

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

                            {return m_p.size(); }

template<class T , class CT , class IT >

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

return a reference on the first element of the Heap

Definition at line 57 of file creaImageIOIndexedHeap.h.

Referenced by creaImageIO::MultiThreadImageReader::GetMaximalPriorityWithoutLocking().

{ }

Here is the caller graph for this function:

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

Referenced by creaImageIO::MultiThreadImageReader::Request(), and creaImageIO::MultiThreadImageReader::UpdateUnloadPriority().

Here is the caller graph for this function:

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 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< ImageToLoadPtr, ImageToLoadPtrPriorityComparator, 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 115 of file creaImageIOIndexedHeap.h.

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

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

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

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

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 >