// ParTree.h: interface for the ParTree class.
//
//////////////////////////////////////////////////////////////////////

#if !defined(AFX_PARTREE_H__CBF85D1A_1086_4E89_9CB6_BEE7FBE72DD0__INCLUDED_)
#define AFX_PARTREE_H__CBF85D1A_1086_4E89_9CB6_BEE7FBE72DD0__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

#include "ParTreeNode.h"

template<class T>
class ParTree  
{
public:
	ParTreeNode<T>* array;							//存儲樹結點的數組
	int	Size;										//數組大小
	ParTreeNode<T>*	Find(ParTreeNode<T>* node)const;//查找node結點的根結點
	ParTreeNode<T>*	FindPC(ParTreeNode<T>* node)const;//壓縮路徑方法查找node結點的根結點
	ParTree(const int size);						//構造函數
	virtual ~ParTree();								//析構函數
	void Union(int i,int j);						//把下標為i，j的結點合并為一棵子樹
	bool Different(int i,int j);					//判定下標為i，j的結點是否在一棵樹中
};

template <class T>
ParTree<T>::ParTree(const int size)
{
	Size=size;
	array=new ParTreeNode<T>[size];
}

template <class T>
ParTree<T>::~ParTree()
{
	delete []array;
}

template <class T>
ParTreeNode<T>*	ParTree<T>::Find(ParTreeNode<T>* node) const
{
	ParTreeNode<T>* pointer=node;
	while(pointer->getParent()!=NULL)
		pointer=pointer->getParent();
	return pointer;
}

template <class T>
ParTreeNode<T>*	ParTree<T>::FindPC(ParTreeNode<T>* node) const
{
	if(node->getParent()==NULL)
		return node;
	node->setParent(FindPC(node->getParent()));
	return node->getParent();
}

template<class T>
bool ParTree<T>::Different(int i,int j)
{
	ParTreeNode<T>* pointeri=Find(&array[i]);		//找到結點i的根
	ParTreeNode<T>* pointerj=Find(&array[j]);		//找到結點j的根
	return pointeri!=pointerj;
}

template<class T>
void ParTree<T>::Union(int i,int j)
{
	ParTreeNode<T>* pointeri=Find(&array[i]);		//找到結點i的根
	ParTreeNode<T>* pointerj=Find(&array[j]);		//找到結點j的根
	if(pointeri!=pointerj)
	{
		if(pointeri->getCount()>=pointerj->getCount())
		{
			pointerj->setParent(pointeri);
			pointeri->setCount(pointeri->getCount()+pointerj->getCount());
		}
		else
		{
			pointeri->setParent(pointerj);
			pointerj->setCount(pointeri->getCount()+pointerj->getCount());
		}
	}

}


#endif // !defined(AFX_PARTREE_H__CBF85D1A_1086_4E89_9CB6_BEE7FBE72DD0__INCLUDED_)