yat/utility/ranking/Impl.cc

Code
Comments
Other
Rev Date Author Line
4064 05 Aug 21 peter 1 // $Id$
4064 05 Aug 21 peter 2
4064 05 Aug 21 peter 3 /*
4359 23 Aug 23 peter 4   Copyright (C) 2021 Peter Johansson
4064 05 Aug 21 peter 5
4064 05 Aug 21 peter 6   This file is part of the yat library, http://dev.thep.lu.se/yat
4064 05 Aug 21 peter 7
4064 05 Aug 21 peter 8   The yat library is free software; you can redistribute it and/or
4064 05 Aug 21 peter 9   modify it under the terms of the GNU General Public License as
4064 05 Aug 21 peter 10   published by the Free Software Foundation; either version 3 of the
4064 05 Aug 21 peter 11   License, or (at your option) any later version.
4064 05 Aug 21 peter 12
4064 05 Aug 21 peter 13   The yat library is distributed in the hope that it will be useful,
4064 05 Aug 21 peter 14   but WITHOUT ANY WARRANTY; without even the implied warranty of
4064 05 Aug 21 peter 15   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
4064 05 Aug 21 peter 16   General Public License for more details.
4064 05 Aug 21 peter 17
4064 05 Aug 21 peter 18   You should have received a copy of the GNU General Public License
4064 05 Aug 21 peter 19   along with yat. If not, see <http://www.gnu.org/licenses/>.
4064 05 Aug 21 peter 20 */
4064 05 Aug 21 peter 21
4064 05 Aug 21 peter 22 #include <config.h>
4064 05 Aug 21 peter 23
4085 29 Aug 21 peter 24 #include "yat/utility/Ranking.h"
4064 05 Aug 21 peter 25
4064 05 Aug 21 peter 26 #include <cassert>
4064 05 Aug 21 peter 27 #include <cstddef>
4064 05 Aug 21 peter 28 #include <iostream>
4064 05 Aug 21 peter 29
4064 05 Aug 21 peter 30 namespace theplu {
4064 05 Aug 21 peter 31 namespace yat {
4064 05 Aug 21 peter 32 namespace utility {
4064 05 Aug 21 peter 33 namespace ranking {
4064 05 Aug 21 peter 34
4064 05 Aug 21 peter 35   Impl::Impl(void)
4064 05 Aug 21 peter 36   {
4064 05 Aug 21 peter 37     reset();
4064 05 Aug 21 peter 38   }
4064 05 Aug 21 peter 39
4064 05 Aug 21 peter 40
4069 06 Aug 21 peter 41   Impl::Impl(Impl&& from)
4064 05 Aug 21 peter 42   {
4069 06 Aug 21 peter 43     reset();
4072 20 Aug 21 peter 44     move_data(std::move(from));
4064 05 Aug 21 peter 45   }
4064 05 Aug 21 peter 46
4064 05 Aug 21 peter 47
4069 06 Aug 21 peter 48   Impl& Impl::operator=(Impl&& rhs)
4069 06 Aug 21 peter 49   {
4069 06 Aug 21 peter 50     assert(!head_.parent_);
4069 06 Aug 21 peter 51     move_data(std::move(rhs));
4069 06 Aug 21 peter 52     assert(validate());
4069 06 Aug 21 peter 53     return *this;
4069 06 Aug 21 peter 54   }
4069 06 Aug 21 peter 55
4069 06 Aug 21 peter 56
4072 20 Aug 21 peter 57   bool Impl::empty(void) const
4072 20 Aug 21 peter 58   {
4072 20 Aug 21 peter 59     return !root_node();
4072 20 Aug 21 peter 60   }
4072 20 Aug 21 peter 61
4072 20 Aug 21 peter 62
4072 20 Aug 21 peter 63   size_t Impl::size(void) const
4072 20 Aug 21 peter 64   {
4072 20 Aug 21 peter 65     assert(head_.size_ > 0);
4072 20 Aug 21 peter 66     return head_.size_ - 1;
4072 20 Aug 21 peter 67   }
4072 20 Aug 21 peter 68
4072 20 Aug 21 peter 69
4064 05 Aug 21 peter 70   void Impl::move_data(Impl&& from)
4064 05 Aug 21 peter 71   {
4075 20 Aug 21 peter 72     assert(empty());
4072 20 Aug 21 peter 73
4064 05 Aug 21 peter 74     head_.parent_ = from.head_.parent_;
4064 05 Aug 21 peter 75     head_.left_ = from.head_.left_;
4072 20 Aug 21 peter 76     if (head_.left_) {
4072 20 Aug 21 peter 77       head_.left_->parent_ = &head_;
4072 20 Aug 21 peter 78       head_.right_ = from.head_.right_;
4079 26 Aug 21 peter 79       right_most_ = root_node()->right_most();
4072 20 Aug 21 peter 80     }
4079 26 Aug 21 peter 81     else {
4072 20 Aug 21 peter 82       head_.right_ = &head_;
4079 26 Aug 21 peter 83       right_most() = &head_;
4079 26 Aug 21 peter 84     }
4071 18 Aug 21 peter 85     head_.height_ = from.head_.height_;
4071 18 Aug 21 peter 86     head_.size_ = from.head_.size_;
4064 05 Aug 21 peter 87     from.reset();
4069 06 Aug 21 peter 88     assert(validate());
4064 05 Aug 21 peter 89   }
4064 05 Aug 21 peter 90
4064 05 Aug 21 peter 91
4070 09 Aug 21 peter 92   void Impl::relink(const NodeBase* node, NodeBase* child)
4070 09 Aug 21 peter 93   {
4070 09 Aug 21 peter 94     assert(node->parent_);
4070 09 Aug 21 peter 95     assert(node != &head_);
4070 09 Aug 21 peter 96     assert(child != &head_);
4070 09 Aug 21 peter 97
4070 09 Aug 21 peter 98     // make child the child of node's parent
4070 09 Aug 21 peter 99     if (node->is_left_node())
4070 09 Aug 21 peter 100       node->parent_->left_ = child;
4070 09 Aug 21 peter 101     else if (node->is_right_node())
4070 09 Aug 21 peter 102       node->parent_->right_ = child;
4070 09 Aug 21 peter 103
4070 09 Aug 21 peter 104     // make node's parent the parent of child
4070 09 Aug 21 peter 105     if (child)
4070 09 Aug 21 peter 106       child->parent_ = node->parent_;
4070 09 Aug 21 peter 107
4070 09 Aug 21 peter 108     // inherit the kids
4070 09 Aug 21 peter 109     if (child) {
4070 09 Aug 21 peter 110       if (node->left_ && node->left_!=child) {
4070 09 Aug 21 peter 111         assert(!child->left_);
4070 09 Aug 21 peter 112         child->left_ = node->left_;
4071 18 Aug 21 peter 113         if (node->left_)
4071 18 Aug 21 peter 114           node->left_->parent_ = child;
4070 09 Aug 21 peter 115       }
4070 09 Aug 21 peter 116       if (node->right_ && node->right_!=child) {
4070 09 Aug 21 peter 117         assert(!child->right_);
4070 09 Aug 21 peter 118         child->right_ = node->right_;
4071 18 Aug 21 peter 119         if (node->right_)
4071 18 Aug 21 peter 120           node->right_->parent_ = child;
4070 09 Aug 21 peter 121       }
4070 09 Aug 21 peter 122     }
4070 09 Aug 21 peter 123
4070 09 Aug 21 peter 124     // update pointer to left_most node
4079 26 Aug 21 peter 125     if (left_most() == node)
4079 26 Aug 21 peter 126       left_most() = child ? child : node->parent_;
4079 26 Aug 21 peter 127     if (right_most() == node)
4079 26 Aug 21 peter 128       right_most() = child ? child : node->parent_;
4070 09 Aug 21 peter 129     assert(child==nullptr || child->is_left_node() || child->is_right_node());
4070 09 Aug 21 peter 130   }
4070 09 Aug 21 peter 131
4070 09 Aug 21 peter 132
4071 18 Aug 21 peter 133   size_t Impl::ranking(const NodeBase* node) const
4071 18 Aug 21 peter 134   {
4072 20 Aug 21 peter 135     assert(node);
4071 18 Aug 21 peter 136     if (node->is_head_node())
4072 20 Aug 21 peter 137       return size();
4071 18 Aug 21 peter 138
4072 20 Aug 21 peter 139     assert(node->parent_);
4071 18 Aug 21 peter 140     // The rank of the parent is the sum of the rank of the
4071 18 Aug 21 peter 141     // left->child, the child itself, and the size of the child's
4071 18 Aug 21 peter 142     // right branch.
4071 18 Aug 21 peter 143     if (node->is_left_node())
4072 20 Aug 21 peter 144       return ranking(node->parent_) - (1 + ranking::size(node->right_));
4071 18 Aug 21 peter 145
4071 18 Aug 21 peter 146     // right node
4072 20 Aug 21 peter 147     return ranking(node->parent_) + 1 + ranking::size(node->left_);
4071 18 Aug 21 peter 148   }
4071 18 Aug 21 peter 149
4071 18 Aug 21 peter 150
4064 05 Aug 21 peter 151   void Impl::reset(void)
4064 05 Aug 21 peter 152   {
4064 05 Aug 21 peter 153     head_.parent_ = nullptr;
4072 20 Aug 21 peter 154     head_.left_ = nullptr;
4072 20 Aug 21 peter 155     head_.right_ = &head_; // most left node
4079 26 Aug 21 peter 156     right_most_ = &head_;
4072 20 Aug 21 peter 157     head_.update_height();
4072 20 Aug 21 peter 158     head_.update_size();
4064 05 Aug 21 peter 159     assert(validate());
4064 05 Aug 21 peter 160   }
4064 05 Aug 21 peter 161
4064 05 Aug 21 peter 162
4072 20 Aug 21 peter 163   void Impl::erase_and_rebalance(const NodeBase* node)
4072 20 Aug 21 peter 164   {
4072 20 Aug 21 peter 165     // two children
4072 20 Aug 21 peter 166     if (node->left_ && node->right_) {
4072 20 Aug 21 peter 167       // When node has two branches, we take the most leftmost node in
4072 20 Aug 21 peter 168       // the right branch and place in nodes place.
4072 20 Aug 21 peter 169       ranking::NodeBase* leftmost = node->right_->left_most();
4072 20 Aug 21 peter 170       assert(leftmost->left_ == nullptr);
4072 20 Aug 21 peter 171
4072 20 Aug 21 peter 172       // If the leftmost node has a kid, we need to relink the kid
4072 20 Aug 21 peter 173       // with its grand parent
4072 20 Aug 21 peter 174       if (leftmost->parent_ != node)
4072 20 Aug 21 peter 175         relink(leftmost, leftmost->right_);
4072 20 Aug 21 peter 176       relink(node, leftmost);
4072 20 Aug 21 peter 177       assert(leftmost->left_ == node->left_);
4072 20 Aug 21 peter 178       assert(!leftmost->left_ || leftmost->left_->parent_==leftmost);
4072 20 Aug 21 peter 179       leftmost->update_height();
4072 20 Aug 21 peter 180       leftmost->parent_->update_height_recursively();
4072 20 Aug 21 peter 181       leftmost->update_size();
4072 20 Aug 21 peter 182       leftmost->parent_->decrement_size();
4072 20 Aug 21 peter 183       erase_rebalance(leftmost);
4072 20 Aug 21 peter 184     }
4072 20 Aug 21 peter 185     else {
4072 20 Aug 21 peter 186       // single child node is simple, the child takes the node's place
4072 20 Aug 21 peter 187       relink(node, node->left_ ? node->left_ : node->right_);
4072 20 Aug 21 peter 188       node->parent_->decrement_size();
4072 20 Aug 21 peter 189       node->parent_->update_height_recursively();
4072 20 Aug 21 peter 190       erase_rebalance(node->parent_);
4072 20 Aug 21 peter 191     }
4072 20 Aug 21 peter 192   }
4072 20 Aug 21 peter 193
4072 20 Aug 21 peter 194
4072 20 Aug 21 peter 195   void Impl::insert_and_rebalance(std::unique_ptr<NodeBase>&& element,
4077 26 Aug 21 peter 196                                   NodeBase& parent, bool left)
4072 20 Aug 21 peter 197   {
4077 26 Aug 21 peter 198     NodeBase* child = nullptr;
4077 26 Aug 21 peter 199     if (left) {
4077 26 Aug 21 peter 200       parent.left_ = element.release();
4077 26 Aug 21 peter 201       child = parent.left_;
4077 26 Aug 21 peter 202       if (&parent == left_most())
4077 26 Aug 21 peter 203         left_most() = child;
4077 26 Aug 21 peter 204     }
4077 26 Aug 21 peter 205     else {
4077 26 Aug 21 peter 206       parent.right_ = element.release();
4077 26 Aug 21 peter 207       child = parent.right_;
4079 26 Aug 21 peter 208       if (&parent == right_most())
4079 26 Aug 21 peter 209         right_most() = child;
4077 26 Aug 21 peter 210     }
4077 26 Aug 21 peter 211
4072 20 Aug 21 peter 212     child->parent_ = &parent;
4072 20 Aug 21 peter 213     parent.increment_size();
4072 20 Aug 21 peter 214     parent.update_height_recursively();
4072 20 Aug 21 peter 215     insert_rebalance(&parent, child);
4072 20 Aug 21 peter 216   }
4072 20 Aug 21 peter 217
4072 20 Aug 21 peter 218
4072 20 Aug 21 peter 219   void Impl::erase_rebalance(NodeBase* node)
4072 20 Aug 21 peter 220   {
4072 20 Aug 21 peter 221     assert(node);
4072 20 Aug 21 peter 222     if (node->is_root_node())
4072 20 Aug 21 peter 223       return;
4072 20 Aug 21 peter 224
4072 20 Aug 21 peter 225     int balance = node->balance();
4072 20 Aug 21 peter 226
4072 20 Aug 21 peter 227     if (std::abs(balance) > 1) {
4072 20 Aug 21 peter 228       assert(0);
4072 20 Aug 21 peter 229     }
4072 20 Aug 21 peter 230
4072 20 Aug 21 peter 231     NodeBase* parent = node->parent_;
4072 20 Aug 21 peter 232     assert(parent);
4072 20 Aug 21 peter 233     erase_rebalance(parent);
4072 20 Aug 21 peter 234   }
4072 20 Aug 21 peter 235
4072 20 Aug 21 peter 236
4072 20 Aug 21 peter 237   void Impl::insert_rebalance(NodeBase* node, NodeBase* child)
4072 20 Aug 21 peter 238   {
4072 20 Aug 21 peter 239     assert(node);
4072 20 Aug 21 peter 240     assert(child);
4072 20 Aug 21 peter 241     assert(child->parent_ == node);
4072 20 Aug 21 peter 242     assert(child == node->left_ || child == node->right_);
4072 20 Aug 21 peter 243
4072 20 Aug 21 peter 244     NodeBase* parent = node->parent_;
4072 20 Aug 21 peter 245     assert(parent);
4072 20 Aug 21 peter 246     if (parent->is_head_node())
4072 20 Aug 21 peter 247       return;
4072 20 Aug 21 peter 248
4072 20 Aug 21 peter 249     // left height minus right height
4072 20 Aug 21 peter 250     int balance = parent->balance();
4072 20 Aug 21 peter 251
4072 20 Aug 21 peter 252     /*
4072 20 Aug 21 peter 253       If parent is unbalanced, we have four cases.
4072 20 Aug 21 peter 254
4072 20 Aug 21 peter 255       Below parent is denoted z
4072 20 Aug 21 peter 256       node is denoted y
4072 20 Aug 21 peter 257       child is denoted x
4072 20 Aug 21 peter 258
4200 19 Aug 22 peter 259       and all three are ancestors of the just inserted node.
4072 20 Aug 21 peter 260
4072 20 Aug 21 peter 261       a) Left Left Case
4072 20 Aug 21 peter 262
4072 20 Aug 21 peter 263       T1, T2, T3 and T4 are subtrees.
4072 20 Aug 21 peter 264             z                                      y
4072 20 Aug 21 peter 265            / \                                   /   \
4072 20 Aug 21 peter 266           y   T4      Right Rotate (z)          x      z
4072 20 Aug 21 peter 267          / \          - - - - - - - - ->      /  \    /  \
4072 20 Aug 21 peter 268         x   T3                               T1  T2  T3  T4
4072 20 Aug 21 peter 269        / \
4072 20 Aug 21 peter 270       T1  T2
4072 20 Aug 21 peter 271
4072 20 Aug 21 peter 272       b) Left Right Case
4072 20 Aug 21 peter 273
4072 20 Aug 21 peter 274             z                              z                           x
4072 20 Aug 21 peter 275            / \                            / \                        /   \
4072 20 Aug 21 peter 276           y   T4  Left Rotate (y)        x   T4  Right Rotate(z)    y     z
4072 20 Aug 21 peter 277          / \      - - - - - - - - ->    / \     - - - - - - - ->   / \   / \
4072 20 Aug 21 peter 278         T1  x                          y   T3                     T1 T2 T3 T4
4072 20 Aug 21 peter 279            / \                        / \
4072 20 Aug 21 peter 280           T2 T3                     T1   T2
4072 20 Aug 21 peter 281
4072 20 Aug 21 peter 282       c) Right Right Case
4072 20 Aug 21 peter 283
4072 20 Aug 21 peter 284           z                              y
4072 20 Aug 21 peter 285          / \                            /  \
4072 20 Aug 21 peter 286         T1  y     Left Rotate(z)       z    x
4072 20 Aug 21 peter 287            / \    - - - - - - - ->    / \  / \
4072 20 Aug 21 peter 288           T2  x                      T1 T2T3 T4
4072 20 Aug 21 peter 289              / \
4072 20 Aug 21 peter 290              T3 T4
4072 20 Aug 21 peter 291
4072 20 Aug 21 peter 292       d) Right Left Case
4072 20 Aug 21 peter 293
4072 20 Aug 21 peter 294         z                            z                            x
4072 20 Aug 21 peter 295        / \                          / \                         /   \
4072 20 Aug 21 peter 296       T1  y   Right Rotate (y)    T1   x    Left Rotate(z)     z     y
4072 20 Aug 21 peter 297          / \  - - - - - - - - ->      / \   - - - - - - - ->  / \   / \
4072 20 Aug 21 peter 298         x   T4                      T2   y                  T1  T2 T3  T4
4072 20 Aug 21 peter 299        / \                              / \
4072 20 Aug 21 peter 300       T2  T3                           T3  T4
4072 20 Aug 21 peter 301     */
4072 20 Aug 21 peter 302
4072 20 Aug 21 peter 303     if (balance < -1) {
4072 20 Aug 21 peter 304       assert(height(parent->right_) > height(parent->left_));
4072 20 Aug 21 peter 305       assert(parent->right_ == node);
4072 20 Aug 21 peter 306       // right right case
4072 20 Aug 21 peter 307       if (node->right_ == child) {
4072 20 Aug 21 peter 308         left_rotate(parent);
4072 20 Aug 21 peter 309         return;
4072 20 Aug 21 peter 310       }
4072 20 Aug 21 peter 311       // right left case
4072 20 Aug 21 peter 312       assert(node->left_ == child);
4072 20 Aug 21 peter 313       right_rotate(node);
4072 20 Aug 21 peter 314       left_rotate(parent);
4072 20 Aug 21 peter 315       return;
4072 20 Aug 21 peter 316     }
4072 20 Aug 21 peter 317     else if (balance > 1) {
4072 20 Aug 21 peter 318       // left right case
4072 20 Aug 21 peter 319       if (node->right_ == child) {
4072 20 Aug 21 peter 320         left_rotate(node);
4072 20 Aug 21 peter 321         right_rotate(parent);
4072 20 Aug 21 peter 322         return;
4072 20 Aug 21 peter 323       }
4072 20 Aug 21 peter 324       // left left case
4072 20 Aug 21 peter 325       assert(node->left_ == child);
4072 20 Aug 21 peter 326       right_rotate(parent);
4072 20 Aug 21 peter 327       return;
4072 20 Aug 21 peter 328     }
4072 20 Aug 21 peter 329
4072 20 Aug 21 peter 330     assert(parent->parent_);
4072 20 Aug 21 peter 331     insert_rebalance(parent, node);
4072 20 Aug 21 peter 332   }
4072 20 Aug 21 peter 333
4072 20 Aug 21 peter 334
4072 20 Aug 21 peter 335   NodeBase* Impl::left_rotate(NodeBase* x)
4072 20 Aug 21 peter 336   {
4072 20 Aug 21 peter 337     assert(x);
4072 20 Aug 21 peter 338     NodeBase* y = x->right_;
4072 20 Aug 21 peter 339     assert(y);
4072 20 Aug 21 peter 340     NodeBase* T2 = y->left_;
4072 20 Aug 21 peter 341
4072 20 Aug 21 peter 342     // rotate
4072 20 Aug 21 peter 343     if (x->is_left_node())
4072 20 Aug 21 peter 344       x->parent_->left_ = y;
4072 20 Aug 21 peter 345     else {
4072 20 Aug 21 peter 346       assert(x->is_right_node());
4072 20 Aug 21 peter 347       x->parent_->right_ = y;
4072 20 Aug 21 peter 348     }
4072 20 Aug 21 peter 349     y->parent_ = x->parent_;
4072 20 Aug 21 peter 350
4072 20 Aug 21 peter 351     y->left_ = x;
4072 20 Aug 21 peter 352     x->parent_ = y;
4072 20 Aug 21 peter 353
4072 20 Aug 21 peter 354     x->right_ = T2;
4072 20 Aug 21 peter 355     if (T2)
4072 20 Aug 21 peter 356       T2->parent_ = x;
4072 20 Aug 21 peter 357
4072 20 Aug 21 peter 358     // update height - always update from leaf and to root
4072 20 Aug 21 peter 359     x->update_height();
4072 20 Aug 21 peter 360     y->update_height();
4072 20 Aug 21 peter 361     assert(y->parent_);
4072 20 Aug 21 peter 362     y->parent_->update_height_recursively();
4072 20 Aug 21 peter 363
4072 20 Aug 21 peter 364     // update size
4072 20 Aug 21 peter 365     x->update_size();
4072 20 Aug 21 peter 366     y->update_size();
4072 20 Aug 21 peter 367
4072 20 Aug 21 peter 368     return y;
4072 20 Aug 21 peter 369   }
4072 20 Aug 21 peter 370
4072 20 Aug 21 peter 371
4072 20 Aug 21 peter 372   NodeBase* Impl::right_rotate(NodeBase* y)
4072 20 Aug 21 peter 373   {
4072 20 Aug 21 peter 374     NodeBase* x = y->left_;
4072 20 Aug 21 peter 375     assert(x);
4072 20 Aug 21 peter 376     NodeBase* T2 = x->right_;
4072 20 Aug 21 peter 377
4072 20 Aug 21 peter 378     // rotate
4072 20 Aug 21 peter 379     if (y->is_left_node())
4072 20 Aug 21 peter 380       y->parent_->left_ = x;
4072 20 Aug 21 peter 381     else {
4072 20 Aug 21 peter 382       assert(y->is_right_node());
4072 20 Aug 21 peter 383       y->parent_->right_ = x;
4072 20 Aug 21 peter 384     }
4072 20 Aug 21 peter 385     x->parent_ = y->parent_;
4072 20 Aug 21 peter 386
4072 20 Aug 21 peter 387     x->right_ = y;
4072 20 Aug 21 peter 388     y->parent_ = x;
4072 20 Aug 21 peter 389
4072 20 Aug 21 peter 390     y->left_ = T2;
4072 20 Aug 21 peter 391     if (T2)
4072 20 Aug 21 peter 392       T2->parent_ = y;
4072 20 Aug 21 peter 393
4072 20 Aug 21 peter 394     // update height
4072 20 Aug 21 peter 395     y->update_height();
4072 20 Aug 21 peter 396     x->update_height();
4072 20 Aug 21 peter 397     assert(x->parent_);
4072 20 Aug 21 peter 398     x->parent_->update_height_recursively();
4072 20 Aug 21 peter 399
4072 20 Aug 21 peter 400     // update size
4072 20 Aug 21 peter 401     y->update_size();
4072 20 Aug 21 peter 402     x->update_size();
4072 20 Aug 21 peter 403
4072 20 Aug 21 peter 404     return x;
4072 20 Aug 21 peter 405   }
4072 20 Aug 21 peter 406
4072 20 Aug 21 peter 407
4064 05 Aug 21 peter 408   bool Impl::validate(void) const
4064 05 Aug 21 peter 409   {
4072 20 Aug 21 peter 410 #ifdef NDEBUG
4072 20 Aug 21 peter 411     return true;
4072 20 Aug 21 peter 412 #else
4072 20 Aug 21 peter 413     if (!head_.validate(true)) {
4072 20 Aug 21 peter 414       std::cerr << "Impl: head failed\n";
4072 20 Aug 21 peter 415       return false;
4064 05 Aug 21 peter 416     }
4072 20 Aug 21 peter 417     assert(left_most() == head_.left_most());
4072 20 Aug 21 peter 418
4072 20 Aug 21 peter 419     if (root_node()) {
4072 20 Aug 21 peter 420       if (root_node()->is_left_node() == false) {
4072 20 Aug 21 peter 421         std::cerr << "error: root is not a left node\n";
4064 05 Aug 21 peter 422         return false;
4064 05 Aug 21 peter 423       }
4072 20 Aug 21 peter 424       if (root_node()->is_right_node()) {
4072 20 Aug 21 peter 425         std::cerr << "error: root is a right node\n";
4072 20 Aug 21 peter 426         return false;
4072 20 Aug 21 peter 427       }
4064 05 Aug 21 peter 428     }
4064 05 Aug 21 peter 429
4072 20 Aug 21 peter 430     if (!validate(root_node())) {
4072 20 Aug 21 peter 431       std::cerr << "Impl: validate(root_node()) failed\n";
4072 20 Aug 21 peter 432       return false;
4072 20 Aug 21 peter 433     }
4072 20 Aug 21 peter 434
4079 26 Aug 21 peter 435     if (root_node()) {
4079 26 Aug 21 peter 436       if (left_most() != root_node()->left_most()) {
4079 26 Aug 21 peter 437         std::cerr << "leftmost incorrect\n";
4079 26 Aug 21 peter 438         return false;
4079 26 Aug 21 peter 439       }
4079 26 Aug 21 peter 440       if (right_most() != root_node()->right_most()) {
4079 26 Aug 21 peter 441         std::cerr << "rightmost incorrect\n";
4079 26 Aug 21 peter 442         return false;
4079 26 Aug 21 peter 443       }
4079 26 Aug 21 peter 444     }
4072 20 Aug 21 peter 445
4079 26 Aug 21 peter 446
4072 20 Aug 21 peter 447     /*
4072 20 Aug 21 peter 448     if (root_node()) {
4072 20 Aug 21 peter 449       if (root_node()->left_most() != head_.right_) {
4072 20 Aug 21 peter 450         std::cerr << "head_.right incorrect\n";
4070 09 Aug 21 peter 451         return false;
4070 09 Aug 21 peter 452       }
4072 20 Aug 21 peter 453       if (!root_node()->recursive_validate())
4064 05 Aug 21 peter 454         return false;
4064 05 Aug 21 peter 455     }
4064 05 Aug 21 peter 456     else if (!head_.validate())
4064 05 Aug 21 peter 457       return false;
4072 20 Aug 21 peter 458     */
4072 20 Aug 21 peter 459     return true;
4072 20 Aug 21 peter 460 #endif
4072 20 Aug 21 peter 461   }
4070 09 Aug 21 peter 462
4072 20 Aug 21 peter 463
4072 20 Aug 21 peter 464   bool Impl::validate(const NodeBase* node) const
4072 20 Aug 21 peter 465   {
4072 20 Aug 21 peter 466     if (node == nullptr)
4072 20 Aug 21 peter 467       return true;
4072 20 Aug 21 peter 468     node->validate();
4072 20 Aug 21 peter 469     validate(node->left_);
4072 20 Aug 21 peter 470     validate(node->right_);
4064 05 Aug 21 peter 471     return true;
4064 05 Aug 21 peter 472   }
4064 05 Aug 21 peter 473
4072 20 Aug 21 peter 474
4072 20 Aug 21 peter 475   NodeBase*& Impl::left_most(void)
4072 20 Aug 21 peter 476   {
4072 20 Aug 21 peter 477     return head_.right_;
4072 20 Aug 21 peter 478   }
4072 20 Aug 21 peter 479
4072 20 Aug 21 peter 480
4072 20 Aug 21 peter 481   const NodeBase* Impl::left_most(void) const
4072 20 Aug 21 peter 482   {
4072 20 Aug 21 peter 483     return head_.right_;
4072 20 Aug 21 peter 484   }
4072 20 Aug 21 peter 485
4072 20 Aug 21 peter 486
4079 26 Aug 21 peter 487   NodeBase*& Impl::right_most(void)
4077 26 Aug 21 peter 488   {
4079 26 Aug 21 peter 489     return right_most_;
4077 26 Aug 21 peter 490   }
4077 26 Aug 21 peter 491
4077 26 Aug 21 peter 492
4077 26 Aug 21 peter 493   const NodeBase* Impl::right_most(void) const
4077 26 Aug 21 peter 494   {
4079 26 Aug 21 peter 495     return right_most_;
4077 26 Aug 21 peter 496   }
4077 26 Aug 21 peter 497
4077 26 Aug 21 peter 498
4072 20 Aug 21 peter 499   NodeBase*& Impl::root_node(void)
4072 20 Aug 21 peter 500   {
4072 20 Aug 21 peter 501     return head_.left_;
4072 20 Aug 21 peter 502   }
4072 20 Aug 21 peter 503
4072 20 Aug 21 peter 504
4072 20 Aug 21 peter 505   const NodeBase* Impl::root_node(void) const
4072 20 Aug 21 peter 506   {
4072 20 Aug 21 peter 507     return head_.left_;
4072 20 Aug 21 peter 508   }
4072 20 Aug 21 peter 509
4072 20 Aug 21 peter 510
4064 05 Aug 21 peter 511 }
4064 05 Aug 21 peter 512 }}} // of namespace utility, yat, and theplu

Generated on Sat Oct 14 02:24:14 2023 (UTC) by svndigest 0.11.2pre (dev build 1672)