tpl_splay_tree.H

/* Aleph-w

     / \  | | ___ _ __ | |__      __      __
    / _ \ | |/ _ \ '_ \| '_ \ ____\ \ /\ / / Data structures & Algorithms
   / ___ \| |  __/ |_) | | | |_____\ V  V /  version 1.9b
  /_/   \_\_|\___| .__/|_| |_|      \_/\_/   https://github.com/lrleon/Aleph-w
                 |_|         

  This file is part of Aleph-w library

  Copyright (c) 2002-2018 Leandro Rabindranath Leon & Alejandro Mujica

  This program is free software: you can redistribute it and/or modify
  it under the terms of the GNU General Public License as published by
  the Free Software Foundation, either version 3 of the License, or
  (at your option) any later version.

  This program 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. See the GNU
  General Public License for more details.

  You should have received a copy of the GNU General Public License
  along with this program. If not, see <https://www.gnu.org/licenses/>.
*/
/*
 *                          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:

  using Node = NodeType<Key>;

private:

  Node headnode; 
  Node * head, *& root;
  Compare cmp;

public:
  
  using key_type = Key;

  Compare & key_comp() noexcept { return cmp; }

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

  void splay(const Key & key) noexcept
  {
    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 = Compare()) noexcept
    : 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) noexcept
  {
    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) noexcept
  {
    assert(p != Node::NullPtr);
    assert(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 nullptr; // item is already in tree

    return __insert(p);
  }

  Node * insert_dup(Node * p) noexcept
  {
    assert(p != Node::NullPtr);
    assert(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) noexcept
  {
    if (root == Node::NullPtr)
      return nullptr;
      
    splay(key);

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

  Node * search_or_insert(Node * p) noexcept
  {
    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) noexcept
  {
    if (root == Node::NullPtr)
      return nullptr;

    splay(key);
      
    if (no_equals<Key, Compare>(KEY(root), key, cmp))
      return nullptr; /* 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() noexcept
  {
    return root;
  } 

  bool verify() const { return true; }

  struct Iterator : public BinNodeInfixIterator<Node>
  {
    Iterator(GenTdSplayTree & t) : BinNodeInfixIterator<Node>(t.getRoot()) {}
  };
};


    template <typename Key, class Compare = Aleph::less<Key>>
struct Splay_Tree : public GenTdSplayTree<BinNode, Key, Compare>
{
  using Base = GenTdSplayTree<BinNode, Key, Compare>;
  using Base::Base;
};


    template <typename Key, class Compare = Aleph::less<Key>>
struct Splay_Tree_Vtl : public GenTdSplayTree<BinNodeVtl, Key, Compare>
{
  using Base = GenTdSplayTree<BinNodeVtl, Key, Compare>;
  using Base::Base;
};


#endif /* TPL_SPLAY_TREE_H */