// Amory KC Wong
// Carson Graham Secondary
// 2015-10-31
// Exercise_7_2.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

class Node {
private:
	Node	*next;			// "*" means pointer to an object
public:
	int		number;

	Node(int num);
	Node(int num, Node *prev);
	// all the following functions require the head node object to be the caller
	void addNodeToEnd(Node *node);	// add a node to the end of the links
	Node *getNode(int num);			// returns 0 if not found, otherwise returns pointer
	Node *getNodeIndex(int index);	// returns the pointer of index, if larger than list return 0
	void sortNode(Node *node);		// this will insert the node in sorted order
	bool deleteNode(int num);		// this will delete a node that has num, returns TRUE if done, FALSE if not found
	void deleteAll();				// delete everything except the head node (the first node)
	void printNodes();				// non-recursive version
	void printNodesRecursive();		// recursive version
	void printNodesReverse();		// easiest to implement recursively
private:
	void printNodesRecur();			// recursive version
	void printNodesReverseRecur();	// easiest to implement recursively
};

Node::Node(int num) {
	number = num;
	next = NULL;
}

Node::Node(int num, Node *prev) {
	prev->next = this;
	number = num;
	next = NULL;
}

// add a node to the end of the links
void Node::addNodeToEnd(Node *node) {
	// you must search through the links and when you find next == NULL, then add the node
	// use printNodes as an example of how to traverse through all the links
}

// returns NULL if not found, otherwise returns pointer
Node *Node::getNode(int num) {
	// you must search through the links and return the pointer when num is found
	// use printNodes as an example of how to traverse through all the links
	// if you reach the end of the links, return NULL
	// skip checking the head node
	return NULL;
}

// returns the pointer of index, if larger than list return NULL
Node *Node::getNodeIndex(int index) {
	// you must count through the links and return the pointer when you reach index
	// use printNodes as an example of how to traverse through all the links
	// if you reach the end of the links, return NULL
	// skip checking the head node
	return NULL;
}

// this will insert the node in sorted order
void Node::sortNode(Node *node) {
	// similar to getNode, but once you find the sort position, insert the node
	// if the new node is greater than the last node, add node to the end
}

// this will delete a node that has num, returns TRUE if done, FALSE if not found
bool Node::deleteNode(int num) {
	// similar to getNode, but once you find the item, remove the link
	// in C++ you must also delete the object to prevent a memory leak
	return false;
}

// delete everything except the head node
void Node::deleteAll() {
	// in C++ you must also delete the object to prevent a memory leak
	Node *curr = this->next;		// skip the head node
	while (curr != NULL) {
		// in C++ you must also delete the object to prevent a memory leak
		Node *delNode = curr;
		curr = curr->next;
		delete(delNode);
	}
	this->next = NULL;
}

// pass in the head node for this routine
void Node::printNodes() {
	Node *curr = this->next;		// skip the head node
	while (curr != NULL) {
		printf("%d ", curr->number);
		curr = curr->next;
	}
	printf("\n");
}

// pass in the head node for this routine
void Node::printNodesRecur() {
	if (this == NULL) {
		printf("\n");
		return;
	}
	printf("%d ", this->number);
	this->next->printNodesRecur();
}

void Node::printNodesRecursive() {
	this->next->printNodesRecur();				// skip the head node
}

// pass in the head node for this routine
void Node::printNodesReverseRecur() {
	if (this == NULL)
		return;
	this->next->printNodesReverseRecur();
	printf("%d ", this->number);
}

void Node::printNodesReverse() {
	this->next->printNodesReverseRecur();		// skip the head node
}

int _tmain(int argc, _TCHAR* argv[])
{
	Node *list = new Node(-1);			// this is a dummy head node required for inserting/deleting nodes
	Node *node1 = new Node(13, list);
	Node *node2 = new Node(18, node1);
	Node *node3 = new Node(23);
	list->addNodeToEnd(node3);

	printf("Print list using loops:\n");
	list->printNodes();
	printf("Print list using recursion:\n");
	list->printNodesRecursive();
	printf("Print list in reverse using recursion:\n");
	list->printNodesReverse();
	printf("\n");

	Node *get = list->getNode(13);
	printf("\nGet 13: %x\n", get);
	get = list->getNode(10);
	printf("Get 10: %x\n\n", get);

	get = list->getNodeIndex(0);
	printf("Get index 0: %x\n", get);
	get = list->getNodeIndex(2);
	printf("Get index 2: %x\n", get);
	get = list->getNodeIndex(3);
	printf("Get index 3: %x\n\n", get);

	Node *node4 = new Node(20);
	list->sortNode(node4);
	printf("Add a sorted item:\n");
	list->printNodes();

	Node *node5 = new Node(30);
	list->sortNode(node5);
	printf("Add a sorted item:\n");
	list->printNodes();

	Node *node6 = new Node(6);
	list->sortNode(node6);
	printf("Add a sorted item:\n");
	list->printNodes();

	bool del = list->deleteNode(18);
	printf("\nDeleting node with 18: %s\n", del ? "true" : "false");
	list->printNodes();

	del = list->deleteNode(17);
	printf("Deleting node with 17: %s\n", del ? "true" : "false");
	list->printNodes();

	del = list->deleteNode(23);
	printf("Deleting node with 23: %s\n", del ? "true" : "false");
	list->printNodes();

	list->deleteAll();
	printf("Deleting all:\n");
	list->printNodes();

	return 0;
}