/////////////////////////////////////////////////////////////////////////
//									/
//  Autores:	Jaime Alonso González y Pedro Hernández Arauzo		/
//  Modificado: 24-Noviembre-2002					/
//									/
//  Contenido:								/
//		Clase abstracta para árboles binarios binaryTree<T>.    /
//									/
//		Clase de árboles binarios basados en nodos. Clase	/
//		binaryTreeNode<T>.					/
//									/
//		Recorridos de arboles binarios:			       	/
//		  - preorden. Iterador preorderTreeTraversal<T>.	/
//		  - inorden. Iterador inorderTreeTraversal<T>.		/
//		  - postorden. Iterador postorderTreeTraversal<T>.	/
//		  - por niveles. Iterador levelorderTreeTraversal<T>.	/
//									/
/////////////////////////////////////////////////////////////////////////

#ifndef __BINARY_TREE_H
#define __BINARY_TREE_H

#include <assert.h>
#include <iterator.h>
#include <nodeTree.h>


namespace EstDatos 
{

  /****************************************************************/
  /*								  */
  /*	      Especificación de la clase binaryTree		  */
  /*								  */
  /****************************************************************/

  //
  // Clase binaryTree<T>
  //	Clase abstracta para árboles binarios
  //

  template <class T>
    class binaryTree {
    public:
    // operaciones
    virtual bool	    isEmpty	 () const = 0;
    /* Produce:  cierto si el árbol receptor es el árbol vacío.  */
    virtual binaryTree<T>&  left	 () const = 0;
    /* Produce:  el subárbol izquierdo del árbol receptor.  */
    virtual binaryTree<T>&  right	 () const = 0;
    /* Produce:  el subárbol derecho del árbol receptor.  */
    virtual T		    labelRoot    () const = 0;
    /* Produce:  la etiqueta de la raíz del árbol receptor.  */
    virtual void	    setLabelRoot (const T & value) = 0;
    /* Necesita: un valor de tipo T.
       Modifica: la etiqueta de la raíz del árbol receptor al valor dado. */
    virtual void	    setLeft	 (const binaryTree<T> & left) = 0;
    /* Necesita: un árbol binario, left.
       Modifica: el subárbol izquierdo del árbol receptor a left.  */
    virtual void	    setRight	 (const binaryTree<T> & right) = 0;
    /* Necesita: un árbol binario, right.
       Modifica: el subárbol derecho del árbol receptor a right.  */
  };


  /****************************************************************/
  /*								  */
  /*	  Especificificación de la clase binaryTreeNode     	  */
  /*								  */
  /****************************************************************/

  //
  // Clase binaryTreeNode<T>
  //	Clase de árboles binarios etiquetados
  //	con elementos de tipo T.
  //

  template <class T>
    class inorderTreeTraversal;
  template <class T>
    class postorderTreeTraversal;
  template <class T>
    class preorderTreeTraversal;
  template <class T>
    class levelorderTreeTraversal;

  template <class T>
    class binaryTreeNode : public binaryTree<T> {

    // clases amigas
    friend class inorderTreeTraversal<T>;
    friend class postorderTreeTraversal<T>;
    friend class preorderTreeTraversal<T>;
    friend class levelorderTreeTraversal<T>;
    friend istream & operator >> <T> (istream & in, binaryTreeNode<T> & t);
    /* Necesita: un stream de entrada con las secuencias en preorden y
       en inorden (entre paréntesis) correspondientes al árbol
       a leer y un árbol binario. Las etiquetas deben ser
       distintas dos a dos.
       Modifica: el árbol con el valor del árbol que se lee del stream. */
    friend ostream & operator << <T> (ostream & out,
				      const binaryTreeNode<T> & t);
    /* Necesita: un stream de salida y un arbol binario.
       Modifica: el stream de salida escribiendo en él el árbol dado.
       Para dar el árbol se dan, entre paréntesis, las secuencias
       correspondientes a los recorridos en preorden e inorden. */
    friend istream & operator >> <T> (istream & in, binaryTreeNode<T> * & t);
    friend ostream & operator << <T> (ostream & out, binaryTreeNode<T> * t);

    public:
    // constructores
    binaryTreeNode	();
    binaryTreeNode	(const T & value);
    binaryTreeNode	(const T & value,
			 const binaryTreeNode<T> & left,
			 const binaryTreeNode<T> & right);
    binaryTreeNode	(const binaryTreeNode<T> & source);

    // destructor
    ~binaryTreeNode	();

    // asignación
    binaryTreeNode<T> & operator = (const binaryTreeNode<T> & source);

    // operaciones
    bool		isEmpty		() const;
    binaryTreeNode<T>&	left		() const;
    binaryTreeNode<T>&	right		() const;
    T			labelRoot      	() const;
    void		setLabelRoot	(const T & value);
    void		setLeft		(const binaryTree<T> & left);
    void		setRight	(const binaryTree<T> & right);

    protected:
    // area de datos
    nodeTree<T> * ptrToRootNode;

    // operación interna
    binaryTreeNode	(nodeTree<T> * root);
  };


  /****************************************************************/
  /*								  */
  /*	Especificación de la clase inorderTreeTraversal     	  */
  /*								  */
  /****************************************************************/

  //
  // Clase inorderTreeTraversal
  //	Permite recorrer en inorden los
  //	nodos de un árbol binario.
  //

  template <class T>
    class inorderTreeTraversal : public inorderTraversal<T> {
    public:
    // constructores
    inorderTreeTraversal	(binaryTreeNode<T> & aTree);
    inorderTreeTraversal	(const binaryTreeNode<T> & aTree);
    inorderTreeTraversal	(const inorderTreeTraversal<T> & source);

    // operación de modificación
    virtual T &	operator =	(const T & value);
  };


  /****************************************************************/
  /*								  */
  /*      Especificación de la clase postorderTreeTraversal	  */
  /*								  */
  /****************************************************************/

  //
  // Clase postorderTreeTraversal<T>
  //	Permite recorrer en postorden los
  //	nodos de un árbol binario.
  //

  template <class T>
    class postorderTreeTraversal : public postorderTraversal<T> {
    public:
    // constructores
    postorderTreeTraversal (binaryTreeNode<T> & aTree);
    postorderTreeTraversal (const binaryTreeNode<T> & aTree);
    postorderTreeTraversal (const postorderTreeTraversal<T> & source);

    // operación de modificación
    virtual T &	operator = (const T & value);
  };


  /****************************************************************/
  /*								  */
  /*	 Especificación de la clase preorderTreeTraversal      */
  /*								  */
  /****************************************************************/

  //
  // Clase preorderTreeTraversal<T>
  //	Permite recorrer en preorden los
  //	nodos de un árbol binario.
  //

  template <class T>
    class preorderTreeTraversal : public preorderTraversal<T> {
    public:
    // constructores
    preorderTreeTraversal	(binaryTreeNode<T> & aTree);
    preorderTreeTraversal	(const binaryTreeNode<T> & aTree);
    preorderTreeTraversal	(const preorderTreeTraversal<T> & source);

    // operación de modificación
    virtual T &	operator =	(const T & value);
  };


  /****************************************************************/
  /*								  */
  /*     Especificación de la clase levelorderTreeTraversal	  */
  /*								  */
  /****************************************************************/

  //
  // Clase levelorderTreeTraversal<T>
  //	Permite recorrer por niveles los
  //	nodos de un árbol binario.
  //

  template <class T>
    class levelorderTreeTraversal : public levelorderTraversal<T> {
    public:
    // constructores
    levelorderTreeTraversal	(binaryTreeNode<T> & aTree);
    levelorderTreeTraversal	(const binaryTreeNode<T> & aTree);
    levelorderTreeTraversal	(const levelorderTreeTraversal<T> & source);

    // operación de modificación
    virtual T &	operator =	(const T & value);
  };


  /****************************************************************/
  /*								  */
  /*	     Implementación de la clase binaryTreeNode      	  */
  /*								  */
  /****************************************************************/

  template <class T>
    binaryTreeNode<T>::binaryTreeNode () : ptrToRootNode(0)
    {
    }

  template <class T>
    binaryTreeNode<T>::binaryTreeNode (const T & value)
    {
      ptrToRootNode = new nodeTree<T>(value, 0, 0);
  
      // comprobar que se ha asignado espacio
      assert(ptrToRootNode != 0);
    }

  template <class T>
    binaryTreeNode<T>::binaryTreeNode (const T & value,
				       const binaryTreeNode<T> & left,
				       const binaryTreeNode<T> & right)
    {
      nodeTree<T> * leftTree;
      nodeTree<T> * rightTree;

      if (left.ptrToRootNode)
	leftTree = left.ptrToRootNode->duplicate();
      else
	leftTree = 0;

      if (right.ptrToRootNode)
	rightTree = right.ptrToRootNode->duplicate();
      else
	rightTree = 0;

      ptrToRootNode = new nodeTree<T>(value, leftTree, rightTree);
  
      // comprobar que se ha asignado espacio
      assert(ptrToRootNode != 0);
    }

  template <class T>
    binaryTreeNode<T>::binaryTreeNode (nodeTree<T> * root) : ptrToRootNode(0)
    {
      if (root)
	ptrToRootNode = root->duplicate();
    }

  template <class T>
    binaryTreeNode<T>::binaryTreeNode (const binaryTreeNode<T> & source)
    {
      if (source.ptrToRootNode)
	ptrToRootNode = source.ptrToRootNode->duplicate();
      else
	ptrToRootNode = 0;
    }

  template <class T>
    binaryTreeNode<T>::~binaryTreeNode ()
    {
      if (ptrToRootNode != 0) {
	ptrToRootNode->free();
	delete ptrToRootNode;
	ptrToRootNode = 0;
      }
    }

  template <class T>
    binaryTreeNode<T> & binaryTreeNode<T>::operator =
    (const binaryTreeNode<T> & source)
    {
      // liberar el espacio asignado
      if (ptrToRootNode != 0) {
	ptrToRootNode->free();
	delete ptrToRootNode;
	ptrToRootNode=0;
      }

      // copiar el árbol asignado
      if (source.ptrToRootNode != 0)
	ptrToRootNode = source.ptrToRootNode->duplicate();

      return *this;
    }

  template <class T>
    bool binaryTreeNode<T>::isEmpty () const
    {
      return ptrToRootNode == 0;
    }

  template <class T>
    T binaryTreeNode<T>::labelRoot () const
    {
      assert(ptrToRootNode != 0);
      return ptrToRootNode->label();
    }

  template <class T>
    void binaryTreeNode<T>::setLabelRoot (const T & value)
    {
      assert(ptrToRootNode != 0);
      ptrToRootNode->setLabel(value);
    }

  template <class T>
    binaryTreeNode<T> & binaryTreeNode<T>::left () const
    {
      assert(ptrToRootNode != 0);

      binaryTreeNode<T> * ptrToLeft;

      ptrToLeft = new binaryTreeNode<T>(ptrToRootNode->left());

      return *ptrToLeft;
    }

  template <class T>
    void binaryTreeNode<T>::setLeft (const binaryTree<T> & left)
    {
      assert(ptrToRootNode != 0);

      nodeTree<T> * ptrToLeft = 0;

      if (! left.isEmpty())
	ptrToLeft = ((binaryTreeNode<T> &) left).ptrToRootNode;

      ptrToRootNode->setLeft(ptrToLeft->duplicate());
    }

  template <class T>
    binaryTreeNode<T> & binaryTreeNode<T>::right () const
    {
      assert(ptrToRootNode != 0);

      binaryTreeNode<T> * ptrToRight;

      ptrToRight = new binaryTreeNode<T>(ptrToRootNode->right());

      return *ptrToRight;
    }

  template <class T>
    void binaryTreeNode<T>::setRight (const binaryTree<T> & right)
    {

      assert(ptrToRootNode != 0);

      nodeTree<T> * ptrToRight = 0;

      if (! right.isEmpty())
	ptrToRight = ((binaryTreeNode<T> &) right).ptrToRootNode;

      ptrToRootNode->setRight(ptrToRight->duplicate());
    }

  template <class T>
    istream & operator >> (istream & in, binaryTreeNode<T> & t)
    {
      in >> t.ptrToRootNode;
      return in;
    }

  template <class T>
    istream & operator >> (istream & in, binaryTreeNode<T> * & t)
    {
      binaryTreeNode<T> * p = new binaryTreeNode<T>();

      in >> p->ptrToRootNode;
      t = p;
  
      return in;
    }

  template <class T>
    ostream & operator << (ostream & out, const binaryTreeNode<T> & t)
    {
      out << t.ptrToRootNode;
      return out;
    }

  template <class T>
    ostream & operator << (ostream & out, binaryTreeNode<T> * t)
    {
      if (t)
	out << *t;

      return out;
    }


  /****************************************************************/
  /*								  */
  /*	Implementación de la clase inorderTreeTraversal 	  */
  /*								  */
  /****************************************************************/

  template <class T>
    inorderTreeTraversal<T>::inorderTreeTraversal (binaryTreeNode<T> & aTree)
    : inorderTraversal<T>(aTree.ptrToRootNode)
    {
    }

  template <class T>
    inorderTreeTraversal<T>::inorderTreeTraversal
    (const binaryTreeNode<T> & aTree) :
    inorderTraversal<T>(aTree.ptrToRootNode)
    {
    }

  template <class T>
    inorderTreeTraversal<T>::inorderTreeTraversal
    (const inorderTreeTraversal<T> & source) :
    inorderTraversal<T>(source)
    {
    }

  template <class T>
    T & inorderTreeTraversal<T>::operator = (const T & value)
    {
      return inorderTraversal<T>::operator=(value);
    }

  /****************************************************************/
  /*								  */
  /*     Implementación de la clase postorderTreeTraversal	  */
  /*								  */
  /****************************************************************/

  template <class T>
    postorderTreeTraversal<T>::postorderTreeTraversal
    (binaryTreeNode<T> & aTree) : 
    postorderTraversal<T>(aTree.ptrToRootNode)
    {
    }

  template <class T>
    postorderTreeTraversal<T>::postorderTreeTraversal
    (const binaryTreeNode<T> & aTree) : 
    postorderTraversal<T>(aTree.ptrToRootNode)
    {
    }

  template <class T>
    postorderTreeTraversal<T>::postorderTreeTraversal
    (const postorderTreeTraversal<T> & source) :
    postorderTraversal<T>(source)
    {
    }

  template <class T>
    T & postorderTreeTraversal<T>::operator = (const T & value)
    {
      return postorderTraversal<T>::operator=(value);
    }

  /****************************************************************/
  /*								*/
  /*     Implementación de la clase preorderTreeTraversal	*/
  /*								*/
  /****************************************************************/

  template <class T>
    preorderTreeTraversal<T>::preorderTreeTraversal
    (binaryTreeNode<T> & aTree) :
    preorderTraversal<T>(aTree.ptrToRootNode)
    {
    }

  template <class T>
    preorderTreeTraversal<T>::preorderTreeTraversal
    (const binaryTreeNode<T> & aTree) :
    preorderTraversal<T>(aTree.ptrToRootNode)
    {
    }

  template <class T>
    preorderTreeTraversal<T>::preorderTreeTraversal
    (const preorderTreeTraversal<T> & source) :
    preorderTraversal<T>(source)
    {
    }

  template <class T>
    T & preorderTreeTraversal<T>::operator = (const T & value)
    {
      return preorderTraversal<T>::operator=(value);
    }

  /****************************************************************/
  /*								  */
  /*    Implementación de la clase levelorderTreeTraversal	  */
  /*								  */
  /****************************************************************/

  template <class T>
    levelorderTreeTraversal<T>::levelorderTreeTraversal
    (binaryTreeNode<T> & aTree) :
    levelorderTraversal<T>(aTree.ptrToRootNode)
    {
    }

  template <class T>
    levelorderTreeTraversal<T>::levelorderTreeTraversal
    (const binaryTreeNode<T> & aTree) :
    levelorderTraversal<T>(aTree.ptrToRootNode)
    {
    }

  template <class T>
    levelorderTreeTraversal<T>::levelorderTreeTraversal
    (const levelorderTreeTraversal<T> & source) :
    levelorderTraversal<T>(source)
    {
    }

  template <class T>
    T & levelorderTreeTraversal<T>::operator = (const T & value)
    {
      return levelorderTraversal<T>::operator=(value);
    }

} // Del espacio de nombres EstDatos

#endif