Loading...
Searching...
No Matches
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
};
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);
}
}}
cxx::Bits::Bst_node
Basic type of a node in a binary search tree (BST).
Definition bst_base.h:71
cxx::Bits::Bst_node::next
static void next(Bst_node *p, Direction d, Bst_node *n)
Set next node of p in direction d to n.
Definition bst_base.h:91
cxx::Bits::Bst_node::next_p
static Bst_node ** next_p(Bst_node *p, Direction d)
Get pointer to link in direction d.
Definition bst_base.h:95
cxx::Bits::Bst_node::next
static Node * next(Bst_node const *p, Direction d)
Get next node in direction d as type Node.
Definition bst_base.h:100
cxx::Bits::Bst_node::Bst_node
Bst_node(bool)
Create initialized node.
Definition bst_base.h:115
cxx::Bits::Bst_node::rotate
static void rotate(Bst_node **t, Direction idir)
Rotate subtree t in the opposite direction of idir.
Definition bst_base.h:120
cxx::Bits::Bst_node::Bst_node
Bst_node()
Create uninitialized node.
Definition bst_base.h:112
cxx::Bits::Bst_node::next
static Bst_node * next(Bst_node const *p, Direction d)
Get next node in direction d.
Definition bst_base.h:87
cxx::Bits
Internal helpers for the cxx package.
Definition avl_map:21
cxx
Our C++ library.
Definition arith:11
cxx::Bits::Direction
The direction to go in a binary search tree.
Definition bst_base.h:29
cxx::Bits::Direction::Direction
Direction(Direction_e d)
Convert a literal direction (L, R, N) to an object.
Definition bst_base.h:43
cxx::Bits::Direction::Direction
Direction(bool b)
Convert a boolean to a direction (false == L, true == R).
Definition bst_base.h:46
cxx::Bits::Direction::operator!=
bool operator!=(Direction_e o) const
Compare for inequality.
Definition bst_base.h:59
cxx::Bits::Direction::operator==
bool operator==(Direction_e o) const
Compare for equality.
Definition bst_base.h:57
cxx::Bits::Direction::Direction
Direction()=default
Uninitialized direction.
cxx::Bits::Direction::operator!
Direction operator!() const
Negate the direction.
Definition bst_base.h:52
cxx::Bits::Direction::Direction_e
Direction_e
The literal direction values.
Definition bst_base.h:32
cxx::Bits::Direction::L
@ L
Go to the left child.
Definition bst_base.h:33
cxx::Bits::Direction::N
@ N
Stop.
Definition bst_base.h:35
cxx::Bits::Direction::R
@ R
Go to the right child.
Definition bst_base.h:34