tpl_binNodeXt.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_BINNODEXT_H
# define TPL_BINNODEXT_H

# include <tpl_binNode.H>
# include <tpl_binNodeUtils.H>

using namespace Aleph;

namespace Aleph {

class BinNodeXt_Data
{
  size_t count; // cardinalidad del árbol

public:

  BinNodeXt_Data() : count(1) { /* empty */ }
  BinNodeXt_Data(SentinelCtor) : count(0) { /* empty */ }
  size_t & getCount() { return count; }
  const size_t & size() const { return count; }
  void reset() { count = 1; }
};

DECLARE_BINNODE_SENTINEL(BinNodeXt, 255, BinNodeXt_Data);

# define COUNT(p) ((p)->getCount())

    template <class Node> inline 
Node * select_rec(Node * r, const size_t & i) 

  throw(std::exception, std::out_of_range) 

{ 

  I(r != Node::NullPtr);
  I(COUNT(Node::NullPtr) == 0);

  if (i >= COUNT(r))
    throw std::out_of_range("infix position out of range");

  if (i == COUNT(LLINK(r)))
    return r;

  if (i < COUNT(LLINK(r)))
    return select_rec(static_cast<Node*>(LLINK(r)), i);

  return select_rec(static_cast<Node*>(RLINK(r)), i - COUNT(LLINK(r)) - 1);
}
    template <class Node> inline
Node * select(Node * r, const size_t & pos) 

  throw(std::exception, std::out_of_range)

{

  I(COUNT(Node::NullPtr) == 0);

  if (pos >= COUNT(r))
    throw std::out_of_range("infix position out of range");


  for (size_t i = pos; i != COUNT(LLINK(r)); /* nada */)

    {
      I(i < COUNT(r));

      if (i < COUNT(LLINK(r)))
        r = static_cast<Node*>(LLINK(r)); 
      else
        {
          i -= COUNT(LLINK(r)) + 1;
          r = static_cast<Node*>(RLINK(r));
        }

    }

  return r;
}
    template <class Node, class Compare> inline
size_t inorder_position(Node *                          r,
                        const typename Node::key_type & key, 
                        Node *&                         node)
{

  I(COUNT(Node::NullPtr) == 0);

  if (r == Node::NullPtr)
    throw std::domain_error("Key not found");


  if (Compare () (key, KEY(r))) 
    return inorder_position(static_cast<Node*>(LLINK(r)), key, node);
  else if (Compare () (KEY(r), key)) 
    return inorder_position(static_cast<Node*>(RLINK(r)), key, node) + 
      COUNT(LLINK(r)) + 1;
  else
    return COUNT(LLINK(r));
}
    template <class Node> inline
int inorder_position(Node *                          r, 
                     const typename Node::key_type & key, 
                     Node *&                         node)
{
  return 
    inorder_position<Node, Aleph::less<typename Node::key_type> >(r, key, node);
}
    template <class Node, class Compare> inline
Node * insert_by_key_xt(Node *& r, Node * p)
{

  I(COUNT(Node::NullPtr) == 0);

  if (r == Node::NullPtr)
    return r = p;

  Node * q;

  if (Compare () (KEY(p), KEY(r)))
    {
      q = insert_by_key_xt<Node, Compare>(static_cast<Node*&>(LLINK(r)), p);

      if (q != Node::NullPtr)
        ++COUNT(r); 
    }
  else if (Compare ()(KEY(r), KEY(p)))
    {
      q = insert_by_key_xt<Node, Compare>(static_cast<Node*&>(RLINK(r)), p);

      if (q != Node::NullPtr)
        ++COUNT(r); 
    }
  else
    return (Node*) Node::NullPtr; // clave duplicada

  return q;
}
    template <class Node> inline
Node * insert_by_key_xt(Node *& root, Node * p)
{
  return insert_by_key_xt<Node, Aleph::less<typename Node::key_type> >(root, p);
}
# define SPLIT split_key_rec_xt<Node, Compare>

    template <class Node, class Compare> inline
bool split_key_rec_xt(Node * root, const typename Node::key_type & key, 
                      Node *& l, Node *& r)
{
  if (root == Node::NullPtr)
    {
      l = r = Node::NullPtr;

      return true;
    }

  if (Compare() (key, KEY(root)))
    {
      if (not SPLIT(LLINK(root), key, l, LLINK(root)))
        return false;

      r = root;
      COUNT(r) -= COUNT(l);
    }
  else if (Compare() (KEY(root), key))
    {
      if (not SPLIT(RLINK(root), key, RLINK(root), r))
        return false;

      l = root;
      COUNT(l) -= COUNT(r);
    }
  else
    return false; // clave duplicada

  return true;
}
# undef SPLIT

    template <class Node> inline
bool split_key_rec_xt(Node * root, const typename Node::key_type & key, 
                      Node *& l, Node *& r)
{
  return 
    split_key_rec_xt<Node, Aleph::less<typename Node::key_type> >(root, key, 
                                                                  l, r);
}
    template <class Node, class Compare> inline
Node * insert_root_xt(Node *& root, Node * p)
{
  if (root == Node::NullPtr) 
    return p;

  if (not split_key_rec_xt<Node, Compare>(root, KEY(p), LLINK(p), RLINK(p)))
    return Node::NullPtr;

  COUNT(p) = COUNT(LLINK(p)) + COUNT(RLINK(p)) + 1;

  root = p;

  return p; 
}
    template <class Node> inline
void split_pos_rec(Node * r, const size_t & i, Node *& ts, Node *& tg)
{

  if (i > COUNT(r))
    throw std::out_of_range("infix position out of range");

  if (i == COUNT(r)) // ¿Es la última posición (que está vacía)?
    {
      ts = r;
      tg = Node::NullPtr;

      return;
    }

  if (i == COUNT(LLINK(r))) // ¿se alcanzó la posición de partición?
    {
      ts = LLINK(r);
      tg = r;
      LLINK(tg) = Node::NullPtr;
      COUNT(tg) -= COUNT(ts);

      return;
    }

  if (i < COUNT(LLINK(r)))
    {
      split_pos_rec(static_cast<Node*>(LLINK(r)), i, ts, 
                    static_cast<Node*&>(LLINK(r)));
      tg = r;
      COUNT(r) -= COUNT(ts);
    }
  else
    {
      split_pos_rec(static_cast<Node*>(RLINK(r)), i - (COUNT(LLINK(r)) + 1), 
                    static_cast<Node*&>(RLINK(r)), tg);
      ts = r;
      COUNT(r) -= COUNT(tg);
    }
}
    template <class Node>  inline
void insert_by_pos_xt(Node *& r, Node * p, const size_t & pos)
{

  I(COUNT(Node::NullPtr) == 0);

  split_pos_rec(r, pos, static_cast<Node*&>(LLINK(p)),
                static_cast<Node*&>(RLINK(p)));

  COUNT(p) = COUNT(LLINK(p)) + 1 + COUNT(RLINK(p));

  r = p;
}
    template <class Node> inline
Node * join_exclusive_xt(Node *& ts, Node *& tg)
{
  if (ts == Node::NullPtr)
    return tg;

  if (tg == Node::NullPtr)
    return ts;

  LLINK(tg) = join_exclusive_xt(RLINK(ts), LLINK(tg));
  RLINK(ts) = tg;

  COUNT(tg) = COUNT(LLINK(tg)) + 1 + COUNT(RLINK(tg)); // actualizar contadores
  COUNT(ts) = COUNT(LLINK(ts)) + 1 + COUNT(RLINK(ts));

  Node * ret_val = ts;

  ts = tg = Node::NullPtr; // deben quedar vacíos después del join

  return ret_val;
}  
# define REMOVE remove_by_key_xt<Node, Compare>

    template <class Node, class Compare> inline
Node * remove_by_key_xt(Node *& root, const typename Node::key_type & key)
{

  I(root != Node::NullPtr);

  if (root == Node::NullPtr)
    return (Node*) Node::NullPtr; // clave no encontrada

  Node * ret_val = Node::NullPtr; 

  if (Compare () (key, KEY(root)))
    {
      ret_val = REMOVE(static_cast<Node*&>(LLINK(root)), key);

      if (ret_val != Node::NullPtr) // ¿hubo eliminación?
        --COUNT(root); // Sí ==> actualizar contador
    
      return ret_val;
    }
  else if (Compare () (KEY(root), key))
    {
      ret_val = REMOVE(static_cast<Node*&>(RLINK(root)), key);

      if (ret_val != Node::NullPtr) // ¿hubo eliminación?
        --COUNT(root); // Sí ==> actualizar contador
    
      return ret_val;
    }

  ret_val = root; // clave encontrada ==> eliminar

  root = join_exclusive_xt(static_cast<Node*&>(LLINK(root)),
                           static_cast<Node*&>(RLINK(root)));

  ret_val->reset();


  return ret_val;
}
# undef REMOVE

    template <class Node> inline
Node * remove_by_key_xt(Node *& root, const typename Node::key_type & key)
{
  I(root != Node::NullPtr);

  return remove_by_key_xt<Node, Aleph::less<typename Node::key_type> >
    (root, key);
}
    template <class Node> inline
Node * remove_by_pos_xt(Node *& root, const size_t & pos)
{

  if (pos >= COUNT(root))
    throw std::out_of_range("infix position out of range");

  if (COUNT(LLINK(root)) == pos) // ¿posición encontrada?
    {     // Si ==> guarde nodo y realice join exclusivo
      Node * ret_val = root;

      root = join_exclusive_xt(static_cast<Node*&>(LLINK(root)), 
                               static_cast<Node*&>(RLINK(root)));

      ret_val->reset();

      return ret_val;
    }

  Node * ret_val; // guarda valor de retorno de llamada recursiva

  if (pos < COUNT(LLINK(root)))
    ret_val = remove_by_pos_xt(static_cast<Node*&>(LLINK(root)), pos);
  else
    ret_val = remove_by_pos_xt(static_cast<Node*&>(RLINK(root)), 
                               pos - (COUNT(LLINK(root)) + 1));

  if (ret_val != Node::NullPtr) // ¿hubo eliminación?
    --COUNT(root); // Si ==> el árbol con raíz root perdió un nodo

  return ret_val;
}  
    template <class Node> inline
bool check_rank_tree(Node * root)
{
  if (root == Node::NullPtr)
    return true;

  if (COUNT(LLINK(root)) + COUNT(RLINK(root)) + 1 != COUNT(root))
    return false;

  return check_rank_tree(LLINK(root)) and check_rank_tree(RLINK(root));
}
    template <class Node> inline
Node * rotate_to_right_xt(Node* p)
{

  I(p != Node::NullPtr);

  Node * q  = static_cast<Node*>(LLINK(p));
  LLINK(p) = RLINK(q);
  RLINK(q) = p;
  COUNT(p) -= 1 + COUNT(LLINK(q));
  COUNT(q) += 1 + COUNT(RLINK(p));
  return q;           
} 
    template <class Node> inline
Node * rotate_to_left_xt(Node* p)
{
  I(p != Node::NullPtr);

  Node * q  = static_cast<Node*>(RLINK(p));
  RLINK(p) = LLINK(q);
  LLINK(q) = p;

  COUNT(p) -= 1 + COUNT(RLINK(q));
  COUNT(q) += 1 + COUNT(LLINK(p));

  return q;                  
} 

} // end namespace Aleph

# endif // TPL_BINNODEXT_H

---