G3D::Queue< T > Class Template Reference

#include <Queue.h>

Public Member Functions
	Queue ()
	Queue (const Queue &other)
virtual	~Queue ()
void	pushFront (const T &e)
void	pushBack (const T &e)
void	enqueue (const T &e)
T	popBack ()
T	popFront ()
T	dequeue ()
void	clear (bool freeStorage=true)
void	fastClear ()
Queue &	operator= (const Queue &other)
int	size () const
int	length () const
T &	operator[] (int n)
const T &	operator[] (int n) const
const T &	last () const
T &	last ()
bool	empty () const
bool	contains (const T &e) const
void	deleteAll ()

Private Member Functions
void	_copy (const Queue &other)
int	index (int i) const
void	repackAndRealloc (int newSize)
void	reserveSpace ()

Private Attributes
T *	data
int	head
int	num
int	numAllocated

Detailed Description

template<class T>
class G3D::Queue< T >

Dynamic queue that uses a circular buffer for performance.

Faster than std::deque for objects with constructors.

Constructor & Destructor Documentation

template<class T >

G3D::Queue< T >::Queue ( )

inline

 : 
 data(NULL),
 head(0),
 num(0),
 numAllocated(0) {
 }

template<class T >

G3D::Queue< T >::Queue ( const Queue< T > &  other )

inline

Copy constructor

 : data(NULL) {
 _copy(other);
 }

Here is the call graph for this function:

template<class T >

virtual G3D::Queue< T >::~Queue ( )

inlinevirtual

Destructor does not delete() the objects if T is a pointer type (e.g. T = int*) instead, it deletes the pointers themselves and leaves the objects. Call deleteAll if you want to dealocate the objects referenced.

 {
 clear();
 }

Here is the call graph for this function:

Member Function Documentation

template<class T >

void G3D::Queue< T >::_copy ( const Queue< T > &  other )

inlineprivate

If a clear was needed, assumes it already occured

 {
 debugAssert(data == NULL);
 data = (T*)System::malloc(sizeof(T) * other.numAllocated);
 debugAssert(data);
 head = other.head;
 num = other.num;
 numAllocated = other.numAllocated;

 FIND_ENDS;

 for (int i = head; i < firstEnd; ++i) {
 new (data + i)T(other.data[i]);
 }

 for (int i = 0; i < secondEnd; ++i) {
 new (data + i)T(other.data[i]);
 }
 }

Here is the call graph for this function:

Here is the caller graph for this function:

template<class T >

void G3D::Queue< T >::clear ( bool  freeStorage = true )

inline

Removes all elements (invoking their destructors).

Parameters

freeStorage

If false, the underlying array is not deallocated (allowing fast push in the future), however, the size of the Queue is reported as zero.

 {

 FIND_ENDS;
 
 // Invoke the destructors on the elements
 int i;
 for (i = head; i < firstEnd; ++i) {
 (data + i)->~T();
 }

 for (i = 0; i < secondEnd; ++i) {
 (data + i)->~T();
 }
 
 num = 0;
 head = 0;
 if (freeStorage) {
 numAllocated = 0;
 System::free(data);
 data = NULL;
 }
 }

Here is the call graph for this function:

Here is the caller graph for this function:

template<class T >

bool G3D::Queue< T >::contains ( const T &  e ) const

inline

Returns true if the given element is in the queue.

 {
 for (int i = 0; i < size(); ++i) {
 if ((*this)[i] == e) {
 return true;
 }
 }

 return false;
 }

Here is the call graph for this function:

template<class T >

void G3D::Queue< T >::deleteAll ( )

inline

Calls delete on all objects[0...size-1] and sets the queue size to zero.

 {
 FIND_ENDS;
 
 int i;
 for (i = 0; i < secondEnd; ++i) {
 delete data[i];
 }

 for (i = head; i < firstEnd; ++i) {
 delete data[i];
 }
 clear();
 }

Here is the call graph for this function:

template<class T >

T G3D::Queue< T >::dequeue ( )

inline

popFront

 {
 return popFront();
 }

Here is the call graph for this function:

template<class T >

bool G3D::Queue< T >::empty ( ) const

inline

 {
 return size() == 0;
 }

Here is the call graph for this function:

template<class T >

void G3D::Queue< T >::enqueue ( const T &  e )

inline

pushBack

 {
 pushBack(e);
 }

Here is the call graph for this function:

template<class T >

void G3D::Queue< T >::fastClear ( )

inline

Clear without freeing the underlying array.

 {
 clear(false);
 }

Here is the call graph for this function:

template<class T >

int G3D::Queue< T >::index ( int  i ) const

inlineprivate

Computes a data array index from a queue position. The queue position may be negative.

 {
 return (head + i + numAllocated) % numAllocated;
 }

Here is the caller graph for this function:

template<class T >

const T& G3D::Queue< T >::last ( ) const

inline

Returns the back element

 {
 return (*this)[size() - 1];
 }

Here is the call graph for this function:

template<class T >

T& G3D::Queue< T >::last ( )

inline

 {
 return (*this)[size() - 1];
 }

Here is the call graph for this function:

template<class T >

int G3D::Queue< T >::length ( ) const

inline

Number of elements in the queue.

 {
 return size();
 }

Here is the call graph for this function:

template<class T >

Queue& G3D::Queue< T >::operator= ( const Queue< T > &  other )

inline

Assignment operator.

 {
 clear();
 _copy(other);
 return *this;
 }

Here is the call graph for this function:

template<class T >

T& G3D::Queue< T >::operator[] ( int  n )

inline

Performs bounds checks in debug mode

 {
 debugAssert((n >= 0) && (n < num));
 return data[index(n)];
 }

Here is the call graph for this function:

template<class T >

const T& G3D::Queue< T >::operator[] ( int  n ) const

inline

Performs bounds checks in debug mode

 {
 debugAssert((n >= 0) && (n < num));
 return data[index(n)];
 }

Here is the call graph for this function:

template<class T >

T G3D::Queue< T >::popBack ( )

inline

Remove the last element from the queue. The queue will never shrink in size. (A typical queue only uses popFront).

 {
 int tail = index(num - 1);
 T result(data[tail]);

 // Call the destructor
 (data + tail)->~T();
 --num;

 return result;
 }

Here is the call graph for this function:

template<class T >

T G3D::Queue< T >::popFront ( )

inline

Remove the next element from the head of the queue. The queue will never shrink in size.

 {
 T result(data[head]);
 // Call the destructor
 (data + head)->~T();
 head = (head + 1) % numAllocated;
 --num;
 return result;
 }

Here is the caller graph for this function:

template<class T >

void G3D::Queue< T >::pushBack ( const T &  e )

inline

Insert a new element at the end of the queue.

 {
 reserveSpace();

 // Get the index of 1+tail
 int i = index(num);

 // Initialize that element
 new (data + i)T(e);
 ++num;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

template<class T >

void G3D::Queue< T >::pushFront ( const T &  e )

inline

Insert a new element into the front of the queue (a traditional queue only uses pushBack).

 {
 reserveSpace();

 // Get the index of head-1
 int i = index(-1);

 // Call the constructor on the newly exposed element.
 new (data + i)T(e);

 // Reassign the head to point to this index
 head = i;
 ++num;
 }

Here is the call graph for this function:

template<class T >

void G3D::Queue< T >::repackAndRealloc ( int  newSize )

inlineprivate

Allocates newSize elements and repacks the array.

 {
 // TODO: shrink queue
 T* old = data;
 data = (T*)System::malloc(newSize * sizeof(T));
 debugAssert(data != NULL);

 FIND_ENDS;

 int j = 0;
 for (int i = head; i < firstEnd; ++i, ++j) {
 new (data + j)T(old[i]);
 (old + i)->~T();
 }

 for (int i = 0; i < secondEnd; ++i, ++j) {
 new (data + j)T(old[i]);
 (old + i)->~T();
 }

 head = 0;
 System::free(old);
 numAllocated = newSize;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

template<class T >

void G3D::Queue< T >::reserveSpace ( )

inlineprivate

Ensure that there is at least one element between the tail and head, wrapping around in the circular buffer.

 {
 if (num == numAllocated) {
 repackAndRealloc(numAllocated * 3 + 20);
 }
 }

Here is the call graph for this function:

Here is the caller graph for this function:

template<class T >

int G3D::Queue< T >::size ( ) const

inline

Number of elements in the queue.

 {
 return num;
 }

Here is the caller graph for this function:

Member Data Documentation

template<class T >

T* G3D::Queue< T >::data

private

Only num elements are initialized.

template<class T >

int G3D::Queue< T >::head

private

Index of the next element to be dequeue-d in data.

template<class T >

int G3D::Queue< T >::num

private

Number of elements (including head) that are visible and initialized.

template<class T >

int G3D::Queue< T >::numAllocated

private

Size of data array in elements.

---

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

• dep/g3dlite/include/G3D/Queue.h