bst_base.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
 
/*
 * This file contains very basic bits for implementing binary serach trees
 */
namespace cxx {
namespace Bits {
 
struct Direction
{
  enum Direction_e
  {
    L = 0, 
    R = 1, 
    N = 2  
  };
  unsigned char d;
 
  Direction() = default;
 
  Direction(Direction_e d) : d(d) {}
 
  explicit Direction(bool b) : d(Direction_e(b)) /*d(b ? R : L)*/ {}
 
  Direction operator ! () const { return Direction(!d); }
 
 
  bool operator == (Direction_e o) const { return d == o; }
  bool operator != (Direction_e o) const { return d != o; }
  bool operator == (Direction o) const { return d == o.d; }
  bool operator != (Direction o) const { return d != o.d; }
};
 
class Bst_node
{
  // all BSTs are friends
  template< typename Node, typename Get_key, typename Compare >
  friend class Bst;
 
protected:
  static Bst_node *next(Bst_node const *p, Direction d)
  { return p->_c[d.d]; }
 
  static void next(Bst_node *p, Direction d, Bst_node *n)
  { p->_c[d.d] = n; }
 
  static Bst_node **next_p(Bst_node *p, Direction d)
  { return &p->_c[d.d]; }
 
  template< typename Node > static
  Node *next(Bst_node const *p, Direction d)
  { return static_cast<Node *>(p->_c[d.d]); }
 
  static void rotate(Bst_node **t, Direction idir);
private:
  Bst_node *_c[2];
 
protected:
  Bst_node() {}
 
  explicit Bst_node(bool) { _c[0] = _c[1] = 0; }
};
 
inline
void
Bst_node::rotate(Bst_node **t, Direction idir)
{
  Bst_node *tmp = *t;
  *t = next(tmp, idir);
  next(tmp, idir, next(*t, !idir));
  next(*t, !idir, tmp);
}
 
}}