//=========================================================
//	TITLE:		Bound Tree 
//				Copyright (C) ClockWork Group
//				Beer-Sheva, Israel
//	MODULE:		BoundTree.h
//	PURPOSE:	Interface of the BoundTree class.
//
//	AUTHOR:		Efim Bassis
//  E-MAIL:		efim.basis@clockwork-group.com
//	NOTES:		Release 04.01.2001
//
//=========================================================
#if !defined(BOUNDTREE_H)
#define BOUNDTREE_H


#if !defined(NULL)
# define NULL 0x00000000
#endif

//          Scheme Structure of BoundTree
//
//                  ---
//                 |   | 
//          parent |   |
//                 |   |     
//                  ---      
//                  /|\               <- previous --  
//                   |              /    sibling     \
//                  ---           ---               ---
//                 |   |         |   |             |   |
//      'this'     |   |------->>|   |----------->>|   | 
// (is also chield |   |         |   |             |   |         
//    of parent)    ---           ---               ---
//                   |              \               /
//		             |                 --- next -->
//                  \|/                  sibling
//                  ---
//                 |   |
//          chield |   |
//                 |   |
//                  ---


template <class T>
class BoundTree
{
public:
	BoundTree():ownParent(NULL),
				ownChield(NULL),
				prevSibling(NULL),
				nextSibling(NULL) {}

	BoundTree(T item, 
				BoundTree<T>* parent = NULL,
				BoundTree<T>* chield = NULL, 
				BoundTree<T>* sibling = NULL);

	virtual ~BoundTree() { Release(); }

	T data; // public data of tree node

	BoundTree<T>*	Root();
	BoundTree<T>*	Parent() const;
	BoundTree<T>*	Chield() const;
	BoundTree<T>*	Previous() const;
	BoundTree<T>*	Next() const;
	BoundTree<T>*	First();
	BoundTree<T>*	Last();

	BoundTree<T>*	Chield(BoundTree<T> *bTree);
	BoundTree<T>*	Insert(BoundTree<T> *bTree);
	BoundTree<T>*	NextTo(BoundTree<T> *bTree);
	BoundTree<T>*	Replace(BoundTree<T> *bTree);
	void			Release();
	BoundTree<T>*	Copy();

private:
	void			Parent(BoundTree<T> *bTree);
	void			Previous(BoundTree<T> *bTree);
	void			Next(BoundTree<T> *bTree);

private:
	BoundTree<T>*	ownParent; //pointer to parent
	BoundTree<T>*	ownChield; //pointer to chield (each parent can have only one chield)
	BoundTree<T>*	prevSibling; //pointer to previous sibling
	BoundTree<T>*	nextSibling; //pointer to next sibling
};

template <class T>
BoundTree<T>::BoundTree
(
 T item, 
 BoundTree<T>* parent,
 BoundTree<T>* chield, 
 BoundTree<T>* sibling
)
{
	data = item;
	ownParent = parent;
	ownChield = chield;
	prevSibling = NULL;
	nextSibling = sibling;
	if (parent)
		parent ->Chield(this);
	if (sibling)
		sibling ->Previous(this);
	if (chield)
		chield ->Parent(this);
}

template <class T>
BoundTree<T>* BoundTree<T>::Root()
{
	BoundTree<T> *parent;

	if (ownParent)
		parent = ownParent ->Root();
	else
		parent = this;
	return parent;

}

template <class T>
BoundTree<T>* BoundTree<T>::Parent() const 
{
	BoundTree<T> *parent;

	if (prevSibling)
		parent = prevSibling ->Parent();
	else
		parent = ownParent;
	return parent; 
}

template <class T>
BoundTree<T>* BoundTree<T>::Chield() const { return ownChield; }

template <class T>
BoundTree<T>* BoundTree<T>::Previous() const { return prevSibling; }

template <class T>
BoundTree<T>* BoundTree<T>::Next() const { return nextSibling; }

template <class T>
BoundTree<T>* BoundTree<T>::First()
{
	BoundTree<T> *prev;

	if (prevSibling)
		prev = prevSibling ->First();
	else
		prev = this;
	return prev;
}

template <class T>
BoundTree<T>* BoundTree<T>::Last()
{
	BoundTree<T> *next;

	if (nextSibling)
		next = nextSibling ->Last();
	else
		next = this;
	return next;
}

template <class T>
BoundTree<T>* BoundTree<T>::Chield(BoundTree<T> *p)
{ 
	BoundTree<T>* begin;

	if (p) 
	{ 
		if (ownChield) 
		{
			begin = ownChield;
			p ->Next(begin);
			begin ->Previous(p);
			begin ->Parent(this);
		}
		ownChield = p;
		p ->Parent(this);
	}
	return p;
}

template <class T>
BoundTree<T>* BoundTree<T>::Insert(BoundTree<T>* p)
{
	BoundTree<T> *t;

	if (p) 
	{
		t = Previous();
		if (t) 
		{ // if 'this' is not chield 'p' can be inserted 
			t ->Next(p);
			p ->Parent(ownParent);
			p ->Previous(t);
			p ->Next(this);
			Previous(p);
		}
		else
		{
			ownParent ->Chield(p);
			p ->Parent(ownParent);
			p ->Next(this);
			Parent(NULL);
			Previous(p);
		}
	}
	return p;
}

template <class T>
BoundTree<T>* BoundTree<T>::NextTo(BoundTree<T> *p)
{
	BoundTree<T> *t;

	if (p) 
	{
		t  = Next();
		if (t) 
			t ->Previous(p);
		p ->Next(t);
		Next(p);
		p ->Previous(this);
	}
	return p;
}

template <class T>
BoundTree<T>* BoundTree<T>::Replace(BoundTree<T> *p)
{
	if (p)
	{
		Release();
		data = p ->data;
		ownChield = p ->Chield();
	}
	return this;
}

template <class T>
void BoundTree<T>::Release()
{
	if (ownChield) 
	{
		ownChield ->Release();
		delete ownChield;
		ownChield = NULL;
	}
	if (nextSibling)
	{
		nextSibling ->Release();
		delete nextSibling;
		nextSibling = NULL;
	}
}

template <class T>
BoundTree<T>* BoundTree<T>::Copy()
{
	BoundTree<T>* chield;
	BoundTree<T>* next;

	BoundTree<T> *newPtr = BoundTreeNode(data);
	if (ownChield)
		chield = ownChield ->Copy();
	else
		chield = NULL;
	if (nextSibling) 
		next = nextSibling ->Copy();
	else
		next = NULL;

	if (chield)
	{
		chield ->Parent(newPtr);
		newPtr ->Chield(chield);
	}
	if (next)
	{
		next ->Previous(newPtr);
		newPtr ->Next(next);
	}

	return newPtr;
}

template <class T>
void BoundTree<T>::Parent(BoundTree<T> *p) { ownParent = p; }

template <class T>
void BoundTree<T>::Previous(BoundTree<T>* p) { prevSibling = p; }

template <class T>
void BoundTree<T>::Next(BoundTree<T> *p) { nextSibling = p; }


template <class T>
BoundTree<T>* BoundTreeNode
(
 T item, 
 BoundTree<T>* parent = NULL,
 BoundTree<T>* chield = NULL, 
 BoundTree<T>* sibling = NULL
)
{
	BoundTree<T> *p = new BoundTree<T>(item, parent, chield, sibling);
	return p;
}

template <class T> 
void CountTie(BoundTree<T> *tree, int &count)
{
	if (tree)
	{
		count++;
		CountTie(tree ->Chield(), count);
		CountTie(tree ->Next(), count);
	}
}

template <class T>
void CountLeaf(BoundTree<T> *tree, int &count)
{
	if (tree)
	{
		CountLeaf(tree ->Chield(), count);
		CountLeaf(tree ->Next(), count);

		if (!tree ->Chield() && !tree ->Next())
			count++;
	}
}
#endif