/*
 * A simple stack implementation (with templates)
 *
 * Description:
 *     Aims to implement a simple stack that users are able to push to, as well
 *     as pop from. They are able to access the top of the stack in the same
 *     way as STL's Stack as well.
 *
 * Author:
 *     Clara Nguyen
 */

#ifndef __STACK__
#define __STACK__

#include <iostream>
using namespace std;

//Prototype
template <typename T>
class cn_stack {
	public:
		struct node {
			T     data;
			node *next,
			     *prev;

			node();
		};

	public:
		cn_stack();
		~cn_stack();

		void clear();

		void push(const T&);
		void pop();

		int size();

		const T& top();

		void debug_print();

	private:
		node *sentinel;
		int N;
};

//Definitions
//Node Struct
template <typename T>
cn_stack<T>::node::node() {
	next = prev = (node *)0x0;
}

//CN_Stack stuff
template <typename T>
cn_stack<T>::cn_stack() {
	//Make sentinel and make it point to itself
	sentinel = new node();
	sentinel->prev = sentinel->next = sentinel;

	N = 0;
}

template <typename T>
cn_stack<T>::~cn_stack() {
	clear();
	delete sentinel;
}

template <typename T>
void cn_stack<T>::clear() {
	while (N) {
		pop();
	}
}

template <typename T>
void cn_stack<T>::push(const T &i) {
	node *p = new node();
	p->data = i;
	
	//Get the top of the list.
	node *end = sentinel->prev;

	p->prev = sentinel->prev;
	p->next = sentinel;

	end->next = p;
	sentinel->prev = p;
	
	N++;
}

template <typename T>
void cn_stack<T>::pop() {
	node *p = sentinel->prev;
	sentinel->prev = p->prev;
	sentinel->prev->next = sentinel;
	delete p;
	N--;
}

template <typename T>
int cn_stack<T>::size() {
	return N;
}

template <typename T>
const T& cn_stack<T>::top() {
	return sentinel->prev->data;
}

template <typename T>
void cn_stack<T>::debug_print() {
	node *c = sentinel;
	cout << "Stack size: " << size() << endl;
	for (int i = 0; i < N; i++) {
		c = c->next;
		cout << c->data << endl;
	}
}

#endif