casa::Queue< T > Class Template Reference [Containers_module]

A First-In-First-Out (FIFO) data structure. More...

#include <Queue.h>

List of all members.

Public Member Functions
	Queue ()
	Create a Queue with no elements.
	Queue (const Queue< T > &other)
	Create a queue which is a copy of other.
	~Queue ()
Queue< T > &	operator= (const Queue< T > &other)
	Create a queue which is a copy of other.
void	enqueue (const T &value)
	Place an element in the queue.
void	operator() (const T &value)
	Short-hand for enqueue();.
void	dequeue (T &value)
	Remove an element from the head of the queue and decrease nelements() by one.
T	operator() ()
	Short-hand for dequeue.
void	clear ()
	Delete all the elements from the queue, and free up any resources.
void	compress ()
	Leave this queue logically unchanged, but remove unused storage.
uInt	nelements () const
	How many elements are in the queue?
Private Attributes
Int	first_p
Int	next_p
Block< T >	data_p

---

Detailed Description

template<class T>
class casa::Queue< T >

A First-In-First-Out (FIFO) data structure.

Review Status

Reviewed By:

Gareth Hunt

Date Reviewed:

94Jan06

Test programs:

tQueue

Synopsis

A Queue as implemented here is a simple container which can grow with time, and which returns its elements (only) in the order they are inserted. That is, the fundamental operations are to insert an element in the queue (at the "back") and retrieve an element (from the "front").

        Queue<Int> queue;
        Int x;
        queue(1);                          // enqueue
        queue.enqueue(2);                  // enqueue
        queue(3);                          // enqueue
        queue(4);                          // enqueue
        queue.dequeue(x);                  // dequeue
        cout << x << endl;
        ..\.
        while (queue.nelements() > 0) 
            cout << queue() << " ";        // dequeue
        cout << endl;

Presently the implementation is rather simple. It stores the elements in a Block<T> which resizes (exponentially to avoid quadratic behaviour) when necessary. New elements are added to the end of the block, old elements are pulled off the front of the Block. The positions at the beginning are only reclaimed when the queue is empty or the compress() member is called. This implementation is reasonably time efficient, but not necessarily space efficient. A more sophisticated implementation may be necessary eventually.

To be used in a Queue, a class must have a default constructor, assignment operator, and copy constructor.

Motivation

This class was written for an application which thought it needed to queue up some Glish events while it processed other Glish events. In fact that application (Clean) was simplified so that it doesn't presently operate that way.

To Do

• It is conceivable that an iterator might be useful for this class.
• If this class is ever heavily used, a more space efficient implementation may be necessary.

Definition at line 92 of file Queue.h.

---

Constructor & Destructor Documentation

template<class T>

casa::Queue< T >::Queue

(

)

Create a Queue with no elements.

template<class T>

casa::Queue< T >::Queue

(

const Queue< T > &

other

)

Create a queue which is a copy of other.

Compresses unused heap storage.

template<class T>

casa::Queue< T >::~Queue

(

)

---

Member Function Documentation

template<class T>

void casa::Queue< T >::clear

(

)

Delete all the elements from the queue, and free up any resources.

template<class T>

void casa::Queue< T >::compress

(

)

Leave this queue logically unchanged, but remove unused storage.

With the present Block<T> based implementation, removes the unused entries at the beginning of the block.

template<class T>

void casa::Queue< T >::dequeue

(

T &

value

)

Remove an element from the head of the queue and decrease nelements() by one.

If called when nelements() is zero, an exception is thrown.

template<class T>

void casa::Queue< T >::enqueue

(

const T &

value

)

Place an element in the queue.

After calling this, nelements() is increaed by one.

template<class T>

uInt casa::Queue< T >::nelements

(

)

const [inline]

How many elements are in the queue?

Definition at line 132 of file Queue.h.

References casa::Queue< T >::first_p, and casa::Queue< T >::next_p.

template<class T>

T casa::Queue< T >::operator()

(

)

Short-hand for dequeue.

template<class T>

void casa::Queue< T >::operator()

(

const T &

value

)

Short-hand for enqueue();.

template<class T>

Queue<T>& casa::Queue< T >::operator=

(

const Queue< T > &

other

)

Create a queue which is a copy of other.

Compresses unused heap storage.

---

Member Data Documentation

template<class T>

Block<T> casa::Queue< T >::data_p [private]

Definition at line 136 of file Queue.h.

template<class T>

Int casa::Queue< T >::first_p [private]

Definition at line 134 of file Queue.h.

Referenced by casa::Queue< T >::nelements().

template<class T>

Int casa::Queue< T >::next_p [private]

Definition at line 135 of file Queue.h.

Referenced by casa::Queue< T >::nelements().

---

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

• casa/Containers/Queue.h