// test_Bin_Tree.cpp (c) 2007 adolfo@di-mare.com

/** \file  test_Bin_Tree.cpp
    \brief Prueba de caja negra de la clase \c Bin_Tree<E>.

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

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

#define lkptr_NULL_POINTERS_ARE_ALONE
#undef  lkptr_NULL_POINTERS_ARE_ALONE
#include "Bin_Tree.h"
#include "Bin_Tree_Lib.h"
#include "BUnit.h"

#include <iostream>
#include <vector>
#include <algorithm> // sort() && next_permutation()
#include <cassert>   // assert()
#include <iostream>  // cout

/// Prueba la clase \c Bin_Tree<E>.
template <class E>
class test_Bin_Tree : public TestCase {
public:
    bool run();
    void do_cout();
    void test_copyDeep();
    void test_homomorfo();
    void test_make_FBHCID();
    void test_make_ab_no();
    void test_swap();
    void test_mirror();
    void test_changeChild();
    void test_heightdepth();
    void test_releaseChild();
    void test_makeOrphan();
    void test_left_right();
    void test_no_swap();
    void test_move_swap();
    void test_multi_child();
    void test_isLeft_isRight();
    void test_isRoot_isLeaf();
    void test_sizeStrong();
    void test_AVL_tree();
}; // test_Bin_Tree

/// Método principal de la prueba.
/// - Requiere que recién haya sido ejecutado \c setUp()
template <class E>
bool test_Bin_Tree<E>::run() {
    test_make_FBHCID();
    test_make_ab_no();
    test_copyDeep();
    test_homomorfo();
    test_swap();
    test_mirror();
    test_changeChild();
    test_heightdepth();
    test_releaseChild();
    test_makeOrphan();
    test_left_right();
    test_no_swap();
    test_move_swap();
    test_multi_child();
    test_isLeft_isRight();
    test_isRoot_isLeaf();
    test_sizeStrong();
    test_AVL_tree();
    return wasSuccessful();
}

/** Construye el árbol de letras \c (F (B (C (D))) (H (I))).
    - Graba en \c COUT los resultados intermedios.
    \code
       F
      / \       F
     B   H      B F
      \   \     B F H
       C   I    B C F H
        \       B C D F H I
         D
    \endcode
*/
Bin_Tree<char> make_FBHCID( std::ostream& COUT ) {
    Bin_Tree<char> T;
    orderedInsert( T, 'F' );  IPD ( COUT, T ); COUT << std::endl;
    orderedInsert( T, 'B' );  IPD ( COUT, T ); COUT << std::endl;
    orderedInsert( T, 'H' );  IPD ( COUT, T ); COUT << std::endl;
    orderedInsert( T, 'C' );  IPD ( COUT, T ); COUT << std::endl;
    orderedInsert( T, 'I' );  IPD ( COUT, T ); COUT << std::endl;
    orderedInsert( T, 'D' );  IPD ( COUT, T ); COUT << std::endl;
    return T;
}

/** Construye el árbol de letras \c (F (B (C (D))) (H (I))).
    \code
       F
      / \
     B   H
      \   \
       C   I
        \
         D
    \endcode
*/
Bin_Tree<char> make_FBHCID() {
    Bin_Tree<char> T;
    orderedInsert( T, 'F' );
    orderedInsert( T, 'B' );
    orderedInsert( T, 'H' );
    orderedInsert( T, 'C' );
    orderedInsert( T, 'I' );
    orderedInsert( T, 'D' );
    return T;
}

/// Verifica que \c make_FBHCID() construyó el árbol correctamente.
template <class E>
void test_Bin_Tree<E>::test_make_FBHCID() {
    Bin_Tree<char> T = make_FBHCID();
    assertTrue( T.size() == strlen( "FBHCID" ) );

    assertTrue( T.root().data() == 'F' );
    assertTrue( T.root().left().data() == 'B' );
    assertTrue( T.root().left().right().data() == 'C' );
    assertTrue( T.root().left().right().right().data() == 'D' );
    assertTrue( T.root().right().data() == 'H' );
    assertTrue( T.root().right().right().data() == 'I' );

    std::basic_ostringstream<char> ost; // receptor de salida
    ost << T;
    assertTrue( ost.str() == "(F (B (C (D))) (H (I)))" );
    assertTrue( T.ok() );
}

/** Construye el árbol de letras \c (a (b (f) (h)) (e (i) (k (l) (m (n) (o))))).
\code
       a
      / \
     /   \
    b     e
   / \   / \
  f   h i   k
           / \
          l   m
             / \
            n   o
\endcode
*/
Bin_Tree<char> make_ab_no() {
    Bin_Tree<char> T, T1, T2;

    T1 = Bin_Tree<char>('b'); {
        T1.makeLeftChild(  Bin_Tree<char>('f') );
        T1.makeRightChild( Bin_Tree<char>('h') );
    }

    T2.changeRoot('k'); {
        T2.makeLeftChild(  Bin_Tree<char>('l') );
        T.changeRoot('m'); {
            T.makeLeftChild(  Bin_Tree<char>('n') );
            T.makeRightChild( Bin_Tree<char>('o') );
        }
        T2.makeRightChild( T );
    }
    T.erase();
    T.changeRoot('a'); {
        T.makeLeftChild( T1 );
        T.makeRightChild(  Bin_Tree<char>('e') ); {
            T.right().makeLeftChild(  Bin_Tree<char>('i') );
            T.right().makeRightChild( T2 );
        }
    }
    return T;
}

/// Verifica que \c make_ab_no() construyó el árbol correctamente.
/// - \c (a (b (f) (h)) (e (i) (k (l) (m (n) (o)))))
template <class E>
void test_Bin_Tree<E>::test_make_ab_no() {
    std::basic_ostringstream<char> ost; // receptor de salida
    ost << make_ab_no();
    assertTrue( ost.str() == "(a (b (f) (h)) (e (i) (k (l) (m (n) (o)))))" );
    assertTrue( make_ab_no().ok() );
}

/// Pasa a minúscula todas las letras de \c "T".
void toLower( Bin_Tree<char> T ) {
    if ( T.isEmpty() ) {
        return;
    }
    T.changeRoot( tolower( *T ) );
    toLower( T.left() );
    toLower( T.right() );
}

/// Verifica que \c Bin_Tree<E>::copyDeep() funciona correctamente.
template <class E>
void test_Bin_Tree<E>::test_copyDeep() {
    Bin_Tree<char> T, T1, T2;
    T.changeRoot( 'A' );
    T.makeLeftChild(  Bin_Tree<char>( 'B' ) );
    T.makeRightChild( Bin_Tree<char>( 'C' ) );
    copyDeep( T1, T );

    copyDeep( T2, T1 ); {
        assertTrue( ! T1.same( T2 ) );
        assertTrue( T1 == T2 );
    }
    T1 = T2; {
        assertTrue( T1.same( T2 ) );
        toLower( T2 );
        assertTrue( T1 == T2 );
    }

    T1 = make_FBHCID(); {
        assertTrue( T1 != T2 );
    }

    copyDeep( T1, T ); {
        assertTrue( ! T1.same( T2 ) );
        assertTrue( T1 != T2 );
        toLower( T1 );
        assertTrue( T1 == T2 );
    }
}

/// Verifica que \c make_FBHCID() construyó el árbol correctamente.
template <class E>
void test_Bin_Tree<E>::test_homomorfo() {
    Bin_Tree<char> T1 = make_FBHCID();
    Bin_Tree<char> T2 = T1, Tmp;
    assertTrue( homomorfo( T1 , T2 ) );
    copyDeep( T2, T1 );
    toLower( T1 );
    assertTrue( TestCase::toString( T1 ) == "(f (b (c (d))) (h (i)))" );
    assertTrue( TestCase::toString( T2 ) == "(F (B (C (D))) (H (I)))" );
    T2.makeRightChild(T1);
    assertTrue( toString( T1 ) == "(f (b (c (d))) (h (i)))" );
    assertTrue( toString( T2 ) == "(F (B (C (D))) (f (b (c (d))) (h (i))))" );
    copyDeep( T1, T2 );
    assertTrue( toString( T1 ) == "(F (B (C (D))) (f (b (c (d))) (h (i))))" );
    assertTrue( toString( T2 ) == "(F (B (C (D))) (f (b (c (d))) (h (i))))" );
    assertTrue( homomorfo( T1 , T2 ) );
    assertTrue( homomorfo( T2 , T1 ) );
    mirror( T2.left() );  // Tmp = T2.left();  mirror( Tmp );
    mirror( T2.right() ); // Tmp = T1.right(); mirror( Tmp );
    assertTrue( homomorfo( T1 , T2 ) );
    assertTrue( homomorfo( T2 , T1 ) );
}

/// Verifica que \c Bin_Tree<E>::swap() funciona correctamente.
template <class E>
void test_Bin_Tree<E>::test_swap() {
    Bin_Tree<char> T1 = make_FBHCID();
    Bin_Tree<char> T2 = 'A';
    assertTrue( T1.father().isEmpty() );

    T2.swap(T1);

    assertTrue( T1.size() == 1 ); {
        std::basic_ostringstream<char> ost; // receptor de salida
        IPD(ost , T2);
        assertTrue( ost.str() == " B C D F H I" );
    }
    assertTrue( comp( T2.left().father(),  T2 ) );
    assertTrue( comp( T2.right().father(), T2 ) );
    assertTrue( comp( T1.left(), Bin_Tree<char>() ) ) ;
    assertTrue( comp( T2.left().left(), Bin_Tree<char>() ) ) ;
    assertTrue( comp( T2.left().right().right(), Bin_Tree<char>('D') ) ) ;
    assertTrue( comp( T2.right().right(), Bin_Tree<char>('I') ) ) ;
    T1.changeRoot( 'H' );
    T1.makeRightChild( Bin_Tree<char>('I') );
    assertTrue( comp( T2.right(), T1) ) ;
}

/// Verifica que \c Bin_Tree<E>::mirror() funciona correctamente.
template <class E>
void test_Bin_Tree<E>::test_mirror() {
    Bin_Tree<char> T1 = make_FBHCID();
    assertTrue( T1.count() == 6 && height(T1) == 3 ); {
        std::basic_ostringstream<char> ost; // receptor de salida
        IPD(ost , T1);
        assertTrue( ost.str() == " B C D F H I" );
    }

    mirror( T1 );

    assertTrue( T1.count() == 6 && height(T1) == 3 ); {
        std::basic_ostringstream<char> ost; // receptor de salida
        IPD(ost , T1);
        assertTrue( ost.str() == " I H F D C B" );
    }

    Bin_Tree<char> T2 = T1;
    assertTrue( comp(T1,T2) ); assertTrue( comp(T2,T1) );

    copyDeep(T2,T1);
    char ch = T1.data();
    T1 = ch+1;  assertTrue( ! comp(T1, T2) );
    T1 = ch;    assertTrue(   comp(T1, T2) );

    copyDeep(T2,T1);
    ch = T1.data();
    T1 = ch+1;  assertTrue( ! comp(T1, T2) );
    T1 = ch;    assertTrue(   comp(T1, T2) );

    mirror( T1 );
    mirror( T2 );

    assertTrue( comp(T1, T2) );
    copyDeep( T2, T1 );
    assertTrue( comp(T1, T2) );

    assertTrue( T1.count() == 6 && height(T1) == 3 ); {
        std::basic_ostringstream<char> ost; // receptor de salida
        IPD(ost , T1);
        assertTrue( ost.str() == " B C D F H I" );
    }

    T2.left().changeRoot( 'X' );
    assertTrue( T2.count() == 6 && height(T2) == 3 ); {
        std::basic_ostringstream<char> ost; // receptor de salida
        IPD(ost , T2);
        assertTrue( ost.str() == " X C D F H I" );
    }

    T2.erase();
    assertTrue( !comp(T1, T2) );
}

/// Verifica que \c changeLeftChild() y \c changeRightChild() funcionan correctamente.
template <class E>
void test_Bin_Tree<E>::test_changeChild() {
    {{  // test::changeChild()
        Bin_Tree<char> T, Tcopy;
        T = 'A'; // agrega la raiz 'A'    A
        T.changeLeftChild(  '0' );  //  ./ \.
        T.changeRightChild( '1' );  //  0   1
        copyDeep( Tcopy , T );
        assertTrue( TestCase::toString(T) == "(A (0) (1))" );
        mirror( T );
        assertTrue( TestCase::toString(T) == "(A (1) (0))" );
        mirror( T ); {
            std::basic_ostringstream<char> ost;
            ost << T;
            assertTrue( ost.str() == "(A (0) (1))" );
        }

        assertTrue( comp(T, Tcopy) );
    }}
    {   // Resto de las pruebas
        Bin_Tree<char> T2;
        T2 = 'A';    // inserta la raiz           //    'A'
        T2.changeLeftChild('0'); {                //    /
            std::basic_ostringstream<char> ost;   //   0
            IPD (ost , T2);
            assertTrue( ost.str() == " 0 A" );
        }

        mirror( T2 ); {
            std::basic_ostringstream<char> ost;
            IPD (ost , T2);
            assertTrue( ost.str() == " A 0" );
        }
        assertTrue( T2.count() == 2 );
    }
}

/// Verifica que \c releaseLeftChild() y \c releaseRightChild() funcionan correctamente.
template <class E>
void test_Bin_Tree<E>::test_releaseChild() {
    {{  // test::releaseChild()
        Bin_Tree<E> Paco = E();     // Paco    Lola //
        Bin_Tree<E> Lola = E();     //              //
        Bin_Tree<E> Bebe;           //   E()   E()  //
        Lola.makeLeftChild( E() );  //     \\ /     //
        Bebe = Lola.left();         //     Bebe     //
        Bebe.makeLeftChild(  E() ); //     // \\    //
        Bebe.makeRightChild( E() ); //   E()   E()  //
        Paco.makeRightChild( Bebe );

        Paco.releaseLeftChild();
        assertTrue( 4 == Paco.size() ); // Paco no tiene hijo izquierdo
        Paco.releaseRightChild();
        assertTrue( 1 == Paco.size() ); // Ya Paco no tiene hijo derecho
        assertTrue( Paco.right() == Bin_Tree<E>() ); // El hijo derecho es un árbol vacío
        assertTrue( Bebe != Bin_Tree<E>() );         // Bebe todavía existe
        assertTrue( Bebe.father() == Paco );  // Paco sigue registrado como padre de Bebe

        assertTrue( 4 == Lola.size() ); // Lola todavía tiene a su hijo izquierdo
        assertTrue( Bebe.same( Lola.left() ) ); // Bebe si es hijo izquierdo de Lola
        assertTrue( Lola.left().same( Bebe ) ); // Lola si tiene hijo izquierdo
        assertTrue( Bebe.father() != Bin_Tree<E>() ); // Bebe no está registrado como hijo de Lola

        Lola.releaseLeftChild(); // Ahora ya Bebe no es hijo de Lola
        assertTrue( ! Bebe.same( Lola.left() ) );
        assertTrue( 1 == Lola.size() ); // Ya Lola no tiene hijos
    }}
}

/// Verifica que \c makeOrphan() funciona correctamente.
template <class E>
void test_Bin_Tree<E>::test_makeOrphan() {
    using namespace std;
    {{  // test::makeOrphan()
        Bin_Tree<E> Paco = E();     // Paco    Lola //
        Bin_Tree<E> Lola = E();     //              //
        Bin_Tree<E> Bebe;           //   E()   E()  //
        Lola.makeLeftChild( E() );  //     \\ /     //
        Bebe = Lola.left();         //     Bebe     //
        Bebe.makeLeftChild(  E() ); //     // \\    //
        Bebe.makeRightChild( E() ); //   E()   E()  //
        Paco.makeRightChild( Bebe );

        assertTrue( Bebe.same( Lola.left()  ) ); // Bebe si es hijo izquierdo de Lola
        assertTrue( Bebe.same( Paco.right() ) ); // Bebe si es hijo derecho de Paco
        assertTrue( Bebe.father() == Paco );     // Bebe está registrado como hijo de Paco
        assertTrue( Bebe.father() != Lola );     // Bebe no está registrado como hijo de Lola

        Bebe.makeOrphan();
        assertTrue( Bebe.father() != Paco );          // Ya Paco no está registrado como el padre de Bebe
        assertTrue( Bebe.father() == Bin_Tree<E>() ); // Bebe no tiene registrado a nadie como su padre

        assertTrue( Bebe.same( Lola.left() ) );  // Bebe sigue registrado como hijo izquierdo de Lola
        assertTrue( Bebe.same( Paco.right() ) ); // Bebe sigue registrado como hijo derecho de Paco
        assertTrue( Bebe.father() != Paco );     // Bebe ya no está registrado como hijo de Paco
        assertTrue( Bebe.father() != Lola );     // Bebe ya no está registrado como hijo de Lola
    }}
}

/// Verifica que \c left() y \c right() funcionan correctamente.
template <class E>
void test_Bin_Tree<E>::test_left_right() {
    using namespace std;
    {{  // test::left_right()
        Bin_Tree<E> T = E(); // no hay hijo izquierdo alguno
        {   T.left() = E();    // sí hace el cambio
            // pero el destructor elimina la referencia
        }   // sin modificar el hijo izquierdo que no existe
        assertTrue( T.size() == 1 );
        assertTrue( T.left().isEmpty() ); // "T.left()" es una nueva referencia al hijo de "T"

        T.makeRightChild( E() ); // esta es la forma de crear un nuevo sub-árbol derecho
        T.right().erase(); // no elimina al hijo derecho: borra la nueva referencia "right()"
        assertTrue( T.size() == 2 );
        assertTrue( ! T.right().isEmpty() ); // el hijo derecho está ahí todavía

        {   // Para eliminar a un hijo hay que poner el árbol nulo en su lugar
            T.right() = Bin_Tree<E>(); // cambia la referencia: el hijo derecho sigue ahí
            assertTrue( ! T.right().isEmpty() ); // el hijo derecho está ahí todavía

            assertTrue( Bin_Tree<E>().isEmpty() ); // referencia nula: árbol vacío

            // esta es la forma correcta de eliminar hijos
            T.makeRightChild( Bin_Tree<E>() ); // elimina al hijo derecho
            assertTrue( T.right().isEmpty() ); // ya no existe el hijo derecho
        }

        if ( T.right().isEmpty() ) {
            if (false) {
                *T.right() = E(); // ERROR: Trata de cambiar un árbol vacío
            }
            T.makeRightChild( E() ); // nuevo hijo derecho
        }
        else {
            T.right().changeRoot( E() ); // sí cambia el valor almacenado
            *( T.right() ) = E(); // efecto similar al renglón anterior
        }
        T = T.right(); // caminar hacia las hojas no cambia el valor almacenado
        assertTrue ( ! T.father().isEmpty() );
        assertTrue( T.size() == 1 );
        T = T.father();
        assertTrue( T.size() == 2 );
        T.right().erase(); // no cambia nada
        assertTrue( T.size() == 2 );

        Bin_Tree<E> Child = T.right();     // sostiene al hijo
        T.right().makeOrphan();            // elimna la conexión hijo->padre
        assertTrue( T.right() == Child );  // no eliminó la conexión hijo->padre
        assertTrue( Child.father() != T ); // ni el antiguo hijo encuentra a su padre
        assertTrue ( ! T.isEmpty() );
        assertTrue ( ! Child.isEmpty() );
        assertTrue ( Child.father().isEmpty() ); // ni el antiguo hijo tiene padre
    }}
}

/// Muestra que \c swap() trabaja en una referencia.
template <class E>
void test_Bin_Tree<E>::test_no_swap() {
    {{  // test::no_swap()
        Bin_Tree<E> T = E();      //  E()     //
        Bin_Tree<E> Right;        //    \     //
        T.makeRightChild( E() );  //     E()  //

        assertTrue( T.size() == 2 );
        assertTrue( T.right().isRightChild() ); // Ahí está el hijo derecho
        Right = T.right();  // no compila >==> T.left().swap( T.right() );
        T.left().swap( Right );
        assertTrue( T.right().isRightChild() ); // El hijo derecho no ha cambiado
        assertTrue( T.size() == 2 );

        T.makeLeftChild( T.right() );            //    E()   //
        assertTrue( T.size() == 3 );             //   /   \  //
        assertTrue( T.left().same( T.right()) ); //   \   /  //
        assertTrue( T.right().isRightChild() );  //    E()   //
        assertTrue( T.left().isLeftChild() );    // hijo compartido

        T.makeLeftChild( T.right() );            // ahora sí cambió el árbol
        T.makeRightChild( Bin_Tree<E>() );       // borra al hijo derecho
        assertTrue( T.size() == 2 );
        assertTrue( ! T.left().same( T.right()) );
        assertTrue( ! T.right().isRightChild() ); // si hay hijo derecho
        assertTrue( T.left().isLeftChild() );     // Ahí está el antiguo hijo derecho
    }}
    {   // Autociclo a la izquierda
        Bin_Tree<E> T = E();
        T.makeLeftChild( T ); // autociclo
        for ( int i=0; i<11; ++i ) {
            T = T.left();
            assertTrue( ! T.isEmpty() );
        }
        assertTrue( ! T.isEmpty() );
    }
    {   // Autociclo a la derecha
        Bin_Tree<E> T = E();
        T.makeRightChild( T ); // autociclo
        for ( int i=0; i<22; ++i ) {
            T = T.right();
            assertTrue( ! T.isEmpty() );
        }
        assertTrue( ! T.isEmpty() );
    }
    {   // Autociclo a la derecha               //  E()       //
        Bin_Tree<E> T = E();                    //    \       //
        T.makeRightChild( E() );                //    E()     //
        T.right().makeRightChild( E() );        //      \     //
                                                //      E()   //
        assertTrue( T.size() == 3 );
        T.right().right().makeRightChild( T );  //  E() <---+ //
        for ( int i=0; i<33; ++i ) {            //    \     | //
            T = T.right();                      //    E()   | //
            assertTrue( ! T.isEmpty() );        //      \   | //
        }                                       //      E() | //
        assertTrue( ! T.isEmpty() );            //        \-+
    }
    if ( false) {
        // Muestra cómo funcionaría el árbol un sub-arbol
        // pudiera ser hijo sólo de un único árbol
        Bin_Tree<E> T = E();      //  E()     //
        Bin_Tree<E> Right;        //    \     //
        T.makeRightChild( E() );  //     E()  //

        T.makeLeftChild( T.right() );              //   E()   //
        assertTrue( T.size() == 2 );               //   /     //
        assertTrue( ! T.left().same( T.right()) ); // E()     //
        assertTrue(  T.left().isLeftChild() );
        assertTrue( ! T.right().isRightChild() );

        T.makeRightChild( T.left() );              //  E()     //
        assertTrue( T.size() == 2 );               //    \     //
        assertTrue( ! T.right().same( T.left()) ); //     E()  //
        assertTrue( T.right().isRightChild() );
        assertTrue( ! T.left().isLeftChild() );

        assertTrue( T.size() == 2 );
        assertTrue( T.right().isRightChild() ); // Ahí está el hijo derecho
        Right = T.right();    // no compila ==> T.left().swap( T.right() );
        T.left().swap( Right );
        assertTrue( T.right().isRightChild() ); // El hijo derecho no ha cambiado
        assertTrue( T.size() == 2 );
    }
}

/// Verifica que \c move() y \c swap() funcionan correctamente.
template <class E>
void test_Bin_Tree<E>::test_multi_child() {
    {{  // test::multi_child()
        // Muestra que un mismo árbol "Bebe" puede ser sub-árbol
        // de varios árboles
        Bin_Tree<E> Paco = E();     // Paco    Lola //
        Bin_Tree<E> Lola = E();     //              //
        Bin_Tree<E> Bebe;           //   E()   E()  //
        Lola.makeLeftChild( E() );  //     \\ /     //
        Bebe = Lola.left();         //     Bebe     //
        Bebe.makeLeftChild(  E() ); //     // \\    //
        Bebe.makeRightChild( E() ); //   E()   E()  //
        Paco.makeRightChild( Bebe );

        // Como se muestra en el diagrama X, debido a este último cambio
        // el padre registrado de Bebe ahora es Paco

        assertTrue( 3 == Bebe.size() );
        assertTrue( 4 == Paco.size() ); // 3 de Bebe + Paco
        assertTrue( 4 == Lola.size() ); // 3 de Bebe + Lola

        assertTrue( Paco.right().same( Bebe ) ); // Bebe es hijo de Paco
        assertTrue( Lola.left() .same( Bebe ) ); // Bebe es hijo de Lola

        assertTrue(   Bebe.father().same( Paco ) ); // El papá de Bebe es Paco
        assertTrue( ! Bebe.father().same( Lola ) ); // Lola no es ancestro de Bebe
        // corrección: "Lola" no aparece registrada como padre para "Bebe"

        Bebe.erase();
        assertTrue( Bebe.isEmpty() ); // La referencia Bebe está vacía

        Bebe = Lola.left();           // Se llega al hijo compartido desde Lola
        assertTrue( ! Bebe.isEmpty() );
        assertTrue(   Bebe.father().same( Paco ) ); // Repito: el papá de Bebe es Paco
        assertTrue( ! Bebe.father().same( Lola ) ); // Repito: Lola no es ancestro de Bebe

        if ( false ) { // Tortón !!!
            Bebe.left().makeRightChild( Paco );  // ciclo infinito en el árbol
            Bebe.right().makeLeftChild( Lola );
        }
    }}
}

/// Verifica que \c move() y \c swap() funcionan correctamente.
template <class E>
void test_Bin_Tree<E>::test_move_swap() {
    {{  // test::move_swap()
        Bin_Tree<E> Paco = E(), Lola = E();  //     E()     //
        Paco.makeLeftChild(  E() );          //    /  \     //
        Paco.makeRightChild( E() );          //  E()   E()  //

        assertTrue( Paco.size() == 3 );
        assertTrue( Lola.size() == 1 );
        Paco.swap( Lola );
        assertTrue( Paco.size() == 1 );
        assertTrue( Lola.size() == 3 );

        Lola.move( Paco );
        assertTrue( Paco.size() == 0 );
        assertTrue( Lola.size() == 1 );
    }}
}

/// Verifica que \c isLeftChild() y \c isRightChild() funcionan correctamente.
template <class E>
void test_Bin_Tree<E>::test_isLeft_isRight() {
    {{  // test::isLeft_isRight()
        Bin_Tree<E> T = E();      //     E()     //
        T.makeLeftChild( E() );   //    /  \     //
        T.makeRightChild( E() );  //  E()   E()  //

        assertTrue( ! T.isLeftChild()  );
        assertTrue( T.left().isLeftChild() );
        assertTrue( T.right().isRightChild() );
        assertTrue( !T.left().left().isLeftChild() );    // árbol vacío
        assertTrue( !T.right().right().isRightChild() ); // árbol vacío
    }}
}

/// Verifica que \c isRoot() y \c isLeaf() funcionan correctamente.
template <class E>
void test_Bin_Tree<E>::test_isRoot_isLeaf() {
    {{  // test::isRoot_isLeaf()
        Bin_Tree<E> T = E();      //     E()     //
        T.makeLeftChild( E() );   //    /  \     //
        T.makeRightChild( E() );  //  E()   E()  //

        assertTrue( T.isRoot() && ! T.isLeaf()  );
        assertTrue( T.left().isLeaf() );
        assertTrue( T.right().isLeaf() );
        assertTrue( !T.left().left().isLeaf() );   // árbol vacío
        assertTrue( !T.right().right().isRoot() ); // árbol vacío
    }}
}

/// Verifica que \c sizeStrong() funciona correctamente.
template <class E>
void test_Bin_Tree<E>::test_sizeStrong() {
    using namespace std;
    {{  // test::sizeStrong()
        Bin_Tree<E> Paco = E();      // Paco    Lola //
        Bin_Tree<E> Lola = E();      //              //
        Bin_Tree<E> Bebe;            //   E()   E()  //
        Lola.makeLeftChild( E() );   //     \\ /     //
        Bebe = Lola.left();          //     Bebe     //
        Bebe.makeLeftChild(  E() );  //     // \\    //
        Bebe.makeRightChild( E() );  //   E()   E()  //
        Paco.makeRightChild( Bebe );

        assertTrue( 4 == Paco.size() );             // Paco    Lola //
        assertTrue( 4 == Lola.size() );             //              //
        assertTrue( 3 == Bebe.size() );             //   E()   E()  //
        Paco.right().left().makeLeftChild(  Paco ); //  /  \\ /  \  //
        Lola.left().right().makeRightChild( Lola ); //  |  Bebe  |  //
        assertTrue( Paco == Bebe.left().left()  );  //  \  // \\ /  //
        assertTrue( Lola == Bebe.right().right() ); //   E()   E()  //

        std::set< E* > S; // hay que vaciarlo antes de incocar "sizeStrong()"
        S.clear(); assertTrue( 5 == sizeStrong( Paco, S ) );
        S.clear(); assertTrue( 5 == sizeStrong( Lola, S ) );

        // Como "S" no está vacío, "sizeStrong()" usa el valor actual
        const int ZERO = 0;
        assertTrue( ZERO == sizeStrong( Bebe, S ) );
    }}
}

/// Verifica que la inserción y/o borrado AVL funciona correctamente.
template <class E>
void test_Bin_Tree<E>::test_AVL_tree() {
    if (true) { // A52512
        Bin_Tree<int> T; std::string watch;
        insertAVL( T, 16 ); assertTrue( isAVL(T) ); assertTrue( 1 == T.size() );
        insertAVL( T,  8 ); assertTrue( isAVL(T) ); assertTrue( 2 == T.size() );
        insertAVL( T,  4 ); assertTrue( isAVL(T) ); assertTrue( 3 == T.size() );
        insertAVL( T,  2 ); assertTrue( isAVL(T) ); assertTrue( 4 == T.size() );
        insertAVL( T,  1 ); assertTrue( isAVL(T) ); assertTrue( 5 == T.size() );
        insertAVL( T,  3 ); assertTrue( isAVL(T) ); assertTrue( 6 == T.size() );
        watch = TestCase::toString( T );

        // se prueba que no existe inserción de un elemento ya repetido
        insertAVL( T,  1 ); assertTrue(  6 == T.size() );
        insertAVL( T,  2 ); assertTrue(  6 == T.size() );
        insertAVL( T,  5 ); assertTrue(  7 == T.size() );
        insertAVL( T, 16 ); assertTrue(  7 == T.size() );
        insertAVL( T, 50 ); assertTrue(  8 == T.size() );
        insertAVL( T,  6 ); assertTrue(  9 == T.size() );
        insertAVL( T, 13 ); assertTrue( 10 == T.size() );
        insertAVL( T, 16 ); assertTrue( 10 == T.size() );

        watch = TestCase::toString( T ); assertFalse_Msg( "deleteBalanceAVL() ==> BEGIN" , "" );
        deleteBalanceAVL( T, 16 ); assertTrue( isAVL(T) ); assertTrue( 9 == T.size() ); watch = TestCase::toString( T );
        deleteBalanceAVL( T, 16 ); assertTrue( isAVL(T) ); assertTrue( 9 == T.size() ); watch = TestCase::toString( T );
        deleteBalanceAVL( T,  8 ); assertTrue( isAVL(T) ); assertTrue( 8 == T.size() ); watch = TestCase::toString( T );
        deleteBalanceAVL( T,  4 ); assertTrue( isAVL(T) ); assertTrue( 7 == T.size() ); watch = TestCase::toString( T );
        deleteBalanceAVL( T,  4 ); assertTrue( isAVL(T) ); assertTrue( 7 == T.size() ); watch = TestCase::toString( T );
        deleteBalanceAVL( T,  2 ); assertTrue( isAVL(T) ); assertTrue( 6 == T.size() ); watch = TestCase::toString( T );
        deleteBalanceAVL( T,  1 ); assertTrue( isAVL(T) ); assertTrue( 5 == T.size() ); watch = TestCase::toString( T );
        deleteBalanceAVL( T,  3 ); assertTrue( isAVL(T) ); assertTrue( 5 == T.size() ); watch = TestCase::toString( T );
        deleteBalanceAVL( T,  3 ); assertTrue( isAVL(T) ); assertTrue( 5 == T.size() ); watch = TestCase::toString( T );
        watch = TestCase::toString( T ); assertFalse_Msg( "deleteBalanceAVL() ==> END" , "" );
    }
    {   // A52512
        Bin_Tree<int> T; std::string watch;
        insertAVL( T,  4 ); assertTrue( isAVL(T) ); assertTrue( 1 == T.size() );
        insertAVL( T,  3 ); assertTrue( isAVL(T) ); assertTrue( 2 == T.size() );
        insertAVL( T,  2 ); assertTrue( isAVL(T) ); assertTrue( 3 == T.size() );
        insertAVL( T,  1 ); assertTrue( isAVL(T) ); assertTrue( 4 == T.size() );
        assertTrue( isAVL(T) );
        watch = TestCase::toString( T );
        assertTrue_Msg("T == (3 (2 (1)) (4))" , "(3 (2 (1)) (4))" == TestCase::toString(T) );

        T.clear();
        insertAVL( T, 16 ); assertTrue( isAVL(T) ); assertTrue( 1 == T.size() );
        insertAVL( T,  8 ); assertTrue( isAVL(T) ); assertTrue( 2 == T.size() );
        insertAVL( T,  4 ); assertTrue( isAVL(T) ); assertTrue( 3 == T.size() );
        insertAVL( T,  2 ); assertTrue( isAVL(T) ); assertTrue( 4 == T.size() );
        insertAVL( T,  1 ); assertTrue( isAVL(T) ); assertTrue( 5 == T.size() );
        insertAVL( T,  3 ); assertTrue( isAVL(T) ); assertTrue( 6 == T.size() );
        assertTrue_Msg(
            "6 == " + TestCase::toString(T.size()) + " [T.size()]",
             6 == T.size()
        );
        watch = TestCase::toString( T );

        // se prueba que no existe inserción de un elemento ya repetido
        insertAVL( T,  1 ); assertTrue(  6 == T.size() );
        insertAVL( T,  2 ); assertTrue(  6 == T.size() );
        insertAVL( T,  5 ); assertTrue(  7 == T.size() );
        insertAVL( T, 16 ); assertTrue(  7 == T.size() );
        insertAVL( T, 50 ); assertTrue(  8 == T.size() );
        insertAVL( T,  6 ); assertTrue(  9 == T.size() );
        insertAVL( T, 13 ); assertTrue( 10 == T.size() );
        insertAVL( T, 16 ); assertTrue( 10 == T.size() );

        int izq = altura ( T.left() ) ;
        int der = altura ( T.right() ) ;
        assertTrue( T.data() == 4 ); // si esta balanceado 4 es la raiz
        // asi se prueba que la funcion balancear funciona.
        if (izq > der) {
            assertTrue( (izq - der) < 2 ); // la diferencia puede ser de 1 o 0.
            assertTrue( (izq - der) > 0 ); // pues es la condicion de un AVL
        }
        if (izq < der) {
            assertTrue( (der - izq) < 2 ); // la diferencia puede ser de 1 o 0.
            assertTrue( (der - izq) > 0 ); // pues es la condicion de un AVL
        }
    }
    {   // A52512
        Bin_Tree<int> T;
        orderedInsert( T, 7 ); assertTrue( isAscending(T) );
        orderedInsert( T, 5 ); assertTrue( isAscending(T) );
        orderedInsert( T, 4 ); assertTrue( isAscending(T) );
        orderedInsert( T, 8 ); assertTrue( isAscending(T) );
        orderedInsert( T, 6 ); assertTrue( isAscending(T) );
        orderedInsert( T, 3 ); assertTrue( isAscending(T) );
        assertTrue( ! isAVL(T) ); assertTrue( 6 == T.size() );
        std::string watch1 = TestCase::toString( T );
            balanceAVL(T); // se prueba la funcion para balancear
        std::string watch2 = TestCase::toString( T );
        assertTrue( isAVL(T) ); assertTrue( 6 == T.size() );
        assertTrue_Msg( watch1 + " != " + watch2 , watch1 != watch2 );
        assertTrue( isAscending(T) );
    }
    if (false) { // es feo usar "cout" porque se mancha la pantalla
        using std::cout; using std::endl;
        Bin_Tree<int> T;
        cout <<"Insercion Ordenada de elementos :"<< endl;

        orderedInsert( T, 7 );
        orderedInsert( T, 5 );
        orderedInsert( T, 4 );
        orderedInsert( T, 8 );
        orderedInsert( T, 6 );
        orderedInsert( T, 3 );

        cout << "La raiz y los dos hijos del arbol antes de ser balanceado:";
        cout << "valor de la raiz :" << T.data()<<"\n";
        cout << "valor del hijo izquierdo :" << T.left().data()<<"\n";
        cout << "valor del hijo derecho :" <<  T.right().data()<<"\n";

        balanceAVL(T); // se prueba la funcion para balancear
        cout << "\nArbol despues de ser enviado a la funcion balancear()\n";

        IPD( cout, T );

        cout << "\nraiz despues del balanceo: " << T.data();
        cout << "\nhijo izquierdo despues del balanceo: " << T.left().data();
        cout << "\nhijo derecho despues del balanceo :" <<  T.right().data();
        cout << "\nEl arbol original cambia debido a que primero se usa una\n";
        cout << "insercion normal de arboles binarios y luego queda como si\n";
        cout << "se hubieran insertado los elementos con un metodo AVL de insercion.\n";
        IPD( cout, T );
    }

    {   // Permutaciones
        Bin_Tree<int> T; // Arbol en el que se insertarán varios valores
        const unsigned MAX_VALUES = 7; // cantidad máxima de nodos insertados en "T"
        std::vector< int > vec, ORIGINAL;
        for ( unsigned i=0; i<MAX_VALUES; ++i ) {
            ORIGINAL.push_back(i);
        }

        std::string T_str;
        for ( unsigned N=0; N<MAX_VALUES; ++N ) {
            // prueba con todos los tamaños de árbol
            unsigned i, N_Fact = 1; // El factorial de N
            for (i = 1; i < N; ++i) {
                N_Fact *= i;
            }
            vec = ORIGINAL;
            for (unsigned i=0; i<N_Fact; ++i ) {
                // Siguiente secuencia desordenada de números
                next_permutation( vec.begin(), vec.end() );
                T_str = "[";
                for ( std::vector<int>::size_type k=0; k<vec.size(); ++k ) {
                    T_str += ' ' + TestCase::toString(vec[k]);
                }
                T_str += " ] ==> ";
                T.clear();
                typename std::vector< int >::const_iterator it = vec.begin();
                for ( unsigned j=0; j<N; ++j,++it ) {
                    insertAVL( T , *it );
                }
                /// Verifica que el árbol está balanceado
                assertTrue_Msg( T_str + "isAVL( "+TestCase::toString( T )+" )" , isAVL(T) );
                if ( false && (failureCount() > 50) ) {
                    return; // se sale para no generar demasidos errores
                }
                assertTrue_Msg( T_str + " T.size() == " + TestCase::toString( T.size() ), T.size() == N );
            }
        }
    }
}

/** Verifica que las funciones \c height() y \c depth() funcionan correctamente.
\code
       a
      / \
     /   \
    b     e
   / \   / \
  f   h i   k
           / \
          l   m
             / \
            n   o
\endcode
*/
template <class E>
void test_Bin_Tree<E>::test_heightdepth() {
     Bin_Tree<E> T = make_ab_no();
     assertTrue( 4 == height( T.root() ) );
     assertTrue( 0 == depth(  T.root() ) );

     Bin_Tree<E> e = T.right();
     assertTrue( 3 == height( e ) );
     assertTrue( 1 == depth(  e ) );

     Bin_Tree<E> b = T.left();
     assertTrue( 1 == height( b ) );
     assertTrue( 1 == depth(  b ) );

     assertTrue( -1 == depth(  Bin_Tree<E>() ) );
     assertTrue( -1 == height( Bin_Tree<E>() ) );
}

using std::cout;
using std::endl;

/// Verifica que \c make_FBHCID() construyó el árbol correctamente.
template <class E>
void test_Bin_Tree<E>::do_cout() {
    Bin_Tree<char> T1,T2 = make_FBHCID();
    copyDeep( T1, T2 );
    mirror( T2.left() );  // Tmp = T2.left();  mirror( Tmp );
    mirror( T2.right() ); // Tmp = T1.right(); mirror( Tmp );
    cout << endl << "homomorfo()" << endl;
    IPD( cout , T1 ); cout << endl;
    IPD( cout , T2 ); cout << endl;
}

/// Programa principal desde donse se invocan todas las pruebas
int main() {
    if (1) {
        cout << "test_Bin_Tree<char>\n";
        test_Bin_Tree<char> tester;
        tester.run();
        cout << tester.report();
    }
}

// EOF: test_Bin_Tree.cpp