#pragma once

/* Generic Linked List implementation by Benjamin Kalytta, 2005
 *
 * This are generic classes which accept each data type.
 * CLinkedList
 * CLinkedListItem : CLinkedListDefaultComperator
 */
template <class T, class C> class CLinkedList;
template <class T, class C> class CLinkedListItem;

template <class T> class CLinkedListDefaultComperator {
public:	
	static int Compare(T &a, T &b) {
		if (a < b) {
			return -1;
		} else if (a > b) {
			return 1;
		} else {
			return 0;
		}
	}
};

template <class T, class C = CLinkedListDefaultComperator<T> > class CLinkedListItem {
protected:
	typedef CLinkedListItem<T, C> CItem;
	typedef CLinkedList<T, C> CList;
	friend class CLinkedList<T,C>;

	T Data;
	CItem *Next, *Prev;
	CList *Header;

public:

	CLinkedListItem() : Next(0), Prev(0), Header(0) {
	}

	CLinkedListItem(CList *Header, T Data) : Data(Data), Header(Header), Next(0), Prev(0) {
	}
	
	~CLinkedListItem() {
	}

	CItem* Clone() {
		return new CItem(Header, Data);
	}

	T &GetData() {
		return Data;
	}

	CItem *GetNext() {
		return Next;
	}

	CItem *GetPrev() {
		return Prev;
	}

	/* CList (Header) specific operations */

	CItem* Enqueue(T Data) {
		return Header->Enqueue(Data);
	}

	CItem* Enqueue(CItem* Item) {
		return Header->Enqueue(Item);
	}

	CItem* Dequeue() {
		return Header->Dequeue();
	}

	CItem* Push(T Data) {
		return Header->Push(Data);
	}

	CItem* Push(CItem* Item) {
		return Header->Push(Item);
	}

	CItem* Pop() {
		return Header->Pop();
	}

	/* CList specific operations */
	
	CItem *Remove() {
		if (this == Header->First) {
			return Header->Dequeue();
		} else if (this == Header->Last) {
			return Header->Pop();
		}
		Prev->Next = Next;
		Next->Prev = Prev;
		Header = 0;
		Next = Prev = 0;
		return this;
	}

	CItem *Insert(T &Data) {
		if (this == Header->First) {
			return Header->Enqueue(Data);
		} else if (this == Header->Last) {
			return Header->Push(Data);
		}
		return Insert(new CItem(Header, Data));
	}

	CItem *Insert(CItem *Item) {
		if (Item == 0) return 0;
		Prev->Next = Item;
		Item->Prev = Prev;
		Prev = Item;
		Item->Next = this;
		Item->Header = Header;
		Header->Count++;
		return Item;
	}
	
	/* Replaces an item with specified one */
	
	CItem* Swap(CItem *Item) {
		if (Item == 0) return 0;
		if (Item == this) return this;
		
		CItem *Current = this;
		
		/* Swap entries first ... */
		
		if (Current->Prev == Item) {
			Current = Item;
			Item = this;
		}
		
		if (Current->Next == Item) {
			/* Items are adjoin to each other */
			
			Current->Next = Item->Next;
			Item->Prev = Current->Prev;
			
			Current->Prev = Item;
			Item->Next = Current;
			
		} else {
			CItem *n = Current->Next, *p = Current->Prev;
			Current->Next = Item->Next;
			Current->Prev = Item->Prev;
		
			Item->Next = n;
			Item->Prev = p;
	
			if (Current->Prev) {
				Current->Prev->Next = Current;
			} else {
				Header->First = Current;
			}

			if (Item->Next) {
				Item->Next->Prev = Item;
			} else {
				Header->Last = Item;
			}

		}
		
		if (Current->Next) {
			Current->Next->Prev = Current;
		} else {
			Header->Last = Current;
		}

		if (Item->Prev) {
			Item->Prev->Next = Item;
		} else {
			Header->First = Item;
		}
		
		return this;
	}
};

template <class T, class C = CLinkedListDefaultComperator<T> > class CLinkedList {
protected:
	typedef CLinkedListItem<T, C> CItem;
	CItem *First, *Last;
	unsigned int Count;

public:
	friend class CLinkedListItem<T, C>;

	CLinkedList() : First(0), Last(0), Count(0) {
	}

	~CLinkedList() {
		Clear();
	}

	CItem *GetFirst() {
		return First;
	}

	CItem *GetLast() {
		return Last;
	}

	int GetCount() {
		return Count;
	}

	CItem* Enqueue(T &Data) {
		return Enqueue(new CItem(this, Data));
	}

	CItem* Enqueue(CItem* Item) {
		if (Item == 0) return 0;
		if (First) {
			First->Prev = Item;
		} else {
			Last = Item;
		}
		Item->Next = First;
		Item->Header = this;
		First = Item;
		Count++;
		return Item;
	}

	CItem* Dequeue() {
		CItem* Item = First;
		if (First) {
			First = First->Next;
			if (First) {
				First->Prev = 0;
			} else {
				Last = 0;
			}
			Item->Next = 0;
			Item->Header = 0;
			Count--;
		}
		return Item;
	}

	CItem* Push(T Data) {
		return Push(new CItem(this, Data));
	}

	CItem* Push(CItem* Item) {
		if (Item == 0) return 0;
		if (Last) {
			Last->Next = Item;
		} else {
			First = Item;
		}
		Item->Prev = Last;
		Item->Header = this;
		Last = Item;
		Count++;
		return Item;
	}

	CItem* Pop() {
		CItem* Item = Last;
		if (Last) {
			Last = Last->Prev;
			if (Last) {
				Last->Next = 0;
			} else {
				First = 0;
			}
			Item->Prev = 0;
			Item->Header = 0;
			Count--;
		}
		return Item;
	}

	CItem* GetAt(int Index) {
		int i = 0;
		CItem *n = First;
		while (n) {
			if (i++ == Index) {
				return n;
			}
			n = n->Next;
		}
		return 0;
	}

	CItem* Search(T& Data) {
		CItem *n = First;
		while (n) {
			if (C::Compare(Data, n->GetData()) == 0) {
				return n;
			}
			n = n->Next;
		}
		return 0;
	}

	CItem* Insert(int Index, T Data) {
		CItem *n = GetAt(Index);
		if (n) {
			return n->Insert(Data);
		}
		return 0;
	}

	CItem* Insert(int Index, CItem *Item) {
		if (Item == 0) return 0;
		CItem *n = GetAt(Index);
		if (n) {
			return n->Insert(Item);
		}
		return 0;
	}

	CItem* Remove(CItem *Item) {
		if (Item == 0) return 0;
		if (Item->Header == this) {
			return Item->Remove();
		}
		return 0;
	}

	void Clear() {
		CItem* n = First, *x = First;
		while (n) {
			x = n->Next;
			delete n;
			n = x;
		}
		Count = 0;
		First = Last = 0;
	}

	bool Dump() {
		int c = Count;
		CItem *n = First;
		while (n) {
			wprintf(L"[%x] prev: %08x next: %08x (Data: %08x)\n", n, n->Prev, n->Next, *(int*) n->GetData());
			n = n->Next;
			c--;
			if (c < 0) return false;
		}
		return true;
	}
	
	/* Bubble Sort Implementation */
	
	void BubbleSort() {
		CItem *i = First;
		CItem *j = First;
		
		while (j) {
			bool IsSet = false;
			i = j;
			while (i->Next) {
				CItem *n = i->Next;
				if (C::Compare(i->Data, n->Data) > 0) {
					if (i == j) {
						j = n;
						IsSet = true;
					}
					i->Swap(n);
				} else {
					i = n;
				}
			}
			if (IsSet == false) j = j->Next;
		}
	}
	
	/* Selection Sort */
	
	void SelectionSort() {
		CItem *j = First;

		while (j) {
			CItem *i = j;
			CItem *Smallest = j;
			while (i->Next) {
				CItem *n = i->Next;
				if (C::Compare(i->Data, n->Data) > 0) {
					if (C::Compare(Smallest->Data, n->Data) > 0) {
						Smallest = n;
					}
				}
				i = n;
			}
			if (Smallest != j) {
				j->Swap(Smallest);
				j = Smallest->Next;
			} else {
				j = j->Next;
			}
		}
	}
	
	void Sort() {
		SelectionSort();
	}
};