tpl_binTree.H

# 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:

  typedef NodeType<Key> Node;

private:

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

  GenBinTree(const GenBinTree & ) = delete;

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

public:

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

  Compare & key_comp() { return cmp; }

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

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

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

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

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

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

  Node*& getRoot() { return root; }

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

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

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

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

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

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

  Node * remove(const Key & key)
  {
    Node * ret = BinTree_Operation<Node, Compare>(cmp).remove(root, key);

    return ret != Node::NullPtr ? ret : NULL;
  }

  void join(GenBinTree & tree, GenBinTree & dup)
  {
    root = BinTree_Operation<Node, Compare>(cmp).join(root, tree.root, dup);
    tree.root = Node::NullPtr;
  }
};
    template  <typename Key, class Compare = Aleph::less<Key> >
class BinTree : public GenBinTree<BinNode, Key, Compare> 
{
public:

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

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

    template  <typename Key, class Compare = Aleph::less<Key> >
class BinTreeVtl : public GenBinTree<BinNodeVtl, Key, Compare> 
{
public:

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

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

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