Queue.h

Go to the documentation of this file.

#ifndef G3D_Queue_h
#define G3D_Queue_h

#include "G3D/platform.h"
#include "G3D/System.h"
#include "G3D/debug.h"

namespace G3D {

#define FIND_ENDS \
 int firstEnd = head + num;\
 int secondEnd = 0;\
 if (firstEnd > numAllocated) {\
 secondEnd = firstEnd - numAllocated;\
 firstEnd = numAllocated;\
 }


template <class T>
class Queue {
private:
 // 
 // |<---- num ---->|
 // [ | | | | | | | | | | | | | ]
 // ^ 
 // |
 // head
 //
 //

 T* data;

 int head;

 int num;
 
 int numAllocated;

 void _copy(const Queue& other) {
 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]);
 }
 }


 inline int index(int i) const {
 return (head + i + numAllocated) % numAllocated;
 }

 void repackAndRealloc(int newSize) {
 // 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;
 }

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

public:

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


 Queue(const Queue& other) : data(NULL) {
 _copy(other);
 }


 virtual ~Queue() {
 clear();
 }

 inline void pushFront(const T& e) {
 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;
 }

 inline void pushBack(const T& e) {
 reserveSpace();

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

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

 inline void enqueue(const T& e) {
 pushBack(e);
 }


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

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

 return result;
 }

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


 inline T dequeue() {
 return popFront();
 }

 void clear(bool freeStorage = true) {

 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;
 }
 }

 void fastClear() {
 clear(false);
 }

 Queue& operator=(const Queue& other) {
 clear();
 _copy(other);
 return *this;
 }

 inline int size() const {
 return num;
 }

 inline int length() const {
 return size();
 }

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

 inline const T& operator[](int n) const {
 debugAssert((n >= 0) && (n < num));
 return data[index(n)];
 }


 inline const T& last() const {
 return (*this)[size() - 1];
 }

 inline T& last() {
 return (*this)[size() - 1];
 }

 bool empty() const {
 return size() == 0;
 }

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

 return false;
 }

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

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

#undef FIND_ENDS

}; // namespace

#endif