#pragma once

template <class T> class CLinkedList;

template <class T> class CLinkedListNode {
public:
	CLinkedListNode() : m_prev(0), m_next(0), m_list(0) {
	}
	
	CLinkedListNode(T Data) : m_prev(0), m_next(0), m_list(0), m_data(Data) {
	}
	
	CLinkedListNode(const CLinkedListNode<T>& Node) {
		m_data = Node.m_data;
	}

	virtual ~CLinkedListNode() {
		if (m_list->m_autodelete) {
			delete m_data;
		}
//		Remove(); WARNING, IN CASE OF UNLINKED NODE CAN'T BE REMOVED!
	}

	virtual CLinkedListNode<T>* GetNext() {
		return m_next;
	}

	virtual CLinkedListNode<T>* GetPrev() {
		return m_prev;
	}

	virtual T GetData() const {
		return m_data;
	}

	virtual void SetData(T Data) {
		m_data = Data;
	}

	virtual CLinkedList<T>* GetList() const {
		return m_list;
	}

	virtual CLinkedListNode<T>* Remove() {
		return m_list->Remove(this);
	}

	virtual CLinkedListNode<T>* Insert(CLinkedListNode<T>* Node) {
		return m_list->Insert(Node, this);
	}
	
	virtual void Delete() {
		delete this;
	}

	/* Operators */

	operator T() {
		return m_data;
	}
#if 0
	CLinkedListNode<T>& operator=(const CLinkedListNode<T>& Node) {
		m_data = Node.m_data;
		return *this;
	}
#endif
protected:
	CLinkedList<T> *m_list;
	CLinkedListNode<T>* m_prev;
	CLinkedListNode<T>* m_next;
	T m_data;
private:
	friend class CLinkedList<T>;
};

template <class T> class CLinkedList {
public:
	CLinkedList(bool AutoDestroy = true, bool AutoDeleteData = true) : m_first(0), m_last(0), m_count(0), m_autodestroy(AutoDestroy), m_autodelete(AutoDeleteData) {
	}
	
	virtual ~CLinkedList() {
		if (m_autodestroy) {
			Destroy();
		}
	}

	CLinkedListNode<T>* GetFirst() const {
		return m_first;
	}

	CLinkedListNode<T>* GetLast() const {
		return m_last;
	}

	unsigned int GetCount() const {
		return m_count;
	}

	CLinkedListNode<T>* Push(CLinkedListNode<T>* Node) {
		if (Node == 0) return 0;
		Node->m_list = this;

		if (m_last) {
			Node->m_next = 0;
			Node->m_prev = m_last;
			m_last->m_next = Node;
		} else {
			m_first = Node;
		}
		m_last = Node;
		m_count++;
		return Node;
	}

	CLinkedListNode<T>* Push(T Data) {
		return Push(new CLinkedListNode<T>(Data));
	}

	CLinkedListNode<T>* Add(CLinkedListNode<T>* Node) {
		return Push(Node);
	}

	CLinkedListNode<T>* Add(T Data) {
		return Push(Data);
	}

	CLinkedListNode<T>* Pop() {
		CLinkedListNode<T>* Node = 0;
		Node = m_last;

		if (m_last) {
			m_last = m_last->m_prev;
			m_count--;
		}
		if (m_last) {
			m_last->m_next = 0;
		} else {
			m_first = 0;
		}
		return Node;
	}

	CLinkedListNode<T>* Enqueue(CLinkedListNode<T>* Node) {
		if (Node == 0) return 0;
		Node->m_list = this;

		if (m_first) {
			Node->m_prev = 0;
			Node->m_next = m_first;
			m_first->m_prev = Node;
		} else {
			m_last = Node;
		}
		m_first = Node;
		m_count++;
		return Node;
	}
	
	CLinkedListNode<T>* Enqueue(T Data) {
		return Enqueue(new CLinkedListNode<T>(Data));
	}

	CLinkedListNode<T>* Dequeue() {
		return Pop();
	}

	CLinkedListNode<T>* Insert(CLinkedListNode<T>* Node, unsigned int Position = 0xffffffff) {
		if (Node == 0) return 0;

		if (Position == 0) {
			return Enqueue(Node);
		} else if (Position >= m_count) {
			return Push(Node);
		} else {
			return Insert(Node, GetAt(Position));
		}
		return Node;
	}

	CLinkedListNode<T>* Insert(CLinkedListNode<T>* Node, CLinkedListNode<T>* Existing) {
		if (Existing == 0 || Node == 0) return 0;
		
		if (Existing == m_first) {
			return Enqueue(Node);
		} else {
			Node->m_list = this;
			Node->m_prev = Existing->m_prev;
			Node->m_next = Existing;
			Existing->m_prev->m_next = Node;
			Existing->m_prev = Node;
			m_count++;
		}
		return Node;
	}

	CLinkedListNode<T>* Insert(T Data, unsigned int Position = 0xffffffff) {
		return Insert(new CLinkedListNode<T>(Data), Position);
	}

	CLinkedListNode<T>* GetAt(unsigned int Position) {
		CLinkedListNode<T>*	Node = m_first;
		unsigned int Index = 0;
		while (Node) {
			if (Position == Index++) {
				return Node;
			}
			Node = Node->m_next;
		}
		return m_last;
	}

	CLinkedListNode<T>* Find(T Data, CLinkedListNode<T> *Start = 0) {
		CLinkedListNode<T>*	Node = Start;
		if (Start == 0) {
			Node = m_first;
		}
		while (Node) {
			if (Node->m_data == Data) {
				return Node;
			}
			Node = Node->m_next;
		}
		return 0;
	}

	CLinkedListNode<T>* Remove(CLinkedListNode<T>* Node) {
		if (Node == 0) return 0;
		if (Node->m_list == 0) return 0;

		if (Node == m_first) {
			if (m_first) {
				m_first = m_first->m_next;
				m_count--;
			}
			if (m_first) {
				m_first->m_prev = 0;
			} else {
				m_last = 0;
			}
		} else if (Node == m_last) {
			return Pop();
		} else {
			Node->m_prev->m_next = Node->m_next;
			Node->m_next->m_prev = Node->m_prev;
			m_count--;
		}

		return Node;
	}

	CLinkedListNode<T>* Remove(unsigned int Position) {
		CLinkedListNode<T>* Node = 0;
		if (Position == 0) {
			/* Will never get here because aliased by overloaded "Remove(NULL)" method */
		} else if(Position >= m_count) {
			return Pop();
		} else {
			return Remove(GetAt(Position));
		}
		return Node;
	}

	CLinkedListNode<T>* Remove(T Data) {
		return Remove(Find(Data));
	}

	void Clear() {
		m_first = 0;
		m_last = 0;
	}

	void Delete(CLinkedListNode<T> *Node) {
		if (Node) {
			Remove(Node);
			delete Node;
		}
	}

	void Destroy() {
		while (m_first) {
			Delete(m_first);
		}
	}

	void Dump() {
		CLinkedListNode<T>* Node = m_first;
		wprintf(L"LIST	%08x: %d ENTRIES\n", this, m_count);
		wprintf(L"FIRST:	%08x\n", m_first);
		wprintf(L"LAST:	%08x\n", m_last);
		while (Node) {
			wprintf(L"	%08x: DATA: %08x, PREV %08x, NEXT %08x\n", Node, Node->m_data, Node->m_prev, Node->m_next);
			Node = Node->m_next;
		}
		wprintf(L"\n");
	}

	/* Status */

	bool IsEmpty() const {
		return m_count == 0;
	}


protected:
	CLinkedListNode<T>* m_first;
	CLinkedListNode<T>* m_last;
	unsigned int m_count;
private:
	bool m_autodestroy;
	bool m_autodelete;
	
	friend class CLinkedListNode<T>;
};