tpl_binTree.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_BINTREE_H
# define TPL_BINTREE_H

# include <tpl_binTreeOps.H>

using namespace Aleph;

namespace Aleph {

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

  using Node = NodeType<Key>; 

private:

  Node      headNode;
  Node  *   head;
  Node *&   root;
  Compare   cmp;

public:

  GenBinTree(const GenBinTree & ) = delete;

  GenBinTree & operator = (const GenBinTree &) = delete;

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

  Compare & key_comp() noexcept { return cmp; }

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

  GenBinTree(Compare __cmp = Compare()) noexcept
    : head(&headNode), root(headNode.getR()), cmp(__cmp)
  {
    // empty
  }

  Node * search(const Key & key) const noexcept
  {
    return BinTree_Operation<Node, Compare>(cmp).search(root, key);
  }

  virtual ~GenBinTree() noexcept { /* Empty */ }

  bool verify() const { return check_bst<Node, Compare>(root); }

  Node *& getRoot() { return root; }

  bool verifyBin() const { return check_bst<Node, Compare>(root); } 

  Node * insert(Node *p) noexcept
  {
    return BinTree_Operation<Node, Compare>(cmp).insert(root, p);
  }

  Node * insert_dup(Node *p) noexcept
  {
    return BinTree_Operation<Node, Compare>(cmp).insert_dup(root, p);
  }

  Node * search_or_insert(Node *p) noexcept
  {
    return BinTree_Operation<Node, Compare>(cmp).search_or_insert(root, p);
  }

  bool split(const Key & key, GenBinTree & l, GenBinTree & r) noexcept
  {
    return BinTree_Operation<Node, Compare>(cmp).
      split_key_rec(root, key, l.root, r.root);
  }

  void split_dup(const Key & key, GenBinTree & l, GenBinTree & r) noexcept
  {
    BinTree_Operation<Node, Compare>(cmp).
      split_key_dup_rec(root, key, l.root, r.root);
  }

  Node * remove(const Key & key) noexcept
  {
    return BinTree_Operation<Node, Compare>(cmp).remove(root, key);
  }

  void join(GenBinTree & tree, GenBinTree & dup) noexcept
  {
    root = BinTree_Operation<Node, Compare>(cmp).join(root, tree.root, dup);
    tree.root = Node::NullPtr;
  }

  void join_dup(GenBinTree & t) noexcept
  {
    root = BinTree_Operation<Node, Compare>(cmp).join_dup(root, t.root);
    t.tree_root = Node::NullPtr;
  }

  void join_exclusive(GenBinTree & t) noexcept
  {
    root = join_exclusive(root, t.root);    
    t.root = Node::NullPtr;
  }

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

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


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


} // end namespace Aleph
# endif /* TPL_BINTREE_H */