tpl_dynSetTree.H

# ifndef TPL_DYNSETTREE_H
# define TPL_DYNSETTREE_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_splay_tree.H>
# include <tpl_nodePool.H>

using namespace Aleph;

namespace Aleph { 

    template <
      typename Key, 
      template <typename, class> class Tree = Avl_Tree, 
      class Compare = Aleph::less<Key>
      >
class DynSetTree
{
public:

  typedef typename Tree<Key, Compare>::Node Node;

private:

  static const size_t dim = 13;

  typedef Tree<Key, Compare> Tree_Type;

  mutable Tree<Key, Compare> tree; 
  size_t num_nodes; 
  Node_Pool<Node> node_pool;

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(std::move(cmp)), num_nodes(0), node_pool(dim)
  {
    /* empty */ 
  }

  DynSetTree(Compare & cmp) 
    : tree(cmp), num_nodes(0), node_pool(dim)
  { 
    /* empty */ 
  }

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

  DynSetTree(const DynList<Key> & list) : DynSetTree()
  {
    list.for_each([this] (const Key & k) { insert(k); });
  }

  DynSetTree(DynSetTree && srcTree) : num_nodes(0), node_pool(dim)
  { 
    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() 
  {
    destroyRec(tree.getRoot());
  }

private:

  Key * __insert(Node * p)
  {
    if (tree.search_or_insert(p) != p)
      {
        node_pool.deallocate(p);
        return NULL;
      }

    ++num_nodes;

    return &p->get_key();
  }

public:

  Key * insert(const Key & key)
  {
    return __insert(node_pool.allocate(key));
  }

  Key * insert(Key && key)
  {
    return __insert(node_pool.allocate(std::move(key)));
  }
  
  Key * append(const Key & key)
  {
    return __insert(node_pool.allocate(key));
  }

  Key * append(Key && key)
  {
    return __insert(node_pool.allocate(std::move(key)));
  }

private:

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

    return &q->get_key();
  }


public:

  Key * search_or_insert(const Key & key)
  {
    return __search_or_insert(node_pool.allocate(key));
  }

  Key * search_or_insert(Key && key)
  {
    return __search_or_insert(node_pool.allocate(std::move(key)));
  }

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(node_pool.allocate(key));
  }

  Key * insert_dup(Key && key)
  {
    return __insert_dup(node_pool.allocate(std::move(key)));
  }

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

  Key * put(Key && key)
  {
    return insert(std::move(key));
  }

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

    if (p == NULL)
      return num_nodes;

    node_pool.deallocate(p);

    return --num_nodes;
  }

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

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

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

  Key & find(const Key & key) throw(std::exception, std::domain_error)
  {
    Node * node = static_cast<Node*>(tree.search(key));

    if (node == NULL)
      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, NULL);

    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
    throw(std::exception, std::domain_error)
  {
    Node * node = static_cast<Node*>(tree.search(key));

    if (node == NULL)
      return NULL;

    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() { 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() { return max(); }

  const Key & get()
  {
    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());
  }

  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);
  }

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

  bool verify() 
  {
    return tree.verify() and check_binary_search_tree(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) 
  { 
    I(root != NULL);
    key_op(KEY(root));
  }
};

public:

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

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

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

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

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

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

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

      template <class Key_Op> 
  void for_each_inorder(Key_Op && key_op = Key_Op()) 
  {
    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, Node_Op <Key_Op>> () (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)
  {
    BinTree_Operation <Node, Compare> (tree.get_compare()).
      join(tree.getRoot(), t.tree.getRoot(), dup.tree.getRoot());

    t.num_nodes = 0;
    t.tree.getRoot() = Node::NullPtr;

    dup.num_nodes = COUNT(dup.tree.getRoot());
    num_nodes = COUNT(tree.getRoot());

    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 split_key_rec_xt<Node, Compare>(tree.getRoot(), key, 
                                            l.tree.getRoot(), r.tree.getRoot()))
      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)
  {
    split_pos_rec(tree.getRoot(), pos, l.tree.getRoot(), r.tree.getRoot());

    tree.getRoot() = Node::NullPtr;
    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)
  {
    split_key_dup_rec_xt<Node,Compare>(tree.getRoot(), key, 
                                       l.tree.getRoot(), r.tree.getRoot());

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

  class Iterator
  {
  protected:
    
    mutable DynSetTree * tree_ptr; 
    mutable Node * curr;
    mutable int    curr_pos;

    static const int Pos_Not_Current     = -1;
    static const int Pos_Empty_Container = -2;
    static const int Pos_Not_Updated     = -3;

  private:

    bool is_container_empty() const
    {
      return tree_ptr->size() == 0;
    }

    bool pos_updated() const
    {
      return curr_pos != Pos_Not_Updated;
    }

    bool curr_updated() const
    {
      return curr != NULL;
    }

    bool is_updated() 
    {
      return pos_updated() and curr_updated();
    }

    void update_pos() const
    {
      I(curr != NULL);

      curr_pos = tree_ptr->position(curr->get_key());
    }

    void update_curr() const
    {
      I(curr_pos != Pos_Not_Updated);

      if (curr_pos == Pos_Empty_Container or curr_pos == Pos_Not_Current or
          curr_pos == tree_ptr->size())
        return;
      
      curr = Node::key_to_node(tree_ptr->select(curr_pos));
    }

  public:

    Iterator() : tree_ptr(NULL), curr(NULL), curr_pos(Pos_Not_Current)
    {
      /* empty */ 
    }

    Iterator(const DynSetTree & tree) 
      : tree_ptr(&const_cast<DynSetTree&>(tree)), curr(NULL)
    {
      curr_pos = is_container_empty() ? Pos_Empty_Container : 0;
    }

    void set_pos(size_t pos)
    {
      if (tree_ptr == NULL)
        std::domain_error("There is not tree associated to iterator");

      curr_pos = pos;
      curr = Node::key_to_node(tree_ptr->select(curr_pos));
    }

    void set_key(const Key & key)
    {
      if (tree_ptr == NULL)
        std::domain_error("There is not tree associated to iterator");

      std::pair<int, Node*> p = tree_ptr->find_position(key);
      curr = Node::key_to_node(KEY(p));
      curr_pos = p.first;
    }

    Iterator (const Iterator & itor)
      : tree_ptr(itor.tree_ptr), curr(itor.curr), curr_pos(itor.curr_pos)
    {
      // Empty
    }

    Iterator & operator = (const Iterator & itor)
    {
      if (this == &itor)
        return *this;

      tree_ptr = itor.tree_ptr;
      curr = itor.curr;
      curr_pos = itor.curr_pos;

      return *this;
    }

    void reset_first()
    {
      curr = NULL;
      curr_pos = is_container_empty() ? Pos_Empty_Container : 0;
    }

    void reset_last()
    {
      curr = NULL;
      curr_pos = 
        is_container_empty() ? Pos_Empty_Container : tree_ptr->size() - 1;
    }

    void reset_to_key (const Key & key)
    {
      std::pair<long, Key*> p = tree_ptr->position(key);
      curr_pos = p.first;
    }

    void reset_to_node (Node * node)
    {
      curr = node;
      curr_pos = -2;
    }

    void reset_to_pos (size_t pos)
    {
      curr = NULL;
      curr_pos = pos;
    }

    Key & get_current() const
    {
      if (not curr_updated())
        update_curr();

      return KEY(curr); 
    }

    Key & get_curr() const
    {
      return get_current();
    }

    size_t get_current_position() const
      throw (std::exception, std::underflow_error, std::overflow_error)
    {
      if (not pos_updated())
        update_pos();

      if (curr_pos < -1 )
        throw std::range_error ("DynSetTree::Iterator has not current");
        
      if (curr_pos > COUNT (tree_ptr->getRoot() ) )
        throw std::range_error ("DynSetTree::iterator has not current");

      return curr_pos;
    }

    bool has_current() const
    {
      if (not pos_updated())
        update_pos();

      return curr_pos >= 0 and curr_pos < tree_ptr->size();
    }

    bool has_curr() const
    {
      return has_current();
    }

    void prev() throw (std::exception, std::underflow_error)
    {
      if (not has_current() )
        throw std::underflow_error ("DynSetTree::Iterator has not current");

      --curr_pos;
      curr = NULL;
    }

    void next() throw (std::exception, std::overflow_error)
    {
      if (not has_current() )
        throw std::underflow_error ("DynSetTree::Iterator has not current");

      ++curr_pos;
      curr = NULL;
    }

    Key del()
    {
      if (not has_current() )
        throw std::underflow_error ("DynSetTree::Iterator has not current");

      if (not curr_updated())
        update_curr();

      Key ret_val = curr->get_key();
      tree_ptr->remove(ret_val);

      curr = NULL;

      return ret_val;
    }

    bool operator == (const Iterator & itor) const
    {
      if (is_container_empty() and itor.is_container_empty())
        return true;

      if (pos_updated() and itor.pos_updated())
        return curr_pos == itor.curr_pos;

      if (curr_updated() and itor.curr_updated())
        return curr == itor.curr;

      if (not pos_updated())
        {
          update_pos();
          return curr_pos == itor.curr_pos;
        }

      itor.update_pos();

      return curr_pos == itor.curr_pos;
    }
  
    bool operator != (const Iterator & itor) const
    {
      return not (*this == itor);
    }
  }; // end class Iterator

  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);
  }

  Functional_Methods(Key);
  Generic_Keys(Key);
  Equal_To_Method(DynSetTree);
};


# 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>
    { /* empty */ };


    template  <typename Key, class Compare = Aleph::less<Key>>
class DynSetAvlTree : public DynSetTree<Key, Avl_Tree, Compare>
    { /* empty */ };


    template  <typename Key, class Compare = Aleph::less<Key>>
class DynSetSplayTree : public DynSetTree<Key, Splay_Tree, Compare>
    { /* empty */ };


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

  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>
    { /* empty */ };

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



    template  <typename Key, class Compare = Aleph::less<Key>>
class DynSetRbTree : public DynSetTree<Key, Rb_Tree, Compare>
    { /* empty */ }; 


} // end namespace Aleph

# endif /* TPL_DYNSETTREE_H */