testBinNodeUtils.C

Go to the documentation of this file.

 
/* Aleph-w
 
     / \  | | ___ _ __ | |__      __      __
    / _ \ | |/ _ \ '_ \| '_ \ ____\ \ /\ / / Data structures & Algorithms
   / ___ \| |  __/ |_) | | | |_____\ V  V /  version 1.9c
  /_/   \_\_|\___| .__/|_| |_|      \_/\_/   https://github.com/lrleon/Aleph-w
                 |_|         
 
  This file is part of Aleph-w library
 
  Copyright (c) 2002-2018 Leandro Rabindranath Leon 
 
  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 3 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, see <https://www.gnu.org/licenses/>.
*/
# include <cstdlib>
# include <ctime>
# include <iostream>
# include <string>
# include <tpl_dynArray.H>
# include <tpl_binTree.H>
# include <tpl_binNodeUtils.H>
 
 
# include <cassert>
using namespace std;
# include <cassert>
using namespace Aleph;
 
 
static void printNode(BinTree<int>::Node* node, int, int)
{
  cout << node->get_key() << " ";
}
 
static void print_node(BinTree<int>::Node* node, int, int)
{
  cout << node->get_key() << " ";
}
 
static void print_node(BinTree<int>::Node* node, int, bool)
{
  cout << node->get_key() << " ";
}
 
 
DynArray<int> preorder;
 
static void fill_preorder(BinTree<int>::Node* node, int, int pos)
{
  preorder[pos] = node->get_key();
}
 
 
DynArray<int> inorder;
 
static void fill_inorder(BinTree<int>::Node* node, int, int pos)
{
  inorder[pos] = node->get_key();
}
 
 
DynArray<int> postorder;
 
static void fill_postorder(BinTree<int>::Node* node, int, int pos)
{
  postorder[pos] = node->get_key();
}
 
 
struct Clave
{
  int operator () (BinNode<int> * p) const
  {
    return p->get_key();
  }
};
 
 
struct Cargar_Clave
{
  void operator () (BinNode<int> * p, istream & input) const
  {
    input >> p->get_key();
  }
};
 
 
int main(int argc, char *argv[])
{
  int n = 1000;
  unsigned int t = std::time(0);
  int value;
 
  try 
    {
      if (argc > 1)
  n = std::stoi(argv[1]);
 
      if (argc > 2)
  t = std::stoi(argv[2]);
    }
  catch (...)
    {
      // ignore
    }
 
  if (n <= 0)
    {
      cout << "n must be positive" << endl;
      return 1;
    }
 
  srand(t);
 
  cout << "testBinNodeUtils " << n << " " << t << endl;
 
  BinTree<int> tree;
  BinTree<int>::Node *node;
  int i;
 
  int insCount = 0, delCount = 0;
 
  for (i = 0; i < n; i++)
    {
      value = 1+(int) (n*100.0*rand()/(RAND_MAX+1.0));
      node = tree.search(value);
      if (node == NULL)
  {
    cout << value << " ";
    insCount++;
    node = new BinTree<int>::Node (value);
    tree.insert(node);
  }
    }
 
  cout << endl << insCount << " Items inserted" << endl;
 
  /* Fills the prefix array */
  cout << "Prefix :";
  int n_preorder = preOrderRec(tree.getRoot(), fill_preorder);
  preOrderRec(tree.getRoot(), printNode);
  cout << endl;
 
  BinNode<int> * tree_copy = 
    preorder_to_bst<BinNode<int> >(preorder, 0, preorder.size() - 1);
 
  assert(areEquivalents(tree.getRoot(), tree_copy));
 
  destroyRec(tree_copy);
 
  /* Fills the infix array */
  inOrderRec(tree.getRoot(), fill_inorder);
  cout << "Infix: ";
  int n_inorder = inOrderRec(tree.getRoot(), print_node);
  cout << endl;
 
  /* Fills the suffix array */
  cout << "Suffix: ";
  postOrderRec(tree.getRoot(), fill_postorder);
  int n_postorder = postOrderRec(tree.getRoot(), print_node);
  cout << endl;
 
  assert(n_preorder == insCount);
  assert(n_inorder == insCount);
  assert(n_postorder == insCount);
 
  try /* Copy binary tree */
    {
      BinNode<int> * aux = copyRec(tree.getRoot());
 
      assert( areEquivalents(tree.getRoot(), aux) );
  
      destroyRec(aux);
    }
  catch (exception & e) { cout << e.what() << endl; }
  catch (...) { cout << "Unknown exception" << endl; }
 
  cout << "Level traverse" << endl;
  level_traverse(tree.getRoot(), [] (BinNode<int> * p)
     {
       cout << p->get_key() << " ";
       return true;
     });
  cout << endl << endl;
 
  /* build a tree from prefix and infix traverses */
  BinNode<int> * new_root = build_tree<BinNode, int>
    (preorder, 0, n_preorder - 1, inorder, 0, n_inorder - 1); 
 
  assert(areEquivalents(new_root, tree.getRoot()));
 
  BinNode<int> * n_root = build_postorder<BinNode, int>
    (postorder, 0, n_postorder - 1, inorder, 0, n_inorder - 1); 
 
  assert(areEquivalents(n_root, tree.getRoot()));
 
  /* Randomly remove items */
  for (i = 0; i < n; i++)
    {
      value = 1+(int) (n*100.0*rand()/(RAND_MAX+1.0));
      node = tree.remove(value);
      if (node not_eq NULL)
  {
    delCount++;
    delete node;
  }
    }
    
  cout << delCount << " Items removed" << endl;
 
  /* Free memory of the original tree */
  try { destroyRec(tree.getRoot()); }
  catch (exception & e) { cout << e.what() << endl; }
  catch (...) { cout << "Unknown exception" << endl; }
 
  BinNode<int> * t1_rec = NULL, * t2_rec = NULL;
 
  /* Search for a number not in the tree for partitioning */
  while (true)
    {
      value = 1+(int) (n*100.0*rand()/(RAND_MAX+1.0));
      if (searchInBinTree(new_root, value) == NULL)
  break;
    }
 
  cout << "Tree ";
  inOrderRec(new_root, print_node); 
  cout << endl
       << "will be recursively partitioned according to key " << value << endl;
 
  /* recursively partition */
  split_key_rec(new_root, value, t1_rec, t2_rec); new_root = NULL;
 
  BinNode<int> * t1_it = NULL, * t2_it = NULL;
 
  inOrderRec(t1_rec, print_node); 
  cout << "|" << value << "| ";
  inOrderRec(t2_rec, print_node); 
  cout << endl << endl;
 
  /* build a tree from prefix and infix traverses */
  new_root = build_tree<BinNode, int>
    (preorder, 0, n_preorder - 1, inorder, 0, n_inorder - 1); 
 
  cout << "Tree ";
  inOrderRec(new_root, print_node); 
  cout << endl
       << "will be iteratively partitioned according to key " << value << endl;
 
  /* recursively partition */
  split_key(new_root, value, t1_it, t2_it);
 
  inOrderRec(t1_it, print_node); 
  cout << "|" << value << "| ";
  inOrderRec(t2_it, print_node); 
  cout << endl << endl;
 
  if (not areEquivalents(t1_rec, t1_it))
    AH_ERROR("Left sides of partitions are not equal");
 
  if (not areEquivalents(t2_rec, t2_it))
    AH_ERROR("Right sides of partitions are not equal");
 
  cout << 
    "Recursive partition result is identical to iterative partition" 
       << endl;
 
  if (t1_rec not_eq NULL)
    destroyRec(t1_rec);
  if (t2_rec not_eq NULL)
    destroyRec(t2_rec);
 
  if (t1_it not_eq NULL)
    destroyRec(t1_it);
  if (t2_it not_eq NULL)
    destroyRec(t2_it);
 
  {
    BinNode<int> * t_rot = NULL;
    DynArray<int> values(n);
    cout << "Recursive insertion of " << n << " nodes at root ..." << endl;
 
    for (i = 0; i < n; i++)
      {
  values[i] = 1+(int) (n*100.0*rand()/(RAND_MAX+1.0));
  node = searchInBinTree(t_rot, values[i]);
  if (node == NULL)
    {
      cout << values[i] << " ";
      node = new BinNode<int> (values[i]);
      t_rot = insert_root(t_rot, node);
    }
      }
 
    assert(check_bst(t_rot));
 
    cout << endl << "Finished" << endl;
 
    BinNode<int> * t_it = NULL;
    cout << "Iterative insertion of " << n << " nodes at root ..." << endl;
 
    for (i = 0; i < n; i++)
      {
  node = searchInBinTree(t_it, values[i]);
  if (node == NULL)
    {
      cout << values[i] << " ";
      node = new BinNode<int> (values[i]);
      t_it = insert_root(t_it, node);
    }
      }
 
    assert(check_bst(t_it));
 
    cout << endl << "Finished" << endl;
 
    cout << "Comparing recursive result with iterative ... " << endl;
    if (areEquivalents(t_rot, t_it))
      cout << "Resulting trees are equal" << endl;
    else
      cout << "Resulting trees are different" << endl;
 
    {
      ofstream out("bintree.tree");
      save_tree(t_it, out);
    }
 
    ifstream input("bintree.tree");
    BinNode<int> * t_load = load_tree<BinNode<int>>(input);
 
    cout << "Comparing loaded tree with iterative ... " << endl;
    if (areEquivalents(t_load, t_it))
      cout << "Resulting trees are equal" << endl;
    else
      cout << "Resulting trees are different" << endl;
    
    destroyRec(t_rot);
    destroyRec(t_it);
  }
}