#include <iostream>
#include "LinkedListNode.cpp"
#include "LinkedListException.cpp"

using namespace std;

#ifndef LINKEDLIST_CLASS_INCLUDED
#define LINKEDLIST_CLASS_INCLUDED

/*
	Linked List Class
	LastModification : 2008. 5. 5
	Version : 1.0.1
	myllyj(myllyj at myllyj dot com) / http://program.myllyj.com

	Requirements:
		require LinkedListNode class.
		require LinkedListException classes.

	Comment:
		이 LinkedList는 이전과 다음을 자유로이 탐색할 수 있는
		DblLinkedList임
		모든 Method는 C# Naming Style을 따르고 있다.

*/

template <class T>
class LinkedList
{

private:
	LinkedListNode<T>* headerNode;
	LinkedListNode<T>* nowNode;
	void init();

public:

	LinkedList();

	void AddFirst(T data);
	void AddLast(T data);

	void Insert(T data);
	void Insert(int index, T data);

	int Count();

	void Remove();
	void Remove(int index);

	T Get();
	T Get(int index);

	void MovePrev();
	void MoveNext();
	bool Move(int index);
	void MoveFirst();
	void MoveLast();

	bool IsHeaderNode();

	void Clear();
	T* ToArray();

	bool Contains(T data);
	
};

template <class T>
LinkedList<T>::LinkedList()
{
	this->init();
}

template <class T>
void LinkedList<T>::init()
{
	this->headerNode = new LinkedListNode<T>();
	this->nowNode = this->headerNode;
	this->headerNode->next = this->headerNode;
	this->headerNode->prev = this->headerNode;
}

// 개체를 리스트의 첫 부분에 추가합니다.
template <class T>
void LinkedList<T>::AddFirst(T data)
{
	nowNode = headerNode;
	this->Insert(data);
}

// 개체를 리스트의 끝 부분에 추가합니다.
template <class T>
void LinkedList<T>::AddLast(T data)
{
	nowNode = headerNode->prev;
	this->Insert(data);
}

// 리스트에 실제로 포함된 요소의 수를 가져옵니다.
template <class T>
int LinkedList<T>::Count()
{
	LinkedListNode<T>* tempNode;
	int count = 0;
	
	tempNode = headerNode->next;

	while (!tempNode->isEmpty)
	{
		tempNode = tempNode->next;
		count++;
	}
	return count;
}

// 리스트의 현재 인덱스에 요소를 삽입합니다.
template <class T>
void LinkedList<T>::Insert(T data)
{
	LinkedListNode<T>* newNode = new LinkedListNode<T>(data);

	newNode->next = nowNode->next;
	newNode->prev = nowNode;

	nowNode->next->prev = newNode;
	nowNode->next = newNode;

	// 현재노드는 새로 추가한 노드
	nowNode = newNode;
}

// 리스트의 지정된 인덱스에 요소를 삽입합니다.
template <class T>
void LinkedList<T>::Insert(int index, T data)
{
	if (!this->move(index)) throw LinkedListIndexOutOfBoundsException();
	this->Insert(data);
}

// 리스트의 현재 인덱스에서 요소를 제거합니다.
template <class T>
void LinkedList<T>::Remove()
{
	// 해더노드는 못지워
	if (nowNode==headerNode) throw LinkedListNoElementException();
	
	nowNode->prev->next = nowNode->next;
	nowNode->next->prev = nowNode->prev;

	// 현재노드는 지운놈 다음으로 설정
	LinkedListNode<T>* tempNode = nowNode;
	nowNode = nowNode->next;
	
	delete tempNode;
}

// 리스트의 지정한 인덱스에서 요소를 제거합니다.
template <class T>
void LinkedList<T>::Remove(int index)
{
	if(!this->Move(index)) throw LinkedListIndexOutOfBoundsException();
	this->Remove();
}

// 리스트의 현재 인덱스에서 데이터를 가져옵니다.
template <class T>
T LinkedList<T>::Get()
{
	return nowNode->data;
}

// 리스트의 지정한 인덱스에서 데이터를 가져옵니다.
template <class T>
T LinkedList<T>::Get(int index)
{
	if(!this->Move(index)) throw LinkedListIndexOutOfBoundsException();
	return nowNode->data;
}

// 이전 노드로 이동합니다.
template <class T>
void LinkedList<T>::MovePrev()
{
	nowNode = nowNode->prev;
}

// 다음 노드로 이동합니다.
template <class T>
void LinkedList<T>::MoveNext()
{
	nowNode = nowNode->next;
}

// 리스트의 지정한 익덱스로 위치를 이동합니다.
template <class T>
bool LinkedList<T>::Move(int index)
{

	if (this->Count() < index) return false;
	if (index < 0) return false;

	nowNode = headerNode;
	int count = 0;

	while(count < index)
	{
		nowNode = nowNode->next;
		count++;
	}

	return true;
}

// 리스트의 첫 노드로 이동합니다.
template <class T>
void LinkedList<T>::MoveFirst()
{
	nowNode = headerNode->next;
}

// 리스트의 마지막 노드로 이동합니다.
template <class T>
void LinkedList<T>::MoveLast()
{
	nowNode = headerNode->prev;
}

// 리스트의 현재 인덱스가 해더노드의 인덱스인지 확인합니다.
template <class T>
bool LinkedList<T>::IsHeaderNode()
{
	if (nowNode==headerNode) return true;
	return false;
}

// 리스트에서 요소를 모두 제거합니다.
template <class T>
void LinkedList<T>::Clear()
{
	this->MoveFirst();
	while(nowNode!=headerNode) this->Remove();
}

// 리스트의 요소를 새 배열에 복사합니다.
template <class T>
T* LinkedList<T>::ToArray()
{
	
	if (this->Count()==0) throw LinkedListNoElementException();

	T* result = new T[this->Count()];
	LinkedListNode<T>* tmpNode = nowNode;
	int count = 0;

	this->MoveFirst();
	while(!nowNode->isEmpty)
	{
		result[count++] = nowNode->data;
		this->MoveNext();
	}

	// 노드 위치 복구
	nowNode = tmpNode;

	return result;
}

// 요소가 리스트에 있는지 여부를 확인합니다.
template <class T>
bool LinkedList<T>::Contains(T data)
{
	// 현재 위치 그냥 기록해 놓고.
	LinkedListNode<T> *tmpNode = nowNode;
	this->MoveFirst();

	while(!this->IsHeaderNode())
	{
		if (this->Get()==data)
		{
			// 노드위치 복구
			nowNode = tmpNode;
			return true;
		}
		this->MoveNext();
	}

	// 노드위치 복구
	nowNode = tmpNode;
	return false;

}

#endif