eg_bbtree.ex.c

Go to the documentation of this file.

/* EGlib "Efficient General Library" provides some basic structures and
 * algorithms commons in many optimization algorithms.
 *
 * Copyright (C) 2005 Daniel Espinoza and Marcos Goycoolea.
 * 
 * This library is free software; you can redistribute it and/or modify it
 * under the terms of the GNU Lesser General Public License as published by the
 * Free Software Foundation; either version 2.1 of the License, or (at your
 * option) any later version.
 *
 * This library 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 Lesser General Public 
 * License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with this library; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA 
 * */
/** @file
 * @ingroup EGbbtree
 * */
/** @addtogroup EGbbtree */
/** @{ */
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>
#include <time.h>
#include <float.h>
#ifdef LINUX
#include <getopt.h>
#endif
#include "eg_mempool.h"
#include "eg_bbtree.h"
/* ========================================================================= */
/** @brief usage function, if we give the wrong number of parameters, we return
 * an error message and print a help.
 * @param program Name of the command from comand-line
 * */
static inline void usage (char const *const program)
{
  fprintf (stderr, "Usage: %s [options]\n", program);
  fprintf (stderr, "Options:\n");
  fprintf (stderr, "    -s   unsigned int, seed of the RNG\n");
  fprintf (stderr,
           "    -z   unsigned int, number of elements to generate in the tree\n");
  /* we allways exit with an error code */
  exit (1);
}

/* ========================================================================= */
/** @brief parse external arguments.
 * @param argc int, number of parameters to process.
 * @param argv char**, array of the parameters.
 * @param z unsigned int*, pointer to the number of elements in the tree.
 * @param s unsigned int*, pointer to the seed.
 * @return zero on success, non-zero otherwise */
static inline int parseargs (int argc,
                             char **argv,
                             unsigned int *s,
                             unsigned int *z)
{
  /* local variables */
  int c;
  /* set initial values */
  *z = 0;
  *s = 1;
  /* scan the input */
  while ((c = getopt (argc, argv, "s:z:")) != EOF)
  {
    switch (c)
    {
    case 's':
      *s = atoi (optarg);
      break;
    case 'z':
      *z = atoi (optarg);
      break;
    default:
      usage (argv[0]);
    }
  }
  if (*z < 1)
    usage (argv[0]);
  fprintf (stderr, "Running %s with options:\n", argv[0]);
  fprintf (stderr, " size         %7u\n", *z);
  fprintf (stderr, " seed         %7u\n", *s);
  return 0;
}

/* ========================================================================= */
/** @brief Tester program for the projection structure and functions
 * @param argc int number of comand line options
 * @param argv char** array of strings of length argc contaianing the command
 * line arguments.
 * @return zero on success, non-zero otherwise 
 * @par Description:
 * This function create a set of 'z' elements in a bbtree, and print the
 * resulting tree, perform some random operations.
 * */
int main (int argc,
          char **argv)
{
  /* local variables */
  EGmemPool_t *mem = EGnewMemPool (1024, EGmemPoolNewSize, 4096);
  EGbbtree_t *tree = EGnewBbtree (mem, EGptCompare);
  EGbbtreeNode_t *c_node;
  unsigned int n,
    z,
    s;
  int rval = 0;

  /* now process the input */
  parseargs (argc, argv, &s, &z);
  srandom (s);

  /* first create a random tree */
  for (n = 0; n < z; n++)
  {
    fprintf (stderr, "Adding %d to the tree...", n);
    c_node = EGbbtreeAdd (tree, (void *) n);
    if (c_node && c_node->this == (void *) n)
      fprintf (stderr, "done\r");
    else
    {
      fprintf (stderr, "Not found!\n");
      exit (1);
    }
    //EGbbtreeDisplay(tree,EGnullDisplay,stderr);
  }
  /* now we half depopulate the random tree */
  for (n = z / 2; n < z; n++)
  {
    fprintf (stderr, "Search %d in the tree...", n);
    c_node = EGbbtreeFind (tree, (void *) n);
    if (c_node && c_node->this == (void *) n)
      fprintf (stderr, "done\r");
    else
    {
      fprintf (stderr, "Not found!\n");
      exit (1);
    }
    fprintf (stderr, "Removing %d from the tree    \r", n);
    rval = EGbbtreeRemove (tree, c_node);
    CHECKRVAL (rval);
  }
  /* now we half populate the random tree */
  for (n = z / 2; n < z; n++)
  {
    fprintf (stderr, "Adding %d to the tree...", n);
    c_node = EGbbtreeAdd (tree, (void *) n);
    if (c_node && c_node->this == (void *) n)
      fprintf (stderr, "done\r");
    else
    {
      fprintf (stderr, "Not found!\n");
      exit (1);
    }
  }
  /* now we half depopulate the random tree */
  for (n = 0; n < z / 2; n++)
  {
    fprintf (stderr, "Search %d in the tree...", n);
    c_node = EGbbtreeFind (tree, (void *) n);
    if (c_node && c_node->this == (void *) n)
      fprintf (stderr, "done\r");
    else
    {
      fprintf (stderr, "Not found!\n");
      exit (1);
    }
    fprintf (stderr, "Removing %d from the tree    \r", n);
    rval = EGbbtreeRemove (tree, c_node);
    CHECKRVAL (rval);
  }
  /* now we half populate the random tree */
  for (n = 0; n < z / 2; n++)
  {
    fprintf (stderr, "Adding %d to the tree...", n);
    c_node = EGbbtreeAdd (tree, (void *) n);
    if (c_node && c_node->this == (void *) n)
      fprintf (stderr, "done\r");
    else
    {
      fprintf (stderr, "Not found!\n");
      exit (1);
    }
  }
  /* now we depopulate the random tree */
  for (n = 0; n < z; n++)
  {
    fprintf (stderr, "Search %d in the tree...", n);
    c_node = EGbbtreeFind (tree, (void *) n);
    if (c_node && c_node->this == (void *) n)
      fprintf (stderr, "done\r");
    else
    {
      fprintf (stderr, "Not found!\n");
      exit (1);
    }
    fprintf (stderr, "Removing %d from the tree    \r", n);
    rval = EGbbtreeRemove (tree, c_node);
    CHECKRVAL (rval);
  }
  /* re-create a random tree */
  for (n = 0; n < z; n++)
  {
    fprintf (stderr, "Adding %d to the tree...", n);
    c_node = EGbbtreeAdd (tree, (void *) n);
    if (c_node && c_node->this == (void *) n)
      fprintf (stderr, "done\r");
    else
    {
      fprintf (stderr, "Not found!\n");
      exit (1);
    }
    //EGbbtreeDisplay(tree,EGnullDisplay,stderr);
  }
  /* now we clear it */
  rval = EGbbtreeClear (tree, nullFree);
  CHECKRVAL (rval);

  /* now we free it */
  EGfreeBbtree (tree);
  EGfreeMemPool (mem);
  fprintf (stderr, "\n");

  /* now we create the objective function */
  return rval;
}

/* ========================================================================= */
/* @} */
/* end of eg_bbtree.c */

---