// TTree.cpp (c) 2004 adolfo@di-mare.com

/** \file TTree.cpp
   [T]est[Tree].cpp ==> Ejemplos de uso de la clase Arbol.
*/

#if defined(__BORLANDC__)
    #include "bool.h"    // Usado sólo para Borland C++ v3.1
#endif

#include "Tree_Ex.h"
#include <bitset>
#include <algorithm> // sort() && next_permutation()

int make_a_o(Tree & T);
int make_graft(Tree & T);
int make_graft_A123(const char* tittle);
int make_mirror(const char* tittle, Tree & T, int make_fun(Tree&));

int make_a13(Tree & T);
int make_a123(Tree & T);
int make_a024(Tree & T);
int make_a1234(Tree & T);
Tree make_A0xx9(const char* Astr);
void make_right_A0xx9(const char* Astr);
void make_Change_Child_Graft_A0xx9(const char * Astr);
void make_Change_Child_Graft_ALL();

int main_TTree();


/// Este el el progama principal para pobar Tree
int main() {

    if (1) {
        make_Change_Child_Graft_A0xx9("A014589");
        make_Change_Child_Graft_A0xx9("A124689");
        make_Change_Child_Graft_A0xx9("A012345");
        make_Change_Child_Graft_A0xx9("A123456");
        make_Change_Child_Graft_A0xx9("A012458");

        make_Change_Child_Graft_A0xx9("A012");
        make_Change_Child_Graft_A0xx9("A123");
        make_Change_Child_Graft_A0xx9("A028");
        make_Change_Child_Graft_A0xx9("A136");
        make_Change_Child_Graft_A0xx9("A048");

        make_Change_Child_Graft_A0xx9("A01");
        make_Change_Child_Graft_A0xx9("A02");
        make_Change_Child_Graft_A0xx9("A04");
        make_Change_Child_Graft_A0xx9("A12");
        make_Change_Child_Graft_A0xx9("A14");

        make_Change_Child_Graft_A0xx9("A0");
        make_Change_Child_Graft_A0xx9("A4");
    }

    if (1) {
        make_Change_Child_Graft_A0xx9("A012345");
        make_Change_Child_Graft_ALL();
    }

    if (1) {
        Tree T;
        T = make_A0xx9("A046");
        Print(T); cout << endl;
        T.Change_Child(2, '2'); 
        Print(T); cout << endl;
        assert( T == make_A0xx9("A0246") );

        T = make_A0xx9("A046"); T.Change_Child(2, '2'); assert( T == make_A0xx9("A0246") );

        T = make_A0xx9("A123"); T.Change_Child(0, '0'); assert( T == make_A0xx9("A0123") );
        T = make_A0xx9("A023"); T.Change_Child(1, '1'); assert( T == make_A0xx9("A0123") );
        T = make_A0xx9("A013"); T.Change_Child(2, '2'); assert( T == make_A0xx9("A0123") );
        T = make_A0xx9("A012"); T.Change_Child(3, '3'); assert( T == make_A0xx9("A0123") );

        T = make_A0xx9("A246"); T.Change_Child(0, '0'); assert( T == make_A0xx9("A0246") );
        T = make_A0xx9("A046"); T.Change_Child(2, '2'); assert( T == make_A0xx9("A0246") );
        T = make_A0xx9("A026"); T.Change_Child(4, '4'); assert( T == make_A0xx9("A0246") );
        T = make_A0xx9("A024"); T.Change_Child(6, '6'); assert( T == make_A0xx9("A0246") );
    }

    if (1) {
        Tree T;
        make_right_A0xx9("A2468");
        make_right_A0xx9("A0123");
        make_right_A0xx9("A389");
        make_right_A0xx9("A019");
    }

    if (1) {
        Tree T402; T402 = 'A';
        T402.Change_Child(4, '4'); T402.Change_Child(0, '0'); T402.Change_Child(2, '2');
        assert( T402.Ok() );

        Tree T204; T204 = 'A';
        T204.Change_Child(2, '2'); T204.Change_Child(0, '0'); T204.Change_Child(4, '4');
        assert( T204.Ok() );

        assert( T402 == T204 );
    }

    if (1) {
        Tree T024;
        T024 = 'A'; // inserta la raiz 'A'
        T024.Change_Child(0, '0'); //     a
        T024.Change_Child(2, '2'); //   ./|\.
        T024.Change_Child(4, '4'); //   0 2 4
        assert( T024.Ok() );

        Tree T402; T402 = 'A';
        T402.Change_Child(4, '4'); T402.Change_Child(0, '0'); T402.Change_Child(2, '2');
        assert( T402.Ok() );

        Tree T204; T204 = 'A';
        T204.Change_Child(2, '2'); T204.Change_Child(0, '0'); T204.Change_Child(4, '4');
        assert( T204.Ok() );

        Tree T420; T420 = 'A';
        T420.Change_Child(4, '4'); T420.Change_Child(2, '2'); T420.Change_Child(0, '0');
        assert( T420.Ok() );

        assert( T024 == T402 );
        assert( T024 == T204 );
        assert( T024 == T420 );
    }

    if (1) {
        Tree T;
        T = 'A';               // inserta la raiz 'A'
        T.Change_Child(0, '0');             //   ./|\.
            Print(T); cout << endl << endl; //   0 2 4
        T.Change_Child(2, '2');
            Print(T); cout << endl << endl;
        T.Change_Child(4, '4');
            Print(T); cout << endl << endl;
        assert( T.Ok() );

        cout << "[a [0 2 4]]" << endl << endl;
        Print(T); cout << endl << endl;
        Ztree_Print(T);

        /***********************************/

        T.Erase();
        cout << T.Count() << " == " << My_Count(T) << " == Cuantos" << endl << endl;
    }

    if (1) {
        Tree T;
        make_a_o(T);
        cout << "make_a_o(T)" << endl << endl;
        Print(T); cout << endl << endl;
        Ztree_Print(T);
        cout << T.Count() << " == " << My_Count(T) << " == Cuantos" << endl << endl;
        cout << Count_Children(T) << " == Hijos de la Raíz" << endl << endl;
    }


    if (1) {              // a
        Tree T;           // |--0            [0]
        make_a024(T);     // |--<empty>      [1]
                          // |--2            [2]
        Ztree_Print(T);   // |--<empty>      [3]
        assert( T.Ok() ); // +--4            [4]

        assert( "Right_Sibling(2.4.->)" && T.Child(2).Right_Sibling() .Same( T.Child(4) ) );
        assert( "Right_Sibling(0.2.->)" && T.Child(0).Right_Sibling() .Same( T.Child(2) ) );
        assert( "Right_Sibling(4.-.->)" && T.Child(4).Right_Sibling() .Same( Tree() ) );

        assert( "Right_Sibling(T.-.->)" && T.Right_Sibling() .Same( Tree() ) );
        assert( "Left_Sibling(T.-.<-)"  && T.Left_Sibling()  .Same( Tree() ) );

        assert( "Left_Sibling(4.2.<-)"  && T.Child(4).Left_Sibling() .Same( T.Child(2) ) );
        assert( "Left_Sibling(2.0.<-)"  && T.Child(2).Left_Sibling() .Same( T.Child(0) ) );
        assert( "Left_Sibling(0.-.<-)"  && T.Child(0).Left_Sibling() .Same( Tree() ) );
    }

    if (1) {               // a
        Tree T;            // |--b -- etc     [0]
        make_a_o(T);       // |--c            [1]
                           // |--d            [2]
        Ztree_Print(T);    // |--e -- etc     [3]
        assert( T.Ok() );

        assert( "Right_Sibling(0.1.->)" && T.Child(0).Right_Sibling() .Same( T.Child(1) ) );
        assert( "Right_Sibling(1.2.->)" && T.Child(1).Right_Sibling() .Same( T.Child(2) ) );
        assert( "Right_Sibling(2.3.->)" && T.Child(2).Right_Sibling() .Same( T.Child(3) ) );
        assert( "Right_Sibling(3.-.->)" && T.Child(3).Right_Sibling() .Same( Tree() ) );

        assert( "Right_Sibling(-.-.->)" && Tree().Right_Sibling() .Same( Tree() ) );
        assert( "Left_Sibling(-.-.<-)"  && Tree().Left_Sibling()  .Same( Tree() ) );

        assert( "Right_Sibling(T.-.->)" && T.Right_Sibling() .Same( Tree() ) );
        assert( "Left_Sibling(T.-.<-)"  && T.Left_Sibling()  .Same( Tree() ) );

        assert( "Left_Sibling(3.2.<-)"  && T.Child(3).Left_Sibling() .Same( T.Child(2) ) );
        assert( "Left_Sibling(2.1.<-)"  && T.Child(2).Left_Sibling() .Same( T.Child(1) ) );
        assert( "Left_Sibling(1.0.<-)"  && T.Child(1).Left_Sibling() .Same( T.Child(0) ) );
        assert( "Left_Sibling(0.-.<-)"  && T.Child(0).Left_Sibling() .Same( Tree() ) );

        if ( ! T.Child(3).Left_Sibling() .Same( T.Child(2) ) )  { cout << "ERRROR(3.2.<-)"  << endl; }
        if ( ! T.Child(2).Left_Sibling() .Same( T.Child(1) ) )  { cout << "ERRROR(2.1.<-)"  << endl; }
        if ( ! T.Child(1).Left_Sibling() .Same( T.Child(0) ) )  { cout << "ERRROR(1.0.<-)"  << endl; }
        if ( ! T.Child(0).Left_Sibling() .Same( Tree() ) )  { cout << "ERRROR(0.-.<-)"  << endl; }
    }

    if (1) {               // a
        Tree T;            // |--b -- etc     [0]
        make_a_o(T);       // |--c            [1]
                           // |--d            [2]
        Ztree_Print(T);    // |--e -- etc     [3]
        assert( T.Ok() );

        assert( "Right_Sibling_Inmediate(0.1.->)" && T.Child(0).Right_Sibling_Inmediate() .Same( T.Child(1) ) );
        assert( "Right_Sibling_Inmediate(1.2.->)" && T.Child(1).Right_Sibling_Inmediate() .Same( T.Child(2) ) );
        assert( "Right_Sibling_Inmediate(2.3.->)" && T.Child(2).Right_Sibling_Inmediate() .Same( T.Child(3) ) );
        assert( "Right_Sibling_Inmediate(3.-.->)" && T.Child(3).Right_Sibling_Inmediate() .Same( T.Child(4) ) );

        assert( "Right_Sibling_Inmediate(-.-.->)" && Tree().Right_Sibling_Inmediate() .Same( Tree() ) );
        assert( "Left_Sibling_Inmediate(-.-.<-)"  && Tree().Left_Sibling_Inmediate()  .Same( Tree() ) );

        assert( "Right_Sibling_Inmediate(T.-.->)" && T.Right_Sibling_Inmediate() .Same( Tree() ) );
        assert( "Left_Sibling_Inmediate(T.-.<-)"  && T.Left_Sibling_Inmediate()  .Same( Tree() ) );

        assert( "Left_Sibling_Inmediate(3.2.<-)"  && T.Child(3).Left_Sibling_Inmediate() .Same( T.Child(2) ) );
        assert( "Left_Sibling_Inmediate(2.1.<-)"  && T.Child(2).Left_Sibling_Inmediate() .Same( T.Child(1) ) );
        assert( "Left_Sibling_Inmediate(1.0.<-)"  && T.Child(1).Left_Sibling_Inmediate() .Same( T.Child(0) ) );
        assert( "Left_Sibling_Inmediate(0.-.<-)"  && T.Child(0).Left_Sibling_Inmediate() .Same( Tree() ) );
    }

    if (1) {
        Tree T;
        make_a024(T);
        cout << endl << endl;
        cout << "Recorrido de los hijos no vacíos de un sub-árbol de izquierda a derecha:" << endl;

        cout << * T.Root() << endl;
        Tree Child = T.Leftmost();
        while ( ! Child.Empty() ) {
            cout << "  [" << Child.Child_Number() << "] " << * Child << " " << endl;
            Child = Child.Right_Sibling();
        }
        assert( T.Ok() );

        cout << endl << endl;
    }

    if (1) {
        Tree T;
        make_a024(T);
        cout << endl << endl;
        cout << "Recorrido de los hijos no vacíos de un sub-árbol de derecha a izquierda:" << endl;

        cout << * T.Root() << endl;
        Tree Child = T.Rightmost();
        while ( ! Child.Empty() ) {
            cout << "  [" << Child.Child_Number() << "] " << * Child << " " << endl;
            Child = Child.Left_Sibling();
        }
        assert( T.Ok() );

        cout << endl << endl;
    }

    if (1) {
        Tree T;
        make_a024(T);

        Tree L_Child = T.Leftmost();
        Tree R_Child = T.Rightmost();
        Tree   Child;
        assert( T.Ok() );
        cout << endl << endl;
        cout << "Uso de Tree::Leftmost()    Tree::Left_Sibling()"  << endl;
        cout << "       Tree::Rightmost()   Tree::Right_Sibling()" << endl;
        Ztree_Print(T);

        cout << endl << endl << "Izquierda ==> Derecha ==> " ;
        Child = L_Child;
        while ( ! Child.Empty() ) {
            cout << '[' << * Child << "] ";
            Child = Child.Right_Sibling();
        }
        assert( T.Ok() );

        cout << endl << endl << "Derecha ==> Izquierda ==> ";
        Child = R_Child;
        while ( ! Child.Empty() ) {
            cout << '[' << * Child << "] ";
            Child = Child.Left_Sibling();
        }
        assert( T.Ok() );

        cout << endl << endl;
    }

    if (1) {
        Tree T;
        make_a_o(T);
        Ztree_Print(T);

        cout << endl;
        while ( T.Count() > 1 ) {
            unsigned n =  T.Leftmost_N();
            T.Graft(n, Tree( ));
            cout << "Acabo de eliminar T.Child(" << n
                 << ") ==> quedan [1+" << T.Count()-1 << ']' << endl;
        }
        assert( T.Count() == 1 );
        assert( *T == 'A' );
    }

    if (1) {
        Tree T;
        T = 'A';
        T.Change_Child(0, '0');
        T.Erase_Son(0);
    }

    if (1) {
        Tree T;
        make_a_o(T);

        cout << endl;
        Ztree_Print(T);
        while ( T.Count() > 1 ) {
            unsigned n =  T.Rightmost_N();
            cout << endl << "Elimino el sub-árbol número " << n 
                 << " de T == [" << *T.Child(n) << "]" << endl;
            T.Graft(n, Tree( ));
            assert( T.Child(n).Empty() );
            Print(T); cout << endl;
            Ztree_Print(T);
            cout << "Acabo de eliminar T.Child(" << n
                 << ") ==> quedan [1+" << T.Count()-1 << ']' << endl;
        }
        assert( T.Count() == 1 );
        assert( *T == 'A' );
    }

    if (1) {              // a
        Tree T;           // |--0            [0]
        make_a024(T);     // |--<empty>      [1]
                          // |--2            [2]
        Ztree_Print(T);   // |--<empty>      [3]
        assert( T.Ok() ); // +--4            [4]

        assert( T.Child(0).Sibling(0) .Same( T.Child(0) ) );
        assert( T.Child(0).Sibling(2) .Same( T.Child(2) ) );
        assert( T.Child(0).Sibling(-1).Same( T.Child(1) ) );

        assert( T.Child(1).Sibling(0) .Same( T.Child(3) ) );
        assert(!T.Child(1).Sibling(1). Same( T.Child(2) ) );

        assert( T.Child(2).Sibling(0) .Same( T.Child(2) ) );
        assert( T.Child(2).Sibling(2). Same( T.Child(4) ) );
        assert( T.Child(2).Sibling(-2).Same( T.Child(0) ) );

        assert( T.Child(4).Sibling(-3).Same( T.Child(1) ) );
        assert( T.Child(4).Sibling(-4).Same( T.Child(0) ) );
        assert( T.Child(4).Sibling(-1).Same( T.Child(3) ) );
        assert( T.Child(4).Sibling(-2).Same( T.Child(2) ) );
        assert( T.Child(4).Sibling(2). Same( T.Child(3) ) );
    }

    if (1) {
        void Print_Depth_Height( Tree & T, unsigned indent);
        cout << "[Profundidad Altura]" << endl << endl;

        Tree T;
        cout << '[' << Depth(T) << ' ' << Height(T) << "] " << "T == []"; cout << endl;

        T='A'; Print_Depth_Height(T,0); cout << endl;

        T.Change_Child(0, '0'); Print_Depth_Height(T,0); cout << endl;

        make_a_o(T); Print_Depth_Height(T,0); cout << endl;
    }

    if (1) {
        Tree Tc, T; make_a_o(T);
            assert( Tc != T );
        Tc = T;
            assert( Tc == T );
            assert( T.Same(Tc) );
        Tc.Copy_Deep(T);
            assert( T == Tc );
            assert( ! T.Same(Tc) );

        Tree S = T;
            assert( S == T );
            assert( T.Same(S) );

        S.Erase();
            assert( S.Empty() );
            assert( ! T .Empty() );
            assert( T != S );
            assert( ! T.Same(S) );

        Tc = S;
            assert( S == Tc );
            assert( ! T.Same(Tc) ) ;

        S.Copy_Deep( T );
            assert( S == T );
            assert( ! T.Same(S) );
    }

    if (1) {
        Tree T;       assert ( T.Empty()      && 0 == Arity(T) );
        T = '1';      assert ( "T = '1'"      && 0 == Arity(T) );
        make_a_o(T);  assert ( "make_a_o(T)"  && 4 == Arity(T) );
        make_a13(T);  assert ( "make_a13(T)"  && 2 == Arity(T) );
        make_a024(T); assert ( "make_a024(T)" && 3 == Arity(T) );
    }

    if (1) {
        Tree T;
        make_a_o(T);

        Tree Te    = T.Child(3);
        Tree Tej   = T.Child(3).Child(1);
        Tree Tejm  = T.Child(3).Child(1).Child(1);
        Tree Tejmn = T.Child(3).Child(1).Child(1).Child(0);
        Tree Tek   = T.Child(3).Child(2);

        assert( ! Ancestor ( T, T ) );
        assert( ! Ancestor ( Tejm, Tejm ) );
        assert( ! Ancestor ( Tree(), T ) );
        assert( ! Ancestor ( Tree(), Tree() ) );

        assert( ! Ancestor ( Tejm, Tek ) );
        assert( ! Ancestor ( Tejm, Tek ) );

        assert( ! Ancestor ( T, Tejm ) );
        assert( ! Ancestor ( Tejm, Tejmn ) );
        assert( ! Ancestor ( T, Tek ) );

        assert( Ancestor ( Tejmn, T    ) );
        assert( Ancestor ( Tejmn, Te   ) );
        assert( Ancestor ( Tejmn, Tej  ) );
        assert( Ancestor ( Tejmn, Tejm ) );

        assert( Ancestor ( Tejm, T    ) );
        assert( Ancestor ( Tejm, Te   ) );
        assert( Ancestor ( Tejm, Tej  ) );

        assert( Ancestor ( Tej, T  ) );
        assert( Ancestor ( Tej, Te ) );
    }

    if (1) {
        cout << endl;     // a
        Tree T;           // |--0            [0]
        make_a024(T);     // |--<empty>      [1]
                          // |--2            [2]
        Ztree_Print(T);   // |--<empty>      [3]
        assert( T.Ok() ); // +--4            [4]

        for (unsigned i = 0; i <= T.Rightmost_N(); ++i) {
            T.Graft(i, Tree( ));
            cout << "Acabo de eliminar T.Child(" << i
                 << ") ==> quedan [1+" << T.Count()-1 << ']' << endl;
        }
        assert( T.Count() == 1 );
    }

    if (1) {
        cout << endl;     // a
        Tree T;           // |--0            [0]
        make_a024(T);     // |--<empty>      [1]
                          // |--2            [2]
        Ztree_Print(T);   // |--<empty>      [3]
        assert( T.Ok() ); // +--4            [4]

        unsigned n = 6;
        do { // assert( n > 0 );
            --n;
            cout << endl << "Elimino[" << n << ']' << endl;
            T.Erase_Son( n );
            Print(T);
            cout << endl;
        } while (n > 0);

        assert( T.Count() == 1 );
    }

    if (1) {
        cout << endl;     // a
        Tree T;           // |--0            [0]
        make_a024(T);     // |--<empty>      [1]
                          // |--2            [2]
        Ztree_Print(T);   // |--<empty>      [3]
        assert( T.Ok() ); // +--4            [4]

        {   cout << endl << "Elimino en el medio [" << 2 << ']' << endl;
            T.Erase_Son( 2 );
            Print(T);
            cout << endl;
        }
        for (unsigned n = 0; n < 6; ++n) {
            cout << endl << "Elimino[" << n << ']' << endl;
            T.Erase_Son( n );
            Print(T);
            cout << endl;
        }

        assert( T.Count() == 1 );
    }

    if (1) {
        Tree T,Tc;         //     a
        make_a13(T);       //   ./ \.
        Tc.Copy_Deep( T ); //   1   3
        assert( T == Tc );
        assert( ! T.Same( Tc ) );
        Tree S1, S3;

        cout << "=========================" << endl;
        Print(Tc); cout << endl << endl;
        S1 = Tc.Child(1);
        S3 = Tc.Child(3);

        Tc.Graft(2, S1); // AQUI DA ERROR
        Print(Tc); cout << endl << endl;
        Tc.Graft(0, S3);
        Print(Tc); cout << endl << endl;

        cout << "=========================" << endl;
        Print(T); cout << endl << endl;
        S1 = T.Child(1);
        S3 = T.Child(3);

        T.Graft(0, S3);
        Print(T); cout << endl << endl;
        T.Graft(2, S1); // AQUI DA ERROR
        Print(T); cout << endl << endl;
    }

    if (1) {
        make_graft_A123("A012");
        make_graft_A123("A123");
        make_graft_A123("A035");
        make_graft_A123("A146");
        make_graft_A123("A268");
    }

    if (1) {
        Tree T = 'A';
        T.Change_Child(1, '1');
        T.Change_Child(3, '3');
        T.Change_Child(5, '5');
        cout << endl; Print(T);
        Mirror(T);
        cout << endl; Print(T);
    }

    if (1) {
        cout << endl << "OJO: T != Mirror(T) + Mirror(T) " << endl;
        Tree T,Tc;
        T = 'A';                 // [00]==> A
        T.Change_Child(11, '1'); //   [11]==> 1
        Tc.Copy_Deep( T );
        assert( T == Tc );

        cout << endl; Print(T);            // [00]==> A
        Mirror(T); assert( Check_Ok(T) );  //   [00]==> 1
        cout << endl; Print(T);
        Mirror(T); assert( Check_Ok(T) );
        cout << endl; Print(T);

        assert( T != Tc );
    }

    if (1) {
        Tree T,Tc;

        make_mirror( "mirror_a13(T)",   T, make_a13   );
        make_mirror( "mirror_a1234(T)", T, make_a1234 );
        make_mirror( "mirror_a_o(T)",   T, make_a_o   );
        make_mirror( "mirror_a024(T)",  T, make_a024  );

        make_a_o(T);
        Tc.Copy_Deep( T ); assert( T == Tc ); assert( ! T.Same(Tc) );
        Mirror(T); assert( Check_Ok(T) );
        Mirror(T); assert( Check_Ok(T) );

        assert( T == Tc );
        assert( ! T.Same(Tc) );
    }

    if (1) {
        Tree T;
        make_graft(T);
        cout << "make_graft(T)" << endl << endl;
        Print(T); cout << endl << endl;
        Ztree_Print(T);
        cout << "Cuantos == " << T.Count() << " == " << My_Count(T) << endl << endl;
    }

    if (1) {
        Tree T = 'b';
        T.Erase();
    }

    return 0;
} // main_TTree()

/** Trabaja con un árbol similar al que produce "make_a_o()" para Mirror()

    \code
    a               a
    |--b            |--e
    |  |--f         |  |--k
    |  |--g         |  |--j
    |  +--h         |  |  |--m
    |--c            |  |  |  |--o
    |--d            |  |  |  +--n
    +--e            |  |  +--l
       |--i         |  +--i
       |--j         |--d
       |  |--l      |--c
       |  +--m      +--b
       |     |--n      |--h
       |     +--o      |--g
       +--k            +--f
    \endcode
*/
int make_mirror(const char* tittle, Tree & T, int make_fun(Tree&)) {
    T.Erase();
    make_fun(T);
    cout << endl << endl << tittle << endl;
    Ztree_Print(T);
    Print(T);
    cout << endl;

    Mirror(T);

    cout << endl << endl;
    Ztree_Print(T);
    Print(T);
    cout << endl;

    assert( T.Ok() );
    return 0;
}

#include <cstring> // strlen(), etc.

/** Toma la hilera \c "Astr" que tiene la forma "A######" y construye un árbol con ella

    - "#" debe ser un dígito [0..9]
    - El árbol retornado tiene a A por raíz, y el hijo número "#" es el dígito "#"

\code
     A                       A                       A
    /|\                     / \                     /|\
   0 2 4                   1   8                   2 3 9
make_A0xx9("A024")    make_A0xx9("A81")    make_A0xx9("A392")
\endcode
*/
Tree make_A0xx9(const char* Astr) {
    assert( 'A' == Astr[0] && 2 <= strlen(Astr) &&  strlen(Astr) <= 11 );
    Tree T = 'A';
    const char* s = &Astr[1];
    while (*s != 0) {
        unsigned n = unsigned(*s-'0');
        assert( ('0' <= *s) && (*s <= '9') );
        T.Change_Child(n, *s);
        ++s;
    }
    return T;
}


int make_graft_A123(const char* Astr) {
    char A2[4] = { 'A', Astr[1], Astr[3], 0 };
    assert( Astr[1] < Astr[2] && Astr[2] < Astr[3] );
    Tree T2 = make_A0xx9(A2);
    Tree T3 = make_A0xx9(Astr);
    Tree T; // la copia de trabajo
    T2 = 'A'; T3 = 'A';
    unsigned left   = unsigned(Astr[1]-'0');
    unsigned middle = unsigned(Astr[2]-'0');
    unsigned right  = unsigned(Astr[3]-'0');
    unsigned N_arity = right;
    Tree S_left, S_middle, S_right;

    {
        cout << "=========================" << endl;
        T.Copy_Deep( T3 );
        S_left   = T.Child( left );
        S_middle = T.Child( middle );
        S_right  = T.Child( right );
                                           Print(T); cout << endl;
        T.Graft(N_arity-left,   S_left);   Print(T); cout << endl;
        T.Graft(N_arity-right,  S_right);  Print(T); cout << endl;
        T.Graft(N_arity-middle, S_middle); Print(T); cout << endl;

        cout << endl << "      ===================" << endl;

        S_left   = T.Child( N_arity-left );
        S_middle = T.Child( N_arity-middle );
        S_right  = T.Child( N_arity-right );
                                           Print(T); cout << endl;
        T.Graft(middle, S_middle);         Print(T); cout << endl;
        T.Graft(left,   S_left);           Print(T); cout << endl;
        T.Graft(right,  S_right);          Print(T); cout << endl;

        assert( T.Ok() );
        assert( T == T3 );
    }
    {
        cout << "=========================" << endl;
        T.Copy_Deep( T2 );
        S_left   = T.Child( left );
        S_right  = T.Child( right );
                                           Print(T); cout << endl;
        T.Graft(N_arity-left,   S_left);   Print(T); cout << endl;
        T.Graft(N_arity-right,  S_right);  Print(T); cout << endl;

        cout << endl << "      ===================" << endl;

        S_left   = T.Child( N_arity-left );
        S_right  = T.Child( N_arity-right );
                                           Print(T); cout << endl;
        T.Graft(left,   S_left);           Print(T); cout << endl;
        T.Graft(right,  S_right);          Print(T); cout << endl;

        assert( T.Ok() );
        assert( T == T2 );
    }
    return 0;
}


/** Primero vacea "T" y luego le inserta los valores [a [1 3]]

\code
     a
   ./ \.
    1 3
\endcode
*/
int make_a13(Tree & T) {
    T.Erase();
    T = 'A';   // inserta la raiz 'A'
    T.Change_Child(1, '1'); //   ./ \.
    T.Change_Child(3, '3'); //   1   3
    return 0;
}

/** Primero vacea "T" y luego le inserta los valores [a [0 2 4]]

\code
     a
   ./|\.
   0 2 4
\endcode
*/
int make_a024(Tree & T) {
    T.Erase();
    T = 'A'; // inserta la raiz 'A'
    T.Change_Child(0, '0'); //     a
    T.Change_Child(2, '2'); //   ./|\.
    T.Change_Child(4, '4'); //   0 2 4
    return 0;
}


/** Primero vacea "T" y luego le inserta los valores [a [1 2 3]]

\code
     a
   ./|\.
   1 2 3
\endcode
*/
int make_a123(Tree & T) {
    T.Erase();
    T = 'A'; // inserta la raiz 'A'
    T.Change_Child(1, '1'); //     a
    T.Change_Child(2, '2'); //   ./|\.
    T.Change_Child(3, '3'); //   1 2 3
    return 0;
}

/** Primero vacea "T" y luego le inserta los valores [a [0 3 5]]

\code
     a
   ./|\.
   0 3 5
\endcode
*/
int make_a035(Tree & T) {
    T.Erase();
    T = 'A'; // inserta la raiz 'A'
    T.Change_Child(0, '0'); //     a
    T.Change_Child(0, '3'); //   ./|\.
    T.Change_Child(5, '5'); //   0 3 5
    return 0;
}

/** Primero vacea "T" y luego le inserta los valores [a [1 2 3 4]]

\code
      a
   . /|\.
   .// \\.
   1 2 3 4
\endcode
*/
int make_a1234(Tree & T) {
    T.Erase();
    T = 'A'; // inserta la raiz 'A'
    T.Change_Child(1, '1');
    T.Change_Child(2, '2');
    T.Change_Child(3, '3');
    T.Change_Child(4, '4');
    return 0;
}


/** Primero vacea "T" y luego le inserta estos valores:

    \code
                 T = a
                     |--b
                     |  |--f
     T = a           |  |--g
        /|\          |  +--h
      / / \ \        |--c
     b  c d  e       |--d
    /|\     /|\      +--e
   f g h   i j k        |--i
            / \         |--j
            l m         |  |--l
             / \        |  +--m
             n o        |     |--n
                        |     +--o
                        +--k
    \endcode
*/
int make_a_o(Tree & T) {
    Tree Th;
    T.Erase();
    T = 'A'; // inserta la raiz 'A'
    assert( T.Ok() );

    /***********************************/

    T.Change_Child(0, 'b'); //     a
    T.Change_Child(1, 'c'); //   ./|\.
    T.Change_Child(2, 'd'); // ./ / \ \.
    T.Change_Child(3, 'e'); // b  c d  e
    assert( T.Ok() );

    /***********************************/

    Th = T.Child(0); // 'b'

    Th.Change_Child(0, 'f'); //   b
    Th.Change_Child(1, 'g'); // ./|\.
    Th.Change_Child(2, 'h'); // f g h
    assert( T.Ok() );

    /***********************************/

    Th = T.Child(3);  //  'e'
    Th.Change_Child(0, 'i'); //   e
    Th.Change_Child(1, 'j'); // ./|\.
    Th.Change_Child(2, 'k'); // i j k
    assert( T.Ok() );

    /***********************************/

    Th = Th.Child(1);      //  'j'
    Th.Change_Child(0, 'l'); // ./ \.
    Th.Change_Child(1, 'm'); //  l m
    assert( T.Ok() );

    Th = Th.Child(1);      //  'm'
    Th.Change_Child(0, 'n'); // ./ \.
    Th.Change_Child(1, 'o'); //  n o
    assert( T.Ok() );

    return 0;
}

/** Trabaja con un árbol similar al que produce "make_a_o()" para
    usar Tree::Graft().
*/
int make_graft(Tree & T) {
    Tree TT = T;
    assert (TT == T);

    {   Tree Tejm;
        T.Erase();
        make_a_o(T);

        Tejm = T.Child(3).Child(1).Child(1);

        cout << endl << endl << "T" << endl;
        Ztree_Print(T);

        T.Graft(4, Tejm);

        cout << endl << endl << "Tejm" << endl;
        Ztree_Print(Tejm);

        cout << endl << endl << "T" << endl;
        Ztree_Print(T);

        assert( T.Ok() );
    }

    {   Tree Tej;
        T.Erase();
        make_a_o(T);

        Tej = T.Child(3).Child(1);

        cout << endl << endl << "T" << endl;
        Ztree_Print(T);

        T.Child(2).Graft(4, Tej);

        cout << endl << endl << "Tej" << endl;
        Ztree_Print(Tej);

        cout << endl << endl << "T" << endl;
        Ztree_Print(T);

        assert( T.Ok() );
    }

    {   Tree Tej;
        T.Erase();
        make_a_o(T);

        Tej = T.Child(3).Child(1);

        cout << endl << endl << "T" << endl;
        Ztree_Print(T);

        T.Child(0).Graft(1, Tej);

        cout << endl << endl << "Tej" << endl;
        Ztree_Print(Tej);

        cout << endl << endl << "T" << endl;
        Ztree_Print(T);

        assert( T.Ok() );
    }
    return 0;
}

void Print_Depth_Height( Tree& T, unsigned indent ) {
    if ( T.Empty() ) {
        return;
    }

    cout << endl;
    unsigned i;
    for (i=0; i < indent; ++i) {
        cout << "  ";
    }
    cout << '[' << Depth(T) << ' ' << Height(T) << "] " << *T;

    for (i=T.Leftmost_N(); i <= T.Rightmost_N(); ++i) {
        Print_Depth_Height( T.Child(i), indent+1 );
    }
}

/** Traslada una posición hacia la derecha cada uno de los hijos de \c "T"

    - Los hijos de "T" son los definidos en la hilera \c "Astr"
    - A "T" lo construye invocando \c make_A0xx9(Astr)
*/
void make_right_A0xx9(const char* Astr) {
    Tree T = make_A0xx9(Astr);
    unsigned N = T.Rightmost_N();
    cout << endl << "================= " << N;
    Print(T); cout << endl;
    for ( unsigned j=N+1; j>0; --j ) {
        T.Graft(j, T.Child(j-1));
    }
    Print(T); cout << endl;
}


/** Inserta en \c "T" los hijos definidos en la hilera \c "Astr" de todas las formas posibles

    - Los hijos de "T" son los definidos en la hilera \c "Astr".
    - A \c "T" lo construye invocando \c make_A0xx9(Astr).
    - Permuta \c "Astr" para obtener todas las formas posibles de insertar valores en el árbol.
    - Para \c Graft() también crea nietos, y los elimina.
    - Usa \c "next_permutation()" para obtener todas las posible permutaciones
      de la hilera \c "Astr".

    \par Complejidad:
        Usa por lo menos tiempo O( \c N! ), donde <code> N == strlen(Astr) </code>,
        así que necesariamente \c strlen(Astr) debe ser pequeño, no mayor a \c 6 o a \c 7.
    */
void make_Change_Child_Graft_A0xx9(const char * Astr) {
    Tree T = make_A0xx9(Astr);
    const size_t len = strlen(Astr);
    if (len < 2) {
        return;
    }
    assert( Astr && strlen(Astr) <= 11 );
    unsigned i, N_Fact = 1;
    for (i = 1; i < len; ++i) {
        N_Fact *= i;
    }
    char copy[12];
    memcpy( copy, Astr, len+1 );
    sort( copy+1, copy+len );
    // cout << endl << copy; Print(T);
    for (i = 0; i < N_Fact; ++i) {
        next_permutation( copy+1, copy+len );
        Tree Twrk;

        {   // Acá prueba Change_Child()
            Twrk = make_A0xx9(copy);
            assert( copy[len] == 0 );
            assert( copy && T == Twrk );
        }

        {   // Acá prueba Graft()
            Twrk.Erase(); Twrk = 'A';
            const char* str = copy+1;
            while( *str != 0 ) {
                Tree R = 'R';
                Tree S = make_A0xx9(copy);
                R.Graft( 10 - unsigned(*str-'0'), S );
                // cout << endl << 'R' << endl << copy; Print(R);
                S = *str;
                Twrk.Graft( unsigned(*str-'0'), S );
                // cout << endl << "Twrk" << endl << copy; Print(Twrk);
                assert( "Twrk.Graft( unsigned(*str-'0'), *str )" && T != Twrk );

                while( S.Count() > 1 ) {
                    unsigned L = S.Leftmost().Child_Number();
                    unsigned R = S.Rightmost().Child_Number();
                    unsigned M = (L + R) / 2;

                    S.Erase_Son( M );
                    S.Erase_Son( L );
                    S.Erase_Son( R );
                }
                if (0) {
                    cout << endl << 'R' << endl << copy; Print(R);
                    cout << endl << 'S' << endl << copy; Print(S);
                    cout << endl << "Twrk" << endl << copy; Print(Twrk);
                    cout << endl << "=============================" << endl;
                }
                str++;
            }
            if ( copy && T == Twrk ) {
            } else {
                cout << "ERROR ==> make_Change_Child_Graft_A0xx9(\"" << copy << ")\";" << endl;
                cout << endl << "Twrk" << endl << copy; Print(Twrk);
                assert( copy && T == Twrk );
            }
        }
    }
}

/** Invoca \c make_Change_Child_Graft_A0xx9() con todas las hileras de 1 a 10
    dígitos, efectivamente probando \c Change_Child() y \c Graft() con todas
    las permutaciones posibles de inserción/traslado de hijos.

    - Hace el trabajo construyendo una hilera de la forma <code> Astr == "A01...9" </code>,
      para luego invocar \c make_Change_Child_Graft_A0xx9(Astr).
    - La cantidad de pruebas es enorme, pues hay 2^10 == 1024 diferentes números
      de 10 dígitos en donde ningún dígito se repite.
    - La cantidad de permutaciones para un número de 10 dígitos es 10! == 362880,
      por lo que esta función toma su buena tajada de tiempo de ejecución, aunque
      cuando hay pocos dígitos en la hilera \c "Astr" el tiempo de ejecución es 
      relativamente corto.
*/
void make_Change_Child_Graft_ALL() {
    char num_str[1+10+1]; // "A0123456789-"
    const unsigned N = 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 + 1;
    //      1 + 1024 ~ 0   1   2   3   4   5   6   7   8   9
    for (unsigned n = 1; n < N/4; ++n) { // assert( n > 0 ); // explota con n == 0
        // if (n % 64 == 0) cout << '.';
        bitset<10> B = n;
        unsigned len = 1;
        for (unsigned i = 0; i < 10; ++i) { // borra el vector de dígitos
            if (B[i] == true) {
                num_str[len] = '0'+ char(i);
                ++len;
            }
        }
        num_str[000] = 'A';
        num_str[len] = 000;
        if (len == 11) {
            cout << "====> " << num_str << " <====" << endl;
        } else if (len == 10) {
            cout << "***" << num_str << "***" << endl;
        } else if (len == 9) {
            cout << num_str << endl;
        } else if (len == 8) {
            cout << '.';
        }
        make_Change_Child_Graft_A0xx9(num_str);
    }
}
// EOF: TTree.cpp