---

test-tree.cc

/*
*  Name:      test-tree.cc
*  Author:    Rafael Jesus Alcantara Perez
*  Summary:   Test for tree
*  Date:      $Date: 2003/10/06 12:45:11 $
*  Revision:  $Revision: 1.2 $
*
*  Copyright (C) 2000-2002  Rafael Jesus Alcantara Perez <rafa@dedalo-ing.com>
*
*  This program is free software; you can redistribute it and/or modify
*  it under the terms of the GNU General Public License as published by
*  the Free Software Foundation; either version 2 of the License, or
*  (at your option) any later version.
*
*  This program is distributed in the hope that it will be useful,
*  but WITHOUT ANY WARRANTY; without even the implied warranty of
*  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
*  GNU General Public License for more details.
*
*  You should have received a copy of the GNU General Public License
*  along with this program; if not, write to the Free Software
*  Foundation, Inc., 59 Temple Place, Suite 330, Boston,
*  MA 02111-1307, USA.
*/

#include <iostream>
#include <mpcl/test.h>
#include <mpcl/text/string.hh>
#include <mpcl/util/collection/general_tree.hh>
#include <typeinfo>


using mpcl::text::Format;


//
//  L O C A L   F U N C T I O N S
//

template <typename TIntTree>
static int _TestMemory (void)
{

  typedef
    typename TIntTree::QTTree
    QTIntTree;

  TIntTree    tTree1;
  TIntTree    tTree2;
  QTIntTree   qtTree3 (new TIntTree (3));
  QTIntTree   qtTree4 (new TIntTree (4));

  TEST_INIT (Format ( "tests for class '%s' and its copying capabilities" ,
                      typeid (TIntTree).name()                            ).c_str());

  TEST_NUMBERS (true, ( tTree1.begin() == tTree2.begin() ));
  TEST_NUMBERS (true, ( tTree2.begin() == tTree1.begin() ));
  TEST_NUMBERS (true, ( tTree1.begin() == tTree1.end() ));
  TEST_NUMBERS (true, ( tTree2.begin() == tTree2.end() ));
  TEST_NUMBERS (0,    tTree1.size());
  TEST_NUMBERS (0,    tTree2.size());

  //
  //  Tests iterator values.
  //
  tTree1.setRoot (1);
  TEST_NUMBERS (true, ( tTree1.begin()   != tTree1.end() ));
  TEST_NUMBERS (true, ( ++tTree1.begin() == tTree1.end() ));
  TEST_NUMBERS (true, ( tTree1.begin()++ != tTree1.end() ));
  TEST_NUMBERS (1,    tTree1.size());
  TEST_NUMBERS (0,    tTree2.size());

  //
  //  Tests assign operator.
  //
  tTree2 = tTree1;
  TEST_NUMBERS (true, ( tTree2.begin()   != tTree2.end() ));
  TEST_NUMBERS (true, ( ++tTree2.begin() == tTree2.end() ));
  TEST_NUMBERS (true, ( tTree2.begin()++ != tTree2.end() ));
  TEST_NUMBERS (1,    tTree1.size());
  TEST_NUMBERS (1,    tTree2.size());
  
  //
  //  Next state:  tree has two nodes.
  //
  //      +-(3)
  //      |
  //  (1)-+
  //
  tTree1.insert (qtTree3);
  TEST_NUMBERS (true, ( *(tTree1.begin())    == 1 ));
  TEST_NUMBERS (true, ( *(++tTree1.begin())  == 3 ));
  TEST_NUMBERS (true, ( ++(++tTree1.begin()) == tTree1.end() ));
  
  //
  //  Next state:  tree has three nodes.
  //
  //      +-(3)
  //      |
  //  (1)-+
  //      |
  //      +-(4)
  //
  tTree1.insert (qtTree3);
  tTree1.insert (tTree1.begin(), qtTree4);

  TEST_MEMORY_STATUS;
  TEST_RETURN_CODE;

}  // _TestMemory()


int main (void)
{

  using std::swap;

  typedef
    mpcl::util::collection::TGeneralTree<int>
    TIntTree;

  TEST_INIT ("tests for class 'TGeneralTree'");
  try
  {
    TIntTree::iterator        tIterator;
    TIntTree::side_iterator   tSideIterator;
    TIntTree                  tTree (1);
    TIntTree::QTTree          qtSon2Tree (new TIntTree (2));
    TIntTree::QTTree          qtSon3Tree (new TIntTree (3));
    TIntTree::QTTree          qtSon4Tree (new TIntTree (4));
    TIntTree::QTTree          qtGrandSon5Tree (new TIntTree (5));

    //
    //  Next state:  tree has only one node.
    //
    //  (1)
    //
    TEST_NUMBERS (1, tTree.size());
    TEST_NUMBERS (1, qtSon2Tree->size());

    //
    //  Next state:  tree has one node.
    //
    //  (1)
    //
    tTree.setRoot (1);
    TEST_NUMBERS (tTree.getRoot(), 1);
    TEST_NUMBERS (tTree.size(),    1);
    tTree.setRoot (2);
    TEST_NUMBERS (tTree.getRoot(), 2);
    TEST_NUMBERS (tTree.size(),    1);

    //
    //  Next state:  tree with one son.
    //
    //  (1)
    //   |
    //  (2)
    //
    tTree.setRoot (1);
    qtSon2Tree->setRoot (2);
    tTree.insert (qtSon2Tree);
    TEST_NUMBERS (1, tTree.getRoot());
    TEST_NUMBERS (2, tTree.size());
    TEST_NUMBERS (1, qtSon2Tree->size());
    TEST_NUMBERS (1, qtSon2Tree->height());

    //
    //  Next state:  tree with three sons.
    //
    //      (1)
    //       |
    //   +---+---+
    //   |   |   |
    //  (2) (3) (4)
    //
    tTree.insert (qtSon3Tree);
    tTree.insert (qtSon4Tree);
    TEST_NUMBERS (4, tTree.size());
    TEST_NUMBERS (2, tTree.height());
    TEST_NUMBERS (1, qtSon2Tree->size());
    TEST_NUMBERS (1, qtSon2Tree->height());

    //
    //  Next state:  tree with three sons and one grandson.
    //
    //      (1)
    //       |
    //   +---+---+
    //   |   |   |
    //  (2) (3) (4)
    //   |
    //  (5)
    //
    qtSon2Tree->insert (qtGrandSon5Tree);
    TEST_NUMBERS (5, tTree.size());
    TEST_NUMBERS (3, tTree.height());
    TEST_NUMBERS (2, qtSon2Tree->size());
    TEST_NUMBERS (2, qtSon2Tree->height());
    TEST_NUMBERS (1, qtGrandSon5Tree->size());
    TEST_NUMBERS (1, qtGrandSon5Tree->height());

    //
    //  Checks node values.
    //
    //      (1)
    //       |
    //   +---+---+
    //   |   |   |
    //  (2) (3) (4)
    //   |
    //  (5)
    //
    tIterator = tTree.begin();
    TEST_NUMBERS (1,    *(tIterator++));
    TEST_NUMBERS (2,    *(tIterator++));
    TEST_NUMBERS (5,    *(tIterator++));
    TEST_NUMBERS (3,    *(tIterator++));
    TEST_NUMBERS (4,    *(tIterator++));
    TEST_NUMBERS (true, ( tIterator == tTree.end() ));

    //
    //  Checks node values.
    //
    //      (1)
    //       |
    //   +---+---+
    //   |   |   |
    //  (2) (3) (4)
    //   |
    //  (5)
    //
    tIterator     = tTree.begin();
    tSideIterator = ++tTree.begin();
    TEST_NUMBERS (1,    *(tIterator++));
    TEST_NUMBERS (2,    *(tSideIterator++));
    TEST_NUMBERS (3,    *(tSideIterator++));
    TEST_NUMBERS (4,    *(tSideIterator++));
    TEST_NUMBERS (2,    *(tIterator++));
    TEST_NUMBERS (5,    *(tIterator++));
    TEST_NUMBERS (3,    *(tIterator++));
    TEST_NUMBERS (true, ( tTree.begin()      != tTree.end() ));
    TEST_NUMBERS (true, ( tTree.beginChild() != tTree.endChild() ));
    TEST_NUMBERS (true, ( tTree.endChild()   == tTree.end() ));
    TEST_NUMBERS (true, ( tSideIterator      == tTree.end() ));
    TEST_NUMBERS (true, ( tSideIterator      != tTree.begin() ));

    //
    //  Tests copy constructor and assign operator.
    //
    {
      TIntTree   tTreeCopy (tTree);
      
      tIterator = tTreeCopy.begin();
      TEST_NUMBERS (1,    *(tIterator++));
      TEST_NUMBERS (2,    *(tIterator++));
      TEST_NUMBERS (5,    *(tIterator++));
      TEST_NUMBERS (3,    *(tIterator++));
      TEST_NUMBERS (4,    *(tIterator++));
      TEST_NUMBERS (true, ( tIterator == tTreeCopy.end() ));

      tTreeCopy = tTree;
      tIterator = tTreeCopy.begin();
      TEST_NUMBERS (1,    *(tIterator++));
      TEST_NUMBERS (2,    *(tIterator++));
      TEST_NUMBERS (5,    *(tIterator++));
      TEST_NUMBERS (3,    *(tIterator++));
      TEST_NUMBERS (4,    *(tIterator++));
      TEST_NUMBERS (true, ( tIterator == tTreeCopy.end() ));

      //
      //  Checks swap function.
      //
      tTreeCopy.clear();
      swap (tTree, tTreeCopy);
      TEST_NUMBERS (true,  tTree.empty());
      TEST_NUMBERS (false, tTreeCopy.empty());
      TEST_NUMBERS (0,     tTree.size());
      TEST_NUMBERS (5,     tTreeCopy.size());

      //
      //  Un-does swap.
      //
      swap (tTree, tTreeCopy);
      TEST_NUMBERS (false, tTree.empty());
      TEST_NUMBERS (true,  tTreeCopy.empty());
      TEST_NUMBERS (5,     tTree.size());
      TEST_NUMBERS (0,     tTreeCopy.size());
    }

    //
    //  Next state:  tree with three sons and one grandson.
    //
    //        (1)
    //         |
    //   +---+---+---+
    //   |   |   |   |
    //  (2) (3) (4) (6)
    //   |
    //  (5)
    //
    tTree.insert (6);
    tIterator = tTree.begin();
    TEST_NUMBERS (1,    *(tIterator++));
    TEST_NUMBERS (2,    *(tIterator++));
    TEST_NUMBERS (5,    *(tIterator++));
    TEST_NUMBERS (3,    *(tIterator++));
    TEST_NUMBERS (4,    *(tIterator++));
    TEST_NUMBERS (6,    *(tIterator++));
    TEST_NUMBERS (true, ( tIterator == tTree.end() ));

    //
    //  Checks node values using trees.
    //
    //        (1)
    //         |
    //   +---+---+---+
    //   |   |   |   |
    //  (2) (3) (4) (6)
    //   |
    //  (5)
    //
    TEST_NUMBERS (2, tTree.leftChild().getRoot());
    TEST_NUMBERS (3, tTree.leftChild().rightSibling().getRoot());
    TEST_NUMBERS (4, tTree.leftChild().rightSibling().rightSibling().getRoot());
    TEST_NUMBERS (5, tTree.leftChild().leftChild().getRoot());
    
    //
    //  Next state:  tree has only one node, but the pointers to the first child
    //               of the tree, are still alive and kicking.
    //
    tTree.erase (tTree.beginChild(), tTree.endChild());
    TEST_NUMBERS (1, tTree.size());
    TEST_NUMBERS (1, tTree.height());
    TEST_NUMBERS (2, qtSon2Tree->size());
    TEST_NUMBERS (2, qtSon2Tree->height());
    TEST_NUMBERS (1, qtGrandSon5Tree->size());
    TEST_NUMBERS (1, qtGrandSon5Tree->height());

    TEST_FUNCTION (_TestMemory<TIntTree>());
  }
  catch (const mpcl::TException& rktEXCEPTION)
  {
    std::cerr << rktEXCEPTION << std::endl;
    TEST_FAIL;
  }
  TEST_MEMORY_STATUS;
  TEST_RETURN_CODE;

}  // main()

---