1// vi:set ft=cpp: -*- Mode: C++ -*- 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#include "std_ops" 28#include "pair" 29 30#include "bits/bst.h" 31#include "bits/bst_iter.h" 32 33namespace cxx { 34 35/** 36 * \brief Node of an AVL tree. 37 */ 38class Avl_tree_node : public Bits::Bst_node 39{ 40private: 41 template< typename Node, typename Get_key, typename Compare > 42 friend class Avl_tree; 43 44 /// Shortcut for Balance values (we use Direction for that). 45 typedef Bits::Direction Bal; 46 /// Alias for Direction. 47 typedef Bits::Direction Dir; 48 49 // We are a final BST node, hide interior. 50 /*@{*/ 51 using Bits::Bst_node::next; 52 using Bits::Bst_node::next_p; 53 using Bits::Bst_node::rotate; 54 /*@}*/ 55 56 /// The balance value (#Direction::N is balanced). 57 Bal _balance; 58 59protected: 60 /// Create an uninitialized node, this is what you should do. 61 Avl_tree_node() = default; 62 63private: 64 Avl_tree_node(Avl_tree_node const &o) = delete; 65 Avl_tree_node(Avl_tree_node &&o) = delete; 66 67 /// default copy for friend Avl_tree 68 Avl_tree_node &operator = (Avl_tree_node const &o) = default; 69 /// default move for friend Avl_tree 70 Avl_tree_node &operator = (Avl_tree_node &&o) = default; 71 72 /// Create an initialized node (for internal stuff). 73 explicit Avl_tree_node(bool) : Bits::Bst_node(true), _balance(Dir::N) {} 74 75 /// Double rotation of \a t. 76 static Bits::Bst_node *rotate2(Bst_node **t, Bal idir, Bal pre); 77 78 /// Is this subtree balanced? 79 bool balanced() const { return _balance == Bal::N; } 80 81 /// What is the balance of this subtree? 82 Bal balance() const { return _balance; } 83 84 /// Set the balance of this subtree to \a b. 85 void balance(Bal b) { _balance = b; } 86}; 87 88 89/** 90 * \brief A generic AVL tree. 91 * \tparam Node The data type of the nodes (must inherit from Avl_tree_node). 92 * \tparam Get_key The meta function to get the key value from a node. 93 * The implementation uses `Get_key::key_of(ptr_to_node)`. The 94 * type of the key values must be defined in `Get_key::Key_type`. 95 * \tparam Compare Binary relation to establish a total order for the 96 * nodes of the tree. `Compare()(l, r)` must return true if 97 * the key \a l is smaller than the key \a r. 98 * 99 * This implementation does not provide any memory management. It is the 100 * responsibility of the caller to allocate nodes before inserting them and 101 * to free them when they are removed or when the tree is destroyed. 102 * Conversely, the caller must also ensure that nodes are removed 103 * from the tree before they are destroyed. 104 */ 105template< typename Node, typename Get_key, 106 typename Compare = Lt_functor<typename Get_key::Key_type> > 107class Avl_tree : public Bits::Bst<Node, Get_key, Compare> 108{ 109private: 110 typedef Bits::Bst<Node, Get_key, Compare> Bst; 111 112 /// Hide this from possible descendants. 113 using Bst::_head; 114 115 /// Provide access to keys of nodes. 116 using Bst::k; 117 118 /// Alias type for balance values. 119 typedef typename Avl_tree_node::Bal Bal; 120 /// Alias type for Direction values. 121 typedef typename Avl_tree_node::Bal Dir; 122 123 Avl_tree(Avl_tree const &o) = delete; 124 Avl_tree &operator = (Avl_tree const &o) = delete; 125 Avl_tree(Avl_tree &&o) = delete; 126 Avl_tree &operator = (Avl_tree &&o) = delete; 127 128public: 129 //@{ 130 typedef typename Bst::Key_type Key_type; 131 typedef typename Bst::Key_param_type Key_param_type; 132 //@} 133 134 // Grab iterator types from Bst 135 //@{ 136 /// Forward iterator for the tree. 137 typedef typename Bst::Iterator Iterator; 138 /// Constant forward iterator for the tree. 139 typedef typename Bst::Const_iterator Const_iterator; 140 /// Backward iterator for the tree. 141 typedef typename Bst::Rev_iterator Rev_iterator; 142 /// Constant backward iterator for the tree. 143 typedef typename Bst::Const_rev_iterator Const_rev_iterator; 144 //@} 145 146 /** 147 * \brief Insert a new node into this AVL tree. 148 * \param new_node A pointer to the new node. 149 * \return A pair, with \a second set to `true` and \a first pointing to 150 * \a new_node, on success. If there is already a node with the 151 * same key then \a first points to this node and \a second is 'false'. 152 */ 153 Pair<Node *, bool> insert(Node *new_node); 154 155 /** 156 * \brief Remove the node with \a key from the tree. 157 * \param key The key to the node to remove. 158 * \return The pointer to the removed node on success, 159 * or 0 if no node with the \a key exists. 160 */ 161 Node *remove(Key_param_type key); 162 /** 163 * \brief An alias for remove(). 164 */ 165 Node *erase(Key_param_type key) { return remove(key); } 166 167 /// Create an empty AVL tree. 168 Avl_tree() = default; 169 170 /// Destroy the tree. 171 ~Avl_tree() noexcept 172 { 173 this->remove_all([](Node *){}); 174 } 175 176#ifdef __DEBUG_L4_AVL 177 bool rec_dump(Avl_tree_node *n, int depth, int *dp, bool print, char pfx); 178 bool rec_dump(bool print) 179 { 180 int dp=0; 181 return rec_dump(static_cast<Avl_tree_node *>(_head), 0, &dp, print, '+'); 182 } 183#endif 184}; 185 186 187//---------------------------------------------------------------------------- 188/* IMPLEMENTATION: Bits::__Bst_iter_b */ 189 190 191inline 192Bits::Bst_node * 193Avl_tree_node::rotate2(Bst_node **t, Bal idir, Bal pre) 194{ 195 typedef Bits::Bst_node N; 196 typedef Avl_tree_node A; 197 N *tmp[2] = { *t, N::next(*t, idir) }; 198 *t = N::next(tmp[1], !idir); 199 A *n = static_cast<A*>(*t); 200 201 N::next(tmp[0], idir, N::next(n, !idir)); 202 N::next(tmp[1], !idir, N::next(n, idir)); 203 N::next(n, !idir, tmp[0]); 204 N::next(n, idir, tmp[1]); 205 206 n->balance(Bal::N); 207 208 if (pre == Bal::N) 209 { 210 static_cast<A*>(tmp[0])->balance(Bal::N); 211 static_cast<A*>(tmp[1])->balance(Bal::N); 212 return 0; 213 } 214 215 static_cast<A*>(tmp[pre != idir])->balance(!pre); 216 static_cast<A*>(tmp[pre == idir])->balance(Bal::N); 217 218 return N::next(tmp[pre == idir], !pre); 219} 220 221//---------------------------------------------------------------------------- 222/* Implementation of AVL Tree */ 223 224/* Insert new _Node. */ 225template< typename Node, typename Get_key, class Compare> 226Pair<Node *, bool> 227Avl_tree<Node, Get_key, Compare>::insert(Node *new_node) 228{ 229 typedef Avl_tree_node A; 230 typedef Bits::Bst_node N; 231 N **t = &_head; /* search variable */ 232 N **s = &_head; /* node where rebalancing may occur */ 233 Key_param_type new_key = Get_key::key_of(new_node); 234 235 // search insertion point 236 for (N *p; (p = *t);) 237 { 238 Dir b = this->dir(new_key, p); 239 if (b == Dir::N) 240 return pair(static_cast<Node*>(p), false); 241 242 if (!static_cast<A const *>(p)->balanced()) 243 s = t; 244 245 t = A::next_p(p, b); 246 } 247 248 *static_cast<A*>(new_node) = A(true); 249 *t = new_node; 250 251 N *n = *s; 252 A *a = static_cast<A*>(n); 253 if (!a->balanced()) 254 { 255 A::Bal b(this->greater(new_key, n)); 256 if (a->balance() != b) 257 { 258 // ok we got in balance the shorter subtree go higher 259 a->balance(Bal::N); 260 // propagate the new balance down to the new node 261 n = A::next(n, b); 262 } 263 else if (b == Bal(this->greater(new_key, A::next(n, b)))) 264 { 265 // left-left or right-right case -> single rotation 266 A::rotate(s, b); 267 a->balance(Bal::N); 268 static_cast<A*>(*s)->balance(Bal::N); 269 n = A::next(*s, b); 270 } 271 else 272 { 273 // need a double rotation 274 n = A::next(A::next(n, b), !b); 275 n = A::rotate2(s, b, n == new_node ? Bal::N : Bal(this->greater(new_key, n))); 276 } 277 } 278 279 for (A::Bal b; n && n != new_node; static_cast<A*>(n)->balance(b), n = A::next(n, b)) 280 b = Bal(this->greater(new_key, n)); 281 282 return pair(new_node, true); 283} 284 285 286/* remove an element */ 287template< typename Node, typename Get_key, class Compare> 288inline 289Node *Avl_tree<Node, Get_key, Compare>::remove(Key_param_type key) 290{ 291 typedef Avl_tree_node A; 292 typedef Bits::Bst_node N; 293 N **q = &_head; /* search variable */ 294 N **s = &_head; /* last ('deepest') node on the search path to q 295 * with balance 0, at this place the rebalancing 296 * stops in any case */ 297 N **t = 0; 298 Dir dir; 299 300 // find target node and rebalancing entry 301 for (N *n; (n = *q); q = A::next_p(n, dir)) 302 { 303 dir = Dir(this->greater(key, n)); 304 if (dir == Dir::L && !this->greater(k(n), key)) 305 /* found node */ 306 t = q; 307 308 if (!A::next(n, dir)) 309 break; 310 311 A const *a = static_cast<A const *>(n); 312 if (a->balanced() || (a->balance() == !dir && A::next<A>(n, !dir)->balanced())) 313 s = q; 314 } 315 316 // nothing found 317 if (!t) 318 return 0; 319 320 A *i = static_cast<A*>(*t); 321 322 for (N *n; (n = *s); s = A::next_p(n, dir)) 323 { 324 dir = Dir(this->greater(key, n)); 325 326 if (!A::next(n, dir)) 327 break; 328 329 A *a = static_cast<A*>(n); 330 // got one out of balance 331 if (a->balanced()) 332 a->balance(!dir); 333 else if (a->balance() == dir) 334 a->balance(Bal::N); 335 else 336 { 337 // we need rotations to get in balance 338 Bal b = A::next<A>(n, !dir)->balance(); 339 if (b == dir) 340 A::rotate2(s, !dir, A::next<A>(A::next(n, !dir), dir)->balance()); 341 else 342 { 343 A::rotate(s, !dir); 344 if (b != Bal::N) 345 { 346 a->balance(Bal::N); 347 static_cast<A*>(*s)->balance(Bal::N); 348 } 349 else 350 { 351 a->balance(!dir); 352 static_cast<A*>(*s)->balance(dir); 353 } 354 } 355 if (n == i) 356 t = A::next_p(*s, dir); 357 } 358 } 359 360 A *n = static_cast<A*>(*q); 361 *t = n; 362 *q = A::next(n, !dir); 363 *n = *i; 364 365 return static_cast<Node*>(i); 366} 367 368#ifdef __DEBUG_L4_AVL 369template< typename Node, typename Get_key, class Compare> 370bool Avl_tree<Node, Get_key, Compare>::rec_dump(Avl_tree_node *n, int depth, int *dp, bool print, char pfx) 371{ 372 typedef Avl_tree_node A; 373 374 if (!n) 375 return true; 376 377 int dpx[2] = {depth,depth}; 378 bool res = true; 379 380 res = rec_dump(n->next<A>(Dir::R), depth + 1, dpx + 1, print, '/'); 381 382 if (print) 383 { 384 fprintf(stderr, "%2d: [%8p] b=%1d: ", depth, n, (int)n->balance().d); 385 386 for (int i = 0; i < depth; ++i) 387 std::cerr << " "; 388 389 std::cerr << pfx << (static_cast<Node*>(n)->item) << std::endl; 390 } 391 392 res = res & rec_dump(n->next<A>(Dir::L), depth + 1, dpx, print, '\\'); 393 394 int b = dpx[1] - dpx[0]; 395 396 if (b < 0) 397 *dp = dpx[0]; 398 else 399 *dp = dpx[1]; 400 401 Bal x = n->balance(); 402 if ((b < -1 || b > 1) || 403 (b == 0 && x != Bal::N) || 404 (b == -1 && x != Bal::L) || 405 (b == 1 && x != Bal::R)) 406 { 407 if (print) 408 fprintf(stderr, "%2d: [%8p] b=%1d: balance error %d\n", depth, n, (int)n->balance().d, b); 409 return false; 410 } 411 return res; 412} 413#endif 414 415} 416 417