tpl_splay_treeRk.H

/*
 *                          Top Dowm Splay Trees
 */

/* This code is a c++ adaptation of Danny Sleator code. It can be loaded from 

   http://www.link.cs.cmu.edu/link/ftp-site/splaying/SplayTree.java

 */

# ifndef TPL_SPLAY_TREE_H
# define TPL_SPLAY_TREE_H

# include <tpl_binNodeXt.H>


using namespace Aleph;


    template <template <class> class NodeType, typename Key, class Compare>
class GenTdSplayTreeRk
{
public:

  typedef NodeType<Key> Node;

private:

  Node * root;
  Compare & cmp;

public:
  
  typedef Key key_type;

  Compare & key_comp() { return cmp; }

  Compare & get_compare() { return key_comp(); }

  void splay(const Key & key)
  {
    Node header(sentinelCtor);
    Node * head_ptr = &header;
    Node * l = head_ptr;
    Node * r = head_ptr;
    Node * t = root;

    while (true)
      if (cmp(key, KEY(t)))
        {     
          if (LLINK(t) == Node::NullPtr)
            break;

          if (cmp(key, KEY(LLINK(t))))
            {
              t = rotate_to_right_xt(t);
              if (LLINK(t) == Node::NullPtr)
                break;
            }

          LLINK(r) = t;
          r        = t;
          t        = LLINK(t);
        }
      else if (cmp(KEY(t), key))
        {   
          if (RLINK(t) == Node::NullPtr)
            break;

          if (cmp(KEY(RLINK(t)), key))
            {
              t = rotate_to_left_xt(t);
              if (RLINK(t) == Node::NullPtr)
                break;
            }

          RLINK(l) = t;
          l        = t;
          t        = RLINK(t);
        }
      else
        break;

    /* 
       t points to the splayed node
       l points to the predecessor of splayed node
       r points to the predecessor of splayed node
    */

    if (l != head_ptr)
      COUNT(l) += -COUNT(RLINK(l)) + COUNT(LLINK(t));
    if (r != head_ptr)
      COUNT(r) += -COUNT(LLINK(r)) + COUNT(RLINK(t));

    /* reassembling of sub trees in one with t as root */
    RLINK(l) = LLINK(t);
    LLINK(r) = RLINK(t);

    LLINK(t) = RLINK(head_ptr);
    RLINK(t) = LLINK(head_ptr);

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

    root = t;
  }

  GenTdSplayTreeRk(Compare & __cmp) 
      : root(Node::NullPtr), cmp(__cmp)
  {
    // Empty
  }

  GenTdSplayTreeRk(Compare && __cmp) 
    : root(Node::NullPtr), cmp(__cmp)
  {
    // Empty
  }

  void swap(GenTdSplayTreeRk & tree)
  {
    std::swap(root, tree.root);
    std::swap(cmp, tree.cmp);
  }

  virtual ~GenTdSplayTreeRk() { /* empty */ }

private:

  Node * __insert(Node * p)
  {
    COUNT(p) = COUNT(root) + 1;
    if (cmp(KEY(p), KEY(root)))
      { 
        COUNT(root) -= COUNT(LLINK(root));
        LLINK(p)     = LLINK(root);
        RLINK(p)     = root;
        LLINK(root)  = Node::NullPtr;
      }
    else 
      { 
        COUNT(root) -= COUNT(RLINK(root));
        RLINK(p)    = RLINK(root);
        LLINK(p)    = root;
        RLINK(root) = Node::NullPtr;
      }

    return root = p; // inserted node become root
  }

public:

  Node * insert(Node * p)
  {
    I(p != Node::NullPtr);
    I(COUNT(p) == 1);
    I(LLINK(p) == Node::NullPtr and RLINK(p) == Node::NullPtr);  

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

    const Key & key = KEY(p);

    splay(key);

    if (are_equals<Key, Compare>(KEY(root), key, cmp))
      return NULL; // item is already in tree

    return __insert(p);
  }

  Node * insert_dup(Node * p)
  {
    I(p != Node::NullPtr);
    I(LLINK(p) == Node::NullPtr and RLINK(p) == Node::NullPtr);  

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

    splay(KEY(p));

    return __insert(p);
  }

  Node * search(const Key & key)
  {
    if (root == Node::NullPtr)
      return NULL;
      
    splay(key);

    return are_equals<Key, Compare>(KEY(root), key) ? root : NULL;
  }

  Node * search_or_insert(Node * p)
  {
    if (root == Node::NullPtr)
      return root = p;

    const Key & key = KEY(p);
    splay(key);
    if (are_equals<Key, Compare>(key, KEY(root), cmp))
      return root;

    return __insert(p);
  }

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

    splay(key);
      
    if (no_equals<Key, Compare>(KEY(root), key, cmp))
      return NULL; /* key not found */

    Node * ret_val = root; /* store node to delete */

    if (LLINK(root) == Node::NullPtr)
      root = RLINK(root);
    else
      {
        Node * p = RLINK(root);
        root = LLINK(root);
        splay(key);
        RLINK(root) = p;
      }

    ret_val->reset();

    return ret_val;
  }

  Node *& getRoot()
  {
    return root;
  } 

  bool verify() const { return check_rank_tree(root); }

  size_t size() const 
  {
    return COUNT(root);
  }

  bool is_empty() const 
  {
    return root == Node::NullPtr; 
  }

  std::pair<int, Node*> position (const Key & key)
  {
    std::pair<int, Node*> ret_val;

    splay(key);

    if (are_equals<Key, Compare>(key, KEY(root), cmp))
      {
        ret_val.first = COUNT(LLINK(root));
        ret_val.second = root;
      }
    else
      ret_val.first = -1;

    return ret_val;
  }

  std::pair<int, Node*> find_position (const Key & key)
  {
    std::pair<int, Node*> r(-2, NULL);

    r.first = COUNT(Splay(key));
    r.second = root;

    return r;
  }

  Node * select (const size_t & i)
  {
    return Aleph::select(root, i); 
  }
};


    template <typename Key, class Compare = Aleph::less<Key>>
class Splay_Tree_Rk : public GenTdSplayTreeRk<BinNodeXt, Key, Compare>
{
public:

  Splay_Tree_Rk(Compare && cmp = Compare()) 
    : GenTdSplayTreeRk<BinNodeXt, Key, Compare> (std::move(cmp))
  {
    // empty 
  }

 Splay_Tree_Rk(Compare & cmp) 
    : GenTdSplayTreeRk<BinNodeXt, Key, Compare> (cmp)
  {
    // empty 
  }
};


    template <typename Key, class Compare = Aleph::less<Key>>
class Splay_Tree_Rk_Vtl : public GenTdSplayTreeRk<BinNodeXtVtl, Key, Compare>
{
public:

  Splay_Tree_Rk_Vtl(Compare && cmp = Compare()) 
    : GenTdSplayTreeRk<BinNodeXtVtl, Key, Compare> (std::move(cmp))
  {
    // empty 
  }

 Splay_Tree_Rk_Vtl(Compare & cmp) 
    : GenTdSplayTreeRk<BinNodeXtVtl, Key, Compare> (cmp)
  {
    // empty 
  }
};


#endif /* TPL_SPLAY_TREE_H */