#include <iostream.h>

template <class T>
struct Node {
	T data;
	Node<T>* next;
	Node();
	Node(T i);
};

template <class T>
class List {
	Node<T>* head;
public:
	List();
	~List();
	void append(T i);
	void insert(T i);
	void del(T i);
	void display();
	int operator++();
};

template <class T>
Node<T>::Node() : data(0), next(NULL) {}

template <class T>
Node<T>::Node(T i) : data(i), next(NULL) {}

template <class T>
List<T>::List() : head(NULL) {}

template <class T>
List<T>::~List() {
	Node<T>* current, *loop = head;
	while(loop) {
		current = loop;
		loop = loop->next;
		cout << "Deleting " << current->data << "\n";
		delete current;
	}
}

template <class T>
void List<T>::append(T i) {
	Node<T>* tail = head;
	while(tail) //find tail (free node)
		tail = tail->next;
	tail = new Node<T>(i);
}

template <class T>
void List<T>::insert(T i) {
	Node<T>* previous = NULL, *current = head, *newNode = new Node<T>(i);
	if(!head) {
		head = newNode;
		return;
	}
	while(current && current->data < i) { //find first node>i or tail
		previous = current;
		current = current->next;
	}
	if(previous) { //if while loop processed
		if(current && current->data == i) {
			cout << "Entry already in list\n";
			return;
		}
		previous->next = newNode;
		newNode->next = current;
	}
	else { //else current = head (there's only 1 node in list)
		if(head->data == i) {
			cout << "Entry already in list\n";
			return;
		}
		if(head->data < i)
			head->next = newNode;
		else {
			previous = head;
			head = newNode;
			head->next = previous;
		}
	}
}

template <class T>
void List<T>::del(T i) {
	Node<T>* previous = NULL, *current = head;
	while(current) { //loop all
		if(current->data == i) {
			if(previous) //loop ran at least once (head doesn't match)
				previous->next = current->next;
			else head = current->next;
			delete current;
			return;
		}
		previous = current;
		current = current->next;
	}
	cout << "Entry not found.\n";
}

template <class T>
void List<T>::display() {
	Node<T>* current = head;
	while(current) {
		cout << current -> data << endl;
		current = current -> next;
	}
}

template <class T>
int List<T>::operator++() {
	int i;
	T t;
	cout << "INT LIST MENU\n1. Append\n2. Insert\n3. Delete\n"
		<< "4. Display\n5. Quit\n";
	cin >> i;
	cout << "\n";
	switch(i) {
	case 1:
		cout << "Enter data to append: ";
		cin >> t;
		insert(t);
		break;
	case 2:
		cout << "Enter data to insert: ";
		cin >> t;
		insert(t);
		break;
	case 3:
		cout << "Enter data to delete: ";
		cin >> t;
		del(t);
		break;
	case 4:
		display();
		break;
	case 5:
		return 0;
	default:
		break;
	}
	cout << "\n";
	return 1;
}

int main() {
	List<float> list;

	while(++list);

	return 1;
}