// FILE: Node.h
// Templated version of the linked list toolkit.
#ifndef Node_H  
#define Node_H

#include <iostream>
#include <cstdlib> // Provides NULL

template <class T>
class Node {
public:
	// Note the use of T's default constructor.
	// This works even for built-in types, like int and double.
	Node(T x = T(), Node* initLink = NULL) : data(x), link(initLink) { }
		T data;
		Node* link;
};

// listLength returns the length of the list pointed to by headPtr.
template <class T>
int listLength(const Node<T>* headPtr) {
	if (headPtr)
		return 1 + listLength(headPtr->link);
	else
		return 0;
	// The above four lines could be written as one:
	// return headPtr ? (1 + listLength(headPtr->link)) : 0;
}

// listInsertHead adds the data item "entry" to the beginning
// of the list pointed to by headPtr.  Note that headPtr must 
// be passed by reference because the value of headPtr must be
// different when the function is finished.
template <class T>
void listInsertHead(T entry, Node<T>*& headPtr) {
	headPtr = new Node<T>(entry, headPtr);
}

// listInsert inserts the data item "entry" after the node 
// pointed to by previousPtr.
template <class T>
void listInsert(T entry, Node<T>* previousPtr) {
	previousPtr->link = new Node<T>(entry, previousPtr->link);
}

// listSearch searches for the first occurence of target in the
// list pointed to by headPtr.  Returns a pointer to the node
// that holds the target or NULL if the target is not found.
template <class T>
Node<T>* listSearch(T target, Node<T>* p) {
	while (p && p->data != target) 
		p = p->link;
	return p;
}

// listLocate returns a pointer to the "nth" node in the list
// or to NULL if there are fewer nodes than that.
template <class T>
Node<T>* listLocate(Node<T>* headPtr, int nth) {
	if (headPtr == NULL)
		return NULL;
	else if (nth == 1)
		return headPtr;
	else
		return listLocate(headPtr->link, nth - 1);
}

// listRemoveHead removes the first node in the list pointed
// to by headPtr.  Assumes that there is at least one node in
// the list.
template <class T>
void listRemoveHead(Node<T>*& headPtr) {
	Node<T>* removePtr = headPtr;
	headPtr = headPtr->link;
	delete removePtr;
}

// listRemove removes the node following the one pointed to by
// previousPtr.
template <class T>
void listRemove(Node<T>* previousPtr) {
	Node<T>* removePtr = previousPtr->link;
	previousPtr->link = removePtr->link;
	delete removePtr;
}

// listClear removes all nodes from the list pointed to by headPtr.
template <class T>
void listClear(Node<T>*& p) {
	while (p) listRemoveHead(p);
}

// listCopy creates a duplicate of the list pointed to by sourcePtr
// and returns a pointer to the new list.
template <class T>
Node<T>* listCopy(const Node<T>* sourcePtr) {
	if (sourcePtr)
		return new Node<T>(sourcePtr->data, listCopy(sourcePtr->link));
	else 
		return NULL;
	// The above four lines could be combined together as:
	//return (sourcePtr ? (new Node(sourcePtr->data, listCopy(sourcePtr->link))) : NULL);

}

// listPrint display the contents of the list pointed to by p.
template <class T>
void listPrint(Node<T>* p) {
	while (p != NULL) {
		std::cout << p->data;
		p=p->link;
	}
} 

// listPrintRecursive is a recursive function to display the 
// contents of the list pointed to by p.
template <class T>
void listPrintRecursive(Node<T>* p) {
	if (p) {
		std::cout << p->data;
		listPrintRecursive(p->link);
	}
}

// listPrintReverse prints (recursively) in reverse the data 
// in the list pointed to by p.
template <class T>
void listPrintReverse(Node<T>* p) {
	if (p) {
		listPrintReverse(p->link);
		std::cout << p->data;
	}
}

#endif