// Copyright 1999
// College of Computer Science
// Northeastern University Boston MA 02115

// This software may be used for educational purposes as long as this copyright
// notice is retained at the top of all files

// Should this software be modified, the words "Modified from Original" must be
// included as a comment below this notice

// All publication rights are retained.  This software or its documentation may
// not be published in any media either in whole or in part.

///////////////////////////////////////////////////////////////////////////////
//	QueueT.h
///////////////////////////////////////////////////////////////////////////////

#ifndef QUEUE_TEMPLATE_H_
#define QUEUE_TEMPLATE_H_

#include "AllocT.h"

template <class DataType>
class Queue {
	DataType*	data;				// pointer to the queue
	int			totalsize;			// total queue space
	int			validsize;			// valid queue space
	int			head;				// index of head of queue
	int			tail;				// index of tail of queue
	
	// tail is index of first cell beyond the valid queue entries
	// tail == (head + validsize) % totalsize


	// copy is the heart of the copy constructor and operator=
	// copy assumes data is invalid and does no extra delete[]

	// data will be copied so head = 0 and tail = validsize
	
	void Copy(const Queue& Original) {
		// set important fields to zero in case allocate fails
		data      = 0;
		totalsize = 0;
		validsize = 0;
		head      = 0;
		tail      = 0;
		
		// allocate
		Allocate(data, Original.totalsize);
		
		// set new parameters
		totalsize = Original.totalsize;
		validsize = Original.validsize;
		head      = 0;
		tail      = validsize;
		
		// copy data
		if ((Original.head + validsize) <= totalsize) {
			CopyData(data, Original.data, 0, Original.head, validsize);
		}
		else {
			int firstpart = totalsize - Original.head;

			CopyData(data, Original.data, 0, Original.head, firstpart);
			CopyData(data, Original.data, firstpart, 0, Original.tail);
		}
	};
	
public:
	// provide means for caller to recover DataType

	typedef DataType datatype;


	// routines to return internal information
	
	int TotalSize() const		{ return totalsize; };
	
	int ValidSize() const		{ return validsize; };


	// standard constructor
	
	Queue(int size = 1) {
		// set important fields to zero in case allocate fails
		data      = 0;
		totalsize = 0;
		validsize = 0;
		head      = 0;
		tail      = 0;
		
		if (size < 1) size = 1;			// force size positive
		
		Allocate(data, size);			// allocate the memory
		
		totalsize = size;				// set totalsize
	};


	// destructor
	
	~Queue() {
		delete [] data;
	};


	// copy constructor
	
	Queue(const Queue& Original) {
		Copy(Original);
	};


	// assignment: operator=
	
	Queue& operator= (const Queue& Original) {
		// if this object is the same as original just return
		if (this == &Original)
			return *this;
		
		// delete allocated memory in object
		delete [] data;
		
		// copy
		Copy(Original);
		
		return *this;
	};


	// Expand: Double available queue size
	// data will be copied so head = 0 and tail = validsize
	
	Queue& Expand() {
		// set new size
		int NewSize;
		
		if (totalsize > 0)
			NewSize = 2 * totalsize;
		else
			NewSize = 1;
		
		// save original
		DataType* original = data;
		
		// allocate and catch error if any
		try {
			Allocate(data, NewSize);
		}
		catch (string& s) {
			// print message
			cout << s << endl << endl;

			// on error restore original and return immediately
			data = original;
			return *this;
		}
		
		// copy original data
		
		if ((head + validsize) <= totalsize) {
			CopyData(data, original, 0, head, validsize);
		}
		else {
			int firstpart = totalsize - head;

			CopyData(data, original, 0, head, firstpart);
			CopyData(data, original, firstpart, 0, tail);
		}

		// delete original data
		delete [] original;
		
		// reset parameters
		totalsize = NewSize;
		head      = 0;
		tail      = validsize;

		return *this;
	};


	// Enqueue: Insert value at tail of queue. Expand if necessary.
	
	bool Enqueue(const DataType& value) {
		// check if more space is needed
		if (validsize == totalsize) Expand();
		
		// append the value if there is enough space now
		if (validsize < totalsize) {
			data[tail] = value;				// store value
			tail++;							// increment tail
			tail %= totalsize;				// wrap tail
			validsize++;					// increment size
			return true;
		}
		else
			return false;
	};


	// Dequeue: Return value at head of queue and remove from queue
	
	bool Dequeue(DataType& value) {
		if (validsize > 0) {
			value = data[head];				// deliver value
			head++;							// increment head
			head %= totalsize;				// wrap head;
			validsize--;					// decrement size
			return true;
		}
		else
			return false;
	};


	// Peek: Return value at head of queue without changes
	
	bool Peek(DataType& value) {
		if (validsize > 0) {
			value = data[head];				// deliver value
			return true;
		}
		else
			return false;
	};


	// IsEmpty: Check if queue is empty
	
	bool IsEmpty() {
		return (validsize == 0);
	};


	// IsFull: If queue is full then first attempt to expand. Then check
	// whether validsize < totalsize
	
	bool IsFull() {
		if (validsize == totalsize) Expand();
		
		return (validsize == totalsize);
	};
};

#endif // QUEUE_TEMPLATE_H_