/* LinkedList.h */

#ifndef _LINKEDLIST_H
#define _LINKEDLIST_H

#include <iostream>
using namespace std;

typedef void* POSITION;

template<class TYPE>
class LinkedList {
	class ListNode {
	public:
		TYPE data;
		ListNode* pNext;
		ListNode(TYPE x) {
			data = x;
			pNext = NULL;
		}
		ListNode(TYPE x,ListNode *next) {
			data = x;
			pNext = next;
		}
	};
private : // data members
	ListNode *pHead;
	int nCount;
public : // member functions
	LinkedList();
	~LinkedList();
	bool isEmpty() {
		if (pHead == NULL) return true;
		else return false;
	}
	int size() {
		return nCount;
	}
	POSITION getHeadPosition() {
		return (POSITION)pHead;
	}
	TYPE getNext(POSITION &pos) {
		ListNode *pNode = (ListNode *)pos;
		TYPE returnValue = (TYPE)pNode->data;
		pNode = pNode->pNext;
		pos = (POSITION)pNode;
		return returnValue;
	}
	void addFirst(TYPE data);
	void addLast(TYPE data);
	void add(int index,TYPE data);
	bool remove(TYPE data);
	friend ostream& operator<<(ostream &outs,LinkedList &l);
};

template<class TYPE>
LinkedList<TYPE>::LinkedList()
{
	pHead = NULL;
	nCount = 0;
}

template<class TYPE>
LinkedList<TYPE>::~LinkedList()
{
	ListNode *pTraverse = pHead;
	for(int i = 0; i < nCount; i++) {
		ListNode *pNext = pTraverse->pNext;
		delete pTraverse;
		pTraverse = pNext;
	}
}

template<class TYPE>
void LinkedList<TYPE>::addFirst(TYPE data)
{
	ListNode *pNode = new ListNode(data,pHead);
	nCount++;
	pHead = pNode;
}

template<class TYPE>
void LinkedList<TYPE>::addLast(TYPE data)
{
	ListNode *pNode = new ListNode(data);
	nCount++;
	if (pHead == NULL) {
		pHead = pNode;
		return;
	}
	ListNode *pTraverse = pHead;
	while(pTraverse->pNext != NULL) {
		pTraverse = pTraverse->pNext;
	}
	pTraverse->pNext = pNode;
}

template<class TYPE>
void LinkedList<TYPE>::add(int index,TYPE data)
{
	if (index < 0 || index > nCount) {
		cout << "index out of bound error - add(index,data) failed." << endl;
		return;
	}
	if (index == 0) {
		addFirst(data);
		return;
	}
	int count = 1;
	ListNode *pFollow = pHead;
	ListNode *pTraverse = pHead->pNext;
	while(pTraverse != NULL) {
		if (index == count) break;
		count++;
		pFollow = pTraverse;
		pTraverse = pTraverse->pNext;
	}
	ListNode *pNode = new ListNode(data,pTraverse);
	nCount++;
	pFollow->pNext = pNode;
}

template<class TYPE>
bool LinkedList<TYPE>::remove(TYPE data)
{
	if (isEmpty() == true) {
		cout << "The list is empty. No data removed." << endl;
		return false;
	}
	if (pHead != NULL && pHead->data == data) {
		ListNode *pNextNode = pHead->pNext;
		delete pHead;
		pHead = pNextNode;
		nCount--;
		return true;
	}
	ListNode *pFollow = pHead;
	ListNode *pTraverse = pHead->pNext;
	while(pTraverse != NULL) {
		if (pTraverse->data == data) {
			ListNode *pNextNode = pTraverse->pNext;
			delete pTraverse;
			pFollow->pNext = pNextNode;
			nCount--;
			return true;
		}
		pFollow = pTraverse;
		pTraverse = pTraverse->pNext;
	}
	cout << data << " is not found. No data removed." << endl;
	return false;
}

template<class TYPE>
ostream& operator<<(ostream &outs,LinkedList<TYPE> &l)
{
	if (l.isEmpty() == true) {
		cout << "The list is empty." << endl;
		return outs;
	}
	cout << "< ";
	LinkedList<TYPE>::ListNode *pNode = l.pHead;
	while (pNode != NULL) {
		outs << pNode->data;
		if (pNode->pNext != NULL) {
			cout << ", ";
		} else {
			cout << " >" << endl;
		}	
		pNode = pNode->pNext;
	}
	return outs;
}

#endif
