bst.h

Go to the documentation of this file.

// vi:ft=cpp
/*
 * (c) 2008-2009 Alexander Warg <warg@os.inf.tu-dresden.de>,
 *               Carsten Weinhold <weinhold@os.inf.tu-dresden.de>
 *     economic rights: Technische Universität Dresden (Germany)
 *
 * This file is part of TUD:OS and distributed under the terms of the
 * GNU General Public License 2.
 * Please see the COPYING-GPL-2 file for details.
 *
 * As a special exception, you may use this file as part of a free software
 * library without restriction.  Specifically, if other files instantiate
 * templates or use macros or inline functions from this file, or you compile
 * this file and link it with other files to produce an executable, this
 * file does not by itself cause the resulting executable to be covered by
 * the GNU General Public License.  This exception does not however
 * invalidate any other reasons why the executable file might be covered by
 * the GNU General Public License.
 */
#pragma once
 
#include "../type_traits"
#include "bst_base.h"
#include "bst_iter.h"
 
struct Avl_set_tester;
 
namespace cxx { namespace Bits {
 
template< typename Node, typename Get_key, typename Compare >
class Bst
{
  friend struct ::Avl_set_tester;
 
private:
  typedef Direction Dir;
  struct Fwd
  {
    static Node *child(Node const *n, Direction d)
    { return Bst_node::next<Node>(n, d); }
 
    static bool cmp(Node const *l, Node const *r)
    { return Compare()(Get_key::key_of(l), Get_key::key_of(r)); }
  };
 
  struct Rev
  {
    static Node *child(Node const *n, Direction d)
    { return Bst_node::next<Node>(n, !d); }
 
    static bool cmp(Node const *l, Node const *r)
    { return Compare()(Get_key::key_of(r), Get_key::key_of(l)); }
  };
 
public:
  typedef typename Get_key::Key_type Key_type;
  typedef typename Type_traits<Key_type>::Param_type Key_param_type;
 
  typedef Fwd Fwd_iter_ops;
  typedef Rev Rev_iter_ops;
 
 
  typedef __Bst_iter<Node, Node, Fwd> Iterator;
  typedef __Bst_iter<Node, Node const, Fwd> Const_iterator;
  typedef __Bst_iter<Node, Node, Rev> Rev_iterator;
  typedef __Bst_iter<Node, Node const, Rev> Const_rev_iterator;
protected:
  Bst_node *_head;
 
  Bst() : _head(0) {}
 
  Node *head() const { return static_cast<Node*>(_head); }
 
  static Key_type k(Bst_node const *n)
  { return Get_key::key_of(static_cast<Node const *>(n)); }
 
  static Dir dir(Key_param_type l, Key_param_type r)
  {
    Compare cmp;
    Dir d(cmp(r, l));
    if (d == Direction::L && !cmp(l, r))
      return Direction::N;
    return d;
  }
 
  static Dir dir(Key_param_type l, Bst_node const *r)
  { return dir(l, k(r)); }
 
  static bool greater(Key_param_type l, Key_param_type r)
  { return Compare()(r, l); }
 
  static bool greater(Key_param_type l, Bst_node const *r)
  { return greater(l, k(r)); }
 
  static bool greater(Bst_node const *l, Bst_node const *r)
  { return greater(k(l), k(r)); }
  template<typename FUNC>
  static void remove_tree(Bst_node *head, FUNC &&callback)
  {
    if (Bst_node *n = Bst_node::next(head, Dir::L))
      remove_tree(n, callback);
 
    if (Bst_node *n = Bst_node::next(head, Dir::R))
      remove_tree(n, callback);
 
    callback(static_cast<Node *>(head));
  }
 
public:
 
  Const_iterator begin() const { return Const_iterator(head()); }
  Const_iterator end() const { return Const_iterator(); }
 
  Iterator begin() { return Iterator(head()); }
  Iterator end() { return Iterator(); }
 
  Const_rev_iterator rbegin() const { return Const_rev_iterator(head()); }
  Const_rev_iterator rend() const { return Const_rev_iterator(); }
 
  Rev_iterator rbegin() { return Rev_iterator(head()); }
  Rev_iterator rend() { return Rev_iterator(); }
 
  Node *find_node(Key_param_type key) const;
 
  Node *lower_bound_node(Key_param_type key) const;
 
  Const_iterator find(Key_param_type key) const;
 
  template<typename FUNC>
  void remove_all(FUNC &&callback)
  {
    if (!_head)
      return;
 
    Bst_node *head = _head;
    _head = 0;
    remove_tree(head, cxx::forward<FUNC>(callback));
  }
 
 
};
 
/* find an element */
template< typename Node, typename Get_key, class Compare>
inline
Node *
Bst<Node, Get_key, Compare>::find_node(Key_param_type key) const
{
  Dir d;
 
  for (Bst_node *q = _head; q; q = Bst_node::next(q, d))
    {
      d = dir(key, q);
      if (d == Dir::N)
  return static_cast<Node*>(q);
    }
  return 0;
}
 
template< typename Node, typename Get_key, class Compare>
inline
Node *
Bst<Node, Get_key, Compare>::lower_bound_node(Key_param_type key) const
{
  Dir d;
  Bst_node *r = 0;
 
  for (Bst_node *q = _head; q; q = Bst_node::next(q, d))
    {
      d = dir(key, q);
      if (d == Dir::L)
  r = q; // found a node greater than key
      else if (d == Dir::N)
  return static_cast<Node*>(q);
    }
  return static_cast<Node*>(r);
}
 
/* find an element */
template< typename Node, typename Get_key, class Compare>
inline
typename Bst<Node, Get_key, Compare>::Const_iterator
Bst<Node, Get_key, Compare>::find(Key_param_type key) const
{
  Bst_node *q = _head;
  Bst_node *r = q;
 
  for (Dir d; q; q = Bst_node::next(q, d))
    {
      d = dir(key, q);
      if (d == Dir::N)
  return Iterator(static_cast<Node*>(q), static_cast<Node *>(r));
 
      if (d != Dir::L && q == r)
  r = Bst_node::next(q, d);
    }
  return Iterator();
}
 
}}