/* BinaryTree.h vr 1.0 Beta
   @Author: flacman -- flacman@cuteam.org
   @Descripción: Arbol binario común, contiene algunos métodos extras que le pueden ayudar al programador

   Esta clase hace parte de la futura Colección de Estructuras de datos de
   ColombiaUnderground team http://www.colombiaunderground.org .
   Está prohibida la copia de cualquiera de los archivos, o de partes de los archivos sin
   hacer referencia a los autores
*/
#ifndef __CBYNARYTREE_H__
#define __CBYNARYTREE_H__

#include <stdlib.h>

#ifndef NULL
#define NULL 0
#endif

#define INORDER 10
#define PREORDER 11
#define POSORDER 12

template<class TYPE>
class CBinaryTree
{
protected:
	struct TreeNode
	{
		//Argumento de nodo
		TYPE arg;
		//Nodo anterior
		TreeNode *izq;
		//Nodo siguiente
		TreeNode *der;
	};
	TreeNode *Root;
	TreeNode *Actual;
	int GetNodeHeight(TreeNode *);
	bool EstaNodoLleno(int,TreeNode*);
	TreeNode* GetNodeFather(TreeNode* , TYPE );
	int GetNodeWeight(TreeNode*);

public:
	CBinaryTree(TYPE);
	CBinaryTree(TYPE[], int);
	~CBinaryTree(void);
	void RemoveAll( void );
	void SetDer(TYPE);
	void SetIzq(TYPE);
	void DeleteNodeAndAbove(TreeNode*);
	TreeNode* CreateNode(TYPE);
	int GetHeight(void);
	TYPE GetIzq(void);
	TYPE GetDer(void);
	TYPE GetCurrent(void);
	TYPE GetRoot(void);
	bool EstaLleno();
	bool isLeaf(TreeNode*);
	TYPE GetFather();
	TYPE* GetPath(TYPE);
	int GetWeight();
	//TYPE[] GetAll(int);

};

template<class TYPE>
CBinaryTree<TYPE>::CBinaryTree(TYPE arg)
{
	Root = Actual = CreateNode(arg);
}
template<class TYPE>
CBinaryTree<TYPE>::CBinaryTree(TYPE arg[], int tam)
{
	/*if(Root)
		RemoveAll();

	int i = 0;
	TreeNode* nodo = null;
	Cola<TreeNode*> cola;
    cola.Push( (Root = Actual = CreateNode(arg[i])) );

    while( cola.GetLenght( ))
    {
        nodo = cola.Pop( );
        nodo.SetIzq(arg[++i]);
        cola.Push( nodo.GetIzq() );
        nodo.SetDer(arg[++i]);
        cola.Push( nodo.GetDer() );
    }*/

}

template<class TYPE>
CBinaryTree<TYPE>::~CBinaryTree(void)
{
	RemoveAll();
}

template<class TYPE>
void CBinaryTree<TYPE>::RemoveAll()
{
	DeleteNodeAndAbove(Root);
}
template<class TYPE>
void CBinaryTree<TYPE>::SetIzq(TYPE arg){
	if(Actual->izq)
		DeleteNodeAndAbove(Actual->izq);
	Actual->izq = CreateNode(arg);
}

template<class TYPE>
void CBinaryTree<TYPE>::SetDer(TYPE arg){
	if(Actual->der)
		DeleteNodeAndAbove(Actual->der);
	Actual->der = CreateNode(arg);
}
//Toca revisarlo!!
template<class TYPE>
void CBinaryTree<TYPE>::DeleteNodeAndAbove(TreeNode* Del)
{
	if(Del->der)
		DeleteNodeAndAbove(Del->der);
	if(Del->izq)
		DeleteNodeAndAbove(Del->izq);
	delete Del;
}

template<class TYPE>
typename CBinaryTree<TYPE>::TreeNode*
CBinaryTree<TYPE>::CreateNode(TYPE arg){

	TreeNode* newNode = new TreeNode;
	newNode->arg = arg;
	newNode->der = NULL;
	newNode->izq = NULL;
	return newNode;
}

template<class TYPE>
int CBinaryTree<TYPE>::GetNodeHeight(TreeNode* nodo)
    {
		TreeNode* auxIzq = nodo->izq;
		TreeNode* auxDer = nodo->der;

		int a1 = ( auxIzq == NULL ) ? 0 : GetNodeHeight(auxIzq);
        int a2 = ( auxDer == NULL ) ? 0 : GetNodeHeight(auxDer);
        return ( a1 >= a2 ) ? a1 + 1 : a2 + 1;
    }

template <class TYPE>
int CBinaryTree<TYPE>::GetHeight(){
	return Root ? GetNodeHeight(Root):0;
}

template <class TYPE>
TYPE CBinaryTree<TYPE>::GetDer(){
	Actual = Actual->der;
	return Actual ? Actual->arg : NULL;
}

template <class TYPE>
TYPE CBinaryTree<TYPE>::GetIzq(){
	Actual = Actual->izq;
	return Actual ? Actual->arg : NULL;
}

template <class TYPE>
TYPE CBinaryTree<TYPE>::GetCurrent(){
	return Actual ? Actual->arg : NULL;
}

template <class TYPE>
TYPE CBinaryTree<TYPE>::GetRoot(){
	Actual = Root;
	return Actual ? Actual->arg : NULL;
}


template <class TYPE>
bool CBinaryTree<TYPE>::EstaLleno(void){
	return ( Root ) ? EstaNodoLleno( GetHeight(), Root ) : true;

}
template <class TYPE>
bool CBinaryTree<TYPE>::EstaNodoLleno( int altura, TreeNode* act )
    {
        if( isLeaf( act ) )
            return altura == 1;
		else {
		TreeNode* izqNodo = act->izq;
		TreeNode* derNodo = act->der;
			if( !izqNodo || !derNodo )
				return false;
			else
				return EstaNodoLleno( altura - 1, izqNodo ) && EstaNodoLleno( altura - 1, derNodo );
		}
    }

template <class TYPE>
bool CBinaryTree<TYPE>::isLeaf(TreeNode* node){
	if(!node)
		return false;
	if(!node->izq && !node->der)
		return true;
	return false;
}

template <class TYPE>
TYPE CBinaryTree<TYPE>::GetFather(){
	return Root && Actual ?( Actual = GetNodeFather(Root, Actual->arg))->arg:NULL;
}

template <class TYPE>
typename CBinaryTree<TYPE>::TreeNode*
CBinaryTree<TYPE>::GetNodeFather(TreeNode* ac, TYPE param){
	TreeNode* ret;
	if((ac->der && ac->der->arg == param) || (ac->izq && ac->izq->arg == param))
		return ac;
	if( ac->der )
		ret = GetNodeFather(ac->der, param);
	if( ac->izq && !ret)
		ret = GetNodeFather(ac->izq, param);
	return ret;
}
template <class TYPE>
TYPE* CBinaryTree<TYPE>::GetPath(TYPE arg){
	/*Cola<TreeNode*> cola;
	TreeNode* node = FindNode(arg);

	while(node != Root){
		cola.push(node->arg);
		node = GetNodeFather(Root, node->arg);
	}
	cola.push(node->arg);
	return cola.toArray();*/
	TYPE bla[1];
	return bla;
}
template <class TYPE>
int CBinaryTree<TYPE>::GetWeight(){
	return GetNodeWeight(Root);
}

template <class TYPE>
int CBinaryTree<TYPE>::GetNodeWeight(TreeNode* node){
	int a = ( !node->izq ) ? 0 : GetNodeWeight(node->izq);
	int b = ( !node->der ) ? 0 : GetNodeWeight(node->der);
	return a + b + 1;
}
#endif