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)
 *
 * License: see LICENSE.spdx (in this directory or the directories above)
 */
 
#pragma once
 
/*
 * This file contains very basic bits for implementing binary search trees
 */
namespace cxx {
namespace Bits {
 
struct Direction
{
  enum Direction_e
  {
    L = 0, 
    R = 1, 
    N = 2  
  };
  enum Direction_e {…};
  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; }
};
struct Direction {…};
 
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 Bst_node *next(Bst_node const *p, Direction d) {…}
 
  static void next(Bst_node *p, Direction d, Bst_node *n)
  { p->_c[d.d] = n; }
  static void next(Bst_node *p, Direction d, Bst_node *n) {…}
 
  static Bst_node **next_p(Bst_node *p, Direction d)
  { return &p->_c[d.d]; }
  static Bst_node **next_p(Bst_node *p, Direction d) {…}
 
  template< typename Node > static
  Node *next(Bst_node const *p, Direction d)
  { return static_cast<Node *>(p->_c[d.d]); }
  Node *next(Bst_node const *p, Direction 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; }
};
class Bst_node {…};
 
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);
}
Bst_node::rotate(Bst_node **t, Direction idir) {…}
 
}}