tpl_binTreeOps.H

# ifndef TPL_BINTREEOPS_H
# define TPL_BINTREEOPS_H

# include <tpl_binNodeUtils.H>
# include <tpl_binNodeXt.H>

namespace Aleph {

  template <class Node,
            class Cmp = Aleph::less<typename Node::key_type>
            >
class BinTree_Operation
{
protected:

  Cmp & cmp;

public:

  Cmp & key_comp() { return cmp; }

  Cmp & get_compare() { return cmp; }

  typedef typename Node::key_type Key;

  typedef typename Node::key_type key_type;

  BinTree_Operation(Cmp & __cmp) : cmp(__cmp) { /* empty */ }

  BinTree_Operation(Cmp && __cmp = Cmp()) : cmp(__cmp) { /* empty */ }

  Node * search(Node * root, const Key & key)
  {
    return searchInBinTree <Node, Cmp> (root, key, cmp);
  }

  Node * search_parent(Node * root, const Key & key, Node *& parent)
  {
    return Aleph::search_parent<Node, Cmp>(root, key, parent, cmp);
  }

  Node * search_rank_parent(Node * root, const Key & key)
  {
    return Aleph::search_rank_parent<Node, Cmp>(root, key, cmp);
  }

  Node * insert(Node *& root, Node * p)
  {
    if (root == Node::NullPtr) 
      return root = p;

    if (cmp(KEY(p), KEY(root)))        // ¿p < root?
      return insert((Node*&) LLINK(root), p);
    else if (cmp(KEY(root), KEY(p)))   // ¿p > root?
      return insert((Node*&) RLINK(root), p);

    return Node::NullPtr; // clave repetida ==> no hay inserción
  }

  Node * insert_dup(Node *& root, Node * p)
  {
    if (root == Node::NullPtr) 
      return root = p;

    if (cmp(KEY(p), KEY(root)))        // ¿p < root?
      return insert_dup((Node*&) LLINK(root), p);
  
    return insert_dup((Node*&) RLINK(root), p);
  }

  Node * search_or_insert(Node *& r, Node * p)
  {
    if (r == Node::NullPtr) 
      return r = p;

    if (cmp(KEY(p), KEY(r)))        // ¿p < root?
      return search_or_insert((Node*&) LLINK(r), p);
    else if (cmp (KEY(r), KEY(p)))   // ¿p > root?
      return search_or_insert((Node*&) RLINK(r), p);

    return r; 
  }

  bool split_key_rec(Node * root, const Key & key, Node *& ts, Node *& tg)
  {
    if (root == Node::NullPtr)
      {    // key no se encuentra en árbol ==> split tendrá éxito
        ts = tg = Node::NullPtr;

        return true;
      }

    if (cmp(key, KEY(root)) ) // ¿key < KEY(root)?
      if (split_key_rec((Node*&) LLINK(root), key, ts, (Node*&) LLINK(root)))
        {
          tg = root;

          return true;
        }
      else
        return false;

    if (cmp(KEY(root), key) ) // ¿key > KEY(root)?
      if (split_key_rec((Node*&) RLINK(root), key, (Node*&) RLINK(root), tg))
        {
          ts = root;

          return true;
        }
      else
        return false;

    return false; // clave existe en árbol ==> se deja intacto
  }

  void split_key_dup_rec(Node * root, const typename Node::key_type & key, 
                         Node *& ts, Node *& tg)
  {
    if (root == Node::NullPtr)
      {    // key no se encuentra en árbol ==> split tendrá éxito
        ts = tg = Node::NullPtr;

        return;
      }

    if (cmp(key, KEY(root))) // ¿key < KEY(root)?
      split_key_dup_rec((Node*&) LLINK(root), key, ts, (Node*&) LLINK(root));
    else if (cmp(KEY(root), key)) // ¿key > KEY(root)?
      split_key_dup_rec((Node*&) RLINK(root), key, (Node*&) RLINK(root), tg);
    else // key == KEY(root)
      split_key_dup_rec((Node*&) LLINK(root), key, ts, (Node*&) LLINK(root));
  }

  Node * remove(Node *& root, const Key & key)
  {
    if (root == Node::NullPtr) 
      return Node::NullPtr;

    if (cmp (key, KEY(root)))       // ¿key < KEY(root)?
      return remove((Node*&) LLINK(root), key);
    else if (cmp(KEY(root), key))  // ¿key > KEY(root)?
      return remove((Node*&) RLINK(root), key);

    Node * ret_val = root; // respaldar root que se va a borrar
    root = join_exclusive((Node*&) LLINK(root), (Node*&) RLINK(root));

    ret_val->reset();

    return ret_val;
  }

  Node * insert_root(Node *& root, Node * p)
  {
    Node * l = Node::NullPtr, * r = Node::NullPtr;

    if (not split_key_rec(root, KEY(p), l, r)) 
      return Node::NullPtr; 

    LLINK(p) = l;
    RLINK(p) = r;
    root = p;

    return root; 
  }

  Node * insert_dup_root(Node *& root, Node * p)
  {
    split_key_dup_rec(root, KEY(p), LLINK(p), RLINK(p));

    return root = p;
  }

  Node * join_preorder(Node * t1, Node * t2, Node *& dup)
  {
    if (t2 == Node::NullPtr) 
      return t1;

    Node * l = (Node*) LLINK(t2); // respaldos de ramas de t2
    Node * r = (Node*) RLINK(t2);

    if (insert(t1, t2) == Node::NullPtr)
      // inserción fallida ==> elemento duplicado ==> insertar en dup
      insert(dup, t2);

    join_preorder(t1, l, dup);
    join_preorder(t1, r, dup);

    return t1;
  }

  Node * join(Node * t1, Node * t2, Node *& dup)
  {
    if (t1 == Node::NullPtr) 
      return t2;

    if (t2 == Node::NullPtr) 
      return t1;

    Node * l = (Node*) LLINK(t1); // respaldos ramas de t1
    Node * r = (Node*) RLINK(t1);

    t1->reset();

      // mientras la clave raíz de t1 esté contenida en t2
    while (insert_root(t2, t1) == Node::NullPtr) 
      {     // sí ==> sáquelo de t1 e insértelo en dup
        Node * p = remove(t1, KEY(t1));

        I(p != Node::NullPtr);

        insert(dup, t1);
      }

    LLINK(t2) = join(l, (Node*) LLINK(t2), dup);
    RLINK(t2) = join(r, (Node*) RLINK(t2), dup);

    return t2;
  }

  void split_key(Node * root, const Key & key, Node *& l, Node *& r)
  {
    if (root == Node::NullPtr) 
      {
        l = r = (Node*) Node::NullPtr;

        return;
      }

    Node * current;
    Node ** current_parent = NULL;
    Node ** pending_child  = NULL;
    char current_is_right;

    if (cmp (key, KEY(root)))
      {
        r = root;
        pending_child    = &l;
        current_is_right = true;
      }
    else
      {
        l = root;
        pending_child    = &r;
        current_is_right = false;
      }

    current = root;

    while (current != Node::NullPtr) 
      {
        if (cmp (key, KEY(current)))
          { /* current must be in right side */
            if (not current_is_right)
              { 
                current_is_right = not current_is_right;
                *pending_child   = *current_parent; /* change of side */
                pending_child    = current_parent;
              }

            current_parent = static_cast<Node**>(&LLINK(current));
          }
        else
          { /* current must be in left side */
            if (current_is_right)
              { 
                current_is_right = not current_is_right;
                *pending_child   = *current_parent; /* change of side */
                pending_child    = current_parent;
              }
            current_parent = static_cast<Node**>(&RLINK(current));
          }

        current = *current_parent;
      }

    *pending_child = static_cast<Node*>(Node::NullPtr);
  }

  Node * insert_root_rec(Node * root, Node * p)
  {
    if (root == Node::NullPtr)
      return p; /* insertion in empty tree */

    if (cmp(KEY(p), KEY(root)))
      { /* insert in left subtree */
        Node *left_branch = insert_root_rec((Node*) LLINK(root), p);
        if (left_branch == Node::NullPtr)
          return (Node*) Node::NullPtr;

        LLINK(root) = left_branch;
        root        = rotate_to_right(root);
      }
    else if (cmp(KEY(root), KEY(p)))
      { /* insert in right subtree */
        Node *right_branch = insert_root_rec((Node*) RLINK(root), p);
        if (right_branch == Node::NullPtr)
          return (Node*) Node::NullPtr;

        RLINK(root) = right_branch;
        root        = rotate_to_left(root);
      }
    else
      return (Node*) Node::NullPtr; /* duplicated key */

    return root;
  }

  Node * search_or_insert_root_rec(Node * root, Node * p)
  {
    if (root == Node::NullPtr)
      return p; // insertion in empty tree

    if (cmp(KEY(p), KEY(root)))
      {     // insert in left subtree 
        Node * left_branch = search_or_insert_root_rec((Node*) LLINK(root), p);
        if (left_branch == p) // ¿hubo inserción?
          {
            LLINK(root) = left_branch;
            root        = rotate_to_right(root);

            return p;
          }

        return left_branch; // no la hubo
      }
    else if (cmp(KEY(root), KEY(p)))
      {     // insert in right subtree 
        Node * right_branch = search_or_insert_root_rec((Node*) RLINK(root), p);
        if (right_branch == p) // ¿hubo inserción?
          {
            RLINK(root) = right_branch;
            root        = rotate_to_left(root);

            return p;
          }

        return right_branch; // no la hubo
      }

    return root;
  }
};


    template <class Node,
              class Cmp = Aleph::less<typename Node::key_type>
              >
class BinTreeXt_Operation : public BinTree_Operation<Node, Cmp>
{
public:

  typedef typename Node::key_type Key;

  BinTreeXt_Operation(Cmp && cmp = Cmp()) 
    : BinTree_Operation<Node, Cmp>(std::move(cmp))
  {
    // empty
  }

  BinTreeXt_Operation(Cmp & cmp) 
    : BinTree_Operation<Node, Cmp>(cmp)
  {
    // empty
  }

  int inorder_position(Node * r, const Key & key, Node *& p)
  {
    I(COUNT(Node::NullPtr) == 0);

    if (r == Node::NullPtr)
      return -1;

    if (this->cmp(key, KEY(r)))
      return inorder_position((Node*) LLINK(r), key, p);
    else if (this->cmp(KEY(r), key)) 
      return inorder_position((Node*) RLINK(r), key, p) + COUNT(LLINK(r)) + 1;
    else
      {
        p = r;
        return COUNT(LLINK(r));
      }
  }

  int find_position(Node * r, const Key & key, Node *& p)
  {
    I(COUNT(Node::NullPtr) == 0);

    Node * parent = NULL;
    int pos = COUNT(LLINK(r));

    while (r != Node::NullPtr)
      if (this->cmp(key, KEY(r)))  
        {
          parent = r;
          r = (Node*) LLINK(r);
          pos -= (COUNT(RLINK(r)) + 1);
        }
      else if (this->cmp(KEY(r), key)) 
        {
          parent = r;
          r = (Node*) RLINK(r);
          pos += COUNT(LLINK(r)) + 1;
        }
      else
        {
          p = r;
          return pos;
        }

    p = parent;

    return pos;
  }

  bool split_key_rec(Node * root, const Key & key, Node *& l, Node *& r)
  {
    if (root == Node::NullPtr)
      {
        l = r = Node::NullPtr;

        return true;
      }

    if (this->cmp(key, KEY(root)))
      {
        if (not split_key_rec(LLINK(root), key, l, LLINK(root))) 
          return false;

        r = root;
        COUNT(r) -= COUNT(l);
      }
    else if (this->cmp(KEY(root), key))
      {
        if (not split_key_rec(RLINK(root), key, RLINK(root), r)) 
          return false;

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

    return true;
  }

  void split_key_dup_rec(Node * root, const Key & key, Node *& l, Node *& r)
  {
    if (root == Node::NullPtr)
      {
        l = r = Node::NullPtr;

        return;
      }

    if (this->cmp(key, KEY(root)))
      {
        split_key_dup_rec(LLINK(root), key, l, LLINK(root));
        r = root;
        COUNT(r) -= COUNT(l);
      }
    else if (this->cmp(KEY(root), key))
      {
        split_key_dup_rec(RLINK(root), key, RLINK(root), r);
        l = root;
        COUNT(l) -= COUNT(r);
      }
    else
      {
        split_key_dup_rec(LLINK(root), key, l, LLINK(root));
        r = root;
        COUNT(r) -= COUNT(l);
      }
  }

  Node * insert_root(Node *& root, Node * p)
  {
    if (root == Node::NullPtr) 
      return p;

    if (not split_key_rec(root, KEY(p), LLINK(p), RLINK(p)))
      return Node::NullPtr;

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

    return p; 
  }

  Node * insert_dup_root(Node *& root, Node * p)
  {
    if (root == Node::NullPtr) 
      return p;

    split_key_dup_rec(root, KEY(p), LLINK(p), RLINK(p));

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

    return root = p;
  }
};

} // end namespace Aleph

# endif // TPL_BINTREEOPS_H