lti::priorityQueue< T, U > Class Template Reference

Simple priority queue data class. More...

#include <ltiPriorityQueue.h>

Inheritance diagram for lti::priorityQueue< T, U >:

[legend]

Collaboration diagram for lti::priorityQueue< T, U >:

[legend]

List of all members.

Public Types
typedef int	index_type
Public Member Functions
	priorityQueue (const T &inv)
	priorityQueue (const priorityQueue< T, U > &other)
virtual	~priorityQueue ()
index_type	insert (const T &key, const U &data)
void	erase (const index_type id)
void	update (const index_type id, const T &newKey)
void	update (const index_type id, const T &newKey, const U &data)
bool	valid (const index_type id) const
const T &	getKey (const index_type id) const
const U &	getData (const index_type id) const
bool	setData (const index_type id, const U &newData)
bool	empty () const
void	create (const std::vector< T > &key, const std::vector< U > &data)
void	create (const std::vector< std::pair< T, U > > &data)
const std::pair< T, U > &	front () const
void	getData (std::vector< std::pair< T, U > > &d) const
void	pop ()
void	clear ()
priorityQueue< T, U > &	copy (const priorityQueue< T, U > &other)
priorityQueue< T, U > &	operator= (const priorityQueue< T, U > &other)
virtual mathObject *	clone () const
const char *	getTypeName () const
virtual bool	write (ioHandler &handler, const bool complete=true) const
virtual bool	read (ioHandler &handler, const bool complete=true)
virtual bool	writeAll (ioHandler &handler, const bool complete=true) const
virtual bool	readAll (ioHandler &handler, const bool complete=true)
Protected Member Functions
bool	checkConsistency () const
Protected Attributes
T	invalid
std::vector< std::pair< T, U > >	data
int	numElements
int	stackPtr
int	numRemoved
std::vector< int >	idToIndex
std::vector< int >	indexToId

---

Detailed Description

template<class T, class U>
class lti::priorityQueue< T, U >

Simple priority queue data class.

The main difference with the std::priority_queue is that when you insert an element in the queue, you get an identification token (positive integer value), that will uniquely identify the element in the queue as long as the element exists. This is used to access the specific element independently of its position in the queue, allowing to change its key or data, changing its positions, but still keeping a valid reference to it.

The queue is always sorted in increasing order of the key. This means that the smallest key is always on the top of the queue.

Removing elements of the queue (pop() or erase()) are O(1) operations. Inserting an elements is a O(n) operation. Therefore, a specialized method to create the queue at once (create()) is provided, which will build the queue in O(n*log(n)), instead of the O(n^2) required inserting the elements one by one.

The type T is the type for the key. The queue is sorted with respect to this key.

The type U is the type of the data contained in each element.

---

Member Typedef Documentation

template<class T, class U>

typedef int lti::priorityQueue< T, U >::index_type

index type used to reference elements in the queue

---

Constructor & Destructor Documentation

template<class T, class U>

lti::priorityQueue< T, U >::priorityQueue

(

const T &

inv

)

constructor

Parameters:

inv

key used to indicate an invalid queue entry. Entries are for example invalid, if they were removed or "poped" from the queue.

template<class T, class U>

lti::priorityQueue< T, U >::priorityQueue

(

const priorityQueue< T, U > &

other

)

copy constructor

template<class T, class U>

virtual lti::priorityQueue< T, U >::~priorityQueue

(

)

[virtual]

destructor

---

Member Function Documentation

template<class T, class U>

bool lti::priorityQueue< T, U >::checkConsistency

(

)

const [protected]

debugging method to check the consistency of the priority queue

template<class T, class U>

void lti::priorityQueue< T, U >::clear

(

)

remove all elements from the priority queue

template<class T, class U>

virtual mathObject* lti::priorityQueue< T, U >::clone

(

)

const [virtual]

returns a copy of this object

Implements lti::mathObject.

template<class T, class U>

priorityQueue<T,U>& lti::priorityQueue< T, U >::copy

(

const priorityQueue< T, U > &

other

)

copy the priority queue

Parameters:

other

the priority queue to be copied.

Returns:

a reference to the current object

Reimplemented from lti::ioObject.

template<class T, class U>

void lti::priorityQueue< T, U >::create

(

const std::vector< std::pair< T, U > > &

data

)

create the queue using the given data.

The ids will be the original element index

template<class T, class U>

void lti::priorityQueue< T, U >::create	(	const std::vector< T > &	key,
		const std::vector< U > &	data
	)

create the queue using the given data.

The ids will be the original element index

template<class T, class U>

bool lti::priorityQueue< T, U >::empty

(

)

const

return true if the queue is empty

template<class T, class U>

void lti::priorityQueue< T, U >::erase

(

const index_type

id

)

remove the node with the given id

template<class T, class U>

const std::pair<T,U>& lti::priorityQueue< T, U >::front

(

)

const

return reference to element at the front

template<class T, class U>

void lti::priorityQueue< T, U >::getData

(

std::vector< std::pair< T, U > > &

d

)

const

copy all data in the priority queue into the given std::vector.

template<class T, class U>

const U& lti::priorityQueue< T, U >::getData

(

const index_type

id

)

const

Get the data for the given index id.

You must ensure first that the id is valid

template<class T, class U>

const T& lti::priorityQueue< T, U >::getKey

(

const index_type

id

)

const

Get the key for the given index id.

You must ensure first that the id is valid

template<class T, class U>

const char* lti::priorityQueue< T, U >::getTypeName

(

)

const [virtual]

returns name of this type

Reimplemented from lti::mathObject.

template<class T, class U>

index_type lti::priorityQueue< T, U >::insert	(	const T &	key,
		const U &	data
	)

insert a new node with the given key and data and return a pointer to the created node

Parameters:

	key	key of the element
	data	data of the element

template<class T, class U>

priorityQueue<T,U>& lti::priorityQueue< T, U >::operator=

(

const priorityQueue< T, U > &

other

)

copy the priority queue

Parameters:

other

the priority queue to be copied.

Returns:

a reference to the current object

Reimplemented from lti::ioObject.

template<class T, class U>

void lti::priorityQueue< T, U >::pop

(

)

remove the first element of the queue

template<class T, class U>

virtual bool lti::priorityQueue< T, U >::read	(	ioHandler &	handler,
		const bool	complete = true
	)			[virtual]

read the priority queue

Reimplemented from lti::mathObject.

template<class T, class U>

virtual bool lti::priorityQueue< T, U >::readAll	(	ioHandler &	handler,
		const bool	complete = true
	)			[virtual]

read the output of the writeAll method.

template<class T, class U>

bool lti::priorityQueue< T, U >::setData	(	const index_type	id,
		const U &	newData
	)

Change the data content of an element indexed by the given id.

You must first ensure that the id is valid.

Parameters:

	id	identification key for the element to be modified.
	newData	new data to be written in the element

Returns:

true if successful, false otherwise.

template<class T, class U>

void lti::priorityQueue< T, U >::update	(	const index_type	id,
		const T &	newKey,
		const U &	data
	)

update the key of an element without changing its id

template<class T, class U>

void lti::priorityQueue< T, U >::update	(	const index_type	id,
		const T &	newKey
	)

update the key of an element without changing its id

template<class T, class U>

bool lti::priorityQueue< T, U >::valid

(

const index_type

id

)

const

Check if the given id is valid.

template<class T, class U>

virtual bool lti::priorityQueue< T, U >::write	(	ioHandler &	handler,
		const bool	complete = true
	)			const [virtual]

write the priority queue

Reimplemented from lti::mathObject.

template<class T, class U>

virtual bool lti::priorityQueue< T, U >::writeAll	(	ioHandler &	handler,
		const bool	complete = true
	)			const [virtual]

write all attributes of the class

To serialize a priority queue, not all data is necessary, but for debugging purposes you might want to have all internals written. This method writes everything.

---

Member Data Documentation

template<class T, class U>

std::vector< std::pair<T,U> > lti::priorityQueue< T, U >::data [protected]

the real data.

Some of its elements can be removed, so the real number of elements is NOT data.size() but numElements. The data here is sorted. Because the indices of the elements will change each time an element is inserted/removed, an equivalences vector will keep track of the element movements.

template<class T, class U>

std::vector<int> lti::priorityQueue< T, U >::idToIndex [protected]

get the real element position in the data vector given the original index.

template<class T, class U>

std::vector<int> lti::priorityQueue< T, U >::indexToId [protected]

get the real element position in the data vector given the original index.

template<class T, class U>

T lti::priorityQueue< T, U >::invalid [protected]

code used to indicate a removed element'

template<class T, class U>

int lti::priorityQueue< T, U >::numElements [protected]

number of elements in data

template<class T, class U>

int lti::priorityQueue< T, U >::numRemoved [protected]

number of elements removed until now

template<class T, class U>

int lti::priorityQueue< T, U >::stackPtr [protected]

top of the stack.

This pointer MUST always point to the first valid element!

---

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

• ltiPriorityQueue.h