/*
*file: AVLTree.cpp
*date: 2004.12.9
*author: 
*description: 
*	A self-balanced tree with balance-factorial.
*	This file is the function bodies of the template.
*	See "AVLTree.h" to get the information of the declarations.
*/

#ifndef __AVLTree_cpp__
#define __AVLTree_cpp__

#include <iostream>
#include <exception>
#include <string>
#include <typeinfo>
#include "AVLTree.h"

using std::string;
using std::cerr;
using std::cout;

template<class KeyType>
AVLTree<KeyType>::AVLTree(KeyType key):
	_key(key),_bf(0),h(1),_lChild(0),_rChild(0)
{
	;
}//~AVLTree(KeyType key);

template<class KeyType>
AVLTree<KeyType>::~AVLTree()
{
	#ifdef debug
		cerr<<"~AVLTree() _key:"<<_key<<endl;
	#endif
	if(_lChild) delete _lChild;
	if(_rChild) delete _rChild;
}//~~AVLTree()

template<class KeyType>
inline KeyType AVLTree<KeyType>::key() const
{
	return _key;
}//~key()

template<class KeyType>
inline void  AVLTree<KeyType>::key(KeyType k)
{
	_key=k;
}//~key(KeyType)

template<class KeyType>
void  AVLTree<KeyType>::out()
{
	reH();
	if(hasLChild()) _lChild->out();
	cout<<"Key:"<<_key<<" BF:"<<_bf<<" H:"<<h<<endl;
	if(hasRChild()) _rChild->out();
}//~key(KeyType)

template<class KeyType>
int  AVLTree<KeyType>::reH()
{
	if(hasNoChildren()) h=1;
	else h=1+(((hasLChild()?_lChild->reH():0)>(hasRChild()?_rChild->reH():0))?_lChild->h:_rChild->h);
	_bf=(hasLChild()?_lChild->h:0)-(hasRChild()?_rChild->h:0);
	return h;
}

template<class KeyType>
int AVLTree<KeyType>::insert(KeyType k,AVLTree<KeyType>*& gr)
{
	if(k<_key)
	{
		hasLChild()?(_lChild->insert(k,_lChild)):(_lChild=new AVLTree<KeyType>(k),_bf++);
	}
	else
	{
		hasRChild()?(_rChild->insert(k,_rChild)):(_rChild=new AVLTree<KeyType>(k),_bf--);
	}
	reH();
	if(_bf==2)
	{
		if(_lChild->_bf<0) _lChild->renodeLeft(_lChild,_lChild->_rChild);
		reH();
		renodeRight(gr,_lChild);
	}
	if(_bf==-2)
	{
		if(_rChild->_bf>0) _rChild->renodeRight(_rChild,_rChild->_lChild);
		reH();
		renodeLeft(gr,_rChild);
	}
	reH();
	return _bf;
}//~insert(KeyType)

template<class KeyType>
bool AVLTree<KeyType>::del(KeyType key,AVLTree*& gr)
{
	if(key==_key)
	{
		delbyCopy(gr);
		return true;
	}
	else if(key>_key)
	{
		_rChild->del(key,_rChild);
	}
	else if(key<_key)
	{
		_lChild->del(key,_lChild);
	}
	reH();
	if(_bf==2)
	{
		if(_lChild->_bf<0) _lChild->renodeLeft(_lChild,_lChild->_rChild);
		reH();
		renodeRight(gr,_lChild);
	}
	if(_bf==-2)
	{
		if(_rChild->_bf>0) _rChild->renodeRight(_rChild,_rChild->_lChild);
		reH();
		renodeLeft(gr,_rChild);
	}
	reH();
	return false;
}//~del(KeyType)


template<class KeyType>
void AVLTree<KeyType>::delbyCopy(AVLTree<KeyType>*& target)
{
	AVLTree<KeyType>* tmp;
	if(target->hasNoChildren())
	{
		delete target;
		target=NULL;
		return;
	}
	else if((!target->hasLChild())&&target->hasRChild())
	{
		tmp=target->_rChild;
		target->_rChild=NULL;
		delete target;
		target=tmp;
		return;
	}
	else if((!target->hasRChild())&&target->hasLChild())
	{
		tmp=target->_lChild;
		target->_lChild=NULL;
		delete target;
		target=tmp;
		return;;
	}
	else 
	{
		tmp=target->_lChild;
		AVLTree<KeyType>* tmp2;
		if(tmp!=NULL) while(tmp->_rChild->hasRChild()) tmp=tmp->_rChild;
		tmp2=tmp->_rChild;
		tmp->_rChild=tmp2->_lChild;
		tmp2->_lChild=0;
		target->key(tmp2->key());
		delete tmp2;
	}
}//~delbyCopy(AVLTree*);

template<class KeyType>
inline bool AVLTree<KeyType>::hasNoChildren()
{
	return _lChild?false:!_rChild;
}//~hasNoChildren()

template<class KeyType>
inline bool AVLTree<KeyType>::hasLChild()
{
	return _lChild?true:false;
}//~hasLChild()

template<class KeyType>
inline bool AVLTree<KeyType>::hasRChild()
{
	return _rChild?true:false;
}//~hasRChild()

template<class KeyType>
void AVLTree<KeyType>::renodeRight(AVLTree<KeyType>*& Gr,AVLTree<KeyType>* Ch/*,AVLTree<KeyType>* Pr*/)
{
	_lChild=Ch->_rChild;
	Ch->_rChild=this;
	Gr=Ch;
	ct.r++;
}//~renodeR

template<class KeyType>
void AVLTree<KeyType>::renodeLeft(AVLTree<KeyType>*& Gr,AVLTree<KeyType>* Pr/*,AVLTree<KeyType>* Ch*/)
{
	_rChild=Pr->_lChild;
	Pr->_lChild=this;
	Gr=Pr;
	ct.l++;
}//~renodeL

template<class KeyType>
inline void AVLTree<KeyType>::clearCounter()
{
	ct.r=ct.l=0;
}

template<class KeyType>
inline Counter AVLTree<KeyType>::getCounter()
{
	return ct;
}

#endif