// Tree_L.h (c) 2006 adolfo@di-mare.com /** \file Tree_L.h \brief Declaraciones y definiciones para la clase \c Tree \author Adolfo Di Mare \date 2006 - Why English names??? ==> http://www.di-mare.com/adolfo/binder/c01.htm#sc04 */ #ifndef Tree_L_h #define Tree_L_h #ifndef NDEBUG // ==> Overview of File Translation ==> C++ #define USE_v_Alive #undef USE_v_Alive #endif #include // para usar assert() /// Arboles de adolfo@di-mare.com cuyos nodos contienen un puntero izquierdo al hijo y uno derecho al hermano o padre namespace TL { template class Tree; template bool check_ok( const E & ); template bool check_ok( const Tree& T); // declaration hacia adelante /// Nodos almacenados en el árbol. template class Tree_Node { public: friend class Tree; typedef E value_type; ///< Nombre estándar del tipo de elemento contenido private: Tree_Node( const value_type& d ) : m_data( d ), m_refCount(1) {} ///< Constructor de vector static Tree_Node* Get_New(const value_type& d); unsigned Abs_n_child() const; private: value_type m_data; ///< Valor almacenado en el nodo unsigned m_refCount; ///< Cantidad de punteros hacia mi int m_n_child; ///< Soy el el hijo número "(m_n_child - 1)" de mi padre Tree_Node * m_left_child; ///< Puntero al nodo hijo más izquierdo Tree_Node * m_right_brother; ///< Puntero al nodo hermano o al padre private: #ifdef USE_v_Alive // ==> NDEBUG ==> Overview of File Translation ==> C++ static const unsigned N_Alive = 333; ///< Cantidad máxima posible de punteros en uso static Tree_Node * m_v_Alive[N_Alive]; ///< Punteros en uso static unsigned m_n_Alive; ///< Cantidad de punteros en uso #endif }; // Tree_Node /** 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 const. - 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. */ template class Tree { public: typedef E value_type; ///< Nombre estándar del tipo de elemento contenido /// \name Constructores y destructor //@{ public: Tree() : m_root(0) {} ///< Constructor de vector Tree(const Tree& o); Tree(const value_type & d); ~Tree(); private: /// Constructor a partir de un nodo Tree(Tree_Node* p) : m_root(p) { if (p!=0) { p->m_refCount++; } } /// Truco para usar el constructor que no verifica (p != 0) typedef void NOT_null_pointer; /// Constructor a partir de un nodo [ requiere p != 0 ] Tree(NOT_null_pointer* p) : m_root( (Tree_Node*)p) { // assert( p != 0 ); ((Tree_Node*)p)->m_refCount++; } //@} /// \name Operaciones básicas //@{ public: bool Empty() const { return (m_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(const 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) { Tree_Node*p; Erase_Son_Prev(n+1,p /*,p*/); } private: void Erase_Son_Prev(unsigned n, Tree_Node*& /*, Tree_Node*& */); //@} /// \name Operaciones de copiado //@{ public: Tree& operator= (const Tree &o) { return Copy(o); } ///< Sinónimo de \c this->Copy(o) Tree& Copy (const 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 m_root->m_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 &(m_root->m_data); } ///< Puntero al valor almacenado en la raíz del sub-árbol const value_type& Data () const { return m_root->m_data; } ///< Valor almacenado en la raíz del sub-árbol const value_type& operator * () const { return Data(); } ///< Valor almacenado en la raíz del sub-árbol const value_type* operator -> () const { return &(m_root->m_data); } ///< Puntero al valor almacenado en la raíz del sub-árbol //@} /// \name Operaciones de comparación //@{ public: template friend bool operator == (const Tree &p, const Tree &q); ///< ¿¿¿ (p == q) ??? template 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 m_root == o.m_root; } //@} /// \name Métodos para recorrer el árbol //@{ public: Tree Root() const { return Tree( m_root ); } ///< Raíz del sub-árbol Tree Father() const ; Tree Child(unsigned n) const; Tree Left() const; Tree Right() const; Tree Leftmost() const; Tree Rightmost() const; Tree Sibling(int n) const; Tree Left_Sibling() const; Tree Right_Sibling() const; Tree Previous_Sibling() const { return Left_Sibling(); } ///< Sinónimo de \c Left_Sibling() Tree Prev_Sibling() const { return Left_Sibling(); } ///< Sinónimo de \c Left_Sibling() Tree Next_Sibling() const { return Right_Sibling(); } ///< Sinónimo de \c Right_Sibling() Tree Right_Sibling_Inmediate() const; Tree Left_Sibling_Inmediate() const; //@} /// \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() const { return ( m_root==0 ? 0 : m_root->Abs_n_child() - 1); } /// 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() const { 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() const { return Rightmost().Child_Number(); } /// Retorna \c "true" si el árbol es una hoja bool Is_Leaf() const { return (m_root != 0) && (m_root->m_left_child != 0); } /// Retorna \c "true" si el árbol no tiene padre bool Is_Root() const { return (m_root != 0) && (m_root->m_right_brother == 0); } /// Cantidad de referencias de la raíz del árbol unsigned use_count() const { return (m_root==0 ? 0 : m_root->m_refCount); } //@} /// \name Funciones para manipular valores a bajo nivel //@{ private: /// Convierte el puntero al nodo en un referencia a \c Tree static Tree& CastTo_Sub_Tree_Ref ( Tree_Node * &p ) { return (Tree&) *( reinterpret_cast (&p)); } //@} /// \name Funciones recursivas que realizan el trabajo sobre nodos //@{ private: static void Erase0(Tree_Node * p); static bool Comp0(const Tree_Node *p, const Tree_Node *q); static void Count0(const Tree_Node * p, unsigned & n); static Tree_Node* Copy_Deep0(const Tree_Node * p); //@} private: Tree_Node * m_root; ///< Un árbol "es" el puntero al nodo raíz }; // Tree #ifdef USE_v_Alive unsigned Tree::Tree_Node::m_n_Alive = 0; // Hay que "repetir" estos nombres acá para que el ... Tree::Tree_Node* Tree::Tree_Node::m_v_Alive[Tree::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 del nodo. - Si la macro \c USE_v_Alive de compilación existe, también agrega el nuevo nodo al contenedor global \c Tree::m_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::m_v_Alive[] para saber si los métodos de árbol están correctamente implementados. */ template inline Tree_Node * Tree_Node::Get_New( const E& d) { Tree_Node* p = new Tree_Node(d); #ifdef USE_v_Alive m_v_Alive[m_n_Alive] = p; m_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. template inline Tree::Tree(const Tree& o) { if (o.m_root != 0) { o.m_root->m_refCount++; // una referencia más porque "o" y "*this" ... } m_root = o.m_root; // ... ahora comparten la raíz } /** Destructor. \par Complejidad: O( \c Count() ) \see http://www.di-mare.com/adolfo/binder/c04.htm#sc04 */ template Tree::~Tree() { if (m_root != 0) { if (m_root->m_refCount == 1) { Erase0(m_root); } else { m_root->m_refCount--; } } } /// Constructor a partir de un valor template inline Tree::Tree(const E & d) { m_root = Tree_Node::Get_New(d); m_root->m_n_child = -1; m_root->m_left_child = 0; m_root->m_right_brother = 0; } /** 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 */ template Tree& Tree::Copy( const Tree &o ) { if (m_root != o.m_root) { // evita auto-borrado if (m_root != 0) { if ( m_root->m_refCount == 1 ) { // como es el último... Erase0(m_root); // ...lo mata } else { m_root->m_refCount--; } } m_root = o.m_root; // comparte la raíz if (o.m_root != 0) { o.m_root->m_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 (*this == o) \par Complejidad: O( \c Count() ) \returns \c *this \see http://www.di-mare.com/adolfo/binder/c04.htm#sc07 */ template Tree& Tree::Move( Tree &o ) { if (m_root == o.m_root) { // evita auto-borrado if (m_root != 0) { if ( m_root->m_refCount == 1 ) { // como es el último... Erase0(m_root); // ...lo mata } else { m_root->m_refCount--; } } m_root = o.m_root; // se roba los hijos o.m_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 T.Child(i). Swap( T.Child(j) ) 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 */ template inline Tree& Tree::Swap( Tree &o ) { Tree_Node * tmp = m_root; m_root = o.m_root; o.m_root = tmp; return *this; } /** Acceso al padre. - Si el sub-árbol no tiene padre retorna el árbol vacío. \par Complejidad: O( Father().Count_Children() ) */ template Tree Tree::Father() const { if (m_root == 0) { return Tree( ); } Tree_Node* p = m_root; // soy el primer hijo de mi padre while (p->m_n_child > 0) { p = p->m_right_brother; // se brinca los que no tienen el puntero al padre } return Tree( p->m_right_brother ); // para la raíz siempre ocurre que [m_root->m_right_brother == 0] por lo que // Tree( p->m_right_brother ) produce un árbol vacío } /** 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( Father().Count_Children() ) */ template Tree Tree::Child( unsigned n ) const { if (m_root == 0) { return Tree( ); } Tree_Node* child = m_root->m_left_child; // soy el primer hijo de mi padre if (child == 0) { return Tree( ); } n++; // lo incrementa para evitar incrementar "m_n_child" para cada hijo de "m_root" for (;;) { if (child->m_n_child <= 0) { // es el último hijo if ( unsigned(- child->m_n_child) == n ) { return Tree( (NOT_null_pointer*) child ); } else { return Tree( ); } } else { // assert( child->m_n_child > 0 ); if ( static_cast(child->m_n_child) == n ) { return Tree( (NOT_null_pointer*) child ); } else if ( unsigned(child->m_n_child) < n) { child = child->m_right_brother; } else { // assert( unsigned(child->m_n_child) > n ); return Tree( ); } } } } /** \typedef Tree::NOT_null_pointer \brief Truco para evitar comparar con \c 0 ( \c nil ) al usar \c Tree::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 Tree::Tree(NOT_null_pointer* p) que no verifica la nulidad de \c "m_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 */ /** Sub-árbol izquierdo [en un árbol binario]. - Sinónimo de \c Child(0). \par Complejidad: O( \c 1 ) */ template inline Tree Tree::Left() const { if (m_root == 0) { return Tree( ); } else if ( -1 ==m_root->m_left_child->m_n_child || 1 ==m_root->m_left_child->m_n_child ) { return Tree( (NOT_null_pointer*) m_root->m_left_child ); } return Tree( ); } /** Sub-árbol derecho [en un árbol binario]. - Sinónimo de \c Child(1). \par Complejidad: O( \c 1 ) */ template Tree Tree::Right() const { if (m_root == 0) { return Tree( ); } else if ( 0 == m_root->m_left_child ) { // no hay hijos return Tree( ); } else if ( -1 ==m_root->m_left_child->m_n_child ) { return Tree( ); // sólo está el hijo izquierdo } else if ( 1 ==m_root->m_left_child->m_n_child ) { if ( -2 == m_root->m_left_child->m_right_brother->m_n_child || 2 == m_root->m_left_child->m_right_brother->m_n_child ) { return Tree( (NOT_null_pointer*) m_root->m_left_child->m_right_brother ); } } else if ( 2 == m_root->m_left_child->m_n_child || -2 == m_root->m_left_child->m_n_child ) { return Tree( (NOT_null_pointer*) m_root->m_left_child ); } return Tree( ); // uso 1-2 en lugar de 0-1 porque "m_n_child" contiene "uno más" } /** 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 n == Child_Number() no necesariamente ocurrirá que (n-1)== Left_Sibling().Child_Number() 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( Father().Count_Children() ) */ template Tree Tree::Left_Sibling() const { if (m_root == 0) { return Tree( ); } unsigned n_child = m_root->Abs_n_child()-1; // assert( n_child >= 0 ); if ( n_child <= 0 ) { // no puede haber un hijo anterior... return Tree( ); // huye porque no existen hijos antes del primero } #ifdef ESTO_SOBRA_en_Left_Sibling if (m_root->m_right_brother == 0) { // sólo la raíz tiene en blanco "m_right_brother" return Tree( ); // la raíz no tiene hermanos } // Para el nodo raíz de un árbol [T] el campo [T.m_root->m_right_brother == 0] es nulo // - Afortunadamente, como [T.m_root->m_n_child == -1], el if(){} anterior retorna // el sub-árbol vacío para el nodo raíz del árbol [T]. #endif Tree_Node* brother = m_root; // camina sobre los hermanos hasta llegar al padre while (brother->m_n_child > 0) { brother = brother->m_right_brother; // se brinca los que no tienen el puntero al padre } Tree_Node* father = brother->m_right_brother; // assert( ! Father().Empty() && Father().Same( Tree( brother ) ) ); brother = father->m_left_child; // hijo más izquierdo de Father() if ( m_root == brother ) { return Tree( ); // ya "m_root" era el hijo más izquierdo } while ( m_root != brother->m_right_brother ) { brother = brother->m_right_brother; } // assert( m_root == brother->m_right_brother ); return Tree( brother ); } /** 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 n == Child_Number() no necesariamente ocurrirá que (n+1) == Right_Sibling().Child_Number() 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( \c 1 ) */ template Tree Tree::Right_Sibling() const { if (m_root == 0) { return Tree( ); } if (m_root->m_n_child < 0) { // es el último hijo return Tree( ); // ==> ya no hay dónde más buscar } else { return Tree( m_root->m_right_brother ); // sólo la raíz tiene "m_right_brother" en blanco (puntero nulo); // en ese caso se retorna el árbol vacío. } } /** 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( Father().Count_Children() ) */ template inline Tree Tree::Left_Sibling_Inmediate() const { return Sibling( -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 ) */ template Tree Tree::Right_Sibling_Inmediate() const { // return Sibling( +1 ); if (m_root == 0) { return Tree( ); } if (m_root->m_n_child <= 0) { // es el último hijo return Tree( ); // ya no hay hermanos a la derecha } // assert( m_root->m_right_brother != 0 ); // pues "(m_root->m_n_child > 0)" Tree_Node* brother = m_root->m_right_brother; // assert( brother->Abs_n_child() > 0 ); // pues "brother" está "a la derecha" de "m_root" int n_brother = brother->Abs_n_child() - 1; if ( m_root->m_n_child == n_brother ) { return Tree( (NOT_null_pointer*) brother ); } else { return Tree( ); } #if 0 if (brother->m_n_child > 0) { if ( m_root->m_n_child + 1 == brother->m_n_child ) { return Tree( (NOT_null_pointer*) brother ); } else { return Tree( ); } } else { if ( m_root->m_n_child + 1 == - brother->m_n_child ) { return Tree( (NOT_null_pointer*) brother ); } else { return Tree( ); } } #endif } /** Retorna el valor absoluto del campo \c "m_n_child". - Hay que tomar en cuenta que que \c m_n_child está incrementado en \c +int(1) porque la marca de "puntero al padre" es un valor negativo, y como hay un hijo número cero \c int(0), no sería posible marcar como "puntero al padre" a ese nodo - Esta rutina también existe para documentar el truco del "puntero al padre", pues más directo habría sido usar la función \c abs() definida en \#include \ - En otras palabras, parte de la invariante de un nodo siempre será que (m_n_child != 0) porque siempre int(0) == int(-0) */ template inline unsigned Tree_Node::Abs_n_child() const { return ( m_n_child >= 0 ? unsigned(m_n_child) : unsigned( - m_n_child ) ); } /** \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: - C.Sibling( +0 ) == C - B.Sibling( +1 ) == C - E.Sibling( -2 ) == C - E.Sibling( -1 ) --> Vacío - A.Sibling( +1 ) --> Vacío - B.Sibling( -1 ) --> Vacío - E.Sibling( +1 ) --> Vacío \code A <-- T /|\ / / \ \ [] --> es representa un sub-árbol vacío B C [] E \endcode \par Complejidad: O( Father().Count_Children() ) */ template Tree Tree::Sibling( int n ) const { if (m_root == 0) { return Tree( ); } else if ( m_root->m_right_brother == 0 ) { return Tree( ); } else if ( n==0 ) { return Tree( (NOT_null_pointer*) m_root ); } Tree_Node* brother; // desde dónde comenzar a buscar en la lista de hermanos unsigned n_target; // número de hijo que hay que encontrar: "(m_n_child + n)" // averigua "n_target" (hay que manejar el "+1" del "puntero al padre") if ( n < 0 ) { // a la izquierda ==> busque al padre para comenzar en m_left_child unsigned n_child = m_root->Abs_n_child()-1; // assert( n_child >= 0 ); unsigned abs_n = unsigned(-n); // assert( abs_n > 0 ); if ( n_child < abs_n ) { // no se puede hacer la resta porque da un número de hijo negativo return Tree( ); // se sale pues no existen hijos antes del hijo más izquierdo } else { n_target = n_child - abs_n; // como el hermano está hacia la izquierda... // return Father().Child( n_target ); // ...hay que buscarlo desde el padre brother = m_root; while (brother->m_n_child > 0) { // se brinca los que no tienen el puntero al padre brother = brother->m_right_brother; } brother = brother->m_right_brother->m_left_child; // buscará desde el primer nodo } } else { // assert( n > 0 ); // a la derecha ==> busque desde aquí en adelante brother = m_root; n_target = unsigned(n) + m_root->Abs_n_child()-1; // assert( (n > 0) && (n_target > m_n_child) ); } // hay que manejar el "+1" del "puntero al padre" en "n_target" ++n_target; // para no tener que restarle int(1) a "child->m_n_child" // avance hacia la derecha en busca del hermano "n_target" // assert( brother != 0 ); for (;;) { if (brother->m_n_child < 0) { // es el último hijo if ( unsigned(- brother->m_n_child) == n_target ) { return Tree( (NOT_null_pointer*) brother ); } else { return Tree( ); // esa era el último ==> ya no hay dónde más buscar } } else { unsigned n_child = brother->m_n_child; if (n_child == n_target) { // lo encontró return Tree( (NOT_null_pointer*) brother ); } else if (n_child < n_target) { // siga buscando... brother = brother->m_right_brother; } else { // if (n_child > n_target) // ya se lo brincó; no está return Tree( ); } } } } /** Obtiene el hijo más izquierdo del árbol. - Este método usualmente se usa junto con \c Right_Sibling() \par Complejidad: O( \c 1 ) \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 */ template inline Tree Tree::Leftmost() const { if (m_root == 0) { return Tree( ); } return Tree( m_root->m_left_child ); // puede ser el puntero nulo } /** Obtiene el hijo más derecho del árbol. - Este método usualmente se usa junto con \c Left_Sibling() \par Complejidad: O( Count_Children() ) \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 */ template Tree Tree::Rightmost() const { if (m_root == 0) { return Tree( ); } Tree_Node* child = m_root->m_left_child; // soy el primer hijo de mi padre if (child == 0) { return Tree( ); } while (child->m_n_child > 0) { // todavía no se ha llegado al último hijo child = child->m_right_brother; } return Tree( (NOT_null_pointer*) child ); } /** 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 */ template void Tree::Count0(const Tree_Node * p, unsigned & n) { Tree_Node* child = p->m_left_child; // soy el primer hijo de mi padre if (child == 0) { return; } for (;;) { ++n; // cuenta a este hijo Count0( child, n ); if (child->m_n_child > 0) { // todavía no se ha llegado al último hijo child = child->m_right_brother; } else { break; } } } /** 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
O( \c Height() ) ==> espacio \see http://www.di-mare.com/adolfo/binder/c05.htm#sc03 */ template unsigned Tree::Count() const { if (m_root == 0) { return 0; } else { unsigned n = 1; // comienza contando en uno... Count0(m_root, n); // ... porque Count0() no cuenta la raíz return n; } } /** Retorna la cantidad de hijos del árbol. \par Complejidad: O( \c Count_Children() ) */ template unsigned Tree::Count_Children() const { if (m_root == 0) { return 0; } Tree_Node* child = m_root->m_left_child; if ( 0 == child ) { // no hay hijos return 0; } unsigned tot = 0; for (;;) { ++tot; // cuenta a este hijo if (child->m_n_child > 0) { // todavía no se ha llegado al último hijo child = child->m_right_brother; } else { break; } } return tot; } template inline bool operator == (const Tree &p, const Tree &q) { return Tree::Comp0(p.m_root, q.m_root); } template 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 operator==(Tree, Tree) . template 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->m_n_child != q->m_n_child ) { return false; // números de hijo diferentes } if ( ! (p->m_data == q->m_data) ) { return false; // valor diferente en la raíz } // A comparar a todos los hijos p = p->m_left_child; q = q->m_left_child; for (;;) { if (p == q) { // como se terminaron juntos... return true; // ...son iguales } if ( (p==0) || (q==0) ) { // son diferentes... return false; // ...pues sólo 1 está vácio } if ( p->m_n_child != q->m_n_child ) { return false; // números de hijo diferentes } if (! Comp0(p, q) ) { return false; // recorrido recursivo } if ( p->m_n_child < 0 ) { // assert( q->m_n_child < 0 ); return true; // ya no hay más hermanos } p = p->m_right_brother; q = q->m_right_brother; } } /** 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
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 */ template bool check_ok(const 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 unsigned N = T.Rightmost().Child_Number(); for (unsigned i = 0; i < 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 template Tree Tree::Change_Root(const value_type & d) { if (m_root == 0) { // como el árbol está vacío hay que agregarle la raíz m_root = Tree_Node::Get_New(d); // crea el nodo raíz m_root->m_left_child = 0; m_root->m_right_brother = 0; m_root->m_n_child = -1; } else { // como no hay más referencias.... m_root->m_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 !Empty() && (0 <= n) && (n < \e infinito) \par Complejidad: O( \c Count_Children() ) \returns Child(n) */ template Tree Tree::Change_Child(unsigned n, const value_type &d) { if (m_root == 0) { // ignora árboles vacíos return Tree( ); } n++; // evita incrementar "m_n_child" en cada iteración if (m_root->m_left_child == 0) { // Hay que agregar un sub-árbol nuevo Tree_Node * p = Tree_Node::Get_New(d); p->m_n_child = -int(n); p->m_right_brother = m_root; m_root->m_left_child = p; p->m_left_child = 0; return Tree ( (NOT_null_pointer*) m_root->m_left_child ); } // assert( m_root->m_left_child != 0 ); Tree_Node* brother = m_root->m_left_child; unsigned n_brother = brother->Abs_n_child(); if ( n < n_brother ) { // Hay que crear Child(n) y ponerlo de primero Tree_Node* p = Tree_Node::Get_New(d); p->m_n_child = +int(n); p->m_right_brother = brother; m_root->m_left_child = p; p->m_left_child = 0; return Tree ( (NOT_null_pointer*) p ); } else if ( n == n_brother ) { brother->m_data = d; // le cae encima al valor anterior return Tree ( (NOT_null_pointer*) brother ); } // Child(n) no es el primer hijo de "m_root" // assert( m_root->m_left_child != Child(n).m_root ); // assert( n_brother < n); // se corre hacia la derecha para encontrar "Child(n)" Tree_Node* prev = brother; for (;;) { if ( brother->m_n_child < 0 ) { if ( int(n) == - brother->m_n_child ) { brother->m_data = d; // le cae encima al valor anterior return Tree ( (NOT_null_pointer*) brother ); } else if (int(n) < - brother->m_n_child ) { Tree_Node* p = Tree_Node::Get_New(d); // ... [d] ==> [brother] ==> end p->m_n_child = int(n); p->m_right_brother = brother; prev->m_right_brother = p; p->m_left_child = 0; return Tree ( (NOT_null_pointer*) p ); } else { Tree_Node* p = Tree_Node::Get_New(d); // ... [brother] ==> [d] ==> end p->m_n_child = - int(n); p->m_right_brother = brother->m_right_brother; brother->m_n_child = - brother->m_n_child; // ahora el último es [d] brother->m_right_brother = p; p->m_left_child = 0; return Tree ( (NOT_null_pointer*) p ); } } else { // assert( brother->m_n_child > 0 ); if ( int(n) == brother->m_n_child ) { brother->m_data = d; // le cae encima al valor anterior return Tree ( (NOT_null_pointer*) brother ); } else if ( brother->m_n_child < int(n) ) { prev = brother; brother = brother->m_right_brother; } else { // como se acaba de pasar ==> hay que agregarlo después de "prev" Tree_Node* p = Tree_Node::Get_New(d); p->m_n_child = int(n); // como "brother" no es el último, tampoco lo será "p" p->m_right_brother = brother; prev->m_right_brother = p; p->m_left_child = 0; return Tree ( (NOT_null_pointer*) p ); } } } } /** Sustituye por \c "d" el valor almacenado en el hermano inmediatamente anterior del sub-árbol. - Si n == Child_Number() 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 !Empty() && (1 <= Child_Number()) \par Complejidad: O( Father().Count_Children() ) \returns El hermano izquierdo, Sibling(-1) */ template Tree Tree::Change_Left_Sibling_Inmediate( const E &d ) { unsigned n = Child_Number(); if (n > 0 ) { return Father().Change_Child( n-1, d ); } else { return Tree( ); } } /** Sustituye por \c "d" el valor almacenado en el hermano inmediatamente posterior del sub-árbol. - Si n == Child_Number() 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 !Empty() && ( Child_Number() < \e infinito ) \par Complejidad: O( \c 1 ) \returns El hermano derecho, Sibling(+1) */ template Tree Tree::Change_Right_Sibling_Inmediate( const value_type &d ) { if (m_root == 0) { return Tree( ); } if ( m_root->m_right_brother == 0 ) { // es la raíz del árbol y por eso no tiene hermanos return Tree( ); } Tree_Node * brother; if ( m_root->m_n_child < 0 ) { // "*this" es el último hijo m_root->m_n_child = - m_root->m_n_child; // ya "m_root" no es el último hijo brother = Tree_Node::Get_New( d ); brother->m_n_child = - ( m_root->m_n_child + 1 ); // "brother" es el último hijo brother->m_left_child = 0; brother->m_right_brother = m_root->m_right_brother; m_root->m_right_brother = brother; return Tree( (NOT_null_pointer*) brother ); } // assert( m_root->m_n_child > 0 ); int n_brother = m_root->m_right_brother->Abs_n_child(); if ( m_root->m_n_child + 1 == n_brother ) { m_root->m_right_brother->m_data = d; return Tree( (NOT_null_pointer*) m_root->m_right_brother ); } else { brother = Tree_Node::Get_New( d ); brother->m_n_child = m_root->m_n_child + 1; // "brother" no puede ser el último hijo brother->m_left_child = 0; brother->m_right_brother = m_root->m_right_brother; m_root->m_right_brother = brother; return Tree( (NOT_null_pointer*) brother ); } } /** 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 saca a \c "*p" de la lista de hijos del padre ==> ese es el trabajo de \c Graft() o \c Erase() - La rutina llamadora invoca \c Erase0() porque sabe que al decrementar \c "p->m_refCount" queda en cero - No decrementa \c "p->m_refCount" porque ya el invocador sabe que hay que destruir \c "*p" - Recursivamente, borra a los descendientes de \c "*p" \code // Forma usual de invocación if ( child->m_refCount <= 1 ) { // Ya no hay más referencias a "child" Erase0( child ); // lo elimina } else { child->m_refCount--; // uno menos le apunta child->m_n_child = -1; child->m_right_brother = 0; // ya no es hijo de nadie } \endcode \pre (p != 0) && (p->m_refCount == 1) \post No cambia \c "p" porque trabaja con una copia de su valor */ template void Tree::Erase0( Tree_Node * p ) { // assert( p != 0 ); // assert( p->m_refCount == 1 ); // Primero hay que matar hijos... if ( p->m_left_child != 0 ) { Tree_Node *next, *child = p->m_left_child; while ( child != 0 ) { // como hay hijos, decide a a cuáles matar if ( child->m_n_child < 0 ) { next = 0; // lo obliga a salir porque "child" es el último } else { next = child->m_right_brother; // recuerda quién es el siguiente } if ( child->m_refCount == 1 ) { Erase0( child ); // lo mata porque ésta es la última referencia // OJO: "child" está destruido ==> "child->m_right_brother" es un error } else { child->m_refCount--; // ya "*p" no le apunta child->m_n_child = -1; // ya no tiene padre porque "*p" va a morir child->m_right_brother = 0; // ni tampoco tiene hermanos } child = next; // hay que evitar usar "child->m_right_brother" si "child" ya está destruido } } #ifdef USE_v_Alive // Elimina a "p" de m_v_Alive[] for (unsigned j = 0; j < Tree_Node::N_Alive; ++j) { if (p == Tree_Node::m_v_Alive[j]) { // busca hasta que encuentra al puntero break; } } if (j < Tree_Node::N_Alive) { // sí lo encontró for (unsigned k = j; k < Tree_Node::N_Alive-1; ++k) { // corre a los demás para atrás Tree_Node::m_v_Alive[k] = Tree_Node::m_v_Alive[k+1]; } Tree_Node::m_n_Alive--; // ahora hay uno menos Tree_Node::m_v_Alive[ Tree_Node::m_n_Alive ] = 0; } else { for (unsigned k = 0; k<3; ++j) { // marca "feos" los del final Tree_Node::m_v_Alive[Tree_Node::N_Alive-1-k] = (Tree::Tree_Node *)(-1); } } #endif // Después de matar a los hijos, mata al nodo... delete p; // ... porque esta es la última referencia } /** Elimina el árbol y sus descendientes. \par Complejidad: O( \c Count() ) + O( Father().Count() ) ==> tiempo
O( \c Height() ) ==> espacio \see http://www.di-mare.com/adolfo/binder/c04.htm#sc03 */ template void Tree::Erase() { if (m_root == 0) { return; } // Encuentra el padre de "m_root" Tree_Node* brother = m_root; // camina sobre los hermanos hasta llegar al padre while (brother->m_n_child > 0) { brother = brother->m_right_brother; // se brinca los que no tienen el puntero al padre } Tree_Node* father = brother->m_right_brother; // assert( Father().Same( Tree( brother ) ) ); // Desconecta a "m_root" de la lista de hijos del padre if (father == 0) { // sólo la raíz tiene en blanco el puntero "m_right_brother" // no hay que desenlazar a la raíz porque nunca está en una lista de hermanos } else { // busca al "nodo anterior" para sacar a "m_root" de la lista de sus hermanos if ( m_root == father->m_left_child ) { // "m_root" es el hijo más izquierdo if ( m_root->m_n_child < 0 ) { father->m_left_child = 0; // elimina la lista de hijos porque "m_root" no tiene hermanos } else { father->m_left_child = m_root->m_right_brother; // desenlaza al primer hijo } } else { brother = father->m_left_child; // hijo más izquierdo de Father() while ( m_root != brother->m_right_brother ) { brother = brother->m_right_brother; } brother->m_right_brother = m_root->m_right_brother; // saca a "m_root" de la lista de hermanos } } // ahora ya puede detruir al nodo if ( m_root->m_refCount == 1 ) { Erase0(m_root); // mata al nodo porque ésta es la última referencia } else { m_root->m_refCount--; // lo va a desconectar de "m_root" m_root->m_n_child = -1; // ya no tiene padre m_root->m_right_brother = 0; // ni tampoco tiene hermanos } m_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( Child(n).Count() ) ==> tiempo
O( Height( Child(n) ) ) ==> espacio */ /** Elimina el sub-árbol número \c "n-1" y retorna un puntero al nodo anterior al borrado. - Esta es la rutina que en realidad hace el trabajo de \c Erase_Son(). - Elimina el sub-árbol número \c "n-1", como también lo hace \c Erase_Son(). - La única diferencia con \c Erase_Son() es que este método retorna un puntero al nodo anterior al nodo eliminado. - "prev" apunta al nodo que está antes de "prev" en el árbol. - Trabaja con \c "n-1" porque no incrementa el valor de \c "n", pues se supone que la rutina invocadora ya hizo ese ajuste en el valor originar de \c "n". - Esta rutina existe para compartir el código que se necesita para implementar \c Erase_Son() y \c Graft(). - Si retorna 0 == NULL es porque Nodo[n-1] debe ser el primero en la lista de hijos del padre. \remark [Eliminado porque ya no hace falta] - "prev_prev" apunta al nodo que está antes de "prev" en el árbol. - Si "prev" y "prev_prev" son la misma variable, el valor correcto para "prev" es calculado. */ template void Tree::Erase_Son_Prev(unsigned n, Tree_Node* & prev /*, Tree_Node* & prev_prev */) { // prev_prev = 0; // el que está "antes" de "prev" prev = 0; // nodo que antecede a "child" if (m_root == 0) { // ignora árboles vacíos return; } Tree_Node* child = m_root->m_left_child; // "child" es el nodo que hay que eliminar if ( child == 0 ) { // no hay hijos ==> el Nodo[n] es un sub-árbol vacío return; } // n++; // sobra, porque la rutina invocadora ya ajustó el valor a cotejar con "m_n_child" // camina sobre los hermanos hasta llegar a Nodo[n] if ( child->m_n_child <= 0 ) { // sólo hay un hijo unsigned n_child = - child->m_n_child; if ( n == n_child ) { // es el único hijo y hay que eliminarlo if ( child->m_refCount <= 1 ) { // aquí saca a "child" de la lista de hijos de "m_root" Erase0( child ); } else { child->m_refCount--; child->m_n_child = -1; child->m_right_brother = 0; // ya no es hijo de nadie } m_root->m_left_child = 0; return; } else { // no hace falta eliminar a nadie pues Child(n) es un sub-árbol vacío // hay que determinar adónde debe apuntar "prev" if ( n > n_child ) { // prev_prev = prev; prev = child; return; // porque el n-ésimo hijo estará después de "child" } else { // assert( n < n_child ); return; // el n-ésimo hijo quedará de primero en la lista de hijos del padre } } } // assert( (child->m_n_child > 0) && (Count_Children() > 1) ); for (;;) { if (child->m_n_child <= 0) { // hay que eliminar el último hijo if ( unsigned(- child->m_n_child) == n ) { // assert( prev != 0 ); prev->m_right_brother = child->m_right_brother; prev->m_n_child = - prev->m_n_child; // este es el nuevo último if ( child->m_refCount <= 1 ) { Erase0( child ); } else { child->m_refCount--; child->m_n_child = -1; child->m_right_brother = 0; // ya no es hijo de nadie } } else if ( unsigned(- child->m_n_child) < n ) { // no encontró al hermano con m_n_child == n // prev_prev = prev; prev = child; } break; } else if ( unsigned(child->m_n_child) == n ) { if ( prev == 0 ) { m_root->m_left_child = child->m_right_brother; } else { prev->m_right_brother = child->m_right_brother; } if ( child->m_refCount <= 1 ) { Erase0( child ); } else { child->m_refCount--; child->m_n_child = -1; child->m_right_brother = 0; // ya no es hijo de nadie } break; } else if ( unsigned(child->m_n_child) < n) { // prev_prev = prev; prev = child; child = child->m_right_brother; } else { // assert( unsigned(child->m_n_child) > n ); break; // no encontró al hermano con m_n_child == n } } } /** 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&) */ template 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->m_refCount porque copia los nodos - El campo \c p->m_right_brother queda con basura porque no queda inicializado - Le corresponde a la rutina invocadora inicializar \c p->m_right_brother \pre p != 0 \post No cambia \c "p" porque trabaja con una copia de su valor \returns Puntero al nodo raíz del árbol copiado */ template Tree_Node * Tree::Copy_Deep0(const Tree_Node * p) { Tree_Node * q; // resultado q = Tree_Node::Get_New(p->m_data); // m_refCount = 1; q->m_n_child = p->m_n_child; if ( p->m_left_child == 0 ) { q->m_left_child = 0; } else { // cuando hay hijos los copia Tree_Node * pChild = p->m_left_child; Tree_Node * qChild = Copy_Deep0( pChild ); // copia el primer nodo q->m_left_child = qChild; while ( pChild->m_n_child > 0 ) { pChild = pChild->m_right_brother; qChild->m_right_brother = Copy_Deep0( pChild ); qChild = qChild->m_right_brother; } qChild->m_right_brother = q; // "q" es el padre de todos } 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 *this == o \par Complejidad: O( \c Count() ) + O( \c o.Count() ) \returns \c *this \see http://www.di-mare.com/adolfo/binder/c04.htm#sc05 */ template Tree& Tree::Copy_Deep(const Tree &o) { // Borra el valor actual if (m_root != 0) { if ( m_root->m_refCount == 1 ) { // como es el último... Erase0(m_root); // ...lo mata } else { m_root->m_refCount--; } } // Hace la copia desde "o" if (o.m_root != 0 ) { m_root = Copy_Deep0( o.m_root ); m_root->m_n_child = -1; // es el nodo raíz m_root->m_right_brother = 0; m_root->m_refCount = 1; } else { m_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 [ Erase_Son(n) ] \pre - ! Root().Empty() - Si el árbol está vacío no tiene raíz, y por lo tanto tampoco puede tener hijos - ! Ancestor(o, *this) - "o" no puede ser ancestro de *this" - (0 <= n) && (n < \e infinito) - ! Root(). Same( o.Root() ) \post - \c "o" deja de ser sub-árbol del árbol en que estaba - o.Father() .Same( Root() ) \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 [ ! Root() .Same( o.Root() ) ] - 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( o.Father().Count_Children() ) */ template Tree Tree::Graft(unsigned n, Tree &o) { if (m_root == 0) { // ignora árboles vacíos return Tree( ); } if (m_root == o.m_root) { // evita auto-borrado return *this; } #ifdef FALTA_verificar_en_Graft bool Ancestor( Tree & Child, Tree & Father ); assert( ! Ancestor( o, *this ) ); // "o" no puede ser ancestro de *this" #endif n++; // lo incrementa para no incrementar "m_n_child" para cada hijo de "m_root" o de "o" if ( o.m_root == 0 ) { // Sólo hay que eliminar el hijo número "n" de "m_root" Tree_Node * prev; Erase_Son_Prev(n, prev /*, prev */); return Tree( ); // si se vale repetir "prev" en Erase_Son_Prev() } // assert( o.m_root != 0 ); // Determina quién es el padre de "o" Tree_Node * brother = o.m_root; while ( brother->m_n_child > 0 ) { brother = brother->m_right_brother; } Tree_Node * o_father = brother->m_right_brother; // éste es el padre de "o" Tree_Node * prev; if ( o_father != m_root ) { /* El puntero "prev" apunta al nodo después del que hay que injertar "o". - Si "prev == 0" hay que poner a "o" de primero en lista de hijos de "m_root". - Si "prev != 0" hay que instalar "o" después de "prev". - Aquí es donde se usa Erase_Son_Prev(). */ // Elimina el hijo número "n" de "m_root" Erase_Son_Prev(n, prev /*, prev */); // assert( Child(n-1).Empty() ); // Ojo: mata "Child(n-1)" porque ya "n" está incrementado } else { // assert( o_father == m_root ); // Caso especial ==> T.Graft( T.Child(n), n ± i ); unsigned o_n_child = o.m_root->Abs_n_child(); if ( o_n_child == n ) { // Caso especial cuando "o" ya es hijo de "m_root" // "o" está en su lugar ==> no hay que hacer nada // [y hay que evitar borrarlo con Erase_Son(n)] return Tree( (NOT_null_pointer*) o.m_root ); } Erase_Son_Prev(n, prev /*, prev */); if ( (prev == o.m_root) || (prev != 0 && prev->m_right_brother == o.m_root ) ) { // ya "o" está en donde debe if ( o.m_root->m_right_brother == m_root ) { // basta cambiar "m_n_child" o.m_root->m_n_child = - int(n); } else { o.m_root->m_n_child = + int(n); } return Tree( (NOT_null_pointer*) o.m_root ); } } if (o_father != 0) { // Saca a "o" de la lista de hijos de su padre o.m_root->m_refCount--; // pues no estará en la lista de hijos de su padre actual assert( o_father->m_left_child != 0 ); if ( o.m_root == o_father->m_left_child ) { // "o" es el primer hijo if ( o.m_root->m_n_child < 0 ) { // "o" es el único hijo o_father->m_left_child = 0; } else { // "o" tiene hermanos o_father->m_left_child = o.m_root->m_right_brother; } } else { brother = o_father->m_left_child; // hermano más izquierdo de "o" while ( brother->m_right_brother != o.m_root ) { brother = brother->m_right_brother; } brother->m_right_brother = o.m_root->m_right_brother; if ( o.m_root->m_n_child < 0 ) { // "o" estaba de último hijo brother->m_n_child = - brother->m_n_child; // hay un nuevo hijo de último } } } // assert( o.Father().Empty() ); // ya "o" está solito y sin familia o.m_root->m_refCount++; // lo incrementa porque lo va a enlazar como hijo de "m_root" if ( prev == 0 ) { // enlaza "o" al principio de la lista de hijos de "m_root" if ( m_root->m_left_child == 0 ) { o.m_root->m_right_brother = m_root; // "o" será el único hijo de "m_root" o.m_root->m_n_child = - int(n); m_root->m_left_child = o.m_root; } else { o.m_root->m_right_brother = m_root->m_left_child; // assert( o.m_root->m_right_brother != m_root ); o.m_root->m_n_child = + int(n); m_root->m_left_child = o.m_root; } } else { // assert( prev != 0 ); // enlaza en el medio de la lista de hijos de "m_root" o.m_root->m_right_brother = prev->m_right_brother; prev->m_right_brother = o.m_root; if ( o.m_root->m_right_brother == m_root ) { prev->m_n_child = - prev->m_n_child; // ya "prev" no está de último o.m_root->m_n_child = - int(n); } else { o.m_root->m_n_child = + int(n); } } return Tree( (NOT_null_pointer*) o.m_root ); /* ¿Por qué hay que usar "prev_prev"? En realidad no hace falta, pero sí hay que destacar un caso especial, cuando "o" es hijo de "*this", o sea cuando: - ( Root(). Same( o.Root() ) ) R T.Erase(); T = 'R'; / \ T.Change_Child(1, '1'); 1 3 T.Change_Child(3, '3'); Al ejecutar T.Graft( 5 , T.Child(3) ); lo que hay que hacer es desligar el Nodo['3'] de su padre, el árbol T que tiene por raíz a Nodo['A'], para ligarlo de nuevo como Nodo['5']. Para este caso, "prev" apunto a T.Child(3), pues es después de Nodo['3'] en donde habría que enlazar a Nodo['5']. Desafortunadamente, como el primer paso del algoritmo saca de T a Nodo[3], al tratar de enlazarlo luego de "prev" en realidad lo que se haría es enlazar al nodo después de sí mismo; estor resulta en la "desaparición misteriosa" de Nodo['3']. Por eso, la solución a este caso especial, es retornar no "prev", sino "prev_prev", que apunta al nodo anterio al Nodo[5], que en este caso es Nodo['1']. */ } // Graft() } // namespace TL #endif // Tree_L_h // EOF: Tree_L.h