tpl_dynSetTree.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/>.
*/

# ifndef TPL_DYNSETTREE_H
# define TPL_DYNSETTREE_H

# include <typeinfo>
# include <ah-args-ctor.H>
# include <ahIterator.H>
# include <tpl_binNodeUtils.H>
# include <tpl_binNodeXt.H>
# include <tpl_binTree.H>
# include <tpl_treap.H>
# include <tpl_treapRk.H>
# include <tpl_avl.H>
# include <tpl_rand_tree.H>
# include <tpl_rb_tree.H>
//# include <tpl_tdRbTree.H>
# include <tpl_splay_tree.H>

using namespace Aleph;

namespace Aleph {

    template <typename Key,
              template <typename, class> class Tree = Avl_Tree,
              class Compare = Aleph::less<Key>>
class DynSetTree
      : public LocateFunctions<DynSetTree<Key, Tree, Compare>, Key>,
        public FunctionalMethods<DynSetTree<Key, Tree, Compare>, Key>,
        public GenericKeys<DynSetTree<Key, Tree, Compare>, Key>,
        public EqualToMethod<DynSetTree<Key, Tree, Compare>>,
        public StlAlephIterator<DynSetTree<Key, Tree, Compare>>
{
public:

  using Node = typename Tree<Key, Compare>::Node;

  using Tree_Type = Tree<Key, Compare>;

private:

  static const size_t dim = 13;

  mutable Tree<Key, Compare> tree;
  size_t num_nodes;

public:

  typedef DynSetTree Set_Type;

  typedef Key Item_Type;

  typedef Key Key_Type;

  void swap(DynSetTree & dset)
  {
    tree.swap(dset.tree);
    std::swap(num_nodes, dset.num_nodes);
  }

  DynSetTree(Compare cmp = Compare())
    : tree(cmp), num_nodes(0)
  {
    /* empty */
  }

  DynSetTree(const DynSetTree & srcTree)
    : tree(srcTree.tree.get_compare()), num_nodes(srcTree.num_nodes)
  {
    Node * srcRoot = srcTree.tree.getRoot();
    try
      {
        tree.getRoot() = copyRec(srcRoot);
      }
    catch (...)
      {
        num_nodes = 0;
        throw;
      }
  }

  Special_Ctors(DynSetTree, Key);

  DynSetTree(DynSetTree && srcTree) : num_nodes(0)
  {
    swap(srcTree);
  }

  void empty()
  {
    destroyRec(tree.getRoot());
    num_nodes = 0;
  }

  DynSetTree & operator = (const DynList<Key> & list)
  {
    return *this = DynSetTree(list);
  }

  DynSetTree & operator = (const DynSetTree & srcTree)
  {
    if (this == &srcTree)
      return *this;

    Node *src_root = (Node*) const_cast<DynSetTree&>(srcTree).tree.getRoot();

    empty();

    tree.getRoot() = copyRec(src_root);
    num_nodes       = srcTree.num_nodes;

    return *this;
  }

  DynSetTree & operator = (DynSetTree && srcTree)
   {
     swap(srcTree);
     return *this;
   }

  virtual ~DynSetTree()
  {
    empty();
  }

private:

  Key * __insert(Node * p)
  {
    if (tree.search_or_insert(p) != p)
      return nullptr;

    ++num_nodes;

    return &p->get_key();
  }

public:

  Key * insert(const Key & key)
  {
    return __insert(new Node(key));
  }

  Key * insert(Key && key)
  {
    return __insert(new Node(std::forward<Key>(key)));
  }

  Key * append(const Key & key)
  {
    return insert(key);
  }

  Key * append(Key && key)
  {
    return insert(std::forward<Key>(key));
  }

private:

  Key * __search_or_insert(Node * p)
  {
    Node * q = tree.search_or_insert(p);
    if (q != p)
      delete p;
    else
      ++num_nodes;

    return &q->get_key();
  }

  pair<Node*, bool> __contains_or_insert(Node * p)
  {
    Node * q = tree.search_or_insert(p);
    if (q != p)
      { // KEY(p) is already inside the tree
        delete p;
        return pair<Node*, bool>(q, true);
      }
    ++num_nodes;
    return pair<Node*, bool>(p, false);
  }

public:

  Key * search_or_insert(const Key & key)
  {
    return __search_or_insert(new Node(key));
  }

  Key * search_or_insert(Key && key)
  {
    return __search_or_insert(new Node(std::forward<Key>(key)));
  }

  /* Busca la clave <code>key</code> en el árbol binario de búsqueda y
     eventualmente lo inserta en caso de no encontrarse.

     <code>contains_or_insert(key)</code> busca en el árbol la clave
     <code>key</code>. Si la clave ya se encuentra, entonces se retorna
     true. De lo contrario la clave es insertada y se retorna false.

     @param[in] key clave a encontrar o a insertar
     @return a pair whose first field is a pointer to the found or
     inserted key and the second field is a boolean whose value is
     `false` if the key was inserted; `true` otherwise, that is if the
     key is already present in the tree.
   */
  pair<Key*, bool> contains_or_insert(const Key & key)
  {
    auto p = __contains_or_insert(new Node(key));
    return pair<Key*, bool>(&p.first->get_key(), p.second);
  }

  pair<Key*, bool> contains_or_insert(Key && key)
  {
    auto p = __contains_or_insert(new Node(std::forward<Key>(key)));
    return pair<Key*, bool>(&p.first->get_key(), p.second);
  }

private:

  Key * __insert_dup(Node * q)
  {
    Node * p = tree.insert_dup(q);
    ++num_nodes;
    return &p->get_key();
  }

public:

  Key * insert_dup(const Key & key)
  {
    return __insert_dup(new Node(key));
  }

  Key * insert_dup(Key && key)
  {
    return __insert_dup(new Node(std::forward<Key>(key)));
  }

  Key * put(const Key & key)
  {
    return insert(key);
  }

  Key * put(Key && key)
  {
    return insert(std::forward<Key>(key));
  }

  size_t remove(const Key & key)
  {
    Node * p = static_cast<Node*>(tree.remove(key));

    if (p == nullptr)
      return num_nodes;

    delete p;

    return --num_nodes;
  }

  Key del(const Key & key)
  {
    Node * p = static_cast<Node*>(tree.remove(key));

    if (p == nullptr)
      throw domain_error("DynSetTree::del key is not found in the tree");

    auto ret_val = p->get_key();

    delete p;

    --num_nodes;

    return ret_val;
  }

  Key remove_pos(const size_t i)
  {
    Node * p = static_cast<Node*>(tree.remove_pos(i));
    const Key ret_val = KEY(p);

    delete p;

    --num_nodes;

    return ret_val;
  }

  bool exist(const Key & key) const
  {
    return const_cast<DynSetTree&>(*this).search(key) != nullptr;
  }

  bool has(const Key & key) const
  {
    return exist(key);
  }

  bool contains(const Key & key) const
  {
    return exist(key);
  }

  Key & find(const Key & key) const
  {
    Node * node = static_cast<Node*>(tree.search(key));

    if (node == nullptr)
      throw std::domain_error("key not found");

    return node->get_key();
  }

  std::pair<int, Key*> find_position(const Key & key) const
  {
    if (num_nodes == 0)
      return std::pair<int, Key*> (0, nullptr);

    std::pair<int, Node*> p = tree.find_position(key);

    return std::pair<int, Key*> (p.first, &p.second->get_key());
  }

  Key * search(const Key & key) const
  {
    Node * node = static_cast<Node*>(tree.search(key));

    if (node == nullptr)
      return nullptr;

    return &(node->get_key());
  }

 const Key & min() const
  {
    if (num_nodes == 0)
      throw std::domain_error("set is empty");

    return find_min(tree.getRoot())->get_key();
  }

  const Key & get_first() const { return min(); }

  const Key & max() const
  {
    if (num_nodes == 0)
      throw std::domain_error("set is empty");

    return find_max(tree.getRoot())->get_key();
  }

  const Key & get_last() const { return max(); }

  const Key & get() const { return max(); }

  const size_t & size() const { return num_nodes; }

  bool is_empty() const { return num_nodes == 0; }

  size_t internal_path_length() const
  {
    return Aleph::internal_path_length(tree.getRoot());
  }

  Node * get_root_node() const { return tree.getRoot(); }

  const Key & get_root() const
  {
    if (num_nodes == 0)
      throw std::domain_error("Tree is empty");
    return KEY(tree.getRoot());
  }

  const Key & get_item() const { return get_root(); }

  size_t height() const { return computeHeightRec(tree.getRoot()); }

      template <class Op>
  void for_each_in_preorder(void (*visitFct)(Node*, int, int))
  {
    Node * root = static_cast<Node*>(tree.getRoot());
    preOrderRec(root, visitFct);
  }

  long position(const Key & key) const
  {
    std::pair<long, Node*> p = tree.position(key);
    return p.first;
  }

  Key & select(const size_t & i)
  {
    return tree.select(i)->get_key();
  }

  const Key & select(const size_t & i) const
  {
    return tree.select(i)->get_key();
  }

  Key & operator () (const size_t & i)
  {
    return select(i);
  }

  const Key & operator [] (const Key & key) const
  {
    return find(key);
  }

  const Key & operator [] (const Key & key)
  {
    return *search_or_insert(key);
  }

  Key & access (const size_t & i)
  {
    return select(i);
  }

  bool verify()
  {
    return tree.verify() and check_bst(tree.getRoot());
  }

private:

    template <class Key_Op>
struct Node_Op
{
  Key_Op & key_op;

  Node_Op(Key_Op & __key_op) : key_op(__key_op) { /* empty */ }

  Node_Op(Key_Op && __key_op) : key_op(__key_op)
  {
    /* empty */
  }

  void operator () (Node * root)
  {
    assert(root != nullptr);
    key_op(KEY(root));
  }
};

public:

      template <class Key_Op>
  void for_each_preorder(Key_Op & key_op) const
  {
    Node * root = (Node *) tree.getRoot();

    Node_Op <Key_Op> node_op(const_cast<Key_Op&>(key_op));

    For_Each_Preorder<Node> () (root, node_op);
  }

      template <class Key_Op>
  void for_each_preorder(Key_Op && key_op = Key_Op()) const
  {
    for_each_preorder<Key_Op>(key_op);
  }

      template <class Key_Op>
  void for_each_inorder(Key_Op & key_op) const
  {
    Node * root = (Node *) tree.getRoot();

    Node_Op <Key_Op> node_op(const_cast<Key_Op&>(key_op));

    For_Each_In_Order<Node> () (root, node_op);
  }

      template <class Key_Op>
  void for_each_inorder(Key_Op && key_op = Key_Op()) const
  {
    for_each_inorder<Key_Op>(key_op);
  }

      template <class Key_Op>
  void for_each_postorder(Key_Op & key_op)
  {
    Node * root = (Node *) tree.getRoot();

    Node_Op <Key_Op> node_op(const_cast<Key_Op&>(key_op));

    For_Each_Postorder<Node> () (root, node_op);
  }

      template <class Key_Op>
  void for_each_postorder(Key_Op && key_op = Key_Op())
  {
    for_each_postorder<Key_Op>(key_op);
  }

  DynSetTree & join(DynSetTree & t, DynSetTree & dup)
  {
    tree.join(t.tree, dup.tree);
    return *this;
  }

  DynSetTree & join(DynSetTree & t, DynSetTree && dup = DynSetTree())
  {
    return join(t, dup);
  }

  DynSetTree & join_dup(DynSetTree & t)
  {
    tree.join_dup(t.tree);
    t.num_nodes = 0;
    t.tree.getRoot() = Node::NullPtr;
    num_nodes = COUNT(tree.getRoot());
    return *this;
  }

  bool split_key(const Key & key, DynSetTree & l, DynSetTree & r)
  {
    if (not tree.split_key(key, l.tree, r.tree))
      return false;

    tree.getRoot() = Node::NullPtr;
    num_nodes = 0;
    l.num_nodes = COUNT(l.tree.getRoot());
    r.num_nodes = COUNT(r.tree.getRoot());

    return true;
  }

  void split_pos(const size_t pos, DynSetTree & l, DynSetTree & r)
  {
    tree.split_pos(pos, l.tree, r.tree);
    num_nodes = 0;
    l.num_nodes = COUNT(l.tree.getRoot());
    r.num_nodes = COUNT(r.tree.getRoot());
  }

  void split_key_dup(const Key & key, DynSetTree & l, DynSetTree & r)
  {
    tree.split_key_dup(key, l.tree, r.tree);
    tree.getRoot() = Node::NullPtr;
    num_nodes = 0;
    l.num_nodes = COUNT(l.tree.getRoot());
    r.num_nodes = COUNT(r.tree.getRoot());
  }

  struct Iterator : public Tree_Type::Iterator
  {
    using Base = typename Tree_Type::Iterator;

    using Set_Type = DynSetTree;

    Iterator(const DynSetTree & tree) : Base(tree.tree) { /* empty */ }

    const Key & get_curr_ne() const noexcept
    {
      return Base::get_curr_ne()->get_key();
    }

    Key & get_curr_ne() noexcept { return Base::get_curr_ne()->get_key(); }

    const Key & get_curr() const { return Base::get_curr()->get_key(); }

    Key & get_curr() { return Base::get_curr()->get_key(); }
  };

  template <class Operation>
  bool traverse(Operation & op)
  {
    return Aleph::traverse(tree.getRoot(), [&op] (Node * p)
                           {
                             return op(p->get_key());
                           });
  }

  template <class Operation>
  bool traverse(Operation && op = Operation())
  {
    return traverse<Operation>(op);
  }

  template <class Operation>
  bool traverse(Operation & op) const
  {
    return Aleph::traverse(tree.getRoot(), [&op] (Node * p)
                           {
                             return op(p->get_key());
                           });
  }

  template <class Operation>
  bool traverse(Operation && op = Operation()) const
  {
    return traverse<Operation>(op);
  }
};


# define SETTREE_ITOR(Name, Key, Cmp)                             \
  class Iterator : public DynSetTree<Key, Name, Cmp>::Iterator          \
  {                                                               \
  public:                                                         \
    Iterator() : DynSetTree<Key, Name, Cmp>::Iterator()           \
      { /* empty */ }                                             \
                                                                  \
    Iterator(DynSetTree<Key, Name, Cmp> & tree)                   \
      : DynSetTree<Key, Name, Cmp>::Iterator(tree)                \
      { /* empty */ }                                             \
  };


  template  <typename Key, class Compare = Aleph::less<Key>>
    class DynSetBinTree : public DynSetTree<Key, BinTree, Compare>
    {
    public:
      using Base = DynSetTree<Key, BinTree, Compare>;
      using Base::Base;
    };


  template  <typename Key, class Compare = Aleph::less<Key>>
    class DynSetAvlTree : public DynSetTree<Key, Avl_Tree, Compare>
    {
    public:
      using Base = DynSetTree<Key, Avl_Tree, Compare>;
      using Base::Base;
    };


  template  <typename Key, class Compare = Aleph::less<Key>>
    class DynSetSplayTree : public DynSetTree<Key, Splay_Tree, Compare>
    {
    public:
      using Base = DynSetTree<Key, Splay_Tree, Compare>;
      using Base::Base;
    };


    template  <typename Key, class Compare = Aleph::less<Key>>
class DynSetRandTree : public DynSetTree<Key, Rand_Tree, Compare>
{
public:
  using Base = DynSetTree<Key, Rand_Tree, Compare>;
  using Base::Base;

  class Iterator : public DynSetTree<Key, Rand_Tree, Compare>::Iterator
  {
  public:
    Iterator() : DynSetTree<Key, Rand_Tree, Compare>::Iterator()
    { /* empty */ }

    Iterator(DynSetTree<Key, Rand_Tree, Compare> & tree)
      : DynSetTree<Key, Rand_Tree, Compare>::Iterator(tree)
    { /* empty */ }
  };
};


  template  <typename Key, class Compare = Aleph::less<Key>>
    class DynSetTreap : public DynSetTree<Key, Treap, Compare>
    {
    public:
      using Base = DynSetTree<Key, Treap, Compare>;
      using Base::Base;
    };

  template  <typename Key, class Compare = Aleph::less<Key>>
    class DynSetTreapRk : public DynSetTree<Key, Treap_Rk, Compare>
    {
    public:
      using Base = DynSetTree<Key, Treap_Rk, Compare>;
      using Base::Base;
      SETTREE_ITOR(Treap_Rk, Key, Compare);
    };


  template  <typename Key, class Compare = Aleph::less<Key>>
    class DynSetRbTree : public DynSetTree<Key, Rb_Tree, Compare>
    {
    public:
      using Base = DynSetTree<Key, Rb_Tree, Compare>;
      using Base::Base;
    };


  template <typename T, class Op, class C>
DynSetTree<T> set_unify(const C & c, Op op)
{
  DynSetTree<T> ret;
  for (auto it = c.get_it(); it.has_curr(); it.next_ne())
    ret.insert(op(it.get_curr_ne()));
  return ret;
}

} // end namespace Aleph

# endif /* TPL_DYNSETTREE_H */