tpl_tree_node.H

/*
  This file is part of Aleph system

  Copyright (c) 2002, 2003, 2004, 2005, 2006
  UNIVERSITY LOS ANDES (ULA) Merida - REPÚBLICA BOLIVARIANA DE VENEZUELA  

  - Center of Studies in Microelectronics & Distributed Systems (CEMISID) 
  - ULA Computer Science Department
  - FUNDACITE Mérida - Ministerio de Ciencia y Tecnología

  PERMISSION TO USE, COPY, MODIFY AND DISTRIBUTE THIS SOFTWARE AND ITS
  DOCUMENTATION IS HEREBY GRANTED, PROVIDED THAT BOTH THE COPYRIGHT
  NOTICE AND THIS PERMISSION NOTICE APPEAR IN ALL COPIES OF THE
  SOFTWARE, DERIVATIVE WORKS OR MODIFIED VERSIONS, AND ANY PORTIONS
  THEREOF, AND THAT BOTH NOTICES APPEAR IN SUPPORTING DOCUMENTATION.

  Aleph 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.

  UNIVERSIDAD DE LOS ANDES requests users of this software to return to 

  Leandro Leon
  CEMISID 
  Ed La Hechicera 
  3er piso, ala sur
  Facultad de Ingenieria 
  Universidad de Los Andes 
  Merida - REPÚBLICA BOLIVARIANA DE VENEZUELA    or

  lrleon@ula.ve

  any improvements or extensions that they make and grant Universidad 
  de Los Andes (ULA) the rights to redistribute these changes. 

  Aleph is (or was) granted by: 
  - Consejo de Desarrollo Cientifico, Humanistico, Tecnico de la ULA 
    (CDCHT)
  - Fundacite Mérida
*/


# ifndef TPL_TREE_H
# define TPL_TREE_H

# include <stdexcept>
# include <dlink.H>
# include <ahFunction.H>
# include <tpl_binNode.H>

# define ISROOT(p)      ((p)->is_root())
# define ISLEAF(p)      ((p)->is_leaf()) 
# define ISLEFTMOST(p)  ((p)->is_leftmost())
# define ISRIGHTMOST(p) ((p)->is_rightmost())

# define SIBLING_LIST(p) ((p)->get_sibling_list())
# define CHILD_LIST(p)   ((p)->get_child_list())
# define LCHILD(p)       ((p)->get_left_child())
# define RSIBLING(p)     ((p)->get_right_sibling())

namespace Aleph
{

    template <class T>
class Tree_Node 
{
  T data;
  Dlink child;
  Dlink sibling;
  struct Flags
  {
    unsigned int is_root          : 1;
    unsigned int is_leaf          : 1;
    unsigned int is_leftmost      : 1;
    unsigned int is_rightmost     : 1;

    Flags() : is_root(1), is_leaf(1), is_leftmost(1), is_rightmost(1)
    {
      /* empty */
    }
  };

  Flags flags;
  LINKNAME_TO_TYPE(Tree_Node, child);
  LINKNAME_TO_TYPE(Tree_Node, sibling);
  Tree_Node * upper_link() { return child_to_Tree_Node(child.get_prev()); }

  Tree_Node * lower_link() { return child_to_Tree_Node(child.get_next()); }

  Tree_Node * left_link() { return sibling_to_Tree_Node(sibling.get_prev()); }

  Tree_Node * right_link() { return sibling_to_Tree_Node(sibling.get_next()); }

public:

  T & get_key() { return get_data(); }

  T & get_data() { return data; }

  typedef T key_type;
  Dlink * get_child_list() { return &child; }

  Dlink * get_sibling_list() { return &sibling; }
  bool is_root() const { return flags.is_root; }

  bool is_leaf() const { return flags.is_leaf; }

  bool is_leftmost() const { return flags.is_leftmost; }

  bool is_rightmost() const { return flags.is_rightmost; }

  void set_is_root(const bool & value) { flags.is_root = value; }

  void set_is_leaf(const bool & value) { flags.is_leaf = value; }

  void set_is_leftmost(const bool & value) { flags.is_leftmost = value; }

  void set_is_rightmost(const bool & value) { flags.is_rightmost = value; }

  Tree_Node() { /* empty */ }

  Tree_Node(const T & __data) : data(__data) { /* empty */ }
  Tree_Node * get_left_sibling() 
  {
    if (is_leftmost())
      return NULL;

    return left_link();
  }

  Tree_Node * get_right_sibling()
  {
    if (is_rightmost())
      return NULL;
    
    return right_link();
  }
  Tree_Node * get_left_child() 
  {
    if (is_leaf())
      return NULL;

    return lower_link();
  }

  Tree_Node * get_right_child()
  {
    if (is_leaf())
      return NULL;

    Tree_Node * left_child = lower_link();


    I(ISLEFTMOST(left_child));

    return left_child->left_link();
  }
  Tree_Node * get_child(const int & i) 
  {
    Tree_Node * c = get_left_child();

    for (int j = 1; c != NULL and j < i; ++j)
      c = c->get_right_sibling();

    return c;
  }
  Tree_Node * get_parent()  
  {
    if (is_root())
      return NULL; 

    Tree_Node * p = this;
    while (not ISLEFTMOST(p)) // retroceda hasta ser el nodo más a la izquierda
      p = p->left_link();


    I(not ISROOT(p));
    I(not CHILD_LIST(p)->is_empty()); 

    return p->upper_link();
  }
  void insert_right_sibling(Tree_Node * p)
  {
    if (p == NULL)
      return;


    I(CHILD_LIST(p)->is_empty());
    I(SIBLING_LIST(p)->is_empty());
    I(p->is_rightmost() and p->is_leftmost() and p->is_root() and p->is_leaf());

    if (not is_root())
      p->set_is_root(false);

    p->set_is_leftmost(false);
    
    Tree_Node * old_next_node = get_right_sibling(); 

    if (old_next_node != NULL)

      {
        I(not this->is_rightmost());

      p->set_is_rightmost(false);

      }


    this->set_is_rightmost(false);
    this->sibling.insert(SIBLING_LIST(p));
  }
  void insert_left_sibling(Tree_Node * p)
  {
    if (p == NULL)
      return;


    I(CHILD_LIST(p)->is_empty());
    I(SIBLING_LIST(p)->is_empty());
    I(p->is_rightmost() and p->is_leftmost() and p->is_root() and p->is_leaf());

    if (not this->is_root()) 
      p->set_is_root(false);

    p->set_is_rightmost(false);

    Tree_Node * old_next_node = this->get_left_sibling();

    if (old_next_node != NULL) 

      {
        I(not this->is_leftmost());

      p->set_is_leftmost(false);

      }

    else if (not this->child.is_empty()) // verifique si p devendrá en más a
                                         // la izquierda 
      {     // this es el más a la izquierda ==> p pasará a ser el primogénito

        I(this->is_leftmost());

        Tree_Node * parent = this->get_parent();
        Tree_Node * left_child = this->get_left_child();


        I(parent != NULL or left_child != NULL);

        CHILD_LIST(this)->del(); // sacar this de lista de hijos

            // ahora meter a p en la lista de hijos
        if (parent != NULL)
          parent->insert(p);
        else
          left_child->append(p);  
      }
      
    this->set_is_leftmost(false);  
    this->sibling.append(SIBLING_LIST(p));
  }
  void insert_leftmost_child(Tree_Node * p)
  {
    if (p == NULL)
      return;


    I(CHILD_LIST(p)->is_empty());
    I(SIBLING_LIST(p)->is_empty());
    I(p->is_rightmost() and p->is_leftmost() and p->is_root() and p->is_leaf());

    p->set_is_root(false);

    if (this->is_leaf())
      {
        this->set_is_leaf(false);
        CHILD_LIST(this)->insert(CHILD_LIST(p));
      } 
    else
      {
        Tree_Node * old_left_child_node = this->lower_link();
          
        old_left_child_node->set_is_leftmost(false);
        p->set_is_rightmost(false);
        CHILD_LIST(old_left_child_node)->del();
        CHILD_LIST(this)->insert(CHILD_LIST(p));

        SIBLING_LIST(old_left_child_node)->append(SIBLING_LIST(p));
      }
  }

  void insert_rightmost_child(Tree_Node * p)
  {
    if (p == NULL)
      return;


    I(CHILD_LIST(p)->is_empty());
    I(SIBLING_LIST(p)->is_empty());
    I(p->is_rightmost() and p->is_leftmost() and p->is_root() and p->is_leaf());

    p->set_is_root(false);

    if (this->is_leaf())
      {
        this->set_is_leaf(false);
        CHILD_LIST(this)->insert(CHILD_LIST(p));
      } 
    else
      {
        Tree_Node * old_right_child_node = this->lower_link()->left_link();
          
        old_right_child_node->set_is_rightmost(false);
        p->set_is_leftmost(false);
          
        SIBLING_LIST(old_right_child_node)->insert(SIBLING_LIST(p));
      }
  }
  void insert_tree_to_right(Tree_Node * tree)
  {

    if (tree == NULL)
      return;

    if (not this->is_root()) 
      throw std::domain_error("\"this\" is not root");

    tree->set_is_leftmost(false);

    Tree_Node * old_next_tree = this->get_right_tree(); 
    if (old_next_tree != NULL) 

      {
        I(not this->is_rightmost());

        tree->set_is_rightmost(false);

      }


    this->set_is_rightmost(false);  
    SIBLING_LIST(this)->insert(SIBLING_LIST(tree));
  }
  Tree_Node * get_left_tree() 
  {
    if (is_leftmost())
      return NULL;


    I(not is_leftmost()); 

    return left_link();
  }

  Tree_Node * get_right_tree() 
  {
    if (is_rightmost())
      return NULL;


    I(not is_rightmost());

    return right_link();
  }
  Tree_Node * get_last_tree() 
  {

    if (not is_leftmost())
      throw 
        std::range_error("\"this\" is not the leftmost tree in the forest");

    return left_link();
  }
};

    template <class Node> static inline
void __tree_preorder_traversal(Node * root, const int & level, 
                               const int & child_index,
                               void (*visitFct)(Node *, int, int))
{
  (*visitFct)(root, level, child_index);

  Node * child = root->get_left_child(); 
  for (int i = 0; child != NULL; 
       i++, child = child->get_right_sibling())
    __tree_preorder_traversal(child, level + 1, i, visitFct);
}
    template <class Node> inline
void tree_preorder_traversal(Node * root, void (*visitFct)(Node *, int, int))
{

  if (not root->is_root())
    throw std::domain_error("root is not root");

  __tree_preorder_traversal(root, 0, 0, visitFct);
}

    template <class Node> inline
void forest_preorder_traversal(Node * root, 
                               void (*visitFct)(Node *, int, int))
{

  if (not root->is_root())
    throw std::domain_error("root is not root");

  for (/* nada */; root != NULL; root = root->get_right_tree())

    {
      I(root->is_root());

    __tree_preorder_traversal(root, 0, 0, visitFct);

    }

}
    template <class Node> static inline
void __tree_postorder_traversal(Node * node, const int & level, 
                                const int & child_index,
                                void (*visitFct)(Node *, int, int))
{
  Node * child = node->get_left_child();
  for (int i = 0; child not_eq NULL; i++, child = child->get_right_sibling())
    __tree_postorder_traversal(child, level + 1, i, visitFct);

  (*visitFct)(node, level, child_index);
}

    template <class Node> inline
void tree_postorder_traversal(Node * root, 
                              void (*visitFct)(Node *, int, int))
{
  __tree_postorder_traversal(root, 0, 0, visitFct);
}

    template <class Node> inline
void forest_postorder_traversal(Node * root, 
                                void (*visitFct)(Node *, int, int))
{

  if (not root->is_leftmost())
    throw std::domain_error("root is not the leftmost node of forest");

  if (not root->is_root())
    throw std::domain_error("root is not root");

  for (/* nada */; root not_eq NULL; root = root->get_right_sibling())

    {
      I(root->is_root());

    __tree_postorder_traversal(root, 0, 0, visitFct);

    }

}
    template <class Node> inline  
void destroy_tree(Node * root)
{
      // recorrer los subárboles de derecha a izquierda
  for (Node * p = root->get_right_child(); p != NULL; /* nada */)
    {
      Node * to_delete = p;      // respaldar subárbol a borrar p
      p = p->get_left_sibling(); // Avanzar p a hermano izquierdo
      SIBLING_LIST(to_delete)->del(); // eliminar to_delete de lista hermanos
      destroy_tree(to_delete);   // eliminar recursivamente árbol
    }

      // Si to_delete es el más a la izquierda ==> sacarlo de lista de hijos
  if (root->is_leftmost()) 
    CHILD_LIST(root)->del(); 

  delete root;
}

    template <class Node> inline 
void destroy_forest(Node * root)
{

  if (not root->is_leftmost())
    throw std::domain_error("root is not the leftmost tree of forest");

  if (not root->is_root())
    throw std::domain_error("root is not root");

      // recorre los árboles de izquierda a derecha
  while (root != NULL) 
    {
      Node * to_delete = root; // respalda raíz 

      root = root->get_right_sibling(); // avanza a siguiente árbol 

      SIBLING_LIST(to_delete)->del(); // elimine árbol de lista de árboles

      destroy_tree(to_delete); // Borre el árbol
    }
}
    template <class Node>
size_t compute_height(Node * root) 
{
  size_t max_h = 0;
  size_t temp_h;

  for (Node * aux = root->get_left_child(); aux != NULL; 
       aux = aux->get_right_sibling()) 
    if ((temp_h = compute_height(aux)) > max_h)
      max_h = temp_h;

  return max_h + 1;
}
    template <class Node> static inline
Node * __deway_search(Node *         node, 
                      int            path [], 
                      const int &    idx,
                      const size_t & size)
{
  if (node == NULL)
    return NULL;

  if (idx > size)
    throw std::out_of_range("index out of maximum range");


  if (path[idx] < 0) // verifique si se ha alcanzado el nodo
    return node; 

      // avance hasta el próximo hijo path[0]
  Node * child = node->get_left_child();
  for (int i = 0; i < path[idx] and child != NULL; ++i)
    child = child->get_right_sibling();

  return __deway_search(child, path, idx + 1, size); // siga en próximo nivel
}
    template <class Node> inline
Node * deway_search(Node * root, int path [], const size_t & size)
{
  for (int i = 0; root != NULL; i++, root = root->get_right_sibling())
    if (path[0] == i)
      return __deway_search(root, path, 1, size);

  return NULL;
}
    template <class Node, class Equal> inline static
Node * __search_deway(Node *                          root, 
                      const typename Node::key_type & key,
                      const size_t &                  current_level,
                      int                             deway [], 
                      const size_t &                  size, 
                      size_t &                        n);
    template <class Node, class Equal> inline
Node * search_deway(Node *                          root, 
                    const typename Node::key_type & key,
                    int                             deway [], 
                    const size_t &                  size, 
                    size_t &                        n)
{
  n = 1; // valor inicial de longitud de número de Deway

  if (size < n)
    throw std::overflow_error("there is no enough space for deway array");


      // recorrer los árboles de la arborescencia
  for (int i = 0; root != NULL; i++, root = root->get_right_sibling())
    {
      deway[0] = i;

      Node * result =
        __search_deway <Node, Equal> (root, key, 0, deway, size, n);

      if (result != NULL)
        return result;
    }

  return NULL;
}
    template <class Node> inline
Node * search_deway(Node *                          root, 
                    const typename Node::key_type & key,
                    int                             deway [], 
                    const size_t &                  size, 
                    size_t &                        n)
{
  return search_deway <Node, Aleph::equal_to<typename Node::key_type> >
    (root, key, deway, size, n) ; 
}
    template <class Node, class Equal> inline static
Node * __search_deway(Node *                          root, 
                      const typename Node::key_type & key,
                      const size_t &                  current_level,
                      int                             deway [], 
                      const size_t &                  size, 
                      size_t &                        n)
{

  if (current_level >= size) 
    throw std::overflow_error("there is no enough space for deway array");

  if (root == NULL)
    return NULL;

  if (Equal () (KEY(root), key))
    {
      n = current_level + 1; // longitud del arreglo deway

      return root;
    }

  Node * child = root->get_left_child();
  for (int i = 0; child != NULL; i++, child = child->get_right_sibling())
    {
      deway[current_level + 1] = i;

      Node * result = __search_deway <Node, Equal> 
        (child, key, current_level + 1, deway, size, n);

      if (result!= NULL)
        return result;
    }

  return NULL;
}
    template <class TNode, class BNode>
BNode * forest_to_bin(TNode * root)
{
  if (root == NULL)
    return BNode::NullPtr;
  
  BNode * result = new BNode (root->get_key());
  
  LLINK(result) = forest_to_bin<TNode, BNode>(root->get_left_child());
  RLINK(result) = forest_to_bin<TNode, BNode>(root->get_right_sibling());
  
  return result;
}
    template <class TNode, class BNode> inline static
void insert_child(BNode * lnode, TNode * tree_node)
{
  if (lnode == BNode::NullPtr)
    return;
  
  TNode * child = new TNode(KEY(lnode));
  
  tree_node->insert_leftmost_child(child);
}
    template <class TNode, class BNode> inline static
void insert_sibling(BNode * rnode, TNode * tree_node)
{
  if (rnode == BNode::NullPtr)
    return;
  
  TNode * sibling = new TNode(KEY(rnode));
  
  tree_node->insert_right_sibling(sibling);
}
    template <class TNode, class BNode> inline static
void bin_to_tree(BNode * broot, TNode * troot)
{
  if (broot == BNode::NullPtr)
    return;
  
  insert_child(LLINK(broot), troot);
  TNode * left_child =  troot->get_left_child();
  bin_to_tree(LLINK(broot), left_child);
  
  insert_sibling(RLINK(broot), troot);
  TNode * right_sibling = troot->get_right_sibling();
  bin_to_tree(RLINK(broot), right_sibling);
}
    template <class TNode, class BNode> inline 
TNode * bin_to_forest(BNode * broot) 
{
  if (broot == BNode::NullPtr)
    return NULL;
  
  TNode * troot = new TNode (KEY(broot));
  
  bin_to_tree(broot, troot);

  return troot;
}

} // fin namespace Aleph

# endif // TPL_TREE_H

---