#include <iostream>
using namespace std;

//NULL is not a standard C++ keyword or defined symbol, Therefore the following 3 lines of code
//make your code portable to compilers that do not define NULL by default.
#ifndef NULL
#define NULL 0
#endif
///////////////////////////////////////////////////////////////////////
struct Node
{
public:
	int data;
	Node *next;

	//The following code is for grading purposes only and you may ignore it.
/***********************************************************************/
	static int numAlive;
	Node() {++numAlive;}		//Executed when a node is created
	~Node() {--numAlive;}		//Executed when a node is destroyed
/***********************************************************************/
};
///////////////////////////////////////////////////////////////////////

//The following code is for grading purposes only and you may ignore it.
/***********************************************************************/
int Node::numAlive = 0;

void resetMemoryCounter()
{
	Node::numAlive = 0;
}

void checkMemory(int val = 0)
{
	if(Node::numAlive > val)
	{
		cout << "CAUTION: You still have " << Node::numAlive - val << " node(s) not deleted !! You should delete all nodes." << endl;
	}

	Node::numAlive = 0;
}
/***********************************************************************/
///////////////////////////////////////////////////////////////////////
//Function prototypes 

void printAll(Node *head);

void prepend(int data, Node *&head);

void insertAt(int data, int location, Node *&head);

Node *search(int data, Node *head);

void remove(int data, Node *&head);

void clear(Node *&head);

Node *reverse(Node *head);
///////////////////////////////////////////////////////////////////////

int main()
{
	//This code segment tests the printAll function
	//Create a list of 2 elements whose head is list1Head.

	//Create 1st Node
	Node *list1Head = new Node;
	list1Head->data = 1;

	//Create 2nd Node
	Node *list1Tail = new Node;
	list1Tail->data = 2;

	//Set Links
	list1Head->next = list1Tail;
	list1Tail->next = NULL;
	
	//Print Values
	cout << "Printing a list of 2 elements: " << endl;
	printAll(list1Head);
	cout << endl << endl;

	//Delete nodes
	delete list1Head;
	delete list1Tail;

	list1Head = NULL;
	list1Tail = NULL;
	//====================================================

	//The following code tests the functions you are required to implement.
	
	Node *list2Head = NULL;		//Start with an empty list.

	//==============================================================
	//							prepend
	//==============================================================
	cout << "Testing prepend function: " << endl;

	cout << "prepending 6, 4 and 2" << endl;
	prepend(6, list2Head);
	prepend(4, list2Head);
	prepend(2, list2Head);
	
	printAll(list2Head);	//The output should be [2]->[4]->[6]->*
	cout << endl << endl;

	//==============================================================
	//							insertAt
	//==============================================================
	cout << "Testing insertAt function: " << endl;
	cout << "list before = ";
	printAll(list2Head);
	cout << endl;

	insertAt(0, 0, list2Head);	//Insert before 1st node.
	cout << "insertAt(0, 0, list2Head)" << endl;	
	
	insertAt(8, 4, list2Head);	//Insert after the last node (The list size before insertion is 4).
	cout << "insertAt(8, 4, list2Head)" << endl;
	
	insertAt(3, 2, list2Head);	//Insert in the middle.
	cout << "insertAt(3, 2, list2Head)" << endl;
	
	cout << "list after = ";
	printAll(list2Head);	//The output should be [0]->[2]->[3]->[4]->[6]->[8]->*
	cout << endl << endl;

	//==============================================================
	//							search
	//==============================================================
	cout << "Testing search function: " << endl;
	Node *list3Head = NULL;
	
	prepend(8, list3Head);
	prepend(6, list3Head);
	prepend(4, list3Head);
	prepend(3, list3Head);
	prepend(2, list3Head);
	prepend(0, list3Head);

	cout << "list = ";
	printAll(list3Head);
	cout << endl;

	search(0, list3Head)->data = -1;			//Search for 0 and replace it with -1
	cout << "search(0, list3Head)->data = -1" << endl;

	search(6, list3Head)->data = 7;				//Search for 6 and replace it with 7
	cout << "search(6, list3Head)->data = 7" << endl;

	cout << "list after = ";
	printAll(list3Head);	//The output should be [-1]->[2]->[3]->[4]->[7]->[8]->*
	cout << endl << endl;

	//==============================================================
	//							remove
	//==============================================================
	cout << "Testing remove function: " << endl;
	resetMemoryCounter();

	Node *list4Head = NULL;
	
	prepend(8, list4Head);
	prepend(7, list4Head);
	prepend(4, list4Head);
	prepend(3, list4Head);
	prepend(2, list4Head);
	prepend(-1, list4Head);

	cout << "list before = ";
	printAll(list4Head);
	cout << endl;

	remove(8, list4Head);		//Delete last node
	cout << "remove(8)" << endl;
	
	remove(3, list4Head);		//Delete a node in the middle
	cout << "remove(3)" << endl;

	remove(-1, list4Head);		//Delete 1st node
	cout << "remove(-1)" << endl;

	cout << "list after = ";
	printAll(list4Head);	//The output should be [2]->[4]->[7]->*
	
	cout << endl;
	checkMemory(3);
	cout << endl;
	
	cout << "Now let's make a serious test for \"remove\": " << endl;
	resetMemoryCounter();

	Node *list5Head = NULL;
	
	prepend(1, list5Head);
	prepend(1, list5Head);
	prepend(1, list5Head);
	prepend(2, list5Head);
	prepend(1, list5Head);
	prepend(1, list5Head);
	prepend(1, list5Head);
	prepend(2, list5Head);
	prepend(1, list5Head);
	prepend(1, list5Head);
	prepend(1, list5Head);

	cout << "list before = ";
	printAll(list5Head);	//The output should be [1]->[1]->[1]->[2]->[1]->[1]->[1]->[2]->[1]->[1]->[1]->*;
	cout << endl;

	remove(1, list5Head);
	cout << "remove(1)" << endl;

	cout << "list = ";
	printAll(list5Head);	//The output should be [2]->[2]->*;
	cout << endl;

	remove(2, list5Head);
	cout << "remove(2)" << endl;

	cout << "list = ";
	printAll(list5Head);	//The output should be *;
	cout << endl;

	//Check that the list is still usable
	prepend(1, list5Head);
	cout << "prepend(1)" << endl;
	cout << "list = ";
	printAll(list5Head);	//The output should be [1]->*;
	cout << endl;

	checkMemory(1);
	cout << endl;

	//==============================================================
	//							clear
	//==============================================================
	cout << "Testing clear function: " << endl;
	resetMemoryCounter();

	Node *list6Head = NULL;

	prepend(6, list6Head);
	prepend(4, list6Head);
	prepend(2, list6Head);

	cout << "list = ";
	printAll(list6Head);	//The output should be [2]->[4]->[6]->*;
	cout << endl;

	clear(list6Head);
		
	cout << "cleared list = ";
	printAll(list6Head);	//The output should be *;
	cout << endl;

	//Check that the list is still usable
	prepend(1, list6Head);
	cout << "prepend(1)" << endl;
	cout << "list = ";
	printAll(list6Head);	//The output should be [1]->*;
	cout << endl;

	checkMemory(1);
	cout << endl;

	//==============================================================
	//							reverse
	//==============================================================
	cout << "Testing reverse function: " << endl;
	
	Node *list7Head = NULL;

	prepend(3, list7Head);	
	prepend(2, list7Head);	
	prepend(1, list7Head);	

	cout << "list = ";
	printAll(list7Head);	//The output should be [3]->[2]->[1]->*
	cout << endl;

	Node* list8Head = reverse(list7Head);
	
	cout << "reversed list = ";
	printAll(list8Head);	//The output should be [1]->[2]->[3]->*
	cout << endl;

	cout << endl << "Testing reverse function with empty list: " << endl;
	Node* list9Head = reverse(NULL);

	cout << "reversed list = ";
	printAll(list9Head);	//The output should be *
	cout << endl;
	//====================================================

	return 0;
}

////////////////////////////////////////////////////////////////////////

/*
* Function: printAll.
* print the values of all nodes in a linked list.
* 
* Parameters:
*	- head : The head of the linked list.
*/
void printAll(Node *head)
{
	Node *p = head;

	while(p != NULL)
	{
		cout << "[ " << p->data << " ]";
		cout << "--->";
		p = p->next;
	}

	cout << "*";
}
////////////////////////////////////////////////////////////////////////

/*
* Function: prepend.
* Creates a new node and adds it to the beginning of a linked list.
* 
* Parameters:
*	- data : The value to be stored in the new node.
*	- head : The head of the linked list. When the function finished, it should be pointing to the new node.
*	Node *&head means that 'head' is a Node* that is passed by reference. So when the function
*	changes the value of 'head', the actual parameter will be changed as well.
*/
void prepend(int data, Node *&head)
{
	Node *newNode = new Node;
	newNode->data = data;
	newNode->next = head;
	head = newNode;
}
////////////////////////////////////////////////////////////////////////

/*
* Function: insertAt.
* Creates a node and inserts it at a specified location.
* 
* Parameters:
*	- data : The data to be stored in the new node.
*	- location : The location to insert the node at ( 0 to insert before the 1st node, 1 to insert before the 2nd .. etc )
*	- head : The head of the linked list. 
*/
void insertAt(int data, int location, Node *&head)
{
	//TODO: Implement
}
////////////////////////////////////////////////////////////////////////

/*
* Function: search.
* Gets the node holding specified data.
* 
* Parameters:
*	- data : The data to search for.
*	- head : The head of the linked list. 
*
* Return:
*	The function returns a pointer to the node holding the specified data. If there are more than
*	one node, only the first is returned. If there are no nodes, NULL is returned.
*/
Node *search(int data, Node *head)
{
	//TODO: Implement	
	return 0;
}
////////////////////////////////////////////////////////////////////////

/*
* Function: remove.
* Deletes ALL nodes holding specified data.
* 
* Parameters:
*	- data : The data to search for to delete associated node.
*	- head : The head of the linked list. If the deleted node is the 1st node, it should be pointing to the 2nd node (the new head) when the function finishes.
*/
void remove(int data, Node *&head)
{
	//TODO: Implement
}
////////////////////////////////////////////////////////////////////////

/*
* Function: clear.
* Deletes all nodes in a linked list.
* 
* Parameters:
*	- head : The head of the linked list. If the deleted node is the 1st node, it should be be set to NULL to indicate that the list is empty.
*/
void clear(Node *&head)
{
	//TODO: Implement
}
////////////////////////////////////////////////////////////////////////

/*
* Function: reverse.
* Creates a new linked list that contains the elements of a given list but in reverse order.
* 
* Parameters:
*	- head : The head of the linked list. This list should NOT be changed, the reverse list is a completely new list.
*
* Returns:
*	The function returns the head of the reversed list. If the input list is empty, the function should return NULL.
*
*/
Node *reverse(Node *head)
{
	//TODO: Implement (Bonus)	
	return 0;
}
////////////////////////////////////////////////////////////////////////