//-----------------------------------------------------------------------------+
// Copyright (C), 1998-2007, SH Software Co. Ltd.
// = FileName	:   Tree.h
// = Version	:   ver2.0
// = Author		:   zjq
// = CreateDate	:   2002-09-09
// = Description:   类的声明
// = Maintainers: 
//                  
//-----------------------------------------------------------------------------+
#ifndef _TREE_H_
#define _TREE_H_

#ifndef _TABLE_H_
#include "Table.h"
#endif

#ifndef _FOREST_H_
#include "Forest.h"
#endif

template<class T> class Forest;

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

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

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

	Tree<T>* &Parent();
	
	Forest<T>& ChildForest();

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

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

	const Forest<T>& GetChildForest()const;

	long GetChildNum()const;

	bool IsParent()const;

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

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

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

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

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

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

}

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

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

}

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

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

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

template<class T>
Forest<T>& Tree<T>::ChildForest()
{
	return forest;
}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

template<class T>
Tree<T>* Tree<T>::GetSameParent(Tree<T>*pTree)
{
	List<Tree<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 Tree<T>::FindTreeNode(const T&t,Table<Tree<T>*>&trees)
{
	if (data == t)
	{
		trees.AddTail(this);
	}

	forest.FindTree(t,trees);

	return trees.GetLength();
}

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

	return pTree;
}

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

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

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

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

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

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

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

	return f.GetCurTree();
}

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

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

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

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

	return *this;
}

#endif