#pragma once
#include "Node.h"
#include <iostream>
#include <stdexcept>

template <class T>
class List
{
public:
	// Constructor and destructor
	// Default constructor
	List();
	// Copy constructor
	List(const List & lst);
	// Destructor
	~List();
	// Overloaded assignment operator
	List& operator=(const List & lst);

	// Mutators
	//PRE:
	//PARAM: value = value to be inserted
	//POST: value is inserted at the front of the list
	void insert(T value);
	//PRE:
	//PARAM: arr = set of values to be inserted
	//POST: values in arr are inserted in list
	//      such that the order of the list is the same
	void load(T arr[], int arr_n);
	//PRE: 
	//PARAM: value to be removed
	//POST: removes parameter from list, returning the number of
	//      list elements that were removed
	int remove(T value);

	// Accessors
	//PRE: 
	//POST: returns number of values in the list
	int size() const;
	//PRE: 
	//POST: returns true if list is empty, otherwise false
	bool empty() const;
	//PRE: 
	//POST: prints the list from head to tail
	void print() const;
	//PRE: 
	//POST: prints the list from tail to head
	void printReverse() const;

private:
	Node<T>* head;
	int n;
	void copyList(const List & lst);
	void deleteList();
	void printReverseHelper(Node<T>* nd) const;
};


// Default contructor
template <class T>
List<T>::List()
{
	head = nullptr;
	n = 0;
}

// Copy constructor
template <class T>
List<T>::List(const List & lst)
{
	copyList(lst);
}

template <class T>
// Destructor
List<T>::~List()
{
	deleteList();
}

template <class T>
// Overloaded assignment operator
List<T>& List<T>::operator=(const List & lst)
{
	if (this != &lst) {
		deleteList();
		copyList(lst);
	}
	return *this;
}

// Mutators
//PRE:
//PARAM: value = value to be inserted
//POST: value is inserted at the front of the list
template <class T>
void List<T>::insert(T value)
{
	Node<T>* newNode = new Node<T>(value, head);
	head = newNode;
	n++;
}

//PRE:
//PARAM: arr = set of values to be inserted
//POST: values in arr are inserted in list
//      such that the order of the list is the same
template <class T>
void List<T>::load(T arr[], int arr_n)
{
	for(int i=arr_n-1; i >= 0; --i){
		insert(arr[i]);
	}
}

//PRE: 
//PARAM: value to be removed
//POST: removes parameter from list, returning the number of
//      list elements that were removed	
template <class T>
int List<T>::remove(T value)
{
	int result = 0;
	Node<T>* current = head;
	// Value to be removed is head of list
	while(head != nullptr && head->data == value){
		head = head->next;
		delete current;
		n++;
		current = head;
	}

	// List may now be empty and head->data != value
	if(head != nullptr){
		while(current->next != nullptr){
			// Splice out node if data == value
			if(current->next->data == value){
				Node<T>* temp = current->next;
				current->next = current->next->next;
				delete temp;
				n++;
			}else{
				current = current->next;
			}
		}
	}
	return result;
}

// Accessors
//PRE: 
//POST: returns number of values in the list
template <class T>
int List<T>::size() const
{
	return n;
}

//PRE: 
//POST: returns true if list is empty, otherwise false
template <class T>
bool List<T>::empty() const
{
	return head == nullptr;
}

//PRE: 
//POST: prints the list from head to tail
template <class T>
void List<T>::print() const
{
	Node<T>* temp = head;
	while (temp != nullptr) {
		std::cout << temp->data << std::endl;
		temp = temp->next;
	}
}

//PRE: 
//POST: prints the list from tail to head
template <class T>
void List<T>::printReverse() const
{
	printReverseHelper(head);
}

// Helper Methods
// Helper method for copy constructor and operator=
//PRE: 
//POST: copies st to the calling object
//PARAM: st = stack to be copied
template <class T>
void List<T>::copyList(const List & lst)
{
	head = nullptr;
	Node<T>* original = lst.head;
	n = lst.n;
	// Copy top of st
	if (original != nullptr) {
		// Copy top of st
		head = new Node(original->data);
		original = original->next;
		Node<T>* copy = head;
		// Copy rest of stack
		while (original != nullptr) {
			Node* newNode = new Node(original->data);
			copy->next = newNode;
			copy = copy->next;
			original = original->next;
		}
	}
}

// Helper method for destructor and operator=
//PRE: 
//POST: deallocates memory associated with stack
template <class T>
void List<T>::deleteList()
{
	Node<T>* temp = head;
	while (head != nullptr) {
		head = head->next;
		delete temp;
		temp = head;
	}
	n = 0;
}

//Recursive helper function for printReverse
//PRE:
//POST: prints the contents of the stack from bottom to top
template <class T>
void List<T>::printReverseHelper(Node<T>* nd) const
{
	if(nd != nullptr){
		
		printReverseHelper(nd->next);
		std::cout << nd->data << std::endl;
	}
}
/*
class List
{
public:
	// Constructor and destructor
	// Default constructor
	List();
	// Copy constructor
	List(const List & lst);
	// Destructor
	~List();
	// Overloaded assignment operator
	List& operator=(const List & lst);

	// Mutators
	//PRE:
	//PARAM: value = value to be inserted
	//POST: value is inserted at the front of the list
	void insert(int value);
	//PRE:
	//PARAM: arr = set of values to be inserted
	//POST: values in arr are inserted in list
	//      such that the order of the list is the same
	void load(int arr[], int arr_n);
	//PRE: 
	//PARAM: value to be removed
	//POST: removes parameter from list, returning the number of
	//      list elements that were removed
	int remove(int value);

	// Accessors
	//PRE: 
	//POST: returns number of values in the list
	int size() const;
	//PRE: 
	//POST: returns true if list is empty, otherwise false
	bool empty() const;
	//PRE: 
	//POST: prints the list from head to tail
	void print() const;
	//PRE: 
	//POST: prints the list from tail to head
	void printReverse() const;

private:
	Node* head;
	int n;
	void copyList(const List & lst);
	void deleteList();
	void printReverseHelper(Node* nd) const;
};


// Default contructor
List::List()
{
	head = nullptr;
	n = 0;
}

// Copy constructor
List::List(const List & lst)
{
	copyList(lst);
}

// Destructor
List::~List()
{
	deleteList();
}

// Overloaded assignment operator
List& List::operator=(const List & lst)
{
	if (this != &lst) {
		deleteList();
		copyList(lst);
	}
	return *this;
}

// Mutators
//PRE:
//PARAM: value = value to be inserted
//POST: value is inserted at the front of the list
void List::insert(int value)
{
	Node* newNode = new Node(value, head);
	head = newNode;
	n++;
}

//PRE:
//PARAM: arr = set of values to be inserted
//POST: values in arr are inserted in list
//      such that the order of the list is the same
void List::load(int arr[], int arr_n)
{
	for(int i=arr_n-1; i >= 0; --i){
		insert(arr[i]);
	}
}

//PRE: 
//PARAM: value to be removed
//POST: removes parameter from list, returning the number of
//      list elements that were removed	
int List::remove(int value)
{
	int result = 0;
	Node* current = head;
	// Value to be removed is head of list
	while(head != nullptr && head->data == value){
		head = head->next;
		delete current;
		n++;
		current = head;
	}

	// List may now be empty and head->data != value
	if(head != nullptr){
		while(current->next != nullptr){
			// Splice out node if data == value
			if(current->next->data == value){
				Node* temp = current->next;
				current->next = current->next->next;
				delete temp;
				n++;
			}else{
				current = current->next;
			}
		}
	}
	return result;
}

// Accessors
//PRE: 
//POST: returns number of values in the list
int List::size() const
{
	return n;
}

//PRE: 
//POST: returns true if list is empty, otherwise false
bool List::empty() const
{
	return head == nullptr;
}

//PRE: 
//POST: prints the list from head to tail
void List::print() const
{
	Node* temp = head;
	while (temp != nullptr) {
		std::cout << temp->data << std::endl;
		temp = temp->next;
	}
}

//PRE: 
//POST: prints the list from tail to head
void List::printReverse() const
{
	printReverseHelper(head);
}

// Helper Methods
// Helper method for copy constructor and operator=
//PRE: 
//POST: copies st to the calling object
//PARAM: st = stack to be copied
void List::copyList(const List & lst)
{
	head = nullptr;
	Node* original = lst.head;
	n = lst.n;
	// Copy top of st
	if (original != nullptr) {
		// Copy top of st
		head = new Node(original->data);
		original = original->next;
		Node* copy = head;
		// Copy rest of stack
		while (original != nullptr) {
			Node* newNode = new Node(original->data);
			copy->next = newNode;
			copy = copy->next;
			original = original->next;
		}
	}
}

// Helper method for destructor and operator=
//PRE: 
//POST: deallocates memory associated with stack
void List::deleteList()
{
	Node* temp = head;
	while (head != nullptr) {
		head = head->next;
		delete head;
	}
	head = nullptr;
	n = 0;
}

//Recursive helper function for printReverse
//PRE:
//POST: prints the contents of the stack from bottom to top
void List::printReverseHelper(Node* nd) const
{
	if(nd != nullptr){
		
		printReverseHelper(nd->next);
		std::cout << nd->data << std::endl;
	}
}
*/