// stack_adt.cpp

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

using namespace std;

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:
	//    puts x on top of the stack (elements already on stack are 
	//    unchanged)
	// Constraints:
	//    O(1) worst-case running time	
	virtual void push(int 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 int 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 int top() const = 0;
}; // class Stack_base

class Vector_stack : public Stack_base {
private:
	vector<int> 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:
	//    puts x on top of the stack (elements already on stack are 
	//    unchanged)
	// Constraints:
	//    O(1) worst-case running time	
	void push(int x) {
		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
	int pop() {
		if (is_empty()) cmpt::error("can't pop an empty stack");
		int 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
	int top() const {
		if (is_empty()) cmpt::error("can't pop an empty stack");
		return v.back();		
	}
}; // class Vector_stack

class List_stack : public Stack_base {
private:
	struct Node {
		int val;
		Node* next;
	}; 

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

	~List_stack() {
		while (!is_empty()) pop();
		// while (head != nullptr) {
		// 	Node* p = head->next;
		// 	delete head;
		// 	head = p;
		// }
		// // invariant: head == nullptr
	}

	// 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:
	//    puts x on top of the stack (elements already on stack are 
	//    unchanged)
	// Constraints:
	//    O(1) worst-case running time	
	void push(int 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
	int pop() {
		if (is_empty()) cmpt::error("can't pop an empty stack");
		int 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
	int top() const {
		if (is_empty()) cmpt::error("can't pop an empty stack");
		return head->val;		
	}
}; // class List_stack

// reverses v using a stack
void reverse(vector<int>& v) {
	const int n = v.size();
	if (n == 0) {
		return;
	} else {
		List_stack 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();
	}
}


void test_Vector_stack() {
	Vector_stack 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 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";
}


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