// stack_adt_generic.cpp

//
// This implements a generic version of the code in stack_adt.cpp. The stacks
// can store values of almost any type T, and the reverse function can reverse
// a vector of values of type T.
// 

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

using namespace std;

template <typename T>
class Stack_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 ~Stack_base() { }

	// Pre-condition:
	//    none
	// Post-condition:
	//    returns true if this stack 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 stack is full, and false
	//    otherwise
	// Constraints:
	//    O(1) worst-case running time
	virtual bool is_full() const = 0;

	// Pre-condition:
	//    none
	// Post-condition:
	//    puts x on top of the stack (elements already on stack are 
	//    unchanged)
	// Constraints:
	//    O(1) worst-case running time	
	virtual void push(const T& x) = 0;

	// Pre-condition:
	//    this stack is not empty
	// Post-condition:
	//    removes and returns the top element of this stack
	// Constraints:
	//    O(1) worst-case running time
	virtual T pop() = 0;

	// Pre-condition:
	//    this stack is not empty
	// Post-condition:
	//    returns the top element of this stack (but does not modify the 
	//    stack)
	// Constraints:
	//    O(1) worst-case running time
	virtual T top() const = 0;

	// Pre-condition:
	//    none
	// Post-condition:
	//    prints the contents of this stack to cout
	// Constraints:
	//    O(n) worst-case running time
	// Note:
	//    uses O(n) extra memory; pops all stack elements, and then
	//    puts them back
	void print() {
		// dump the stack into a vector
		vector<T> v;
		while (!is_empty()) v.push_back(pop());
		
		// put the elements all back into the stack (in proper order!)
		for(int i = v.size()-1; i >= 0; i--) push(v[i]);

		// print the vector (in proper order!)
		for(int i = v.size()-1; i >= 0; i--) cout << v[i] << " ";
		cout << "\n";
	}
}; // class Stack_base

template <typename T>
class Vector_stack : public Stack_base<T> {
private:
	vector<T> v;
public:
	Vector_stack() : v() { }

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

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

	// Pre-condition:
	//    this stack is not full
	// Post-condition:
	//    puts x on top of the stack (elements already on stack are 
	//    unchanged)
	// Constraints:
	//    O(1) worst-case running time	
	void push(const T& x) {
	 	if (is_full()) cmpt::error("push: stack is full");
		v.push_back(x);
	}

	// Pre-condition:
	//    this stack is not empty
	// Post-condition:
	//    removes and returns the top element of this stack
	// Constraints:
	//    O(1) worst-case running time
	T pop() {
		if (is_empty()) cmpt::error("can't pop an empty stack");
		T result = v.back();
		v.pop_back();
		return result;
	}

	// Pre-condition:
	//    this stack is not empty
	// Post-condition:
	//    returns the top element of this stack (but does not modify the 
	//    stack)
	// Constraints:
	//    O(1) worst-case running time
	T top() const {
		if (is_empty()) cmpt::error("can't pop an empty stack");
		return v.back();		
	}
}; // class Vector_stack

template <typename T>
class List_stack : public Stack_base<T> {
private:
	struct Node {
		T val;
		Node* next;
	}; 

	Node* head;
public:
	List_stack() : head(nullptr) { }

	~List_stack() {
		while (!is_empty()) pop();
	}

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

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

	// Pre-condition:
	//    this stack is not full
	// Post-condition:
	//    puts x on top of the stack (elements already on stack are 
	//    unchanged)
	// Constraints:
	//    O(1) worst-case running time	
	void push(const T& x) {
		head = new Node{x, head};
	}

	// Pre-condition:
	//    this stack is not empty
	// Post-condition:
	//    removes and returns the top element of this stack
	// Constraints:
	//    O(1) worst-case running time
	T pop() {
		if (is_empty()) cmpt::error("pop: stack is empty");
		T result = head->val;
		Node* p = head->next;
		delete head;
		head = p;
		return result;
	}

	// Pre-condition:
	//    this stack is not empty
	// Post-condition:
	//    returns the top element of this stack (but does not modify the 
	//    stack)
	// Constraints:
	//    O(1) worst-case running time
	T top() const {
		if (is_empty()) cmpt::error("top: stack is empty");
		return head->val;		
	}
}; // class List_stack

// reverses v using a list stack
template<typename T>
void reverse(vector<T>& v) {
	const int n = v.size();
	if (n == 0) {
		return;
	} else {
		List_stack<T> stack;
		// read all of v into stack
		for(int i = 0; i < n; i++) stack.push(v[i]);

		// read stack back into v
		for(int i = 0; i < n; i++) v[i] = stack.pop();
	}
}

// This reverses a vector using the passed-in stack. stack is a pointer to an
// already-created stack, that does not (!) need to empty.
template<typename T>
void rev(vector<T>& v, Stack_base<T>* stack) {
	const int n = v.size();
	if (n == 0) {
		return;
	} else {
		// read all of v into stack
		for(int i = 0; i < n; i++) stack->push(v[i]);

		// read stack back into v
		for(int i = 0; i < n; i++) v[i] = stack->pop();
	}
}

// Prints the contents of stack (leaving it the same after as before).
// This works with any type of stack that implemennts Stack_base.
template<typename T>
void print(Stack_base<T>* stack) {
	// dump the stack into a vector
	vector<T> v;
	while (!stack->is_empty()) v.push_back(stack->pop());
	
	// put the elements all back into the stack (in proper order!)
	for(int i = v.size()-1; i >= 0; i--) stack->push(v[i]);

	// print the vector (in proper order!)
	for(int i = v.size()-1; i >= 0; i--) cout << v[i] << " ";
	cout << "\n";
}

void test_Vector_stack() {
	Vector_stack<int> stack;

	assert(stack.is_empty());
	stack.push(5);
	assert(!stack.is_empty());
	assert(stack.top() == 5);
	assert(stack.pop() == 5);
	assert(stack.is_empty());

	cout << "all Vector_stack tests passed\n";
}

void test_List_stack() {
	List_stack<int> stack;

	assert(stack.is_empty());
	stack.push(5);
	assert(!stack.is_empty());
	assert(stack.top() == 5);
	assert(stack.pop() == 5);
	assert(stack.is_empty());

	for(int i = 0; i < 10; i++) stack.push(i);

	cout << "all List_stack tests passed\n";
}

void test_reverse() {
	vector<int> v = {1,2,3,4,5};
	reverse(v);
	for(int x : v) cout << x << " ";
	cout << "\n";

	vector<string> words = {"one", "two", "three", "four"};
	reverse(words);
	for(const string& s : words) cout << s << " ";
	cout << "\n";	
}

void test_rev() {
	vector<int> v = {1,2,3,4,5};
	List_stack<int>* stack1 = new List_stack<int>();
	rev(v, stack1);
	delete stack1;
	for(int x : v) cout << x << " ";
	cout << "\n";

	vector<string> words = {"one", "two", "three", "four"};
	Vector_stack<string>* stack2 = new Vector_stack<string>();
	rev(words, stack2);
	delete stack2;
	for(const string& s : words) cout << s << " ";
	cout << "\n";	
}

void print_test() {
	List_stack<int> s1;
	s1.push(3); s1.push(4); s1.push(5);
	print(&s1);
	print(&s1);

	Vector_stack<string> s2;
	s2.push("a"); s2.push("b"); s2.push("c");	
	print(&s2);
	print(&s2);
}

void print_test2() {
	List_stack<int> s1;
	s1.push(3); s1.push(4); s1.push(5);
	s1.print();
	s1.print();

	Vector_stack<string> s2;
	s2.push("a"); s2.push("b"); s2.push("c");	
	s2.print();
	s2.print();
}

int main() {
    test_Vector_stack();
    test_List_stack();
    test_reverse();
    test_rev();
    print_test();
}