// queue_adt_generic.cpp

//
// This implements a generic version of a simple queue.
// 

#include "cmpt_error.h"
#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

template <typename T>
class Queue_base {
public:
	// C++ base classes should always have a virtual destructor (so that
	// inheriting classes can, if they need to, override it and implement
	// their own destructor)
	virtual ~Queue_base() { }

	// Pre-condition:
	//    none
	// Post-condition:
	//    returns true if this queue is empty, and false otherwise
	// Constraints:
	//    O(1) worst-case running time
	virtual bool is_empty() const = 0;

	// Pre-condition:
	//    none
	// Post-condition:
	//    returns true if this queue is full, and false otherwise
	// Constraints:
	//    O(1) worst-case running time
	virtual bool is_full() const = 0;

	// Pre-condition:
	//    this queue is not full
	// Post-condition:
	//    puts x on the end of the queue (other elements are unchanged)
	// Constraints:
	//    O(1) worst-case running time	
	virtual void enqueue(const T& x) = 0;

	// Pre-condition:
	//    this queue is not empty
	// Post-condition:
	//    removes and returns the front element of this queue
	// Constraints:
	//    O(1) worst-case running time
	// Note:
	//    dequeue returns a copy of the element that has been de-queued
	virtual T dequeue() = 0;

	// Pre-condition:
	//    this queue is not empty
	// Post-condition:
	//    returns a copy of the front element of this queue (but does not 
	//    modify the queue)
	// Constraints:
	//    O(1) worst-case running time
	// Note:
	//    front returns a copy of the element at the front of the queue.
	//    Thus, this does *not* allow the front element of the queue to
	//    be modified. If you do want to allow the front to modified, then
	//    this method should return a reference, i.e. its return type
	//    should be T&.
	virtual T front() const = 0;
}; // class Queue_base

//
// The following queue is implemented as a circular vector (of a fixed
// capacity).
//
template <typename T>
class Vector_queue : public Queue_base<T> {
private:
	vector<T> v;
	int sz; // number of elements in this queue
	int f;  // index of the front element
	int r;  // index of the rear element
public:
	// creates a new empty queue with the given capacity 
	Vector_queue(int capacity) : v(capacity), sz(0), f(0), r(0) { }

	int capacity() const {
		return v.size();
	}

	int size() const {
		return sz;
	}

	// Pre-condition:
	//    none
	// Post-condition:
	//    returns true if this queue is empty, and false otherwise
	// Constraints:
	//    O(1) worst-case running time
	bool is_empty() const {
		return size() == 0;
	}

	// Pre-condition:
	//    none
	// Post-condition:
	//    returns true if this queue is full, and false otherwise
	// Constraints:
	//    O(1) worst-case running time
	virtual bool is_full() const {
		return size() == capacity();
	}

	// Pre-condition:
	//    queue is not full
	// Post-condition:
	//    puts x on the end of the queue (other elements are unchanged)
	// Constraints:
	//    O(1) worst-case running time	
	void enqueue(const T& x) {
		if (is_full()) cmpt::error("enqueue: queue is full");
		v[r] = x;
		r = (r + 1) % capacity();
		sz++;
	}

	// Pre-condition:
	//    this queue is not empty
	// Post-condition:
	//    removes and returns the front element of this queue
	// Constraints:
	//    O(1) worst-case running time
	T dequeue() {
		if (is_empty()) cmpt::error("dequeue: queue is empty");
		T result = v[f];
		f = (f + 1) % capacity();
		sz--;
		return result;
	}

	// Pre-condition:
	//    this queue is not empty
	// Post-condition:
	//    returns a copy of the front element of this queue (but does not modify 
	//    the queue)
	// Constraints:
	//    O(1) worst-case running time
	T front() const {
		if (is_empty()) cmpt::error("front: queue is empty");
		return v[f];
	}

}; // class Vector_queue


//
// Circular list class from the textbook (p.129-133)
//
template<class T>
class Circular_list {
	struct Node {
		T val;
		Node* next;
	};

	Node* cursor;  // is nullptr, or points to a node in the list

public:
	// creates an empty list
	Circular_list() : cursor(nullptr) { }

	~Circular_list() {
		while (!is_empty()) remove();
	}

	bool is_empty() const {
		return cursor == nullptr;
	}

	T& back() const {  // reference to element at cursor (allows modification)
		if (is_empty()) cmpt::error("back: list is empty");
		return cursor->val;
	}

	T& front() const {  // reference to element after cursor (allows modification)
		if (is_empty()) cmpt::error("front: list is empty");
		return cursor->next->val;
	}

	void advance() {
		if (is_empty()) cmpt::error("advance: list is empty");
		cursor = cursor->next;
	}

	void add(const T& x) {
		Node* v = new Node{x, nullptr};
		if (is_empty()) {
			v->next = v;
			cursor = v;
		} else {
			v->next = cursor->next;
			cursor->next = v;
		}
	}

	void remove() {
		if (is_empty()) cmpt::error("remove: list is empty");
		Node* old = cursor->next;
		if (old == cursor) {
			cursor = nullptr;
		} else {
			cursor->next = old->next;
		}
		delete old;
	}
}; // class Circular_list


//
// The following queue is implemented as a circular linked list.
//
template <typename T>
class List_queue : public Queue_base<T> {
private:
	struct Node {
		T val;
		Node* next;
	};

	Circular_list<T> lst;
	int sz;  // number of elements in this queue
public:
	// creates a new empty queue
	List_queue() : lst(), sz(0) { }

	// Pre-condition:
	//    none
	// Post-condition:
	//    returns the number of elements in this queue
	// Constraints:
	//    O(1) worst-case running time
	int size() const {
		return sz;
	}

	// Pre-condition:
	//    none
	// Post-condition:
	//    returns true if this queue is empty, and false otherwise
	// Constraints:
	//    O(1) worst-case running time
	bool is_empty() const {
		return size() == 0;
	}

	// Pre-condition:
	//    none
	// Post-condition:
	//    returns true if this queue is full, and false otherwise
	// Constraints:
	//    O(1) worst-case running time
	virtual bool is_full() const {
		return false;
	}

	// Pre-condition:
	//    queue is not full
	// Post-condition:
	//    puts x on the end of the queue (other elements are unchanged)
	// Constraints:
	//    O(1) worst-case running time	
	void enqueue(const T& x) {
		if (is_full()) cmpt::error("enqueue: queue is full");
		lst.add(x);
		lst.advance();
		sz++;
	}

	// Pre-condition:
	//    this queue is not empty
	// Post-condition:
	//    removes and returns the front element of this queue
	// Constraints:
	//    O(1) worst-case running time
	T dequeue() {
		if (is_empty()) cmpt::error("dequeue: queue is empty");
		T result = front();
		lst.remove();
		sz--;
		return result;
	}

	// Pre-condition:
	//    this queue is not empty
	// Post-condition:
	//    returns a copy of the front element of this queue (but does not 
	//    modify the queue)
	// Constraints:
	//    O(1) worst-case running time
	T front() const {
		if (is_empty()) cmpt::error("front: queue is empty");
		return lst.front();
	}

}; // class List_queue

template<typename T>
void test_queue(Queue_base<T>* q) {
	assert(q->is_empty());
	assert(!q->is_full());
	q->enqueue(5);
	assert(!q->is_empty());
	assert(q->front() == 5);
	assert(q->dequeue() == 5);
	assert(q->is_empty());
	for(int i = 0; i < 10; i++) {
		q->enqueue(i+1);
		assert(!q->is_empty());
	}
	for(int i = 0; i < 10; i++) {
		assert(q->dequeue() == i+1);
	}
	assert(q->is_empty());
}

void test_Vector_queue() {
	Vector_queue<int> q(100);
	test_queue(&q);
	cout << "all Vector_queue tests passed\n";
}

void test_List_queue() {
	List_queue<int> q;
	test_queue(&q);
	cout << "all List_queue tests passed\n";
}

int main() {
    test_Vector_queue();
    test_List_queue();
}