1 // vi:ft=cpp
2 /**
3 * \file
4 * \brief AVL tree
5 */
6 /*
7 * (c) 2008-2009 Alexander Warg <warg@os.inf.tu-dresden.de>,
8 * Carsten Weinhold <weinhold@os.inf.tu-dresden.de>
9 * economic rights: Technische Universität Dresden (Germany)
10 *
11 * This file is part of TUD:OS and distributed under the terms of the
12 * GNU General Public License 2.
13 * Please see the COPYING-GPL-2 file for details.
14 *
15 * As a special exception, you may use this file as part of a free software
16 * library without restriction. Specifically, if other files instantiate
17 * templates or use macros or inline functions from this file, or you compile
18 * this file and link it with other files to produce an executable, this
19 * file does not by itself cause the resulting executable to be covered by
20 * the GNU General Public License. This exception does not however
21 * invalidate any other reasons why the executable file might be covered by
22 * the GNU General Public License.
23 */
24
25 #pragma once
26
27 /*
28 * This file contains very basic bits for implementing binary serach trees
29 */
30 namespace cxx {
31 /**
32 * \brief Internal helpers for the cxx package.
33 */
34 namespace Bits {
35
36 /**
37 * \brief The direction to go in a binary search tree.
38 */
39 struct Direction
40 {
41 /// The literal direction values.
42 enum Direction_e
43 {
44 L = 0, ///< Go to the left child
45 R = 1, ///< Go to the right child
46 N = 2 ///< Stop
47 };
48 unsigned char d;
49
50 /// Uninitialized direction
51 Direction() = default;
52
53 /// Convert a literal direction (#L, #R, #N) to an object
DirectionDirection54 Direction(Direction_e d) : d(d) {}
55
56 /// Convert a boolean to a direction (false == #L, true == #R)
DirectionDirection57 explicit Direction(bool b) : d(Direction_e(b)) /*d(b ? R : L)*/ {}
58
59 /**
60 * \brief Negate the direction.
61 * \note This is only defined for a current value of #L or #R
62 */
63 Direction operator ! () const { return Direction(!d); }
64
65 /// \name Comparison operators (equality and inequality)
66 //@{
67 bool operator == (Direction_e o) const { return d == o; }
68 bool operator != (Direction_e o) const { return d != o; }
69 bool operator == (Direction o) const { return d == o.d; }
70 bool operator != (Direction o) const { return d != o.d; }
71 //@}
72 };
73
74 /**
75 * \brief Basic type of a node in a binary search tree (BST).
76 */
77 class Bst_node
78 {
79 // all BSTs are friends
80 template< typename Node, typename Get_key, typename Compare >
81 friend class Bst;
82
83 protected:
84 /**
85 * \name Access to BST linkage.
86 *
87 * Provide access to the tree linkage to inherited classes
88 * Inherited nodes, such as AVL nodes should make these methods
89 * private via 'using'
90 */
91 /*@{*/
92
93 /// Get next node in direction \a d.
next(Bst_node const * p,Direction d)94 static Bst_node *next(Bst_node const *p, Direction d)
95 { return p->_c[d.d]; }
96
97 /// Set next node of \a p in direction \a d to \a n.
next(Bst_node * p,Direction d,Bst_node * n)98 static void next(Bst_node *p, Direction d, Bst_node *n)
99 { p->_c[d.d] = n; }
100
101 /// Get pointer to link in direction \a d.
next_p(Bst_node * p,Direction d)102 static Bst_node **next_p(Bst_node *p, Direction d)
103 { return &p->_c[d.d]; }
104
105 /// Get next node in direction \a d as type \a Node.
106 template< typename Node > static
next(Bst_node const * p,Direction d)107 Node *next(Bst_node const *p, Direction d)
108 { return static_cast<Node *>(p->_c[d.d]); }
109
110 /// Rotate subtree \a t in the opposite direction of \a idir.
111 static void rotate(Bst_node **t, Direction idir);
112 /*@}*/
113
114 private:
115 Bst_node *_c[2];
116
117 protected:
118 /// Create uninitialized node
Bst_node()119 Bst_node() {}
120
121 /// Create initialized node
Bst_node(bool)122 explicit Bst_node(bool) { _c[0] = _c[1] = 0; }
123 };
124
125 inline
126 void
rotate(Bst_node ** t,Direction idir)127 Bst_node::rotate(Bst_node **t, Direction idir)
128 {
129 Bst_node *tmp = *t;
130 *t = next(tmp, idir);
131 next(tmp, idir, next(*t, !idir));
132 next(*t, !idir, tmp);
133 }
134
135 }}
136