// Tree_V.h (c) 2004 adolfo@di-mare.com

/** \file Tree_V.h
    \brief Declaraciones y definiciones para la clase \c Tree

    \author Adolfo Di Mare <adolfo@di-mare.com>
    \date    2004

    - Why English names??? ==> http://www.di-mare.com/adolfo/binder/c01.htm#sc04
*/

#ifndef Tree_V_h
#define Tree_V_h

#ifndef Tdef_h_incluido
    #include "Tdef.h" // truco que evita que el programador necesariamente debe crear el archivo Tdef.h
#endif

#ifndef NDEBUG // ==> Overview of File Translation ==> C++
    #define USE_v_Alive
    #undef  USE_v_Alive
#endif

#include <cassert> // para usar assert()

/// Arboles de adolfo@di-mare.com cuyos nodos contienen un vector de punteros a sus hijos
namespace TV {

/** \brief Los métodos para trabajar con árboles regresan "referencias" que son sub-árboles

    - Un sub-árbol es parte del árbol, por lo que al modificar los valores del
      sub-árbol también el árbol original queda cambiado.
    - Para evitar este tipo de modificación indirecta, es necesario trabajar
      con una "copia profunda" del árbol orignal, la que se puede obtener con
      \c Tree::Copy_Deep().
    - Aún si el árbol original es eliminado, el sub-árbol continúa existiendo
    - Debido a que los árboles y sub-árboles son referencias, en C++ es necesario mantener
      internamente "cuentas de referencia" que impiden que métodos como \c Father() o \c Root()
      sean métodos <code>const</code>.
    - Muchos métodos retornan referencias \c Tree& porque es más eficiente, pues cada
      vez que un \c Tree es copiado hay que actualizar la "cuenta de referencia" de
      la raíz del sub-árbol.
*/
class Tree {
public:
    typedef Elem_Tree value_type; ///< Nombre estándar del tipo de elemento contenido
private:
    static const unsigned N = 15; ///< Cantidad máxima de hijos por nodo
    /// Nodos almacenados en el árbol
    class Node {
        friend class Tree; friend class Tree;
    private:
        Node( const value_type& d ) : _data( d ), _refCount(1), _n_child(0), _father(0) {} ///< Constructor de vector
        static Node* Get_New(const value_type& d);
        void No_Children() { for (unsigned i=0; i < N; ++i) { _Lchild[i]= 0; } } ///< Pone en nulo todos los punteros a los hijos porque ni \c Get_New() ni el constructor lo hacen
    private:
        value_type _data; ///< Valor almacenado en el nodo
        unsigned   _refCount; ///< Cantidad de punteros hacia mi
        int        _n_child; ///< Soy el el hijo número \c "_n_child" de mi padre
        Node *     _father; ///< Puntero al nodo padre
        Node *     _Lchild[N]; ///< Punteros a cada uno de los hijos
    private:
        #ifdef USE_v_Alive // ==> NDEBUG ==> Overview of File Translation ==> C++
            static const unsigned N_Alive = 1033; ///< Cantidad máxima posible de punteros en uso
            static Node *   _v_Alive[N_Alive]; ///< Punteros en uso
            static unsigned _n_Alive; ///< Cantidad de punteros en uso
        #endif
    }; // Node

/// \name Constructores y destructor
//@{
public:
    Tree() : _root(0) {} ///< Constructor de vector
    Tree(Tree& o);
    Tree(const value_type & d);
    ~Tree();
private:
    /// Constructor a partir de un nodo
    Tree(Node* p) : _root(p) { if (p!=0) { p->_refCount++; } } 
    /// Truco para usar el constructor que no verifica <code> (p != 0) </code>
    typedef void NOT_null_pointer;
    /// Constructor a partir de un nodo [ requiere <code> p != 0 </code> ]
    Tree(NOT_null_pointer* p) : _root( (Node*)p) { // assert( p != 0 );
        ((Node*)p)->_refCount++; } 
//@}

/// \name Operaciones básicas
//@{
public:
    bool     Empty() const { return (_root == 0); } ///< Retorna \c "true" si el sub-árbol está vacío
    unsigned Count() const ;
    unsigned Count_Children() const ;
    unsigned Size () const { return Count(); } ///< Usa \c Count() para retornar la cantidad de valores almacenados en el sub-árbol
    friend bool Check_Ok(Tree& T);
    bool        Ok() { return Check_Ok(*this); } ///< Usa \c Check_Ok(Tree& T) para verificar la invariante de \c Tree
//@}

/// \name Operaciones de borrado
//@{
public:
    void Erase();
    void Erase_Son(unsigned n) { Graft(n, Tree()); }
//@}

/// \name Operaciones de copiado
//@{
public:
    Tree& operator= (Tree &o) { return Copy(o); } ///< Sinónimo de \c this->Copy(o)
    Tree& Copy (Tree &o);
    Tree& Move (Tree &o);
    Tree& Swap (Tree &o);
    Tree& Copy_Deep( const Tree &o );
    /// Usa \c Change_Root() para sustituir por "d" el valor almacenado en la raíz del árbol
    Tree& operator=( const value_type & d) { Change_Root(d); return *this; }
//@}

/// \name Métodos para cambiar los valores almacenados en el árbol
//@{
public:
    Tree Change_Root(const value_type &d);
    Tree Change_Child( unsigned n, const value_type &d );
    Tree Change_Left_Sibling_Inmediate( const value_type &d );
    Tree Change_Right_Sibling_Inmediate( const value_type &d );
    Tree Graft( unsigned n, Tree &o );
//@}

/// \name Operaciones para usar los valores almacenados
//@{
public:
    value_type& Data        () { return  _root->_data;  } ///< Valor almacenado en la raíz del sub-árbol
    value_type& operator *  () { return   Data();  } ///< Valor almacenado en la raíz del sub-árbol
    value_type* operator -> () { return &(_root->_data); } ///< Puntero al valor almacenado en la raíz del sub-árbol
//@}

/// \name Operaciones de comparación
//@{
public:
    friend bool operator == (const Tree &p, const Tree &q); ///< ¿¿¿ (p == q) ???
    friend bool operator != (const Tree &p, const Tree &q); ///< ¿¿¿ (p != q) ???
    bool Equals( const Tree & o ) const { return (*this)==o; } ///< ¿¿¿ (*this==o) ???
    /// Retorna \c true si \c "o" comparte la raíz con \c "*this"
    bool Same( const Tree & o ) const { return _root == o._root; }
//@}

/// \name Métodos para recorrer el árbol
//@{
public:
    Tree Root()   { return Tree( _root ); } ///< Raíz del sub-árbol
    Tree Father();
    Tree Child(unsigned n);
    Tree Left();
    Tree Right();
    Tree Leftmost();
    Tree Rightmost();
    Tree Sibling(int n);
    Tree Left_Sibling();
    Tree Right_Sibling();
    Tree Previous_Sibling() { return Left_Sibling(); } ///<  Sinónimo de \c Left_Sibling()
    Tree Prev_Sibling() { return Left_Sibling(); } ///<  Sinónimo de \c Left_Sibling()
    Tree Next_Sibling() { return Right_Sibling(); } ///<  Sinónimo de \c Right_Sibling()
    Tree Right_Sibling_Inmediate();
    Tree Left_Sibling_Inmediate();
//@}

/// \name Propiedades del árbol
//@{
public:
    /// Retorna \c "n" si \c "*this" es el n-ésimo hijo de su padre, si no retorna \c 0 (cero)
    unsigned Child_Number() { return ( _root==0 ? 0 : _root->_n_child ); }
    /// Retorna \c "n" si el hijo más izquierdo de \c "*this" es el n-ésimo hijo, si no retorna \c 0 (cero)
    unsigned Leftmost_N() { return Leftmost().Child_Number(); }
    /// Retorna \c "n" si el hijo más derecho de \c "*this" es el n-ésimo hijo, si no retorna \c 0 (cero)
    unsigned Rightmost_N() { return Rightmost().Child_Number(); }
    /// Retorna \c "true" si el árbol es una hoja
    bool Is_Leaf() { return ( ! Empty() && Leftmost().Empty() ); }
    /// Retorna \c "true" si el árbol no tiene padre
    bool Is_Root() { return ( _root != 0  && _root->_father == 0 ); }
    /// Cantidad de referencias de la raíz del árbol
    unsigned Nref() { return (_root==0 ? 0 : _root->_refCount); } 
//@}

/// \name Funciones para manipular valores a bajo nivel
//@{
private:
    /// Convierte el puntero al nodo en un referencia a \c Tree
    static Tree& CastTo_Tree_Ref ( Node * &p )
    { return (Tree&) *( reinterpret_cast<Tree*> (&p)); } 
//@}

/// \name Funciones recursivas que realizan el trabajo sobre nodos
//@{
private:
    static void Erase0(Node * p);
    static bool Comp0(const Node *p, const Node *q);
    static void Count0(const Node * p, unsigned & n);
    static Node* Copy_Deep0(Node * father, const Node * p);
    friend class Tree;
//@}
private:
    Tree::Node * _root; ///< Un árbol "es" el puntero al nodo raíz
}; // Tree

#ifdef USE_v_Alive
    unsigned Tree::Node::_n_Alive = 0; // Hay que "repetir" estos nombres acá para que el ...
    Tree::Node* Tree::Node::_v_Alive[Tree::Node::N_Alive]; // ... compilador les asigne memoria
#endif

/** Crea un nuevo nodo y lo inicializa con \c "d"

    - Para mejorar la eficiencia, no incializa los punteros a los hijos.
    - Si la macro \c USE_v_Alive de compilación existe, también agrega el nuevo
      nodo al contenedor global \c Tree::_v_Alive[], de manera que es posible
      saber si un puntero a un nodo está o no en uso.
    - En realidad sobra usar este método, pero la utilidad de usarlo es
      que es posible examinar \c Tree::_v_Alive[] para saber si los métodos
      de árbol están correctamente implementados.
*/
inline Tree::Node * Tree::Node::Get_New( const Tree::value_type& d) {
    Node* p = new Node(d);
    #ifdef USE_v_Alive
        _v_Alive[_n_Alive] = p;
        _n_Alive++;
    #endif
    return p;
}

/**  Constructor de copia desde otro árbol (copia superficial)

    - Como un sub-árbol en realidad es una referencia, este método
      no hace la copia completa [profunda] del árbol.
*/
inline Tree::Tree(Tree& o) {
    if (o._root != 0) {
        o._root->_refCount++; // una referencia más porque "o" y "*this" ...
    }
    _root =  o._root; // ... ahora comparten la raíz
}

/**  Destructor

    \par Complejidad:
         O( \c Count() )

    \see http://www.di-mare.com/adolfo/binder/c04.htm#sc04
*/
inline Tree::~Tree() {
    if (_root != 0) { Erase0(_root); }
}

/// Constructor a partir de un valor
inline Tree::Tree(const Tree::value_type & d) {
    _root = Node::Get_New(d);
    _root->No_Children(); // ... pues el constructor no inicializa los punteros a los hijos
}

/** Copia superficial desde \c "o"

    - El valor anterior de \c "*this" se pierde

    \par Complejidad:
         O( \c Count() )

    \returns *this

    \see http://www.di-mare.com/adolfo/binder/c04.htm#sc05
*/
Tree& Tree::Copy (Tree &o) {
    if (_root != o._root) { // evita auto-borrado
        if (_root != 0) {
            Erase0(_root); // borra el valor actual
        }
        _root =  o._root; // comparte la raíz
        if (o._root != 0) {
            o._root->_refCount++; // una referencia más
        }
    }
    return *this;
}

/** Traslada el valor de \c "o" a \c "*this"

  - El valor anterior de \c "*this" se pierde
  - El nuevo valor de \c "*this" es el que \c "o" tuvo
  - \c "o" queda en el estado en que lo dejaría \c Erase()
  - Si \c "*this" es \c "o" entonces su valor no cambia
  - En general, después de esta operación casi
    nunca ocurre que <code> (*this == o) </code>

    \par Complejidad:
         O( \c Count() )

    \returns \c *this

    \see http://www.di-mare.com/adolfo/binder/c04.htm#sc07
*/
Tree& Tree::Move (Tree &o) {
    if (_root == o._root) { // evita auto-borrado
        if (_root != 0) {
            Erase0(_root); // borra el valor actual
        }
        _root = o._root; // se roba los hijos
        o._root = 0; // anula al dador
    }
    return *this;
}

/** Intercambia los valores de \c "*this" y \c "o"

    - Debido a que algunos métodos retornan copias del valor de \c "*this" en
      lugar de una referencia, como ocurre con \c Tree::Child(), a veces
      \c Swap() no tiene el resultado esperado por el programador.
    - Por ejemplo, si se invoca <code> T.Child(i). Swap( T.Child(j) ) </code> 
      el resultado no es intercambiar los hijos, sino más bien intercambiar
      los valores de los sub-árboles temporales \c T.Child(i) y \c T.Child(j). 
      La forma correcta de intercambiar hijos es usar \c Graft().

      \par Complejidad:
         O( \c 1 )

    \returns *this

    \see http://www.di-mare.com/adolfo/binder/c04.htm#sc08
*/
inline Tree& Tree::Swap (Tree &o) {
    Node * tmp = _root;
    _root = o._root;
    o._root = tmp;
    return *this;
}

/** Acceso al padre

    - Si el sub-árbol no tiene padre retorna el árbol vacío.

    \par Complejidad:
         O( \c 1 )
    
*/
inline Tree Tree::Father() {
    if (_root == 0) {
        return Tree( );
    } else {
        return Tree( _root->_father );
    }
}

/** Acceso al \c "n"-ésimo hijo

    - Si el sub-árbol no tiene un hijo número \c "n" retorna el sub-árbol vacío.

    \par Complejidad:
         O( \c 1 )
*/
Tree Tree::Child( unsigned n ) {
    if (n >= Tree::N) {
        return Tree( );
    }
    if (_root == 0) { // ignora árboles vacíos
        return Tree( );
    }
    return Tree ( _root->_Lchild[n] );
}

/** Sub-árbol izquierdo [en un árbol binario]

    - Sinónimo de \c Child(0).
    \par Complejidad:
         O( \c 1 )
*/
inline Tree Tree::Left() {
    if (_root == 0) {
        return Tree( );
    } else {
        return Tree( _root->_Lchild[0] );
    }
}

/** Sub-árbol derecho [en un árbol binario]

    - Sinónimo de \c Child(1).

    \par Complejidad:
         O( \c 1 )
*/
inline Tree Tree::Right() {
    if (_root == 0) {
        return Tree( );
    } else {
        return Tree( _root->_Lchild[1] );
    }
}

/** \typedef Tree::NOT_null_pointer
    \brief Truco para evitar comparar con \c 0 ( \c nil )
    al usar \c Tree::Node* para construir \c Tree().

    Al implementar cada uno de los métodos de \c Tree con frecuencia ocurre
    que es posible saber que el sub-árbol retornado no está vacío. En estos casos, conviene
    usar un contructor que no verifique si la raíz del árbol es nula.

    Esta clase se usa como una marca para que se ejecute el contructor 
    <code> Tree::Tree(NOT_null_pointer* p) </code>
    que no verifica la nulidad de \c "_root"; esta es una micro-eficiencia, pero aquí sirve 
    para mostrar un truco que es muy usado en C++ para aumentar la eficiencia de los 
    programas, pues le permite al programado usar la sobrecarga de operadores para evitar 
    repetir verificaciones innecesarias.
    
    \see http://www.di-mare.com/adolfo/binder/c01.htm#k1-micro-eficiencia
*/

/** Obtiene el hermano no vacío anterior, que está hacia la izquierda

    - Si no existe un hermano no vacío hacia la izquierda, retorna un sub-árbol vacío.
    - Si <code>n == Child_Number()</code> no necesariamente ocurrirá que
      <code> (n-1)== Left_Sibling().Child_Number()</code>
      pues los anteriores hijos de \c Father() pueden ser sub-árboles vacíos, como ocurre si
      un árbol binario tiene hijo derecho pero no tiene hijo izquierdo.
    - Este método usualmente se usa junto con \c Rightmost()

    \par Complejidad:
         O( <code> Father().Count_Children() </code> )
*/
Tree Tree::Left_Sibling() {
    if (_root == 0)  {
        return Tree( );
    }
    if (_root->_father == 0)  {
        return Tree( );
    }

    unsigned i = _root->_n_child;
    for (;;) {
        if (i == 0) { // tanto enredo para usar "unsigned" en lugar de "int"
            break;
        }
        --i;
        if (_root->_father->_Lchild[i] != 0) {
            return Tree( (NOT_null_pointer*) _root->_father->_Lchild[i] );
        }
    }
    return Tree( ); // ya no hay más hermanos
}

/** Obtiene el hermano no vacío siguiente, que está hacia la derecha

    - Si no existe un hermano hacia la derecha, retorna un sub-árbol vacío.
    - Si <code>n == Child_Number()</code> no necesariamente ocurrirá que
      <code>(n+1) == Right_Sibling().Child_Number()</code>
      pues los siguientes hijos de \c Father() pueden ser sub-árboles vacíos, como ocurre si
      un árbol binario tiene hijo izquierdo pero no tiene hijo derecho.
    - Este método usualmente se usa junto con \c Leftmost()

    \par Complejidad:
         O( <code> Father().Count_Children() </code> )
*/
Tree Tree::Right_Sibling() {
    if (_root == 0)  {
        return Tree( );
    }
    if (_root->_father == 0) {
        return Tree( );
    }
    for (unsigned i = _root->_n_child + 1; i<N; ++i) { // comienza en el hermano derecho
        if ( _root->_father->_Lchild[i] != 0) {
            return Tree ( (NOT_null_pointer*) _root->_father->_Lchild[i] );
        }
    }
    return Tree( ); // ya no hay más hermanos
}

/** Obtiene el hermano que está inmediatamente hacia la izquierda

    - Este método es equivalente a invocar \c Sibling( -1 )
    - Si no existe un hermano hacia la derecha, retorna un sub-árbol vacío.

    \par Complejidad:
         O( \c 1 )
*/
Tree Tree::Left_Sibling_Inmediate() {
    if (_root == 0)  {
        return Tree( );
    }
    if (_root->_father == 0)  {
        return Tree( );
    }
    unsigned nplus = 1 + _root->_n_child;
    if ( _root->_n_child == 0 ) {
        return Tree( );
    } else {
        return Tree ( _root->_father->_Lchild[ _root->_n_child - 1 ] );
    }
}

/** Obtiene el hermano que está inmediatamente hacia la derecha

    - Este método es equivalente a invocar \c Sibling( +1 )
    - Si no existe ese hermano hacia la derecha, retorna un sub-árbol vacío.

    \par Complejidad:
         O( \c 1 )
*/
Tree Tree::Right_Sibling_Inmediate() {
    if (_root == 0)  {
        return Tree( );
    }
    if (_root->_father == 0)  {
        return Tree( );
    }
    unsigned nplus = 1 + _root->_n_child;
    if ( nplus == N ) {
        return Tree( );
    } else {
        return Tree ( _root->_father->_Lchild[nplus] );
    }
}

/** \c "n"-ésimo hermano a partir de \c "*this".

    - El hermano puede ser vacío aunque haya otros hermanos que no son vacíos.
    - Se "corre" hacia el n-ésimo hermano \c "n" "posiciones".
    - El hermano se determina contando sub-árboles hacia la derecha o izquierda de acuerdo
      al signo de \c "n":
          - Si \c n=0, regresa \c "*this".
          - Si \c n>0, regresa el hermano número \c "+n" contando hacia la derecha de \c "*this".
          - Si \c n<0, regresa el hermano número \c "-n" contando hacia la izquierda de \c "*this".
    - Si no existe un hermano número \c "n" retorna un sub-árbol vacío.
    - El árbol \c "T" tiene 3 hijos no vacíos \c "B", \c "C" y \c "E" y tiene 4 sub-árboles:
            - <code> C.Sibling( +0 ) == C</code>
            - <code> B.Sibling( +1 ) == C</code>
            - <code> E.Sibling( -2 ) == C</code>
            - <code> E.Sibling( -1 ) --> Vacío</code>
            - <code> A.Sibling( +1 ) --> Vacío </code>
            - <code> B.Sibling( -1 ) --> Vacío </code>
            - <code> E.Sibling( +1 ) --> Vacío </code>
        \code
           A <-- T
          /|\
        / / \ \       [] --> es representa un sub-árbol vacío
       B C  [] E
        \endcode

    \par Complejidad:
         O( <code> Father().Count_Children() </code> )
*/
Tree Tree::Sibling( int n ) {
    if (_root == 0)  {
        return Tree( );
    }
    if ( n==0 ) {
        return Tree( (NOT_null_pointer*) _root );
    } 
    if (_root->_father == 0)  {
        return Tree( );
    }

    if ( n >= 0 ) {
        unsigned n_new = n + _root->_n_child;
        if (n_new < Tree::N) {
            return Tree( _root->_father->_Lchild[n_new] );
        } else {
            return Tree( );
        }
    } else {
        int n_abs = -n;
        if ( _root->_n_child >= n_abs ) { // se puede hacer la resta
            return Tree( _root->_father->_Lchild[ _root->_n_child - n_abs ] );
        } else {
            return Tree( );
        }
    }
}

/** Obtiene el hijo más izquierdo del árbol

    - Este método usualmente se usa junto con \c Right_Sibling()

    \par Complejidad:
         O( <code> Count_Children() </code> )

    \remark Esta es una forma de procesar los hijos no vacíos de un sub-árbol de izquierda a derecha:

    \code
    Tree Child = T.Leftmost();
    while ( ! Child.Empty() ) {
        Process( Child );
        Child = Child.Right_Sibling();
    }
    \endcode
*/
Tree Tree::Leftmost() {
    if (_root == 0)  {
        return Tree( );
    }
    for (unsigned i=0; i<N; ++i) {
        if ( _root->_Lchild[i] != 0) {
            return Tree ( (NOT_null_pointer*) _root->_Lchild[i] );
        }
    }
    return Tree( ); // ==> _root == 0
}

/** Obtiene el hijo más derecho del árbol

    - Este método usualmente se usa junto con \c Left_Sibling()
    - Requiere O(n) tiempo de ejecución, donde \c "n" es la cantidad de hijos de \c "*this"

   \remark Esta es una forma de procesar los hijos no vacíos de un sub-árbol de derecha a izquierda:

   \code
    Tree Child = T.Rightmost();
    while ( ! Child.Empty() ) {
        Process( Child );
        Child = Child.Left_Sibling();
    }
   \endcode
*/
Tree Tree::Rightmost() {
    if (_root == 0)  {
        return Tree( );
    }

    unsigned i = N;
    for (;;) {
        if (i == 0) { // tanto enredo ... para usar "unsigned" en lugar de "int"
            break;
        }
        --i;
        if (_root->_Lchild[i] != 0) {
            return Tree( (NOT_null_pointer*) _root->_Lchild[i] );
        }
    }
    return Tree( ); // ==> _root == 0
}

/** Implementación recursiva para \c Count()

    - Incrementa \c "n" en el número de hijos que tiene el sub-árbol cuya raíz es \c "p"
    - Cambia el valor de \c "n"
    - No cuenta el nodo raíz \c "p"
    - Esta función complementa a \c Count()

    \pre p != 0
*/
void Tree::Count0(const Node * p, unsigned & n) {
    for (unsigned i=0; i < N; ++i) {
        if (p->_Lchild[i] != 0) {
            ++n; // cuenta a este hijo
            Count0( p->_Lchild[i], n );
        }
    }
}

/** Retorna la cantidad de valores almacenados en el sub-árbol

    - Calcula el número de sub-árboles no vacíos del árbol

    \par Complejidad:
         O( \c Count() ) ==> tiempo <br>
         O( \c Height() ) ==> espacio

    \see http://www.di-mare.com/adolfo/binder/c05.htm#sc03
*/
unsigned Tree::Count() const {
    if (_root == 0) {
        return 0;
    } else {
        unsigned n = 1; // comienza contando en uno...
        Count0(_root, n); // ... porque Count0() no cuenta la raíz
        return n;
    }
}

/** Retorna la cantidad de hijos del árbol

    \par Complejidad:
         O( \c Count_Children() )
*/
unsigned Tree::Count_Children() const {
    unsigned tot = 0;
    for (unsigned i=0; i < N; ++i) {
        if (_root->_Lchild[i] != 0) {
            ++tot; // cuenta a este hijo porque no está vacío
        }
    }
    return tot;
}

inline bool operator == (const Tree &p, const Tree &q) { return Tree::Comp0(p._root, q._root); }
inline bool operator != (const Tree &p, const Tree &q) { return !(p == q); }

/** Compara recursivamente los árboles cuyos nodo raíz son \c "*p" y \c "*q"

    - Implementación recursiva para <code> operator==(Tree, Tree) </code>
*/
bool Tree::Comp0(const Tree::Node *p, const Tree::Node *q) {
    if (p == q) {
        return true;
    }
    if ( (p==0) || (q == 0)) { // son diferentes...
        return false; // ...pues sólo 1 está vácio
    }
    if ( ! (p->_data == q->_data) ) {
        return false; // valor diferente en la raíz
    }

    // A comparar a todos los hijos
    for (unsigned i=0; i < Tree::N; ++i) {
        if (! Comp0(p->_Lchild[i], q->_Lchild[i]) ) {
            return false;
        }
    }

    return true; // pues nunca encontró nodos diferentes
}

/**   Verifica que se cumpla la invariante de la clase, o sea, que el objeto esté bien construido

      - La razón por la que esta función no es un método es continuar la costumbre de muchos
        programadores quienes no definen la invariante para sus clases, pues en muchos
        casos sobra hacerlo.
      - No invoca \c Check_Ok( value_type& ) para cada valor almacenado, aunque si el árbol
        cumple con su invariante necesariamentes es porque también sus elementos almacenados
        están bien construidos.
      - Esta función en general es difícil de implementar, y en algunos casos es imposible
        pues, cuando el objeto no está bien construido, puede ocurrir que la función no
        retorne (como ocurriria si un nodo interno del árbol apunta de vuelta a la raíz, lo
        que se resulta en un círculo).
      - En general, la implementáción de esta función no es completa pues hay casos en que
        es imposible verificar la invariante de una clase.

    \par Complejidad:
         O( \c Count() ) ==> tiempo <br>
         O( \c Height() ) ==> espacio

         \post Retorna \c "true" si el árbol es un objeto bien construido
      \see \c Check_Ok(Tree&)

    \see http://www.di-mare.com/adolfo/binder/c04.htm#sc11
*/
bool Check_Ok(Tree& T) {

    if ( T.Empty() ) {
        return true;
    }

    #ifdef NO_Implementado_para_evitar_forzar_que_el_valor_almacenado_tenga_su_metodo_OK
        if (! Check_Ok( T.Data() ) ) { // si el valor almacenado no esta bien...
            return false; //... tampoco lo está el árbol
        }
        /* Usar la función Check_Ok(Tree::value_type en lugar del método
        Tree::value_type::Ok() evitar forzar a que los programadores clientes
        que usen árboles estén obligados a implementar el método
        Tree::value_type::Ok(), que se encarga de verificar la invariante del valor
        almacenado en le árbol.
        - Lindo: if (! Check_Ok( T.Data() ) ) //.... la función Check_Ok() es opcional
        - ¡FEO!: if (! T.Data().Ok() ) //... pues obliga a que exista el método value_type::Ok()
        */
    #endif

    for (unsigned i = 0; i < Tree::N; ++i) {
        if ( T.Child(i).Empty() ) { // este hijo no existe
            // continue; // con el siguiente
        }
        else if ( T.Child(i).Father() != T.Root() ) { // ==> ! T.Father.Empty()
            return false; // parece que este hijo no es mi hijo...
        }
        else if ( i != T.Child(i).Child_Number() ) {
            return false; // no estoy registrado como el i-ésimo hijo de mi padre
        }
        else if ( T.Child(i).Father().Child( i ) != T.Child( i ) ) {
            return false; // no estoy registrado como el i-ésimo hijo de mi padre
        }
        else if ( ! Check_Ok( T.Child(i) ) ) {
            return false; // hijo roto...
        }
    }
    return true;

    // Las siguientes relaciones lógicas se cumplen
    // [ ! T.Empty() ]                    ==> [ T.Root()!= Tree() ]
    // [ T.Child(i).Father() == T.Root()] ==> [ ! T.Father.Empty() ]

    /* Si este método retorna es porque el árbol está bien construido. Sin embargo,
       una invocación a Check_Ok() con un árbol mal construido posiblemente nunca retorne.
    */
}

/**  Sustituye por \c "d" el valor almacenado en la raíz del árbol

    - Si el árbol está vacío, le agrega el nodo raíz.

    \returns \c *this
*/
Tree Tree::Change_Root(const value_type & d) {
    if (_root == 0) { // como el árbol está vacío hay que agregarle la raíz
        _root = Node::Get_New(d); // crea el nodo raíz
        _root->No_Children(); // y le pone en blanco todos sus hijos
    } else { // como no hay más referencias....
        _root->_data = d; // ... cambia el valor directamente
    }
    return *this;
}

/** Sustituye por \c "d" el valor almacenado en el hijo número \c "n" del árbol

    - Si no existe el hijo número \c "n", lo agrega como una hoja con valor \c "d"
    - Si ya existe el hijo número \c "n", le sustituye su valor por \c "d"

    \pre <code> !Empty() && (0 <= n) && (n < Tree::N) </code>

    \par Complejidad:
         O( \c Count_Children() )

    \returns <code> Child(n) </code>
*/
Tree Tree::Change_Child(unsigned n, const value_type &d) {
    if (_root == 0) { // ignora árboles vacíos
        return Tree( );
    }
    if (n >= Tree::N) { // ignora índices fuera de rango
        return Tree( );
    }
    if (_root->_Lchild[n] == 0) { // Hay que agregar un sub-árbol nuevo
        Node * p = Node::Get_New(d);
        p->No_Children();
        p->_father = _root;
        p->_n_child = n;
        _root->_Lchild[n] = p;
    } else {
        _root->_Lchild[n]->_data = d; // cambia el valor directamente
    }
    return Tree( (NOT_null_pointer*) _root->_Lchild[n] );
}

/** Sustituye por \c "d" el valor almacenado en el hermano inmediatamente anterior del sub-árbol

    - Si <code> n == Child_Number() </code> cambia el valor
      del hijo número \c "n-1" de \c Father()
    - Si no existe el hijo número \c "n-1" de \c Father() lo agrega como
      una hoja con valor \c "d"
    - Si ya existe ese hijo número \c "n-1", le sustituye su valor por \c "d"
    - Retorna un árbol vacío si no es posible que exista el hijo número \c "n-1" de \c Father()

    \pre <code> !Empty() && (1 <= Child_Number()) </code>

    \par Complejidad:
         O( \c 1 )

    \returns El hermano izquierdo, <code> Sibling(-1) </code>
*/
Tree Tree::Change_Left_Sibling_Inmediate( const value_type &d ) {
    if (_root == 0) { // ignora árboles vacíos
        return Tree( );
    }
    unsigned n = _root->_n_child;
    if ( n == 0 ) { // no hay hijos hacia la izquierda
        return Tree( );
    }
    // assert( (_root->_n_child > 0) && (n > 0) );
    n--;
    if (_root->_father->_Lchild[ n ] == 0) { // Hay que agregar un sub-árbol nuevo
        Node * p = Node::Get_New(d);
        p->No_Children();
        p->_father = _root->_father;
        p->_n_child = n;
        _root->_father->_Lchild[ n ]->_data = d;
    } else {
        _root->_father->_Lchild[ n ]->_data = d; // cambia el valor directamente
    }
    return Tree( (NOT_null_pointer*) _root->_Lchild[n] );
}

/** Sustituye por \c "d" el valor almacenado en el hermano inmediatamente posterior del sub-árbol

    - Si <code> n == Child_Number() </code> cambia el valor
      del hijo número \c "n+1" de \c Father()
    - Si no existe el hijo número \c "n+1" de \c Father() lo agrega como
      una hoja con valor \c "d"
    - Si ya existe ese hijo número \c "n+1", le sustituye su valor por \c "d"
    - Retorna un árbol vacío si no es posible que exista el hijo número \c "n+1" de \c Father()

    \pre <code> !Empty() && ( Child_Number() < Tree::N ) </code>

    \par Complejidad:
         O( \c 1 )

    \returns El hermano derecho, <code> Sibling(+1) </code>
*/
Tree Tree::Change_Right_Sibling_Inmediate( const value_type &d ) {
    if (_root == 0) { // ignora árboles vacíos
        return Tree( );
    }
    unsigned n = _root->_n_child + 1;
    if (n >= Tree::N) { // no hay hijos hacia la derecha
        return Tree( );
    }
    // assert( n < Tree::N );
    if (_root->_father->_Lchild[ n ] == 0) { // Hay que agregar un sub-árbol nuevo
        Node * p = Node::Get_New(d);
        p->No_Children();
        p->_father = _root->_father;
        p->_n_child = n;
        _root->_father->_Lchild[ n ]->_data = d;
    } else {
        _root->_father->_Lchild[ n ]->_data = d; // cambia el valor directamente
    }
    return Tree ( _root->_Lchild[n] );
}

/** Elimina recursivamente a \c "*p" y a todos sus descendientes

    - Implementación recursiva para \c Erase()
    - Borra el nodo sólo después de que constata que ya no hay punteros que le apunten
    - No actualiza los punteros en el padre ==> ese es el trabajo de \c Graft() o \c Erase()
    - Lo que sí hace es decrementar \c "p->_refCount"
    - Recursivamente, borra a los descendientes de \c "*p"

    \pre <code> p != 0 </code>
    \post No cambia \c "p" porque trabaja con una copia de su valor
*/
void Tree::Erase0( Tree::Node * p ) {
    // assert( p != 0 );
    p->_refCount--; // ya "p" no apunta al nodo
    if (p->_refCount == 0) { // elimina el nodo ==> esta es la última referencia
        // A matar hijos...
        for (unsigned i = 0; i < N; i++) {
            Tree::Node * q = p->_Lchild[i];
            if (q != 0) {
                if (q->_father == p) { // lo des-padre-ja...
                    q->_father = 0; // ... pues ya "p" no es su padre
                }
                Erase0(q); // elimina recursivamente a cada uno de sus hijos
            }
            // Esta sobra porque "*p" va a desaparecer
            // p->_Lchild[i] = 0; // ya ese nodo no es hijo de nadie
        }
        #ifdef USE_v_Alive
            // Elimina a "p" de _v_Alive[]
            for (unsigned j = 0; j < Node::N_Alive; ++j) {
                if (p == Node::_v_Alive[j]) { // busca hasta que encuentra al puntero
                    break;
                }
            }
            if (j < Node::N_Alive) { // sí lo encontró
                for (unsigned k = j; k < Node::N_Alive; ++k) { // corre a los demás para atrás
                    Node::_v_Alive[k] = Node::_v_Alive[k+1];
                }
                Node::_n_Alive--; // ahora hay uno menos
            } else {
                for (unsigned k = 0; k<3; ++j) { // marca "feos" los del final
                    Node::_v_Alive[Node::N_Alive-1-k] = (Tree::Node *)(-1);
                }
            }
        #endif
        delete p; // ... lo mata sólo si esta es la última referencia
    }
}

/** Elimina el árbol y sus descendientes

    \par Complejidad:
         O( \c Count() ) + O( <code> Father().Count() </code> ) ==> tiempo <br>
         O( \c Height() ) ==> espacio

    \see http://www.di-mare.com/adolfo/binder/c04.htm#sc03
*/
void Tree::Erase() {
    if (_root == 0) {
        return;
    } else if (_root->_father != 0) {
        _root->_father->_Lchild[_root->_n_child] = 0;
    }
    Erase0(_root);
    _root = 0;
}

// Esta documentación para Tree::Erase_Son() aparece acá porque Doxygen no permite
// incluir un párrafo aparte "\par" en la documentación de 1 sólo renglón.

/** \fn void Tree::Erase_Son(unsigned n)

    \brief Elimina el sub-árbol número \c "n"

    \par Complejidad:
         O( <code> Child(n).Count() </code> ) ==> tiempo <br>
         O( <code> Height( Child(n) )  </code> ) ==> espacio
*/

/**   Verifica que se cumpla la invariante de la clase, o sea, que el objeto esté bien construido

      - Además de todo el trabajo que hace \c Check_Ok(Tree& T), acá hay que constatar que
        el nodo raíz no tiene padre, que es la diferencia fundamental entre un árbol y un sub-árbol

      \post Retorna \c "true" si el árbol es un objeto bien construido

      \deprecated Los árboles y los sub-árboles son la misma cosa.

      \see \c Check_Ok(Tree&)
*/
inline bool Check_Ok_Tree(Tree& T) {
    if ( T.Root().Empty() ) {
        return true;
    } else {
        return ( T.Root().Father().Empty() ) && Check_Ok( Tree (T) );
    }
}

/** Hace una copia profunda nodo por nodo del árbol cuyo nodo raíz es \c "*p"

    - Implementación recursiva para \c Tree::Copy_Deep()
    - No altera \c p->_refCount porque copia los nodos.
    - \c "father" indica quién debe ser el padre del nuevo nodo
    - \c "father" no es el padre de \c "*p"

    \pre <code> p != 0 </code>
    \post No cambia \c "p" porque trabaja con una copia de su valor

    \returns Puntero al nodo raíz del árbol copiado
*/
Tree::Node * Tree::Copy_Deep0(Node * father, const Node * p) {
    Node * q; // resultado
    q = Node::Get_New(p->_data); // _refCount = 1; _n_child = 0; _father = 0;
    q->_n_child = p->_n_child;
    q->_father = father;

    // inicializa los punteros a los hijos que estarán en _Lchild[]
    for (unsigned i=0; i < N; ++i) {
        if (p->_Lchild[i] == 0) { // si en el árbol fuente este hijo no existe...
            q->_Lchild[i]  = 0; // ...tampoco existirá en la copia
        } else { // copie todo el sub-árbol
            q->_Lchild[i] = Copy_Deep0(q, p->_Lchild[i]);
        }
    }
    return q;
}

/** Copia profunda de \c "o"

    - Copia todo el valor de \c "o" sobre \c "*this", de forma que el nuevo valor de 
      \c "*this" sea un duplicado exacto del valor de \c "o"
    - El valor anterior de \c "*this" se pierde
    - El objeto \c "o" mantiene su valor anterior
    - Luego de la copia, cuando el valor de \c "o" cambia, el de \c "*this" no cambiará,
      y viceversa, pues la copia es una copia profunda; no es superficial
    - Si \c "*this" es \c "o" entonces su valor no cambia
    - Después de esta operación siempre ocurre que <code> *this == o </code>

    \par Complejidad:
         O( \c Count() ) + O( \c o.Count() )

  \returns \c *this

    \see http://www.di-mare.com/adolfo/binder/c04.htm#sc05
*/
Tree& Tree::Copy_Deep(const Tree &o) {
    if (_root != 0) {
        Erase0(_root);  // Borra el contenido actual del árbol
    }
    if (o._root != 0 ) {
        _root = Copy_Deep0(0, o._root); // 0 == cero == this->Father()
    } else {
        _root = 0;
    }
    return *this;
}

/** Injerta \c "o" para que sea el \c "n"-ésimo hijo de \c "*this"

    - Si \c "o" es sub-árbol de otro árbol, dejara de serlo para pasar ser hijo de \c "*this"
    - Si \c "*this" tiene un \c "n"-ésimo hijo, ese hijo desaparece
    - Si \c "o" está vacío, elimina el \c "n"-ésimo hijo del árbol [<code> Erase_Son(n) </code>]

    \pre
        - <code> ! Root().Empty() </code>
           - Si el  árbol está vacío no tiene raíz, y por lo tanto tampoco puede tener hijos
        - <code> ! Ancestor(o, *this) </code>
           - "o" no puede ser ancestro de *this"
        - <code> (0 <= n) && (n < Tree::N) </code>
        - <code> ! Root(). Same( o.Root() ) </code>

    \post
        - \c "o" deja de ser sub-árbol del árbol en que estaba
        - <code> o.Father() .Same( Root() ) </code>

    \remarks
        - Un sub-árbol puede ser hijo (o sub-árbol) de otro árbol
        - Un sub-árbol puede ser hijo únicamente de un árbol
        - Este método no hace nada cuando [ <code> ! Root() .Same( o.Root() ) </code> ]
        - Injertar un sub-árbol vacío es una forma de eliminar a un hijo junto con 
          toda su descendencia

    \returns "o" ==> El árbol recién injertado

    \par Complejidad::
         O( \c Count_Children() ) + O( <code> o.Father().Count_Children() </code> )

*/
Tree Tree::Graft(unsigned n, Tree &o) {
    if (_root == 0) { // ignora árboles vacíos
        return Tree( );
    }
    if (_root == o._root) { // evita auto-borrado
        return Tree( (NOT_null_pointer*) _root );
    }
    #ifdef FALTA_verificar_en_Graft
        bool Ancestor( Tree & Child, Tree & Father );
        assert( ! Ancestor( o, *this ) ); // "o" no puede ser ancestro de *this"
    #endif
    if (n >= Tree::N) { // ignora punteros nulos
        return Tree( (NOT_null_pointer*) _root );
    }
    if (_root->_Lchild[n] == o._root) { // ya el hijo está ahí
        return Tree( (NOT_null_pointer*) _root );
    }
    if (_root->_Lchild[n] != 0) {
        _root->_Lchild[n]->_father = 0; // deja a este hijo [n] sin padre aunque...
        _root->_Lchild[n]->_n_child = 0; // ...puede que haya otras referencias a este mismo nodo
        Erase0( _root->_Lchild[n] ); // elimna el n-ésimo hijo de "*this"
    }
    if (o._root == 0) {
        _root->_Lchild[n] = 0; // Caso trival si el árbol "o" a injertar está vacío
    } else {
        if (o._root->_father != 0) { // desliga al hijo "o" de su padre actual
            o._root->_father->_Lchild[o._root->_n_child] = 0; // ya no es hijo del padre anterior
            o._root->_refCount--; // pues dejó de ser hijo del padre anterior
        }
        o._root->_father = _root; // nuevo padre
        o._root->_n_child = n; // coloca a "o" como el "n-ésimo" hijo
        o._root->_refCount++; // su nuevo padre ahora ya le apunta
        _root->_Lchild[n] = o._root;
    }

    return Tree( _root->_Lchild[n] );
} // Tree::Graft()

} // namespace TV

using namespace TV;

#endif  // Tree_V_h

// EOF: Tree_V.h