#ifndef LIST_H
#define LIST_H

#include <sstream>
using namespace std;

template<typename T>
class DoubleLinkedList {
private:
	template<typename T>
	class Entry {
	private:
		Entry(const Entry<T>&);
		Entry<T>& operator=(const Entry<T>&);
		
	public:
		Entry<T>* next;
		Entry<T>* pre;
		T* data;
		
		Entry(const T& obj);
		virtual ~Entry();
	};
	
	Entry<T>* head;
	Entry<T>* tail;
	int size;
	
	DoubleLinkedList& operator=(const DoubleLinkedList&);
	Entry<T>* getEntryAt(int n) const;
	
public:
	DoubleLinkedList();
	virtual ~DoubleLinkedList();
	
	void addFirst(const T& obj);
	void addLast(const T& obj);
	void addAt(int n, const T& obj);
	
	bool removeFirst();
	bool removeLast();
	bool removeAt(int n);
	
	T getFirst() const;
	T getLast() const;
	T get(int n) const;
	int getSize() const;
};


// ¸ðµç Æ÷ÀÎÅÍ´Â NULL·Î ÃʱâÈ­ÇÏ¸ç »èÁ¦ÇÒ ¶§µµ ´Ù½Ã NULLÀ» °¡¸®Å°°ÔÇÑ´Ù.

//--------------------- Entry Ŭ·¡½º Á¤ÀÇ -------------------

template<typename T>
DoubleLinkedList<T>::Entry<T>::Entry() :
next(NULL), pre(NULL), data(NULL) {}

template<typename T>
DoubleLinkedList<T>::Entry<T>::Entry(const T& obj) :
next(NULL), pre(NULL) {
	data = new T(obj);
}

template<typename T>
DoubleLinkedList<T>::Entry<T>::~Entry() {
	delete data;
}

//--------------------- DoubleLinkedList ÅÛÇø´Å¬·¡½º Á¤ÀÇ -------------

template<typename T>
DoubleLinkedList<T>::DoubleLinkedList() :
head(NULL), tail(NULL), size(0) {}

template<typename T>
DoubleLinkedList<T>::~DoubleLinkedList() {
	while (getSize() != 0)
		removeFirst();
}

/*
 * obj¸¦ ¸®½ºÆ®ÀÇ ¸Ç ¾Õ¿¡ Ãß°¡ÇÑ´Ù.
 */
template<typename T>
void DoubleLinkedList<T>::addFirst(const T& obj) {
	if (size == 0) {
		head = new Entry<T>(obj);
		tail = head;
	}
	else {
		head->pre = new Entry<T>(obj);
		head->pre->next = head;
		head = head->pre;
	}
	size++;
}

/*
 * obj¸¦ ¸®½ºÆ®ÀÇ ¸¶Áö¸·¿¡ Ãß°¡ÇÑ´Ù.
 */
template<typename T>
void DoubleLinkedList<T>::addLast(const T& obj) {
	if (size == 0) {
		addFirst(obj);
		return;
	}
	else {
		Entry<T>* e = new Entry(obj);
		e->pre = tail;
		tail->next = e;
		tail = e;
	}
	size++;
}

/*
 * n ¹ø° Ç׸ñ¿¡ obj¸¦ Ãß°¡ÇÑ´Ù.
 */
template<typename T>
void DoubleLinkedList<T>::addAt(int n, const T& obj) {
	if (n != 0 && n >= size || n < 0) {
		ostringstream sout;
		sout << "¹üÀ§¸¦ ³Ñ¾î¼¹½À´Ï´Ù.\n°¡´É¹üÀ§: 0 ~ " << size - 1 << " ¿äû: " << n;
		throw sout.str();
	}
	else if (size <= 2) {
		if (getEntryAt(n) == head) {
			addFirst(obj);
			return;
		}
		else {
			addLast(obj);
			return;
		}
	}
	else {
		Entry<T>* next = getEntryAt(n);
		Entry<T>* pre = next->pre;
		Entry<T>* nowEntry = new Entry<T>(obj);
		
		nowEntry->next = next;
		next->pre = nowEntry;
		pre->next = nowEntry;
		nowEntry->pre = pre;
		
		size++;
	}
}


/*
 * ¸®½ºÆ®ÀÇ Ã¹¹ø° Ç׸ñÀ» »èÁ¦ÇÑ´Ù.
 * ÀúÀåµÈ °´Ã¼°¡ ¾øÀ¸¸é false°¡ ¸®ÅϵȴÙ.
 */
template<typename T>
bool DoubleLinkedList<T>::removeFirst() {
	if (size == 0)
		return false;
	else {
		if (--size == 0) {
			delete head;
			head = tail = NULL;
		}
		else {
			head = head->next;
			delete head->pre;
			head->pre = NULL;
		}
	}
	return true;
}

/*
 * ¸®½ºÆ®ÀÇ ¸¶Áö¸· Ç׸ñÀ» »èÁ¦ÇÑ´Ù.
 */
template<typename T>
bool DoubleLinkedList<T>::removeLast() {
	if (size == 0) {
		return false;
	}
	else {
		if (size == 1) {
			delete tail;
			head = tail = NULL;
		}
		else {
			tail = tail->pre;
			delete tail->next;
			tail->next = NULL;
		}
	}
	size--;
	return true;
}

/*
 * n¹ø° Ç׸ñÀ» »èÁ¦ÇÑ´Ù.
 */
template<typename T>
bool DoubleLinkedList<T>::removeAt(int n) {
	if (n >= size || n < 0) {
		ostringstream sout;
		sout << "List°¡ ºñ¾ú°Å³ª ¹üÀ§¸¦ ³Ñ¾î¼¹½À´Ï´Ù.\n°¡´É¹üÀ§: 0 ~ " << size - 1 << ", ¿äû: " << n;
		throw sout.str();
	}
	else if (size <= 2) {
		if (getEntryAt(n) == head)
			return removeFirst();
		else
			return removeLast();
	}
	else {
		Entry<T>* pre = getEntryAt(n);
		pre->next - pre->next->next;
		pre->next->next->pre = pre;
		size--;
	}
	return true;
}

/* 
 * ¸®½ºÆ®ÀÇ Ã¹¹ø° Ç׸ñ¿¡ ÀúÀåµÈ °´Ã¼¸¦ ¸®ÅÏÇÑ´Ù.
 * getSize()°¡ 0À̸é NULLÀÌ ¹ÝȯµÈ´Ù.
 */
template<typename T>
T DoubleLinkedList<T>::getFirst() const {
	if (size == 0) 
		throw "ÀúÀåµÈ Ç׸ñÀÌ ¾ø½À´Ï´Ù.";
	return *head->data;
}

/*
 * ¸®½ºÆ®ÀÇ ¸¶Áö¸· Ç׸ñ¿¡ ÀúÀåµÈ °´Ã¼¸¦ ¸®ÅÏÇÑ´Ù.
 * getSize()°¡ 0À̸é NULLÀÌ ¹ÝȯµÈ´Ù.
 */
template<typename T>
T DoubleLinkedList<T>::getLast() const {
	if (size == 0) 
		throw "ÀúÀåµÈ Ç׸ñÀÌ ¾ø½À´Ï´Ù.";
	return *tail->data;
}

/* 
 * n¹ø° Ç׸ñÀÇ °´Ã¼¸¦ ¸®ÅÏÇÑ´Ù.
 */
template<typename T>
T DoubleLinkedList<T>::get(int n) const {
	return *getEntryAt(n)->data;
}

/*
 * n¹ø° Ç׸ñÀ» ¸®ÅÏÇÑ´Ù.
 * ¾øÀ¸¸é NULLÀÌ ¹ÝÇѵȴÙ.
 */
template<typename T>
DoubleLinkedList<T>::Entry<T>* DoubleLinkedList<T>::getEntryAt(int n) const {
	if (n >= size || n < 0) {
		ostringstream sout;
		sout << "List°¡ ºñ¾ú°Å³ª ¹üÀ§¸¦ ³Ñ¾î¼¹½À´Ï´Ù.\n°¡´É¹üÀ§: 0 ~ " << size - 1 << ", ¿äû: " << n;
		throw sout.str();
	}
	Entry<T>* e = head;
	while (n != 0) {
		e = e->next;
		n--;
	}
	return e;
}

template<typename T>
int DoubleLinkedList<T>::getSize() const {
	return size;
}


#endif