tpl_tree_node.H

# ifndef TPL_TREE_H
# define TPL_TREE_H

# include <stdexcept>
# include <dlink.H>
# include <ahFunction.H>
# include <htlist.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())
# define IS_UNIQUE_SIBLING(p) (RSIBLING(p) == (p))

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) {}
  };

  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(bool value) { flags.is_root = value; }

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

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

  void set_is_rightmost(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)) // baje hasta 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());

    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);
      }
    else
      {
        I(this->is_rightmost());
        p->set_is_rightmost(true);
      }

    this->set_is_rightmost(false);
    this->sibling.insert(SIBLING_LIST(p));
  }

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

    if (this->is_root())
      throw std::domain_error("Cannot insert sibling of a root");

    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);
    p->set_is_rightmost(false);

    Tree_Node * old_prev_node = this->get_left_sibling();
    if (old_prev_node != NULL) 
      {
        I(not this->is_leftmost());
        p->set_is_leftmost(false);
      }
    else 
      { // this es más a la izq ==> p debe a ser primogénito
        I(this->is_leftmost());

        Tree_Node * parent = this->get_parent();

        ID(Tree_Node * left_child = this->get_left_child());
        I(parent != NULL or left_child != NULL);

        // Busca la raíz del árbol. Para ello buscamnos la hoja de this
        Tree_Node * leaf = this;
        while (not leaf->is_leaf())
          {
            leaf = leaf->get_left_child();
            I(leaf != NULL);
          }
        
        Tree_Node * root = leaf->lower_link();
        I(root != NULL);

        Dlink tree = CHILD_LIST(root)->cut_list(CHILD_LIST(this));
        tree.del();
        CHILD_LIST(parent)->insert(CHILD_LIST(p));
        p->set_is_leftmost(true);

        I(p->get_parent() == parent);
      }

    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 = this->lower_link();
        Tree_Node * leaf = old_left_child;
        while (not leaf->is_leaf())
          leaf = leaf->get_left_child();

        Tree_Node * root = leaf->lower_link();
        Dlink subtree = CHILD_LIST(root)->cut_list(CHILD_LIST(old_left_child));
        subtree.del();
        CHILD_LIST(this)->insert(CHILD_LIST(p));
        SIBLING_LIST(old_left_child)->append(SIBLING_LIST(p));
        old_left_child->set_is_leftmost(false);
        p->set_is_rightmost(false);
        I(p->get_right_sibling() == old_left_child);
        I(old_left_child->get_left_sibling() == p);
      }
    I(p->is_leftmost());
  }

  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 <typename Operation>
  void for_each_child(Operation & op)
  {
    for (Tree_Node * child = get_left_child(); child != NULL; 
         child = child->get_right_sibling())
      op(child);
  }

  template <typename Operation>
  void for_each_child(Operation && op = Operation())
  {
    for_each_child<Operation>(op);
  }

  template <typename Operation>
  void for_each_child(Operation & op) const
  {
    return const_cast<Tree_Node*>(this)->for_each_child(op);
  }

  template <typename Operation>
  void for_each_child(Operation && op = Operation()) const
  {
    return const_cast<Tree_Node*>(this)->for_each_child(op);
  }

  template <template <typename> class Container = DynList>
  Container<Tree_Node*> children_nodes() const
  {
    Container<Tree_Node*> ret_val;
    this->for_each_child([&ret_val] (Tree_Node * p) { ret_val.append(p); });
    return ret_val;
  }

  template <template <typename> class Container = DynList>
  Container<T> children() const
  {
    Container<T> ret_val;
    this->for_each_child([&ret_val] (Tree_Node * p) 
                         {
                           ret_val.append(p->get_key());
                         });
    return ret_val;
  }
};

    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)
{
  if (not IS_UNIQUE_SIBLING(root))
    SIBLING_LIST(root)->del(); // no ==> sacarlo de lista hermanos

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

  if (root->is_leftmost()) // ¿sacar lista hijos?
    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");

  while (root != NULL) // recorre los árboles de izquierda a derecha
    {
      Node * to_delete = root;          // respalda raíz 
      root = root->get_right_sibling(); // avanza a siguiente árbol 
      SIBLING_LIST(to_delete)->del();   // elimine de lista árboles
      destroy_tree(to_delete);          // Borre el árbol
    }
}

    template <class Node>
size_t compute_height(Node * root) 
{
  size_t temp_h, max_h = 0;
  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); // 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 = Aleph::equal_to<typename Node::key_type> > 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");

  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, 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