eg_bbtree.h

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 
 * */
#ifndef __EG_BBTREE_H__
#define __EG_BBTREE_H__
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <float.h>
#include <math.h>
#include "eg_io.h"
#include "eg_config.h"
#include "eg_macros.h"
#include "eg_mempool.h"
#include "eg_compare.h"
/* ========================================================================= */
/** @defgroup EGbbtree EGbbtree
 *
 * Here we define an implementation of bimary balanced trees. In this
 * implementation the depth of the tree is bounded by 2*ceil(log_2(size)).
 * Note that this structure don't support repeated elements.
 *
 * -2005-09-09
 *          - Fix EGbbtreeAdd (By Faram Engineer)
 *          
 * -2005-09-08
 *          - Fix EGbbtreeClear (By Faram Engineer)
 *
 * -2004-08-16
 *          - First Implementation
 * */
/** @file
 * @ingroup EGbbtree */
/** @{ */
/* ========================================================================= */

/* ========================================================================= */
/** @brief Macro controling the debuging level for this structure. */
#define EG_BBTREE_DEBUGL 10

/* ========================================================================= */
/** @brief Balance Binary Tree Node structure.
 * @par Description:
 * This structure stores a pointer to satellite data, the depth of the node,
 * and pointers to it parent and sons.
 * */
typedef struct EGbbtreeNode_t
{
  struct EGbbtreeNode_t *parent;/**< Pointer to the parent of this node. */
  struct EGbbtreeNode_t *left;  /**< Pointer to the lefthand son. */
  struct EGbbtreeNode_t *right; /**< Pointer to the righthand son. */
  void *this;         /**< Pointer to the satelite data */
  unsigned depth;     /**< Note that the depth can be stored in a 
                        char, but since the size of the struct is anyway the 
                        complete word, we won't gain anything by doing this. 
                        This field store the longest distance to a leaf of the
                        related sub-tree. */
}
EGbbtreeNode_t;

/* ========================================================================= */
/** @brief Balance Binary Tree structure.
 * @par Description:
 * This structure has a pointer to a root node, the number of nodes in the tree
 * structure, and a pointer to a comparison function used to build the tree and
 * to add/remove elements from the tree, and a pointer to a memory manager from
 * where the local memory will be draw.
 * */
typedef struct EGbbtree_t
{
  EGbbtreeNode_t *root; /**< Pointer to the root of the tree. */
  EGmemPool_t *mem;     /**< Pointer to the local memory manager from where all
                          memory will be draw/freed. */
  EGcompare_f compare;  /**< Pointer to a comparison function, this function
                          will be used while building/modifying the tree */
  unsigned int size;    /**< Number of nodes in the tree. */
}
EGbbtree_t;

/* ========================================================================= */
/** @brief Defeault constructor.
 * @param mem EGmemPool_t* pointer to the memory pool from where we will
 * alocate all memory for internal structures.
 * @param compare EGcompare_f pointer to a comparison function, used to mantain
 * the tree structure.
 * @return EGbbtree_t pointer to an initialized bbtree.
 * @par Description:
 * Given a memory pool, and a comparison function, we create an empty (and
 * initialized) bbtree that works on elements comparable by the given function.
 * */
extern inline EGbbtree_t *EGnewBbtree (EGmemPool_t * mem,
                                       EGcompare_f compare)
{
  EGbbtree_t *tree = EGmemPoolSMalloc (mem, EGbbtree_t, 1U);
  MESSAGE (EG_BBTREE_DEBUGL, "entering");
  memset (tree, 0, sizeof (EGbbtree_t));
  tree->compare = compare;
  tree->mem = mem;
  MESSAGE (EG_BBTREE_DEBUGL, "done");
  return tree;
}

/* ========================================================================= */
/** @brief Defeault destructor.
 * @param tree EGbbtree_t pointer to the tree to be freed.
 * @par Description:
 * Given an initialized bbtree, this function free al internal data to the
 * local memory pool, but won't free the satelite data.
 * */
extern inline void EGfreeBbtree (void *tree)
{
  /* local variables */
  EGbbtreeNode_t *c_node;
  unsigned int stack_size = 4 * (1.5 + log2l ((long
                                               double) ((EGbbtree_t *) tree)->
                                              size + 1)),
    stack_pos = 0;
  EGbbtreeNode_t **stack = EGmemPoolSMalloc (((EGbbtree_t *) tree)->mem,
                                             EGbbtreeNode_t *, stack_size);

  MESSAGE (EG_BBTREE_DEBUGL, "entering");
  /* init the stack */
  stack[stack_pos] = ((EGbbtree_t *) tree)->root;
  if (((EGbbtree_t *) tree)->size)
    while (~stack_pos)
    {
      c_node = stack[stack_pos];
      stack_pos--;
      if (c_node->left)
        stack[++stack_pos] = c_node->left;
      if (c_node->right)
        stack[++stack_pos] = c_node->right;
      EGmemPoolSFree (c_node, EGbbtreeNode_t, 1, ((EGbbtree_t *) tree)->mem);
    }
  ((EGbbtree_t *) tree)->size = 0;

  /* ending */
  EGmemPoolSFree (stack, EGbbtreeNode_t *, stack_size,
                  ((EGbbtree_t *) tree)->mem);
  EGmemPoolSFree (tree, EGbbtree_t, 1, ((EGbbtree_t *) tree)->mem);
  MESSAGE (EG_BBTREE_DEBUGL, "done");
  return;
}

/* ========================================================================= */
/** @brief Given an initialized bbtree, left it at it initial state (just after
 * EGnewBbtree).
 * @param tree EGbbtree_t* pointer to the tree to be reseted to its initial
 * state.
 * @param dataFree free function for the satelite data.
 * @return zero on success, non-zero otherwise.
 * @par Description:
 * Set the structure to its initiial state, free all internal data to the
 * memory pool, and apply the given free function to the satelite data.
 * */
extern inline int EGbbtreeClear (EGbbtree_t * tree,
                                 EGfree_f dataFree)
{
  /* local variables */
  EGbbtreeNode_t *c_node;
  unsigned int stack_size = 4 * (1.5 + log2l ((long double) (tree->size + 1))),
    stack_pos = 0;
  EGbbtreeNode_t **stack = EGmemPoolSMalloc (tree->mem,
                                             EGbbtreeNode_t *, stack_size);

  MESSAGE (EG_BBTREE_DEBUGL, "entering");
  /* init the stack */
  stack[stack_pos] = tree->root;
  if (tree->size)
    while (~stack_pos)
    {
      c_node = stack[stack_pos];
      stack_pos--;
      if (c_node->left)
        stack[++stack_pos] = c_node->left;
      if (c_node->right)
        stack[++stack_pos] = c_node->right;
      if (dataFree)
        dataFree (c_node->this);
      EGmemPoolSFree (c_node, EGbbtreeNode_t, 1, tree->mem);
    }
  tree->size = 0;
  tree->root = 0;

  /* ending */
  EGmemPoolSFree (stack, EGbbtreeNode_t *, stack_size, tree->mem);
  MESSAGE (EG_BBTREE_DEBUGL, "done");
  return 0;
}

/* ========================================================================= */
/** @brief Given an initialized bbtree, left it at it initial state (just after
 * EGnewBbtree).
 * @param tree EGbbtree_t* pointer to the tree to be reseted to its initial
 * state.
 * @param dataFree free function for the satelite data.
 * @param datamem pointer to the memory pool used to allocate the satelite
 * data.
 * @return zero on success, non-zero otherwise.
 * @par Description:
 * Set the structure to its initiial state, free all internal data to the
 * memory pool, and apply the given free function to the satelite data.
 * */
extern inline int EGbbtreeClearMP (EGbbtree_t * tree,
                                   EGfreeMP_f dataFree,
                                   EGmemPool_t * datamem)
{
  /* local variables */
  EGbbtreeNode_t *c_node;
  unsigned int stack_size = 4 * (1.5 + log2l ((long double) (tree->size + 1))),
    stack_pos = 0;
  EGbbtreeNode_t **stack = EGmemPoolSMalloc (tree->mem,
                                             EGbbtreeNode_t *, stack_size);

  MESSAGE (EG_BBTREE_DEBUGL, "entering");
  /* init the stack */
  stack[stack_pos] = tree->root;
  if (tree->size)
    while (~stack_pos)
    {
      c_node = stack[stack_pos];
      stack_pos--;
      if (c_node->left)
        stack[++stack_pos] = c_node->left;
      if (c_node->right)
        stack[++stack_pos] = c_node->right;
      if (dataFree)
        dataFree (c_node->this, datamem);
      EGmemPoolSFree (c_node, EGbbtreeNode_t, 1, tree->mem);
    }
  tree->size = 0;
  tree->root = 0;

  /* ending */
  EGmemPoolSFree (stack, EGbbtreeNode_t *, stack_size, tree->mem);
  MESSAGE (EG_BBTREE_DEBUGL, "done");
  return 0;
}


/* ========================================================================= */
/** @brief Find an element in the tree.
 * @param tree EGbbtree_t* pointer to the tree where we will perform the
 * search.
 * @param elem void* pointer to the structure that we are looking for.
 * @return EGbbtreeNode_t pointer to the node in the tree containing the
 * element, if no such node exists, return NULL.
 * @par Description:
 * This function will searxh for the element in the tree that satisfy
 * compare(elem,found)==0. */
extern inline EGbbtreeNode_t *EGbbtreeFind (EGbbtree_t * tree,
                                            const void *elem)
{
  /* local variables */
  EGbbtreeNode_t *c_node = tree->root;
  int rval = 0;

  MESSAGE (EG_BBTREE_DEBUGL, "entering");
  /* now we iterate */
  while (c_node)
  {
    rval = tree->compare (elem, c_node->this);
    if (!rval)
      break;
    if (rval < 0)
      c_node = c_node->left;
    else
      c_node = c_node->right;
  }

  /* ending */
  MESSAGE (EG_BBTREE_DEBUGL, "done");
  return c_node;
}

/* ========================================================================= */
/** @brief Add a new element to the tree.
 * @param tree EGbbtree_t* pointer to the tree where we will add the new
 * element.
 * @param elem void* pointer to the element to be added to the tree.
 * @return EGbbtreeNode_t* pointer to the newly created node containing the
 * inserted element, if the eement already existed, we return NULL.
 * @par Description:
 * Add a new element (according to the comopare function) to the tree and
 * maintain the balance on the tree. If the element is repeated on the tree, it
 * will return NULL.
 * */
EGbbtreeNode_t *EGbbtreeAdd (EGbbtree_t * tree,
                             void *elem);

/* ========================================================================= */
/** @brief Delete an element from the tree.
 * @param tree EGbbtree_t* pointer to the tree from where we will eliminate the
 * given node.
 * @param node EGbbtreeNode_t* pointer to the node of the tree to be
 * eliminated.
 * @return zero on success, non-zero otherwise.
 * @par Description:
 * Given an initialized tree, and a ode pertaianing to it (the code won't check
 * this), it will eliminate the node form the tree. If an error occour, it will
 * return non-zero. Note that this funcion won't free the internal satelite
 * data of the given node, this should be done by the caller of the function
 * __BEFORE__ using this function.
 * */
int EGbbtreeRemove (EGbbtree_t * tree,
                    EGbbtreeNode_t * node);

/* ========================================================================= */
/** @brief, get the predecessor of the current node.
 * @param node EGbbtreeNode_t* pointer to the node to wich we are looking for
 * its predecessor.
 * @return EGbbtreeNode_t* pointer to the predecessor of the given node.
 * @par Description:
 * This function try to find the predecessor of the given node, if no such
 * node exists, return NULL.
 * */
extern inline EGbbtreeNode_t *EGbbtreePredecessor (EGbbtreeNode_t * node)
{
  /* local variables */
  EGbbtreeNode_t *c_node = node->left,
   *x_node = node;
  MESSAGE (EG_BBTREE_DEBUGL, "entering");
  if (c_node)
  {
    while (c_node->right)
      c_node = c_node->right;
    MESSAGE (EG_BBTREE_DEBUGL, "done");
    return c_node;
  }
  c_node = node->parent;
  while (c_node && x_node == c_node->left)
  {
    x_node = c_node;
    c_node = c_node->parent;
  }
  MESSAGE (EG_BBTREE_DEBUGL, "done");
  return c_node;
}

/* ========================================================================= */
/** @brief, get the successor of the current node.
 * @param node EGbbtreeNode_t* pointer to the node to wich we are looking for
 * its successor.
 * @return EGbbtreeNode_t* pointer to the successor of the given node.
 * @par Description:
 * This function try to find the successor of the given node, if no such node
 * exists, return NULL.
 * */
extern inline EGbbtreeNode_t *EGbbtreeSuccessor (EGbbtreeNode_t * node)
{
  /* local variables */
  EGbbtreeNode_t *c_node = node->right,
   *x_node = node;
  MESSAGE (EG_BBTREE_DEBUGL, "entering");
  if (c_node)
  {
    while (c_node->left)
      c_node = c_node->left;
    MESSAGE (EG_BBTREE_DEBUGL, "done");
    return c_node;
  }
  c_node = node->parent;
  while (c_node && x_node == c_node->right)
  {
    x_node = c_node;
    c_node = c_node->parent;
  }
  MESSAGE (EG_BBTREE_DEBUGL, "done");
  return c_node;
}


/* ========================================================================= */
/** @brief Return the minimum element in the tree.
 * @param tree EGbbtree_t* pointer to the tree to be displayed.
 * @return pointer to the treeNode pointing to the minimum element.
 * @par Description:
 * Given a tree, return the minimum eloement on the tree (pointer to the
 * connector).
 * */
extern inline EGbbtreeNode_t *EGbbtreeMin (EGbbtree_t * tree)
{
  EGbbtreeNode_t *root = tree->root;
  MESSAGE (EG_BBTREE_DEBUGL, "entering");
  while (root && root->left)
    root = root->left;
  MESSAGE (EG_BBTREE_DEBUGL, "done");
  return root;
}

/* ========================================================================= */
/** @brief Return the maximum element in the tree.
 * @param tree EGbbtree_t* pointer to the tree to be displayed.
 * @return pointer to the treeNode pointing to the maximum element.
 * @par Description:
 * Given a tree, return the maximum eloement on the tree (pointer to the
 * connector).
 * */
extern inline EGbbtreeNode_t *EGbbtreeMax (EGbbtree_t * tree)
{
  EGbbtreeNode_t *root = tree->root;
  MESSAGE (EG_BBTREE_DEBUGL, "entering");
  while (root && root->right)
    root = root->right;
  MESSAGE (EG_BBTREE_DEBUGL, "done");
  return root;
}

/* ========================================================================= */
/** @brief Display function for the tree.
 * @param tree EGbbtree_t* pointer to the tree to be displayed.
 * @param dataDisplay EGdisplay_f function that display the internal data (can
 * be NULL).
 * @param file FILE* pointer to the output stream.
 * @par Description: Display information of the tree, it's nodes, and the
 * internal data.
 * */
void EGbbtreeDisplay (EGbbtree_t * tree,
                      EGdisplay_f dataDisplay,
                      FILE * file);

/* ========================================================================= */
/** @} */
/* end of eg_bbtree.h */
#endif

---