/*
 * squeue.cpp
 *
 *  Created on: 07.11.2012
 *      Author: trifon
 */

#include "queue.h"

const int MAX = 100;

template<typename T = int>
class SQueue : public Queue<T>
{
private:
	T* q;
	int front, back;
	int size;
private:
	bool full() const
	{
		return (back + 1) % size == front;
	}

	// O(n)
	void copy(SQueue const& queue)
	{
		size = queue.size;
		q = new T[size];
		front = queue.front;
		back = queue.back;
		for(int i = front; i != back; i++, i%= size)
			q[i] = queue.q[i];
	}
public:

	SQueue(int _size = MAX) : size(_size)
	{
		q = new T[size];
		front = back = 0;
	}

	// O(n)
	SQueue(SQueue const& queue) {
		copy(queue);
	}

	// O(n)
	SQueue& operator=(SQueue const& queue) {
		if (this != &queue)
		{
			delete[] q;
			copy(queue);
		}
		return *this;
	}

	~SQueue() {
		delete[] q;
	}

	bool empty() const {
		return front == back;
	}

	bool push(T const& x) {
		if (full())
			return false;
		q[back++] = x;
		back %= size;
		return true;
	}

	bool pop(T& x) {
		if (empty())
			return false;
		x = q[front++];
		front %= size;
		return true;
	}

	bool head(T& x) {
		if (empty())
			return false;
		x = q[front];
		return true;
	}
};