#pragma once
#include <windows.h>

template <class T> class BTree;

template <class T>
class TreeNode
{
	friend BTree<T>;

protected:
	DWORD		m_ID;
	TreeNode<T>	*m_pLeft,*m_pRight,*m_pFather;
	T*			m_pInfo;
	BTree<T>*	m_pTree;
public:
public:
	void SetLeft(TreeNode<T> *n)
	{
		m_pLeft=n;
	}

	TreeNode<T>* GetLeft(void)
	{
		return m_pLeft;
	}

	void SetRight(TreeNode<T> *p)
	{
		m_pRight=p;
	}

	TreeNode<T>* GetRight(void)
	{
		return m_pRight;
	}

	void SetFather(TreeNode<T> *p)
	{
		m_pFather=p;
	}

	TreeNode<T>* GetFather(void)
	{
		return m_pFather;
	}

	TreeNode(T*info,DWORD id)
	{
		m_pInfo = info;
		m_ID = id;
		m_pLeft = NULL;
		m_pRight = NULL;
		m_pFather = NULL;
		m_pTree = NULL;
	}

	~TreeNode(void)
	{
	}

	T* GetInfo(void)
	{
		return m_pInfo;
	}

	static TreeNode<T>* Minimum(TreeNode<T>*node)
	{
		if(!node)
			return NULL;
		while(node->m_pLeft != NULL)
		{
			node = node->m_pLeft;
		}
		return node;
	}

	static TreeNode<T>* Maximum(TreeNode<T>*node)
	{
		if(!node)
			return NULL;
		while(node->m_pRight != NULL)
		{
			node = node->m_pRight;
		}
		return node;
	}

	static TreeNode<T>* Successor(TreeNode<T>*node)
	{
		if(!node)
			return NULL;

		if(node->m_pRight)
		{
			return Minimum(node->m_pRight);
		}
		else
		{
			TreeNode<T> *p = node->m_pFather;
			while(p && node == p->m_pRight)
			{
				node = p;
				p = p->m_pFather;
			}
			return p;
		}
	}

	static TreeNode<T>* Predecessor(TreeNode<T>*node)
	{
		if(!node)
			return NULL;

		if(node->m_pLeft)
		{
			return Maximum(node->m_pLeft);
		}
		else
		{
			TreeNode<T> *p = node->m_pFather;
			while(p && node == p->m_pLeft)
			{
				node = p;
				p = p->m_pFather;
			}
			return p;
		}
	}

	void Unlink(void)
	{
		if(m_pTree)
		{
			if(m_pLeft)//at least 1 son
			{
				if(m_pRight)//2 sons
				{
					//find successor of this node
					TreeNode<T>* h = Minimum(m_pRight);

					if(m_pRight == h) // h == right son
					{
						h->m_pLeft = m_pLeft;
						if(m_pLeft)
							m_pLeft->m_pFather = h;
					}
					else
					{
						h->m_pFather->m_pLeft = h->m_pRight;
						if(h->m_pRight)
							h->m_pRight->m_pFather = h->m_pFather;
						
						h->m_pRight = m_pRight;
						m_pRight->m_pFather = h;
					}
					
					if(!m_pFather)
					{
						m_pTree->m_pRoot = h;	
					}
					else
					{
						if(m_pFather->m_pLeft==this)
							m_pFather->m_pLeft = h;
						else
							m_pFather->m_pRight = h;
					}
					h->m_pFather = m_pFather;
				}
				else //only left son
				{
					if(!m_pFather)
					{
						m_pTree->m_pRoot = m_pLeft;
					}
					else 
					{
						if(m_pFather->m_pLeft==this)
							m_pFather->m_pLeft = m_pLeft;
						else
							m_pFather->m_pRight = m_pLeft;
					}
					m_pLeft->m_pFather = m_pFather;
				}
			}
			else if(m_pRight)//only right son
			{
				if(!m_pFather)
				{
					m_pTree->m_pRoot = m_pRight;
				}
				else
				{
					if(m_pFather->m_pLeft==this)
					 	m_pFather->m_pLeft = m_pRight;
					else
						m_pFather->m_pRight = m_pRight;
				}
				m_pRight->m_pFather = m_pFather;
			}
			else//no son
			{
				if(!m_pFather)
					m_pTree->m_pRoot = NULL;
				else if(m_pFather->m_pLeft==this)
					m_pFather->m_pLeft = NULL;
				else
					m_pFather->m_pRight = NULL;
			}
			m_pTree->m_ElementCount--;
			m_pTree = NULL;
			m_pLeft = NULL;
			m_pRight = NULL;
			m_pFather = NULL;
		}
	}

	void Delete(void)
	{
		Unlink();
		if(m_pInfo)
			delete m_pInfo;
		delete this;
	}

	DWORD GetID(void)
	{
 		return m_ID;
	}

	void SetID(DWORD id)
	{
		m_ID = id;
	}

	void SetInfo(T*info)
	{
		m_pInfo = info;
	}

	BTree<T>* GetTree(void)
	{
		return m_pTree;
	}
};

template <class T>
class BTree
{
	friend TreeNode<T>;
protected:

	TreeNode<T> *m_pRoot;
	DWORD		m_ElementCount;

	void IntRelease(TreeNode<T> *p)
	{
		if(!p)
			return;
		IntRelease(p->m_pLeft);
		IntRelease(p->m_pRight);
		delete p;
	}

	void IntClear(TreeNode<T> *p)
	{
		if(!p)
			return;
		IntClear(p->m_pLeft);
		IntClear(p->m_pRight);
		if(p->m_pInfo)
			delete p->m_pInfo;
		delete p;
	}

public:

	void Release(void)
	{
		IntRelease(m_pRoot);
		ZeroMemory(this,sizeof(BTree));
	}

	void Clear(void)
	{
		IntClear(m_pRoot);
		ZeroMemory(this,sizeof(BTree));
	}

	BTree(void)
	{
		ZeroMemory(this,sizeof(BTree));
	}

	~BTree(void)
	{
		Release();
	}

	void Add(T*info,DWORD id)
	{
		Add(new TreeNode<T>(info,id));
	}

	void Add(TreeNode<T>*node)
	{
		if(node->m_pTree)
			node->Unlink();

		TreeNode<T> *r = NULL,*p = m_pRoot;

		while(p!=NULL)
		{
			r = p;
			if(node->m_ID < p->m_ID)
				p = p->m_pLeft;
			else
				p = p->m_pRight;
		}

		node->m_pTree = this;
		node->m_pFather = r;
		//node->m_pLeft = NULL;
		//node->m_pRight = NULL;
		if(r == NULL)
		{
			m_pRoot = node;
		}
		else
		{
			if(node->m_ID < r->m_ID)
				r->m_pLeft = node;
			else
				r->m_pRight = node;
		}

		m_ElementCount++;
	}

	TreeNode<T>* GetRoot(void) const
	{
		return m_pRoot;
	}

	TreeNode<T>* GetElement(const DWORD id) const 
	{
		TreeNode<T>	*p=m_pRoot;

		while(p && p->m_ID != id)
		{
			if(id < p->m_ID)
				p = p->m_pLeft;
			else
				p = p->m_pRight;
		}
		return p;
	}

	TreeNode<T>* GetElementGreaterEqual(const DWORD id) const
	{
		TreeNode<T>	*q=NULL,*p=m_pRoot;

		while(p && p->m_ID != id)
		{
			q = p;
			if(id < p->m_ID)
				p = p->m_pLeft;
			else
				p = p->m_pRight;
		}
		if(p)
			return p;
		else
		{
			if(!q)
				return q;
			else
			{
				if(q->m_ID > id) // equal isnt possilbe here
					return q;
				else
					return TreeNode<T>::Successor(q);
			}
		}
	}

	TreeNode<T>* GetElementLessEqual(DWORD id)
	{
		TreeNode<T>	*q = NULL,*p=m_pRoot;

		while(p && p->m_ID != id)
		{
			q = p;
			if(id < p->m_ID)
				p = p->m_pLeft;
			else
				p = p->m_pRight;
		}
		if(p)
			return p;
		else
		{
			if(!q)
				return q;
			else
			{
				if(q->m_ID < id) // equal isnt possilbe here
					return q;
				else
					return TreeNode<T>::Predeseccor(q);
			}
		}
	}

	TreeNode<T>* GetMinimum(void) const
	{
		return TreeNode<T>::Minimum(m_pRoot);
	}

	TreeNode<T>* GetMaximum(void) const
	{
		return TreeNode<T>::Maximum(m_pRoot);
	}
};
