/* 一般樹（使用二叉樹方法實現的一般樹）
 * 函數傳回指針是為效率問題，得到指針只可用于訪問其數據成員，不可在外部調用 delete 釋放，要刪除樹節點請調用本類的 delete 函數
 */

#ifndef GENERAL_TREE_CLASS
#define GENERAL_TREE_CLASS

#include "treenode.h"
#include "dclinkedlist.h"	// 鏈表，用于遍歷

enum NextItemPos {TI_CURRENT, TI_ROOT, TI_CHILD, TI_NEXT, TI_PARENT /*TI_PREVIOUS*/};
enum InsertItemPos {TI_FIRST, TI_LAST};
enum IterMathod {TI_PREORDER, TI_POSTORDER, TI_LEVERORDER};	// 遍歷方法（前序、后序和層次）

template <class T>
class GenTree
{
private:
	// 指向樹根及當前節點的指針
	TreeNode<T> *root;
	TreeNode<T> *current;
	
	// 樹中數據項個數
	int size;

	// 上次選擇的遍歷方法
	enum IterMathod itermathod;
	// 用于遍歷的堆棧
	DCLinkedList < TreeNode<T>* > iterstack;
	// 用于遍歷的函數
	TreeNode<T> *GoFarLeft(TreeNode<T> *t); // 用于后序遍歷
	void GoAllChild(TreeNode<T> *t);		// 用于層次遍歷 	

	// 用于復制構造函數及賦值運算符
	TreeNode<T> *CopyTree(TreeNode<T> *t);
	
public:
	// 構造函數，析構函數
	GenTree(void);
	GenTree(const GenTree<T>& tree);
	~GenTree(void);
	
	// 賦值運算符
	GenTree<T>& operator= (const GenTree<T>& rhs);
	
// 返回匹配元素（得到指針后不可在外部 delete，否則會造成樹結構損壞）
//	TreeNode<T> *Find(const T& item);
	/*
		TI_FIRST	// 插入兄弟節點的頭部
		TI_LAST		// 插入兄弟節點的末尾
	*/
	TreeNode<T> *Insert(const T& item, TreeNode<T>* parent, enum InsertItemPos insertpos = TI_LAST);
	void Delete(TreeNode<T> *t);	// 如果刪除了 current 指向的節點，會導致 current = NULL
	void ClearTree(void);
	bool TreeEmpty(void) const;
	int TreeSize(void) const;		// 樹的總節點數

	// 遍歷樹的函數
	// 切記：遍歷過程中不可刪除樹節點（遍歷過程中只可訪問和修改樹節點的數據成員），否則結果無法預料
	void Reset(enum IterMathod itm = TI_POSTORDER);
	void Next(void);
	bool EndOfList(void) const;
	
	// 樹的特殊方法（得到指針后不可在外部 delete，否則會造成樹結構損壞）
	/*	
		TI_CURRENT	// 取得當前節點
		TI_ROOT		// 取得樹根節點
		TI_CHILD	// 取得當前節點的第一個子節點
		TI_NEXT		// 取得當前節點的下一個兄弟節點
		TI_PREVIOUS	// 取得當前節點的上一個兄弟節點(sorry, not implement) 
		TI_PARENT	// 取得當前節點的父節點	
	*/
	TreeNode<T> *GetNext(enum NextItemPos nextpos);
};

// 構造函數，初始化 root、current 為空，size 為 0，itermathod 為后序遍歷
template <class T>
GenTree<T>::GenTree(void):root(NULL), current(NULL), size(0), itermathod(TI_POSTORDER)
{}

// 復制構造函數
template <class T>
GenTree<T>::GenTree(const GenTree<T>& tree)
{
    // 將 tree 復制到當前對象，分配 current、size 和 itermathod
    root = CopyTree(tree.root);
    current = root;
    size = tree.size;
	itermathod = tree.itermathod;
}

// 析構函數
template <class T>
GenTree<T>::~GenTree(void)
{
    ClearTree();
}

// 刪除以 t 為根的子樹
template <class T>
void GenTree<T>::Delete(TreeNode<T> *t)
{
    if (t != NULL)
    {
        Delete(t->left);
        Delete(t->right);
		if (t == current)
			current = NULL;
        delete t;
		size--;
	}
}

// 復制樹 t 并使其存儲在當前對象中
template <class T>
TreeNode<T> *GenTree<T>::CopyTree(TreeNode<T> *t)
{
    TreeNode<T> *newlptr, *newrptr, *newNode;
   
    // 如果樹分支為空，返回 NULL
    if (t == NULL)
        return NULL;
        
    // 復制樹 t 的左子樹并將其根分配給 newlptr
    if (t->left != NULL) 
        newlptr = CopyTree(t->left);
    else
        newlptr = NULL;
 
    // 復制樹 t 的右子樹并將其根分配給 newrptr
    if (t->right != NULL) 
        newrptr = CopyTree(t->right);
    else
        newrptr = NULL;
 
    // 為當前根節點分配存儲器并將其數據值和指針分配給它的子樹，構造父指針，返回新指針
    newNode = new TreeNode<T>(t->data, newlptr, newrptr);
	if (newlptr != NULL)
	{
		newlptr->parent = newNode;
		TreeNode<T> *rptr = newlptr->right;
		while (rptr != NULL)
		{
			rptr->parent = newNode;
			rptr = rptr->right;
		}
	}

    return newNode;
}

// 賦值運算符
template <class T>
GenTree<T>& GenTree<T>::operator= (const GenTree<T>& rhs)
{
    // 不能將樹復制到自身
    if (this == &rhs)
        return *this;
        
    // 清除當前樹，將新樹復制到當前對象
    ClearTree();
    root = CopyTree(rhs.root);
    
    // 將 current 指針指向 root 并設置樹的 size 值及遍歷方法
    current = root;
    size = rhs.size;
	itermathod = rhs.itermathod;
    
    // 返回當前對象的指針
    return *this;
}

// 刪除樹中的所有節點
template <class T>
void GenTree<T>::ClearTree(void)
{
    Delete(root);
    root = current = NULL;
    size = 0;
}

// 指示樹是否為空
template <class T>
bool GenTree<T>::TreeEmpty(void) const
{
    return (size == 0);
}

// 返回樹中的數據項個數
template <class T>
int GenTree<T>::TreeSize(void) const
{
    return size;
}

// 返回從 t 開始的子樹左邊分支最左下方節點的地址，并將經過節點的地址壓入棧中
template <class T>
TreeNode<T> *GenTree<T>::GoFarLeft(TreeNode<T> *t)
{
   // 若 t 為 NULL，則返回 NULL
   if (t == NULL)
      return NULL;
      
   // 遍歷樹的最左邊，往棧中壓入每個節點的地址直到遇到左指針為 NULL 的節點
   // 返回指向該節點的指針
   while (t->left != NULL)
   {
      iterstack.InsertFront(t);
      t = t->left;
   }
   return t;
}

// 取得 t 的所有孩子并依次加入鏈表末尾
template <class T>
void GenTree<T>::GoAllChild(TreeNode<T> *t)
{
	if (t != NULL)
	{
		TreeNode<T> *rptr = t->left;
		while (rptr != NULL)
		{
			iterstack.InsertRear(rptr);
			rptr = rptr->right;
		}
	}
}

// 以選定的遍歷順序遍歷整個樹
template <class T>
void GenTree<T>::Reset(enum IterMathod itm)
{
	itermathod = itm;
	iterstack.ClearList();

	switch (itm)
	{
		case TI_PREORDER:
			current = root;
			break;
		case TI_POSTORDER:
			current = GoFarLeft(root);
			break;
		case TI_LEVERORDER:
			current = root;
			GoAllChild(root);
			break;
		default:
			throw "GenTree::Reset: Unknown iterator method";
	}
}

// 按指定遍歷順序將 current 設為下一節點
template <class T>
void GenTree<T>::Next(void)
{
	if (current == NULL)
		return;

	switch (itermathod)
	{
		case TI_POSTORDER:	// 前序遍歷
			if (current->right != NULL)
				current = GoFarLeft(current->right);
			else if (!iterstack.ListEmpty())
			{
				current = iterstack.Data();
				iterstack.DeleteFront();
			}
			else
				current = NULL;	// 遍歷結束
			break;
		case TI_PREORDER:	// 后序遍歷
			if (current->left != NULL)
			{
				iterstack.InsertFront(current);
				current = current->left;
			}
			else if (current->right != NULL)
				current = current->right;
			else if (!iterstack.ListEmpty())
			{
				current = iterstack.Data();
				iterstack.DeleteFront();
				current = current->right;
			}
			else
				current = NULL;
			break;
		case TI_LEVERORDER:	// 層次遍歷
			if (!iterstack.ListEmpty())
			{
				iterstack.Reset();
				current = iterstack.Data();
				iterstack.DeleteFront();
				GoAllChild(current);
			}
			else
				current = NULL;
			break;
		default:
			throw "GenTree::Next: Unknown iterator method";
	}
}

// 用來終止循環
template <class T>
bool GenTree<T>::EndOfList(void) const
{
	return (current == NULL);
}

template <class T>
TreeNode<T> *GenTree<T>::Insert(const T& item, TreeNode<T>* parent, enum InsertItemPos insertpos)
{
	TreeNode<T> *newNode = new TreeNode<T>(item);

	// 沒有 parent 的節點，只能是根節點
	if (parent == NULL)
	{
		ClearTree();
		root = current = newNode;
		size++;
		return newNode;
	}

	current = newNode;
	size++;
	switch (insertpos)
	{
		case TI_FIRST:
			newNode->right = parent->left;
			parent->left = newNode;
			break;
		case TI_LAST:
			{
				TreeNode<T> *rptr = parent->left;
				if (rptr == NULL)	// 這個節點還沒有孩子
				{
					parent->left = newNode;
					break;
				}
				while (rptr->right != NULL)
					rptr = rptr->right;
				rptr->right = newNode;
			}
			break;
		default:
			throw "GenTree::Insert: Unknown insert pos";
	}
	return newNode;
}

template <class T>
TreeNode<T> *GenTree<T>::GetNext(enum NextItemPos nextpos)
{
	if (nextpos == TI_ROOT)
		return root;
	else if (current == NULL)
		return NULL;
	
	switch (nextpos)
	{
		case TI_CURRENT:
			return current;
		case TI_CHILD:
			return current->left;
		case TI_NEXT:
			return current->right;
		case TI_PARENT:
			return current->parent;
		default:
			throw "GenTree::GetNext: Unknown next pos";
	}
}

#endif  // GENTREE_CLASS