tpl_splay_tree.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_binNode.H>
# include <tpl_binNodeUtils.H>

using namespace Aleph;


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

  typedef NodeType<Key> Node;

private:

  Node headnode; 
  Node * head, *& 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 headNode;
    Node * l = &headNode;
    Node * r = &headNode;
    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(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(t);
              if (RLINK(t) == Node::NullPtr)
                break;
            }

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

    /* reassembling of sub trees in one with current as root */
    RLINK(l) = LLINK(t);
    LLINK(r) = RLINK(t);
    LLINK(t) = headNode.getR();
    RLINK(t) = headNode.getL();
                 
    root = t;
  }

  GenTdSplayTree(Compare & __cmp) 
    : head(&headnode), root(headnode.getR()), cmp(__cmp)
  {
    // Empty
  }

  GenTdSplayTree(Compare && __cmp) 
    : head(&headnode), root(headnode.getR()), cmp(__cmp)
  {
    // Empty
  }

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

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

private:

  Node * __insert(Node * p)
  {
    if (cmp(KEY(p), KEY(root)))
      { /* root is predecessor of p */
        LLINK(p)    = LLINK(root);
        RLINK(p)    = root;
        LLINK(root) = Node::NullPtr;
      }
    else 
      { /* root is successor of p */
        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(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 true; }
};


    template <typename Key, class Compare = Aleph::less<Key>>
class Splay_Tree : public GenTdSplayTree<BinNode, Key, Compare>
{
public:

  Splay_Tree(Compare && cmp = Compare()) 
    : GenTdSplayTree<BinNode, Key, Compare> (std::move(cmp))
  {
    // empty 
  }

 Splay_Tree(Compare & cmp) 
    : GenTdSplayTree<BinNode, Key, Compare> (cmp)
  {
    // empty 
  }
};


    template <typename Key, class Compare = Aleph::less<Key>>
class Splay_Tree_Vtl : public GenTdSplayTree<BinNodeVtl, Key, Compare>
{
public:

  Splay_Tree_Vtl(Compare && cmp = Compare()) 
    : GenTdSplayTree<BinNodeVtl, Key, Compare> (std::move(cmp))
  {
    // empty 
  }

 Splay_Tree_Vtl(Compare & cmp) 
    : GenTdSplayTree<BinNodeVtl, Key, Compare> (cmp)
  {
    // empty 
  }
};


#endif /* TPL_SPLAY_TREE_H */