//-----------------------------------------------------------------------------+
// Copyright (C), 1998-2007, Beijing Tangent Software Co. Ltd.
// = FileName	:   TTree.h
// = Version	:   ver2.0
// = Author		:   xlc
// = CreateDate	:   2002-09-09
// = Description:   类的声明
// = Maintainers: 
//                  
//-----------------------------------------------------------------------------+
#ifndef _TTREE_H_
#define _TTREE_H_

#ifndef _TTABLE_H_
#include "TTable.h"
#endif

#ifndef _TFOREST_H_
#include "TForest.h"
#endif

template<class T> class TForest;

template <class T>class TTree
{
public:
	TTree(const TTree<T>* tree);
	
	TTree(TTree<T> *pParentTree = NULL);
	
	virtual ~TTree();

	//深拷贝
	TTree<T>& operator=(const TTree<T>&tree);

	//增加子树的四个一般方式，如直接在子森林中增加，则应手动设置子树的pParent.
	void AppendChild(TTree<T>*pTree = NULL);
	
	void AppendForest(TForest<T>&trees);
	
	void InsertChild(long i,TTree<T>*pTree = NULL);
	
	void InsertFirstChild(TTree<T>*pTree = NULL);
	
	//结点数据
	T& NodeData();

	TTree<T>* &Parent();
	
	TForest<T>& ChildForest();

	//直接操作子森林的一般方式
	TForest<T>* operator->();

	const T& GetNodeData()const;
	
	const TTree<T>* GetParent()const;

	const TForest<T>& GetChildForest()const;

	long GetChildNum()const;

	bool IsParent()const;

	bool IsLeaf()const;
	
	bool IsRoot()const;
	
	bool IsChild()const;
	
	bool IsChildOf(TTree<T>* pTree)const;

	bool operator==(const TTree<T>&t)const;
	
	bool operator!=(const TTree<T>&t)const;
	
	bool operator>(const TTree<T>&t)const;
	
	bool operator<(const TTree<T>&t)const;

	//到根结点，如果本身为根则返回this;
	TTree<T>*  GoRoot()const;
	
	//到父结点，如无则返回NULL;
	TTree<T>* GoUp()const;
	
	//到当前结点，超出范围则返回NULL
	TTree<T>* GoDown();
	
	//到第一个子结点，无子结点则返回NULL
	TTree<T>* GoDownFirst();
	
	//到最后一个子结点，无子结点则返回NULL
	TTree<T>* GoDownLast();
	
	//到第i个子结点，超出范围则返回NULL
	TTree<T>* GoDown(long i);
	
	//到下一个兄弟结点，最后一个则返回NULL
	TTree<T>* GoRight();
	
	//到前一个兄弟结点，第一个则返回NULL
	TTree<T>* GoLeft();

	long GetIndexInForest()const;
	
	long FindTreeNode(const T&t,TTable<TTree<T>* >&trees);
	
	void GetPath(TTable<long>&path)const;
	
	long GetLeafNum();
	
	void GetLeafNodes(TTable<TTree<T>*> &leafs);
	
	TTree<T>* GetSameParent(TTree<T>*pTree);

protected: 
	
	T data;				//结点数据
	
	TTree<T>* pParent;	//父树
	
	TForest<T> forest;	//子树森林
};

template<class T>
TTree<T>::TTree(TTree<T> *pParentTree)
: pParent(pParentTree)
{

}

template<class T>
TTree<T>::TTree(const TTree<T>* tree)
: pParent(NULL)
{
	*this = tree;
}

template<class T>
TTree<T>::~TTree()
{

}

template<class T>
void TTree<T>::AppendForest(TForest<T>&trees)
{
	trees.SetParent(this);
	forest.Conbine(trees);
}

template<class T>
T& TTree<T>::NodeData()
{
	return data;
}

template<class T>
TTree<T>* & TTree<T>::Parent()
{
	return pParent;
}

template<class T>
TForest<T>& TTree<T>::ChildForest()
{
	return forest;
}

//直接操作子森林的一般方式
template<class T>
TForest<T>* TTree<T>::operator->()
{
	return &forest;
}

template<class T>
const T& TTree<T>::GetNodeData()const
{
	return data;
}

template<class T>
const TForest<T>& TTree<T>::GetChildForest()const
{
	return forest;
}

template<class T>
const TTree<T>* TTree<T>::GetParent()const
{
	return pParent;
}

template<class T>
long TTree<T>::GetChildNum()const
{
	return forest.GetLength();
}

template<class T>
bool TTree<T>::IsParent()const
{
	return !forest.IsEmpty();
}

template<class T>
bool TTree<T>::IsLeaf()const
{
	return !IsParent();
}

template<class T>
bool TTree<T>::IsRoot()const
{
	return GetParent() == NULL;
}

template<class T>
bool TTree<T>::IsChild()const
{
	return GetParent() != NULL;
}

template<class T>
bool TTree<T>::operator == (const TTree<T> &t)const
{
	return data == t.GetNodeData() && this->GetForest() == t.GetChildForest();
}

template<class T>
bool TTree<T>::operator != (const TTree<T>&t)const
{
	return !(*this == t);
}

template<class T>
bool TTree<T>::operator>(const TTree<T>&t)const
{
	return data > t.GetNodeData();
}

template<class T>
bool TTree<T>::operator<(const TTree<T>&t)const
{
	return data < t.GetNodeData();
}

template<class T> 
long TTree<T>::GetIndexInForest()const
{
	return IsChild() ? GetParent()->GetChildForest().Find((TTree<T>*)this) : -1;
}

template<class T>
void TTree<T>::GetLeafNodes(TTable<TTree<T>*>&leafs)
{
	if (IsLeaf())
	{
		leafs.AddTail(this);
	}
	else
	{
		forest.GetLeafNodes(leafs);
	}
}

template<class T>
long TTree<T>::GetLeafNum()
{
	return IsLeaf() ? 1 : forest.GetLeafNum();
}

template<class T>
void TTree<T>::InsertChild(long i,TTree<T>*pTree)
{
	if (pTree == NULL)
	{
		pTree = new TTree<T>;
	}

	forest.Insert(i,pTree);
	pTree->Parent() = this;
}

template<class T>
void TTree<T>::InsertFirstChild(TTree<T>*pTree)
{
	if (pTree == NULL)
	{
		pTree = new TTree<T>;
	}

	forest.InsertHead(pTree);
	pTree->Parent() = this;
}

template<class T>
void TTree<T>::AppendChild(TTree<T>*pTree)
{
	if (pTree == NULL)
	{
		pTree = new TTree<T>;
	}

	forest.AddTail(pTree);
	pTree->Parent() = this;
}

template<class T>
void TTree<T>::GetPath(TTable<long>&path)const
{
	if (IsChild())
	{
		GetParent()->GetPath(path);
		path.AddTail(GetIndexInForest());
	}
}

template<class T>
bool TTree<T>::IsChildOf(TTree<T>*pTree)const
{
	if (!IsChild())
	{
		return false;
	}

	if (GetParent() == pTree)
	{
		return true;
	}
	else 
	{
		return GetParent()->IsChildOf(pTree);
	}
}

template<class T>
TTree<T>* TTree<T>::GetSameParent(TTree<T>*pTree)
{
	TList<TTree<T>* > path1,path2;
	GetPath(path1);

	pTree->GetPath(path2);
	for (path1.MoveToFirst(),path2.MoveToFirst();
		!path1.IsOut() && !path2.IsOut() && path1.GetCurData() != path2.GetCurData();
		path1.MoveToNext(),path2.MoveToNext());
	{
		path1.MoveToPre();
	}

	return path1.GetCurData();
}

template<class T>
long TTree<T>::FindTreeNode(const T&t,TTable<TTree<T>*>&trees)
{
	if (data == t)
	{
		trees.AddTail(this);
	}

	forest.FindTree(t,trees);

	return trees.GetLength();
}

template<class T>
TTree<T>* TTree<T>::GoRoot()const
{
	TTree<T>*pTree = (TTree<T>*)this;
	while (pTree->IsChild())
	{
		pTree = pTree->GoUp();
	}

	return pTree;
}

template<class T>
TTree<T>* TTree<T>::GoUp()const
{
	return (TTree<T>*)GetParent();
}

template<class T>
TTree<T>* TTree<T>::GoDown()
{
	return forest.GetCurTree();
}

template<class T>
TTree<T>* TTree<T>::GoDownFirst()
{
	forest.MoveToFirst();
	return forest.GetCurTree();
}

template<class T>
TTree<T>* TTree<T>::GoDownLast()
{
	forest.MoveToLast();
	return forest.GetCurTree();
}

template<class T>
TTree<T>* TTree<T>::GoDown(long i)
{
	forest.MoveTo(i);
	return forest.GetCurTree();
}

template<class T>
TTree<T>* TTree<T>::GoLeft()
{
	if (IsRoot())
	{
		return NULL;
	}

	TForest<T> &f = Parent()->ChildForest();
	if (f.GetCurTree() != this)		//所在子树森林的游标未指向本树
	{
		f.MoveTo(GetIndexInForest());
	}
	f.MoveToPre();

	return f.GetCurTree();
}

template<class T>
TTree<T>* TTree<T>::GoRight()
{
	if (IsRoot())
	{
		return NULL;
	}

	TForest<T> &f = Parent()->ChildForest();
	if (f.GetCurTree() != this)		//所在子树森林的游标未指向本树
	{
		f.MoveTo(GetIndexInForest());
	}

	f.MoveToNext();
	return f.GetCurTree();
}

template<class T>
TTree<T>& TTree<T>::operator=(const TTree<T>&tree)
{
	data = tree.GetNodeData();
	forest = tree.GetChildForest();
	forest.SetParent(this);

	return *this;
}

#endif