#if !defined(DICT_H)
#define DICT_H

#ifndef NULL
#include <cstdio>
#endif

#ifndef _strcmpi
#include <cstring>
#endif

template <class DataType> class Dict;
typedef void (*delete_t)(void*);

template <class DataType>
class DictNode {
	friend class Dict<DataType>;
private:
	DataType Data;
	DictNode *LeftNode, *RightNode;
	DictNode *PrevNode, *NextNode;

public:
	const char *Key;

	DictNode(const char *NodeKey, DataType NodeData) : Key(NodeKey), Data(NodeData) {
		NextNode = PrevNode = NULL;
		LeftNode = RightNode = NULL;
	}

	~DictNode(void) {
		Key = NULL;
		Data = NULL;
	}
};

template <class DataType>
class Dict {
private:
	unsigned long DictSize;
	bool FreeKey, FreeData;
	delete_t DeleteKey, DeleteData;
	DictNode<DataType> *RootNode, *FirstNode, *LastNode;

	static DictNode<DataType> *SplayTree(DictNode<DataType> *Node, const char *Key) {
		DictNode<DataType> Stack(NULL, NULL);
		DictNode<DataType> *Left, *Right, *Up;

		if (!Node) return NULL;
		Left = Right = &Stack;

		int res;
		for (;;) {
		if (!(res = _strcmpi(Key, Node->Key)))
			break;
		if (res < 0) {
			if (!Node->LeftNode) break;
			res = _strcmpi(Key, Node->LeftNode->Key);
			if (res < 0) {
				Up = Node->LeftNode;
				Node->LeftNode = Up->RightNode;
				Up->RightNode = Node;
				Node = Up;
				if (!Node->LeftNode) break;
			}
			Right->LeftNode = Node;
			Right = Node;
			Node = Node->LeftNode;
		} else {
			if (!Node->RightNode) break;
			if ((res = _strcmpi(Key, Node->RightNode->Key)) > 0) {
				Up = Node->RightNode;
				Node->RightNode = Up->LeftNode;
				Up->LeftNode = Node;
				Node = Up;
				if (!Node->RightNode) break;
			}
			Left->RightNode = Node;
			Left = Node;
			Node = Node->RightNode;
		}
		}
		Left->RightNode = Node->LeftNode;
		Right->LeftNode = Node->RightNode;
		Node->LeftNode = Stack.RightNode;
		Node->RightNode = Stack.LeftNode;
		return Node;
	}

	inline void DeleteNode(DictNode<DataType> *Node) {
		if (Node->Key && FreeKey) {
			if (DeleteKey) {
				DeleteKey((void*)Node->Key);
			} else {
				delete[] Node->Key;
			}
		}
		if (Node->Data && FreeData) {
			if (DeleteData) {
				DeleteData((void*)Node->Data);
			} else {
				delete[] Node->Data;
			}
		}
		delete Node;
	}

public:
	Dict(bool FreeKeys, bool FreeDatas) : DictSize(0), FreeKey(FreeKeys), FreeData(FreeDatas) {
		DeleteKey = DeleteData = NULL;
		FirstNode = LastNode = RootNode = NULL;
	}

	~Dict(void) {
		DictDelete();
	}

	inline void SetDeleteKey(delete_t DeleteKeyF) {
		DeleteKey = DeleteKeyF;
	}

	inline void SetDeleteData(delete_t DeleteDataF) {
		DeleteData = DeleteDataF;
	}

	inline unsigned long Size(void) {
		return DictSize;
	}

	inline const char *ForEach(int (*comparator)(const char *, DataType, void *), void *Extra) {
		DictNode<DataType> *Node = FirstNode;

		while (Node) {
			if (comparator(Node->Key, Node->Data, Extra))
				return Node->Key;
			Node = Node->NextNode;
		}
		return NULL;
	}

	inline DataType ForEachData(int (*comparator)(const char *, DataType, void *), void *Extra) {
		DictNode<DataType> *Node = FirstNode;
	
		while (Node) {
			if (comparator(Node->Key, Node->Data, Extra))
				return Node->Data;
			Node = Node->NextNode;
		}
		return NULL;
	}

	void InsertNode(const char *Key, DataType Data) {
		DictNode<DataType> *NewNode = new DictNode<DataType>(Key, Data);

		if (!Key) {
			delete NewNode;
			return;
		}
		if (RootNode) {
		RootNode = SplayTree(RootNode, Key);
		int res = _strcmpi(Key, RootNode->Key);
		if (res < 0) {
			NewNode->LeftNode = RootNode->LeftNode;
			NewNode->RightNode = RootNode;
			RootNode->LeftNode = NULL;
			if (RootNode->PrevNode) {
				RootNode->PrevNode->NextNode = NewNode;
			} else {
				FirstNode = NewNode;
			}
			NewNode->PrevNode = RootNode->PrevNode;
			NewNode->NextNode = RootNode;
			RootNode->PrevNode = NewNode;
			RootNode = NewNode;
		} else if (res > 0) {
			NewNode->RightNode = RootNode->RightNode;
			NewNode->LeftNode = RootNode;
			RootNode->RightNode = NULL;
			if (RootNode->NextNode) {
				RootNode->NextNode->PrevNode = NewNode;
			} else {
				LastNode = NewNode;
			}
			NewNode->NextNode = RootNode->NextNode;
			NewNode->PrevNode = RootNode;
			RootNode->NextNode = NewNode;
			RootNode = NewNode;
		} else {
			if (FreeData) {
				if (DeleteData) {
					DeleteData((void*)RootNode->Data);
				} else {
					delete[] RootNode->Data;
				}
			}
			if (FreeKey) {
				if (DeleteKey) {
					DeleteKey((void*)RootNode->Key);
				} else {
					delete[] RootNode->Key;
				}
			}
			delete NewNode;
			RootNode->Data = Data;
			RootNode->Key = Key;
			DictSize--;
		}
		} else {
			NewNode->LeftNode = NewNode->RightNode = NULL;
			NewNode->NextNode = NewNode->PrevNode = NULL;
			RootNode = FirstNode = LastNode = NewNode;
		}
		DictSize++;
	}

	bool RemoveNode(const char *Key) {
		DictNode<DataType> *NewRoot, *OldRoot;

		if (!RootNode) return false;
		RootNode = SplayTree(RootNode, Key);
		if (_strcmpi(Key, RootNode->Key))
			return false;

		if (!RootNode->LeftNode) {
			NewRoot = RootNode->RightNode;
		} else {
			NewRoot = SplayTree(RootNode->LeftNode, Key);
			NewRoot->RightNode = RootNode->RightNode;
		}
		if (RootNode->PrevNode) RootNode->PrevNode->NextNode = RootNode->NextNode;
		if (RootNode == FirstNode) FirstNode = FirstNode->NextNode;
		if (RootNode->NextNode) RootNode->NextNode->PrevNode = RootNode->PrevNode;
		if (RootNode == LastNode) LastNode = LastNode->PrevNode;
		OldRoot = RootNode;
		RootNode = NewRoot;
		DeleteNode(OldRoot);
		DictSize--;
		return true;
	}

	inline DataType FindNode(const char *Key) {
		if (!Key || !RootNode) return NULL;
		RootNode = SplayTree(RootNode, Key);
		return (_strcmpi(Key, RootNode->Key)) ? NULL : RootNode->Data;
	}

	void DictDelete(void) {
		DictNode<DataType> *Node, *Next;
		if (!DictSize) return;
		for (Node = FirstNode; Node; Node = Next) {
			Next = Node->NextNode;
			DeleteNode(Node);
		}
		DictSize = 0;
	}
};

#endif /* !defined(DICT_H) */