lkptr<X> - simple reference LinKed PoinTeR:: test_Bin

00001 // test_Bin_Tree.cpp (c) 2007 adolfo@di-mare.com
00002 
00003 /** \file  test_Bin_Tree.cpp
00004     \brief Prueba de caja negra de la clase \c Bin_Tree<E>.
00005 
00006     \author Adolfo Di Mare <adolfo@di-mare.com>
00007     \date   2007
00008 
00009     - Why English names??? ==> http://www.di-mare.com/adolfo/binder/c01.htm#sc04
00010 */
00011 
00012 #define lkptr_NULL_POINTERS_ARE_ALONE
00013 #undef  lkptr_NULL_POINTERS_ARE_ALONE
00014 #include "Bin_Tree.h"
00015 #include "Bin_Tree_Lib.h"
00016 #include "BUnit.h"
00017 
00018 #include <iostream>
00019 #include <vector>
00020 #include <algorithm> // sort() && next_permutation()
00021 #include <cassert>   // assert()
00022 #include <iostream>  // cout
00023 
00024 /// Prueba la clase \c Bin_Tree<E>.
00025 template <class E>
00026 class test_Bin_Tree : public TestCase {
00027 public:
00028     bool run();
00029     void do_cout();
00030     void test_copyDeep();
00031     void test_homomorfo();
00032     void test_make_FBHCID();
00033     void test_make_ab_no();
00034     void test_swap();
00035     void test_mirror();
00036     void test_changeChild();
00037     void test_heightdepth();
00038     void test_releaseChild();
00039     void test_makeOrphan();
00040     void test_left_right();
00041     void test_no_swap();
00042     void test_move_swap();
00043     void test_multi_child();
00044     void test_isLeft_isRight();
00045     void test_isRoot_isLeaf();
00046     void test_sizeStrong();
00047     void test_AVL_tree();
00048 }; // test_Bin_Tree
00049 
00050 /// Método principal de la prueba.
00051 /// - Requiere que recién haya sido ejecutado \c setUp()
00052 template <class E>
00053 bool test_Bin_Tree<E>::run() {
00054     test_make_FBHCID();
00055     test_make_ab_no();
00056     test_copyDeep();
00057     test_homomorfo();
00058     test_swap();
00059     test_mirror();
00060     test_changeChild();
00061     test_heightdepth();
00062     test_releaseChild();
00063     test_makeOrphan();
00064     test_left_right();
00065     test_no_swap();
00066     test_move_swap();
00067     test_multi_child();
00068     test_isLeft_isRight();
00069     test_isRoot_isLeaf();
00070     test_sizeStrong();
00071     test_AVL_tree();
00072     return wasSuccessful();
00073 }
00074 
00075 /** Construye el árbol de letras \c (F (B (C (D))) (H (I))).
00076     - Graba en \c COUT los resultados intermedios.
00077     \code
00078        F
00079       / \       F
00080      B   H      B F
00081       \   \     B F H
00082        C   I    B C F H
00083         \       B C D F H I
00084          D
00085     \endcode
00086 */
00087 Bin_Tree<char> make_FBHCID( std::ostream& COUT ) {
00088     Bin_Tree<char> T;
00089     orderedInsert( T, 'F' );  IPD ( COUT, T ); COUT << std::endl;
00090     orderedInsert( T, 'B' );  IPD ( COUT, T ); COUT << std::endl;
00091     orderedInsert( T, 'H' );  IPD ( COUT, T ); COUT << std::endl;
00092     orderedInsert( T, 'C' );  IPD ( COUT, T ); COUT << std::endl;
00093     orderedInsert( T, 'I' );  IPD ( COUT, T ); COUT << std::endl;
00094     orderedInsert( T, 'D' );  IPD ( COUT, T ); COUT << std::endl;
00095     return T;
00096 }
00097 
00098 /** Construye el árbol de letras \c (F (B (C (D))) (H (I))).
00099     \code
00100        F
00101       / \
00102      B   H
00103       \   \
00104        C   I
00105         \
00106          D
00107     \endcode
00108 */
00109 Bin_Tree<char> make_FBHCID() {
00110     Bin_Tree<char> T;
00111     orderedInsert( T, 'F' );
00112     orderedInsert( T, 'B' );
00113     orderedInsert( T, 'H' );
00114     orderedInsert( T, 'C' );
00115     orderedInsert( T, 'I' );
00116     orderedInsert( T, 'D' );
00117     return T;
00118 }
00119 
00120 /// Verifica que \c make_FBHCID() construyó el árbol correctamente.
00121 template <class E>
00122 void test_Bin_Tree<E>::test_make_FBHCID() {
00123     Bin_Tree<char> T = make_FBHCID();
00124     assertTrue( T.size() == strlen( "FBHCID" ) );
00125 
00126     assertTrue( T.root().data() == 'F' );
00127     assertTrue( T.root().left().data() == 'B' );
00128     assertTrue( T.root().left().right().data() == 'C' );
00129     assertTrue( T.root().left().right().right().data() == 'D' );
00130     assertTrue( T.root().right().data() == 'H' );
00131     assertTrue( T.root().right().right().data() == 'I' );
00132 
00133     std::basic_ostringstream<char> ost; // receptor de salida
00134     ost << T;
00135     assertTrue( ost.str() == "(F (B (C (D))) (H (I)))" );
00136     assertTrue( T.ok() );
00137 }
00138 
00139 /** Construye el árbol de letras \c (a (b (f) (h)) (e (i) (k (l) (m (n) (o))))).
00140 \code
00141        a
00142       / \
00143      /   \
00144     b     e
00145    / \   / \
00146   f   h i   k
00147            / \
00148           l   m
00149              / \
00150             n   o
00151 \endcode
00152 */
00153 Bin_Tree<char> make_ab_no() {
00154     Bin_Tree<char> T, T1, T2;
00155 
00156     T1 = Bin_Tree<char>('b'); {
00157         T1.makeLeftChild(  Bin_Tree<char>('f') );
00158         T1.makeRightChild( Bin_Tree<char>('h') );
00159     }
00160 
00161     T2.changeRoot('k'); {
00162         T2.makeLeftChild(  Bin_Tree<char>('l') );
00163         T.changeRoot('m'); {
00164             T.makeLeftChild(  Bin_Tree<char>('n') );
00165             T.makeRightChild( Bin_Tree<char>('o') );
00166         }
00167         T2.makeRightChild( T );
00168     }
00169     T.erase();
00170     T.changeRoot('a'); {
00171         T.makeLeftChild( T1 );
00172         T.makeRightChild(  Bin_Tree<char>('e') ); {
00173             T.right().makeLeftChild(  Bin_Tree<char>('i') );
00174             T.right().makeRightChild( T2 );
00175         }
00176     }
00177     return T;
00178 }
00179 
00180 /// Verifica que \c make_ab_no() construyó el árbol correctamente.
00181 /// - \c (a (b (f) (h)) (e (i) (k (l) (m (n) (o)))))
00182 template <class E>
00183 void test_Bin_Tree<E>::test_make_ab_no() {
00184     std::basic_ostringstream<char> ost; // receptor de salida
00185     ost << make_ab_no();
00186     assertTrue( ost.str() == "(a (b (f) (h)) (e (i) (k (l) (m (n) (o)))))" );
00187     assertTrue( make_ab_no().ok() );
00188 }
00189 
00190 /// Pasa a minúscula todas las letras de \c "T".
00191 void toLower( Bin_Tree<char> T ) {
00192     if ( T.isEmpty() ) {
00193         return;
00194     }
00195     T.changeRoot( tolower( *T ) );
00196     toLower( T.left() );
00197     toLower( T.right() );
00198 }
00199 
00200 /// Verifica que \c Bin_Tree<E>::copyDeep() funciona correctamente.
00201 template <class E>
00202 void test_Bin_Tree<E>::test_copyDeep() {
00203     Bin_Tree<char> T, T1, T2;
00204     T.changeRoot( 'A' );
00205     T.makeLeftChild(  Bin_Tree<char>( 'B' ) );
00206     T.makeRightChild( Bin_Tree<char>( 'C' ) );
00207     copyDeep( T1, T );
00208 
00209     copyDeep( T2, T1 ); {
00210         assertTrue( ! T1.same( T2 ) );
00211         assertTrue( T1 == T2 );
00212     }
00213     T1 = T2; {
00214         assertTrue( T1.same( T2 ) );
00215         toLower( T2 );
00216         assertTrue( T1 == T2 );
00217     }
00218 
00219     T1 = make_FBHCID(); {
00220         assertTrue( T1 != T2 );
00221     }
00222 
00223     copyDeep( T1, T ); {
00224         assertTrue( ! T1.same( T2 ) );
00225         assertTrue( T1 != T2 );
00226         toLower( T1 );
00227         assertTrue( T1 == T2 );
00228     }
00229 }
00230 
00231 /// Verifica que \c make_FBHCID() construyó el árbol correctamente.
00232 template <class E>
00233 void test_Bin_Tree<E>::test_homomorfo() {
00234     Bin_Tree<char> T1 = make_FBHCID();
00235     Bin_Tree<char> T2 = T1, Tmp;
00236     assertTrue( homomorfo( T1 , T2 ) );
00237     copyDeep( T2, T1 );
00238     toLower( T1 );
00239     assertTrue( TestCase::toString( T1 ) == "(f (b (c (d))) (h (i)))" );
00240     assertTrue( TestCase::toString( T2 ) == "(F (B (C (D))) (H (I)))" );
00241     T2.makeRightChild(T1);
00242     assertTrue( toString( T1 ) == "(f (b (c (d))) (h (i)))" );
00243     assertTrue( toString( T2 ) == "(F (B (C (D))) (f (b (c (d))) (h (i))))" );
00244     copyDeep( T1, T2 );
00245     assertTrue( toString( T1 ) == "(F (B (C (D))) (f (b (c (d))) (h (i))))" );
00246     assertTrue( toString( T2 ) == "(F (B (C (D))) (f (b (c (d))) (h (i))))" );
00247     assertTrue( homomorfo( T1 , T2 ) );
00248     assertTrue( homomorfo( T2 , T1 ) );
00249     mirror( T2.left() );  // Tmp = T2.left();  mirror( Tmp );
00250     mirror( T2.right() ); // Tmp = T1.right(); mirror( Tmp );
00251     assertTrue( homomorfo( T1 , T2 ) );
00252     assertTrue( homomorfo( T2 , T1 ) );
00253 }
00254 
00255 /// Verifica que \c Bin_Tree<E>::swap() funciona correctamente.
00256 template <class E>
00257 void test_Bin_Tree<E>::test_swap() {
00258     Bin_Tree<char> T1 = make_FBHCID();
00259     Bin_Tree<char> T2 = 'A';
00260     assertTrue( T1.father().isEmpty() );
00261 
00262     T2.swap(T1);
00263 
00264     assertTrue( T1.size() == 1 ); {
00265         std::basic_ostringstream<char> ost; // receptor de salida
00266         IPD(ost , T2);
00267         assertTrue( ost.str() == " B C D F H I" );
00268     }
00269     assertTrue( comp( T2.left().father(),  T2 ) );
00270     assertTrue( comp( T2.right().father(), T2 ) );
00271     assertTrue( comp( T1.left(), Bin_Tree<char>() ) ) ;
00272     assertTrue( comp( T2.left().left(), Bin_Tree<char>() ) ) ;
00273     assertTrue( comp( T2.left().right().right(), Bin_Tree<char>('D') ) ) ;
00274     assertTrue( comp( T2.right().right(), Bin_Tree<char>('I') ) ) ;
00275     T1.changeRoot( 'H' );
00276     T1.makeRightChild( Bin_Tree<char>('I') );
00277     assertTrue( comp( T2.right(), T1) ) ;
00278 }
00279 
00280 /// Verifica que \c Bin_Tree<E>::mirror() funciona correctamente.
00281 template <class E>
00282 void test_Bin_Tree<E>::test_mirror() {
00283     Bin_Tree<char> T1 = make_FBHCID();
00284     assertTrue( T1.count() == 6 && height(T1) == 3 ); {
00285         std::basic_ostringstream<char> ost; // receptor de salida
00286         IPD(ost , T1);
00287         assertTrue( ost.str() == " B C D F H I" );
00288     }
00289 
00290     mirror( T1 );
00291 
00292     assertTrue( T1.count() == 6 && height(T1) == 3 ); {
00293         std::basic_ostringstream<char> ost; // receptor de salida
00294         IPD(ost , T1);
00295         assertTrue( ost.str() == " I H F D C B" );
00296     }
00297 
00298     Bin_Tree<char> T2 = T1;
00299     assertTrue( comp(T1,T2) ); assertTrue( comp(T2,T1) );
00300 
00301     copyDeep(T2,T1);
00302     char ch = T1.data();
00303     T1 = ch+1;  assertTrue( ! comp(T1, T2) );
00304     T1 = ch;    assertTrue(   comp(T1, T2) );
00305 
00306     copyDeep(T2,T1);
00307     ch = T1.data();
00308     T1 = ch+1;  assertTrue( ! comp(T1, T2) );
00309     T1 = ch;    assertTrue(   comp(T1, T2) );
00310 
00311     mirror( T1 );
00312     mirror( T2 );
00313 
00314     assertTrue( comp(T1, T2) );
00315     copyDeep( T2, T1 );
00316     assertTrue( comp(T1, T2) );
00317 
00318     assertTrue( T1.count() == 6 && height(T1) == 3 ); {
00319         std::basic_ostringstream<char> ost; // receptor de salida
00320         IPD(ost , T1);
00321         assertTrue( ost.str() == " B C D F H I" );
00322     }
00323 
00324     T2.left().changeRoot( 'X' );
00325     assertTrue( T2.count() == 6 && height(T2) == 3 ); {
00326         std::basic_ostringstream<char> ost; // receptor de salida
00327         IPD(ost , T2);
00328         assertTrue( ost.str() == " X C D F H I" );
00329     }
00330 
00331     T2.erase();
00332     assertTrue( !comp(T1, T2) );
00333 }
00334 
00335 /// Verifica que \c changeLeftChild() y \c changeRightChild() funcionan correctamente.
00336 template <class E>
00337 void test_Bin_Tree<E>::test_changeChild() {
00338     {{  // test::changeChild()
00339         Bin_Tree<char> T, Tcopy;
00340         T = 'A'; // agrega la raiz 'A'    A
00341         T.changeLeftChild(  '0' );  //  ./ \.
00342         T.changeRightChild( '1' );  //  0   1
00343         copyDeep( Tcopy , T );
00344         assertTrue( TestCase::toString(T) == "(A (0) (1))" );
00345         mirror( T );
00346         assertTrue( TestCase::toString(T) == "(A (1) (0))" );
00347         mirror( T ); {
00348             std::basic_ostringstream<char> ost;
00349             ost << T;
00350             assertTrue( ost.str() == "(A (0) (1))" );
00351         }
00352 
00353         assertTrue( comp(T, Tcopy) );
00354     }}
00355     {   // Resto de las pruebas
00356         Bin_Tree<char> T2;
00357         T2 = 'A';    // inserta la raiz           //    'A'
00358         T2.changeLeftChild('0'); {                //    /
00359             std::basic_ostringstream<char> ost;   //   0
00360             IPD (ost , T2);
00361             assertTrue( ost.str() == " 0 A" );
00362         }
00363 
00364         mirror( T2 ); {
00365             std::basic_ostringstream<char> ost;
00366             IPD (ost , T2);
00367             assertTrue( ost.str() == " A 0" );
00368         }
00369         assertTrue( T2.count() == 2 );
00370     }
00371 }
00372 
00373 /// Verifica que \c releaseLeftChild() y \c releaseRightChild() funcionan correctamente.
00374 template <class E>
00375 void test_Bin_Tree<E>::test_releaseChild() {
00376     {{  // test::releaseChild()
00377         Bin_Tree<E> Paco = E();     // Paco    Lola //
00378         Bin_Tree<E> Lola = E();     //              //
00379         Bin_Tree<E> Bebe;           //   E()   E()  //
00380         Lola.makeLeftChild( E() );  //     \\ /     //
00381         Bebe = Lola.left();         //     Bebe     //
00382         Bebe.makeLeftChild(  E() ); //     // \\    //
00383         Bebe.makeRightChild( E() ); //   E()   E()  //
00384         Paco.makeRightChild( Bebe );
00385 
00386         Paco.releaseLeftChild();
00387         assertTrue( 4 == Paco.size() ); // Paco no tiene hijo izquierdo
00388         Paco.releaseRightChild();
00389         assertTrue( 1 == Paco.size() ); // Ya Paco no tiene hijo derecho
00390         assertTrue( Paco.right() == Bin_Tree<E>() ); // El hijo derecho es un árbol vacío
00391         assertTrue( Bebe != Bin_Tree<E>() );         // Bebe todavía existe
00392         assertTrue( Bebe.father() == Paco );  // Paco sigue registrado como padre de Bebe
00393 
00394         assertTrue( 4 == Lola.size() ); // Lola todavía tiene a su hijo izquierdo
00395         assertTrue( Bebe.same( Lola.left() ) ); // Bebe si es hijo izquierdo de Lola
00396         assertTrue( Lola.left().same( Bebe ) ); // Lola si tiene hijo izquierdo
00397         assertTrue( Bebe.father() != Bin_Tree<E>() ); // Bebe no está registrado como hijo de Lola
00398 
00399         Lola.releaseLeftChild(); // Ahora ya Bebe no es hijo de Lola
00400         assertTrue( ! Bebe.same( Lola.left() ) );
00401         assertTrue( 1 == Lola.size() ); // Ya Lola no tiene hijos
00402     }}
00403 }
00404 
00405 /// Verifica que \c makeOrphan() funciona correctamente.
00406 template <class E>
00407 void test_Bin_Tree<E>::test_makeOrphan() {
00408     using namespace std;
00409     {{  // test::makeOrphan()
00410         Bin_Tree<E> Paco = E();     // Paco    Lola //
00411         Bin_Tree<E> Lola = E();     //              //
00412         Bin_Tree<E> Bebe;           //   E()   E()  //
00413         Lola.makeLeftChild( E() );  //     \\ /     //
00414         Bebe = Lola.left();         //     Bebe     //
00415         Bebe.makeLeftChild(  E() ); //     // \\    //
00416         Bebe.makeRightChild( E() ); //   E()   E()  //
00417         Paco.makeRightChild( Bebe );
00418 
00419         assertTrue( Bebe.same( Lola.left()  ) ); // Bebe si es hijo izquierdo de Lola
00420         assertTrue( Bebe.same( Paco.right() ) ); // Bebe si es hijo derecho de Paco
00421         assertTrue( Bebe.father() == Paco );     // Bebe está registrado como hijo de Paco
00422         assertTrue( Bebe.father() != Lola );     // Bebe no está registrado como hijo de Lola
00423 
00424         Bebe.makeOrphan();
00425         assertTrue( Bebe.father() != Paco );          // Ya Paco no está registrado como el padre de Bebe
00426         assertTrue( Bebe.father() == Bin_Tree<E>() ); // Bebe no tiene registrado a nadie como su padre
00427 
00428         assertTrue( Bebe.same( Lola.left() ) );  // Bebe sigue registrado como hijo izquierdo de Lola
00429         assertTrue( Bebe.same( Paco.right() ) ); // Bebe sigue registrado como hijo derecho de Paco
00430         assertTrue( Bebe.father() != Paco );     // Bebe ya no está registrado como hijo de Paco
00431         assertTrue( Bebe.father() != Lola );     // Bebe ya no está registrado como hijo de Lola
00432     }}
00433 }
00434 
00435 /// Verifica que \c left() y \c right() funcionan correctamente.
00436 template <class E>
00437 void test_Bin_Tree<E>::test_left_right() {
00438     using namespace std;
00439     {{  // test::left_right()
00440         Bin_Tree<E> T = E(); // no hay hijo izquierdo alguno
00441         {   T.left() = E();    // sí hace el cambio
00442             // pero el destructor elimina la referencia
00443         }   // sin modificar el hijo izquierdo que no existe
00444         assertTrue( T.size() == 1 );
00445         assertTrue( T.left().isEmpty() ); // "T.left()" es una nueva referencia al hijo de "T"
00446 
00447         T.makeRightChild( E() ); // esta es la forma de crear un nuevo sub-árbol derecho
00448         T.right().erase(); // no elimina al hijo derecho: borra la nueva referencia "right()"
00449         assertTrue( T.size() == 2 );
00450         assertTrue( ! T.right().isEmpty() ); // el hijo derecho está ahí todavía
00451 
00452         {   // Para eliminar a un hijo hay que poner el árbol nulo en su lugar
00453             T.right() = Bin_Tree<E>(); // cambia la referencia: el hijo derecho sigue ahí
00454             assertTrue( ! T.right().isEmpty() ); // el hijo derecho está ahí todavía
00455 
00456             assertTrue( Bin_Tree<E>().isEmpty() ); // referencia nula: árbol vacío
00457 
00458             // esta es la forma correcta de eliminar hijos
00459             T.makeRightChild( Bin_Tree<E>() ); // elimina al hijo derecho
00460             assertTrue( T.right().isEmpty() ); // ya no existe el hijo derecho
00461         }
00462 
00463         if ( T.right().isEmpty() ) {
00464             if (false) {
00465                 *T.right() = E(); // ERROR: Trata de cambiar un árbol vacío
00466             }
00467             T.makeRightChild( E() ); // nuevo hijo derecho
00468         }
00469         else {
00470             T.right().changeRoot( E() ); // sí cambia el valor almacenado
00471             *( T.right() ) = E(); // efecto similar al renglón anterior
00472         }
00473         T = T.right(); // caminar hacia las hojas no cambia el valor almacenado
00474         assertTrue ( ! T.father().isEmpty() );
00475         assertTrue( T.size() == 1 );
00476         T = T.father();
00477         assertTrue( T.size() == 2 );
00478         T.right().erase(); // no cambia nada
00479         assertTrue( T.size() == 2 );
00480 
00481         Bin_Tree<E> Child = T.right();     // sostiene al hijo
00482         T.right().makeOrphan();            // elimna la conexión hijo->padre
00483         assertTrue( T.right() == Child );  // no eliminó la conexión hijo->padre
00484         assertTrue( Child.father() != T ); // ni el antiguo hijo encuentra a su padre
00485         assertTrue ( ! T.isEmpty() );
00486         assertTrue ( ! Child.isEmpty() );
00487         assertTrue ( Child.father().isEmpty() ); // ni el antiguo hijo tiene padre
00488     }}
00489 }
00490 
00491 /// Muestra que \c swap() trabaja en una referencia.
00492 template <class E>
00493 void test_Bin_Tree<E>::test_no_swap() {
00494     {{  // test::no_swap()
00495         Bin_Tree<E> T = E();      //  E()     //
00496         Bin_Tree<E> Right;        //    \     //
00497         T.makeRightChild( E() );  //     E()  //
00498 
00499         assertTrue( T.size() == 2 );
00500         assertTrue( T.right().isRightChild() ); // Ahí está el hijo derecho
00501         Right = T.right();  // no compila >==> T.left().swap( T.right() );
00502         T.left().swap( Right );
00503         assertTrue( T.right().isRightChild() ); // El hijo derecho no ha cambiado
00504         assertTrue( T.size() == 2 );
00505 
00506         T.makeLeftChild( T.right() );            //    E()   //
00507         assertTrue( T.size() == 3 );             //   /   \  //
00508         assertTrue( T.left().same( T.right()) ); //   \   /  //
00509         assertTrue( T.right().isRightChild() );  //    E()   //
00510         assertTrue( T.left().isLeftChild() );    // hijo compartido
00511 
00512         T.makeLeftChild( T.right() );            // ahora sí cambió el árbol
00513         T.makeRightChild( Bin_Tree<E>() );       // borra al hijo derecho
00514         assertTrue( T.size() == 2 );
00515         assertTrue( ! T.left().same( T.right()) );
00516         assertTrue( ! T.right().isRightChild() ); // si hay hijo derecho
00517         assertTrue( T.left().isLeftChild() );     // Ahí está el antiguo hijo derecho
00518     }}
00519     {   // Autociclo a la izquierda
00520         Bin_Tree<E> T = E();
00521         T.makeLeftChild( T ); // autociclo
00522         for ( int i=0; i<11; ++i ) {
00523             T = T.left();
00524             assertTrue( ! T.isEmpty() );
00525         }
00526         assertTrue( ! T.isEmpty() );
00527     }
00528     {   // Autociclo a la derecha
00529         Bin_Tree<E> T = E();
00530         T.makeRightChild( T ); // autociclo
00531         for ( int i=0; i<22; ++i ) {
00532             T = T.right();
00533             assertTrue( ! T.isEmpty() );
00534         }
00535         assertTrue( ! T.isEmpty() );
00536     }
00537     {   // Autociclo a la derecha               //  E()       //
00538         Bin_Tree<E> T = E();                    //    \       //
00539         T.makeRightChild( E() );                //    E()     //
00540         T.right().makeRightChild( E() );        //      \     //
00541                                                 //      E()   //
00542         assertTrue( T.size() == 3 );
00543         T.right().right().makeRightChild( T );  //  E() <---+ //
00544         for ( int i=0; i<33; ++i ) {            //    \     | //
00545             T = T.right();                      //    E()   | //
00546             assertTrue( ! T.isEmpty() );        //      \   | //
00547         }                                       //      E() | //
00548         assertTrue( ! T.isEmpty() );            //        \-+
00549     }
00550     if ( false) {
00551         // Muestra cómo funcionaría el árbol un sub-arbol
00552         // pudiera ser hijo sólo de un único árbol
00553         Bin_Tree<E> T = E();      //  E()     //
00554         Bin_Tree<E> Right;        //    \     //
00555         T.makeRightChild( E() );  //     E()  //
00556 
00557         T.makeLeftChild( T.right() );              //   E()   //
00558         assertTrue( T.size() == 2 );               //   /     //
00559         assertTrue( ! T.left().same( T.right()) ); // E()     //
00560         assertTrue(  T.left().isLeftChild() );
00561         assertTrue( ! T.right().isRightChild() );
00562 
00563         T.makeRightChild( T.left() );              //  E()     //
00564         assertTrue( T.size() == 2 );               //    \     //
00565         assertTrue( ! T.right().same( T.left()) ); //     E()  //
00566         assertTrue( T.right().isRightChild() );
00567         assertTrue( ! T.left().isLeftChild() );
00568 
00569         assertTrue( T.size() == 2 );
00570         assertTrue( T.right().isRightChild() ); // Ahí está el hijo derecho
00571         Right = T.right();    // no compila ==> T.left().swap( T.right() );
00572         T.left().swap( Right );
00573         assertTrue( T.right().isRightChild() ); // El hijo derecho no ha cambiado
00574         assertTrue( T.size() == 2 );
00575     }
00576 }
00577 
00578 /// Verifica que \c move() y \c swap() funcionan correctamente.
00579 template <class E>
00580 void test_Bin_Tree<E>::test_multi_child() {
00581     {{  // test::multi_child()
00582         // Muestra que un mismo árbol "Bebe" puede ser sub-árbol
00583         // de varios árboles
00584         Bin_Tree<E> Paco = E();     // Paco    Lola //
00585         Bin_Tree<E> Lola = E();     //              //
00586         Bin_Tree<E> Bebe;           //   E()   E()  //
00587         Lola.makeLeftChild( E() );  //     \\ /     //
00588         Bebe = Lola.left();         //     Bebe     //
00589         Bebe.makeLeftChild(  E() ); //     // \\    //
00590         Bebe.makeRightChild( E() ); //   E()   E()  //
00591         Paco.makeRightChild( Bebe );
00592 
00593         // Como se muestra en el diagrama X, debido a este último cambio
00594         // el padre registrado de Bebe ahora es Paco
00595 
00596         assertTrue( 3 == Bebe.size() );
00597         assertTrue( 4 == Paco.size() ); // 3 de Bebe + Paco
00598         assertTrue( 4 == Lola.size() ); // 3 de Bebe + Lola
00599 
00600         assertTrue( Paco.right().same( Bebe ) ); // Bebe es hijo de Paco
00601         assertTrue( Lola.left() .same( Bebe ) ); // Bebe es hijo de Lola
00602 
00603         assertTrue(   Bebe.father().same( Paco ) ); // El papá de Bebe es Paco
00604         assertTrue( ! Bebe.father().same( Lola ) ); // Lola no es ancestro de Bebe
00605         // corrección: "Lola" no aparece registrada como padre para "Bebe"
00606 
00607         Bebe.erase();
00608         assertTrue( Bebe.isEmpty() ); // La referencia Bebe está vacía
00609 
00610         Bebe = Lola.left();           // Se llega al hijo compartido desde Lola
00611         assertTrue( ! Bebe.isEmpty() );
00612         assertTrue(   Bebe.father().same( Paco ) ); // Repito: el papá de Bebe es Paco
00613         assertTrue( ! Bebe.father().same( Lola ) ); // Repito: Lola no es ancestro de Bebe
00614 
00615         if ( false ) { // Tortón !!!
00616             Bebe.left().makeRightChild( Paco );  // ciclo infinito en el árbol
00617             Bebe.right().makeLeftChild( Lola );
00618         }
00619     }}
00620 }
00621 
00622 /// Verifica que \c move() y \c swap() funcionan correctamente.
00623 template <class E>
00624 void test_Bin_Tree<E>::test_move_swap() {
00625     {{  // test::move_swap()
00626         Bin_Tree<E> Paco = E(), Lola = E();  //     E()     //
00627         Paco.makeLeftChild(  E() );          //    /  \     //
00628         Paco.makeRightChild( E() );          //  E()   E()  //
00629 
00630         assertTrue( Paco.size() == 3 );
00631         assertTrue( Lola.size() == 1 );
00632         Paco.swap( Lola );
00633         assertTrue( Paco.size() == 1 );
00634         assertTrue( Lola.size() == 3 );
00635 
00636         Lola.move( Paco );
00637         assertTrue( Paco.size() == 0 );
00638         assertTrue( Lola.size() == 1 );
00639     }}
00640 }
00641 
00642 /// Verifica que \c isLeftChild() y \c isRightChild() funcionan correctamente.
00643 template <class E>
00644 void test_Bin_Tree<E>::test_isLeft_isRight() {
00645     {{  // test::isLeft_isRight()
00646         Bin_Tree<E> T = E();      //     E()     //
00647         T.makeLeftChild( E() );   //    /  \     //
00648         T.makeRightChild( E() );  //  E()   E()  //
00649 
00650         assertTrue( ! T.isLeftChild()  );
00651         assertTrue( T.left().isLeftChild() );
00652         assertTrue( T.right().isRightChild() );
00653         assertTrue( !T.left().left().isLeftChild() );    // árbol vacío
00654         assertTrue( !T.right().right().isRightChild() ); // árbol vacío
00655     }}
00656 }
00657 
00658 /// Verifica que \c isRoot() y \c isLeaf() funcionan correctamente.
00659 template <class E>
00660 void test_Bin_Tree<E>::test_isRoot_isLeaf() {
00661     {{  // test::isRoot_isLeaf()
00662         Bin_Tree<E> T = E();      //     E()     //
00663         T.makeLeftChild( E() );   //    /  \     //
00664         T.makeRightChild( E() );  //  E()   E()  //
00665 
00666         assertTrue( T.isRoot() && ! T.isLeaf()  );
00667         assertTrue( T.left().isLeaf() );
00668         assertTrue( T.right().isLeaf() );
00669         assertTrue( !T.left().left().isLeaf() );   // árbol vacío
00670         assertTrue( !T.right().right().isRoot() ); // árbol vacío
00671     }}
00672 }
00673 
00674 /// Verifica que \c sizeStrong() funciona correctamente.
00675 template <class E>
00676 void test_Bin_Tree<E>::test_sizeStrong() {
00677     using namespace std;
00678     {{  // test::sizeStrong()
00679         Bin_Tree<E> Paco = E();      // Paco    Lola //
00680         Bin_Tree<E> Lola = E();      //              //
00681         Bin_Tree<E> Bebe;            //   E()   E()  //
00682         Lola.makeLeftChild( E() );   //     \\ /     //
00683         Bebe = Lola.left();          //     Bebe     //
00684         Bebe.makeLeftChild(  E() );  //     // \\    //
00685         Bebe.makeRightChild( E() );  //   E()   E()  //
00686         Paco.makeRightChild( Bebe );
00687 
00688         assertTrue( 4 == Paco.size() );             // Paco    Lola //
00689         assertTrue( 4 == Lola.size() );             //              //
00690         assertTrue( 3 == Bebe.size() );             //   E()   E()  //
00691         Paco.right().left().makeLeftChild(  Paco ); //  /  \\ /  \  //
00692         Lola.left().right().makeRightChild( Lola ); //  |  Bebe  |  //
00693         assertTrue( Paco == Bebe.left().left()  );  //  \  // \\ /  //
00694         assertTrue( Lola == Bebe.right().right() ); //   E()   E()  //
00695 
00696         std::set< E* > S; // hay que vaciarlo antes de incocar "sizeStrong()"
00697         S.clear(); assertTrue( 5 == sizeStrong( Paco, S ) );
00698         S.clear(); assertTrue( 5 == sizeStrong( Lola, S ) );
00699 
00700         // Como "S" no está vacío, "sizeStrong()" usa el valor actual
00701         const int ZERO = 0;
00702         assertTrue( ZERO == sizeStrong( Bebe, S ) );
00703     }}
00704 }
00705 
00706 /// Verifica que la inserción y/o borrado AVL funciona correctamente.
00707 template <class E>
00708 void test_Bin_Tree<E>::test_AVL_tree() {
00709     if (true) { // A52512
00710         Bin_Tree<int> T; std::string watch;
00711         insertAVL( T, 16 ); assertTrue( isAVL(T) ); assertTrue( 1 == T.size() );
00712         insertAVL( T,  8 ); assertTrue( isAVL(T) ); assertTrue( 2 == T.size() );
00713         insertAVL( T,  4 ); assertTrue( isAVL(T) ); assertTrue( 3 == T.size() );
00714         insertAVL( T,  2 ); assertTrue( isAVL(T) ); assertTrue( 4 == T.size() );
00715         insertAVL( T,  1 ); assertTrue( isAVL(T) ); assertTrue( 5 == T.size() );
00716         insertAVL( T,  3 ); assertTrue( isAVL(T) ); assertTrue( 6 == T.size() );
00717         watch = TestCase::toString( T );
00718 
00719         // se prueba que no existe inserción de un elemento ya repetido
00720         insertAVL( T,  1 ); assertTrue(  6 == T.size() );
00721         insertAVL( T,  2 ); assertTrue(  6 == T.size() );
00722         insertAVL( T,  5 ); assertTrue(  7 == T.size() );
00723         insertAVL( T, 16 ); assertTrue(  7 == T.size() );
00724         insertAVL( T, 50 ); assertTrue(  8 == T.size() );
00725         insertAVL( T,  6 ); assertTrue(  9 == T.size() );
00726         insertAVL( T, 13 ); assertTrue( 10 == T.size() );
00727         insertAVL( T, 16 ); assertTrue( 10 == T.size() );
00728 
00729         watch = TestCase::toString( T );
00730         deleteBalanceAVL( T, 16 ); assertTrue( isAVL(T) ); assertTrue( 9 == T.size() ); watch = TestCase::toString( T );
00731         deleteBalanceAVL( T, 16 ); assertTrue( isAVL(T) ); assertTrue( 9 == T.size() ); watch = TestCase::toString( T );
00732         deleteBalanceAVL( T,  8 ); assertTrue( isAVL(T) ); assertTrue( 8 == T.size() ); watch = TestCase::toString( T );
00733         deleteBalanceAVL( T,  4 ); assertTrue( isAVL(T) ); assertTrue( 7 == T.size() ); watch = TestCase::toString( T );
00734         deleteBalanceAVL( T,  4 ); assertTrue( isAVL(T) ); assertTrue( 7 == T.size() ); watch = TestCase::toString( T );
00735         deleteBalanceAVL( T,  2 ); assertTrue( isAVL(T) ); assertTrue( 6 == T.size() ); watch = TestCase::toString( T );
00736         deleteBalanceAVL( T,  1 ); assertTrue( isAVL(T) ); assertTrue( 5 == T.size() ); watch = TestCase::toString( T );
00737         deleteBalanceAVL( T,  3 ); assertTrue( isAVL(T) ); assertTrue( 5 == T.size() ); watch = TestCase::toString( T );
00738         deleteBalanceAVL( T,  3 ); assertTrue( isAVL(T) ); assertTrue( 5 == T.size() ); watch = TestCase::toString( T );
00739         watch = TestCase::toString( T );
00740     }
00741     {   // A52512
00742         Bin_Tree<int> T; std::string watch;
00743         insertAVL( T,  4 ); assertTrue( isAVL(T) ); assertTrue( 1 == T.size() );
00744         insertAVL( T,  3 ); assertTrue( isAVL(T) ); assertTrue( 2 == T.size() );
00745         insertAVL( T,  2 ); assertTrue( isAVL(T) ); assertTrue( 3 == T.size() );
00746         insertAVL( T,  1 ); assertTrue( isAVL(T) ); assertTrue( 4 == T.size() );
00747         assertTrue( isAVL(T) );
00748         watch = TestCase::toString( T );
00749         assertTrue_Msg("T == (3 (2 (1)) (4))" , "(3 (2 (1)) (4))" == TestCase::toString(T) );
00750 
00751         T.clear();
00752         insertAVL( T, 16 ); assertTrue( isAVL(T) ); assertTrue( 1 == T.size() );
00753         insertAVL( T,  8 ); assertTrue( isAVL(T) ); assertTrue( 2 == T.size() );
00754         insertAVL( T,  4 ); assertTrue( isAVL(T) ); assertTrue( 3 == T.size() );
00755         insertAVL( T,  2 ); assertTrue( isAVL(T) ); assertTrue( 4 == T.size() );
00756         insertAVL( T,  1 ); assertTrue( isAVL(T) ); assertTrue( 5 == T.size() );
00757         insertAVL( T,  3 ); assertTrue( isAVL(T) ); assertTrue( 6 == T.size() );
00758         assertTrue_Msg(
00759             "6 == " + TestCase::toString(T.size()) + " [T.size()]",
00760              6 == T.size()
00761         );
00762         watch = TestCase::toString( T );
00763 
00764         // se prueba que no existe inserción de un elemento ya repetido
00765         insertAVL( T,  1 ); assertTrue(  6 == T.size() );
00766         insertAVL( T,  2 ); assertTrue(  6 == T.size() );
00767         insertAVL( T,  5 ); assertTrue(  7 == T.size() );
00768         insertAVL( T, 16 ); assertTrue(  7 == T.size() );
00769         insertAVL( T, 50 ); assertTrue(  8 == T.size() );
00770         insertAVL( T,  6 ); assertTrue(  9 == T.size() );
00771         insertAVL( T, 13 ); assertTrue( 10 == T.size() );
00772         insertAVL( T, 16 ); assertTrue( 10 == T.size() );
00773 
00774         int izq = altura ( T.left() ) ;
00775         int der = altura ( T.right() ) ;
00776         assertTrue( T.data() == 4 ); // si esta balanceado 4 es la raiz
00777         // asi se prueba que la funcion balancear funciona.
00778         if (izq > der) {
00779             assertTrue( (izq - der) < 2 ); // la diferencia puede ser de 1 o 0.
00780             assertTrue( (izq - der) > 0 ); // pues es la condicion de un AVL
00781         }
00782         if (izq < der) {
00783             assertTrue( (der - izq) < 2 ); // la diferencia puede ser de 1 o 0.
00784             assertTrue( (der - izq) > 0 ); // pues es la condicion de un AVL
00785         }
00786     }
00787     {   // A52512
00788         Bin_Tree<int> T;
00789         orderedInsert( T, 7 ); assertTrue( isAscending(T) );
00790         orderedInsert( T, 5 ); assertTrue( isAscending(T) );
00791         orderedInsert( T, 4 ); assertTrue( isAscending(T) );
00792         orderedInsert( T, 8 ); assertTrue( isAscending(T) );
00793         orderedInsert( T, 6 ); assertTrue( isAscending(T) );
00794         orderedInsert( T, 3 ); assertTrue( isAscending(T) );
00795         assertTrue( ! isAVL(T) ); assertTrue( 6 == T.size() );
00796         std::string watch1 = TestCase::toString( T );
00797             balanceAVL(T); // se prueba la funcion para balancear
00798         std::string watch2 = TestCase::toString( T );
00799         assertTrue( isAVL(T) ); assertTrue( 6 == T.size() );
00800         assertTrue_Msg( watch1 + " != " + watch2 , watch1 != watch2 );
00801         assertTrue( isAscending(T) );
00802     }
00803     if (false) { // es feo usar "cout" porque se mancha la pantalla
00804         using std::cout; using std::endl;
00805         Bin_Tree<int> T;
00806         cout <<"Insercion Ordenada de elementos :"<< endl;
00807 
00808         orderedInsert( T, 7 );
00809         orderedInsert( T, 5 );
00810         orderedInsert( T, 4 );
00811         orderedInsert( T, 8 );
00812         orderedInsert( T, 6 );
00813         orderedInsert( T, 3 );
00814 
00815         cout << "La raiz y los dos hijos del arbol antes de ser balanceado:";
00816         cout << "valor de la raiz :" << T.data()<<"\n";
00817         cout << "valor del hijo izquierdo :" << T.left().data()<<"\n";
00818         cout << "valor del hijo derecho :" <<  T.right().data()<<"\n";
00819 
00820         balanceAVL(T); // se prueba la funcion para balancear
00821         cout << "\nArbol despues de ser enviado a la funcion balancear()\n";
00822 
00823         IPD( cout, T );
00824 
00825         cout << "\nraiz despues del balanceo: " << T.data();
00826         cout << "\nhijo izquierdo despues del balanceo: " << T.left().data();
00827         cout << "\nhijo derecho despues del balanceo :" <<  T.right().data();
00828         cout << "\nEl arbol original cambia debido a que primero se usa una\n";
00829         cout << "insercion normal de arboles binarios y luego queda como si\n";
00830         cout << "se hubieran insertado los elementos con un metodo AVL de insercion.\n";
00831         IPD( cout, T );
00832     }
00833 
00834     {   // Permutaciones
00835         Bin_Tree<int> T; // Arbol en el que se insertarán varios valores
00836         const int MAX_VALUES = 7; // cantidad máxima de nodos insertados en "T"
00837         std::vector< int > vec, ORIGINAL;
00838         for ( int i=0; i<MAX_VALUES; ++i ) {
00839             ORIGINAL.push_back(i);
00840         }
00841 
00842         std::string T_str;
00843         for ( int N=0; N<MAX_VALUES; ++N ) {
00844             // prueba con todos los tamaños de árbol
00845             int i, N_Fact = 1; // El factorial de N
00846             for (i = 1; i < N; ++i) {
00847                 N_Fact *= i;
00848             }
00849             vec = ORIGINAL;
00850             for ( int i=0; i<N_Fact; ++i ) {
00851                 // Siguiente secuencia desordenada de números
00852                 next_permutation( vec.begin(), vec.end() );
00853                 T_str = "[";
00854                 for ( std::vector<int>::size_type k=0; k<vec.size(); ++k ) {
00855                     T_str += ' ' + TestCase::toString(vec[k]);
00856                 }
00857                 T_str += " ] ==> ";
00858                 T.clear();
00859                 typename std::vector< int >::const_iterator it = vec.begin();
00860                 for ( int j=0; j<N; ++j,++it ) {
00861                     insertAVL( T , *it );
00862                 }
00863                 /// Verifica que el árbol está balanceado
00864                 assertTrue_Msg( T_str + "isAVL( "+TestCase::toString( T )+" )" , isAVL(T) );
00865                 if ( false && (failureCount() > 50) ) {
00866                     return; // se sale para no generar demasidos errores
00867                 }
00868                 assertTrue_Msg( T_str + " T.size() == " + TestCase::toString( T.size() ), T.size() == N );
00869             }
00870         }
00871     }
00872 }
00873 
00874 /** Verifica que las funciones \c height() y \c depth() funcionan correctamente.
00875 \code
00876        a
00877       / \
00878      /   \
00879     b     e
00880    / \   / \
00881   f   h i   k
00882            / \
00883           l   m
00884              / \
00885             n   o
00886 \endcode
00887 */
00888 template <class E>
00889 void test_Bin_Tree<E>::test_heightdepth() {
00890      Bin_Tree<E> T = make_ab_no();
00891      assertTrue( 4 == height( T.root() ) );
00892      assertTrue( 0 == depth(  T.root() ) );
00893 
00894      Bin_Tree<E> e = T.right();
00895      assertTrue( 3 == height( e ) );
00896      assertTrue( 1 == depth(  e ) );
00897 
00898      Bin_Tree<E> b = T.left();
00899      assertTrue( 1 == height( b ) );
00900      assertTrue( 1 == depth(  b ) );
00901 
00902      assertTrue( -1 == depth(  Bin_Tree<E>() ) );
00903      assertTrue( -1 == height( Bin_Tree<E>() ) );
00904 }
00905 
00906 using std::cout;
00907 using std::endl;
00908 
00909 /// Verifica que \c make_FBHCID() construyó el árbol correctamente.
00910 template <class E>
00911 void test_Bin_Tree<E>::do_cout() {
00912     Bin_Tree<char> T1,T2 = make_FBHCID();
00913     copyDeep( T1, T2 );
00914     mirror( T2.left() );  // Tmp = T2.left();  mirror( Tmp );
00915     mirror( T2.right() ); // Tmp = T1.right(); mirror( Tmp );
00916     cout << endl << "homomorfo()" << endl;
00917     IPD( cout , T1 ); cout << endl;
00918     IPD( cout , T2 ); cout << endl;
00919 }
00920 
00921 /// Programa principal desde donse se invocan todas las pruebas
00922 int main() {
00923     if (1) {
00924         cout << "test_Bin_Tree<char>\n";
00925         test_Bin_Tree<char> tester;
00926         tester.run();
00927         cout << tester.report();
00928     }
00929 }
00930 
00931 // EOF: test_Bin_Tree.cpp