yat/utility/ranking/NodeBase.cc

Code
Comments
Other
Rev Date Author Line
4082 27 Aug 21 peter 1 // $Id$
4082 27 Aug 21 peter 2
4082 27 Aug 21 peter 3 /*
4082 27 Aug 21 peter 4   Copyright (C) 2021 Peter Johansson
4082 27 Aug 21 peter 5
4082 27 Aug 21 peter 6   This file is part of the yat library, http://dev.thep.lu.se/yat
4082 27 Aug 21 peter 7
4082 27 Aug 21 peter 8   The yat library is free software; you can redistribute it and/or
4082 27 Aug 21 peter 9   modify it under the terms of the GNU General Public License as
4082 27 Aug 21 peter 10   published by the Free Software Foundation; either version 3 of the
4082 27 Aug 21 peter 11   License, or (at your option) any later version.
4082 27 Aug 21 peter 12
4082 27 Aug 21 peter 13   The yat library is distributed in the hope that it will be useful,
4082 27 Aug 21 peter 14   but WITHOUT ANY WARRANTY; without even the implied warranty of
4082 27 Aug 21 peter 15   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
4082 27 Aug 21 peter 16   General Public License for more details.
4082 27 Aug 21 peter 17
4082 27 Aug 21 peter 18   You should have received a copy of the GNU General Public License
4082 27 Aug 21 peter 19   along with yat. If not, see <http://www.gnu.org/licenses/>.
4082 27 Aug 21 peter 20 */
4082 27 Aug 21 peter 21
4082 27 Aug 21 peter 22 #include <config.h>
4082 27 Aug 21 peter 23
4082 27 Aug 21 peter 24 #include "NodeBase.h"
4082 27 Aug 21 peter 25
4082 27 Aug 21 peter 26 #include <cassert>
4082 27 Aug 21 peter 27 #include <cmath>
4082 27 Aug 21 peter 28 #include <cstddef>
4082 27 Aug 21 peter 29 #include <iostream>
4082 27 Aug 21 peter 30
4082 27 Aug 21 peter 31 namespace theplu {
4082 27 Aug 21 peter 32 namespace yat {
4082 27 Aug 21 peter 33 namespace utility {
4082 27 Aug 21 peter 34 namespace ranking {
4082 27 Aug 21 peter 35
4082 27 Aug 21 peter 36   NodeBase::NodeBase(void)
4082 27 Aug 21 peter 37     : parent_(nullptr), left_(nullptr), right_(nullptr),
4082 27 Aug 21 peter 38       height_(1), size_(1)
4082 27 Aug 21 peter 39   {
4082 27 Aug 21 peter 40   }
4082 27 Aug 21 peter 41
4082 27 Aug 21 peter 42
4082 27 Aug 21 peter 43   NodeBase::~NodeBase(void)
4082 27 Aug 21 peter 44   {
4082 27 Aug 21 peter 45   }
4082 27 Aug 21 peter 46
4082 27 Aug 21 peter 47
4082 27 Aug 21 peter 48   int NodeBase::balance(void) const
4082 27 Aug 21 peter 49   {
4082 27 Aug 21 peter 50     return static_cast<int>(height(left_))-static_cast<int>(height(right_));
4082 27 Aug 21 peter 51   }
4082 27 Aug 21 peter 52
4082 27 Aug 21 peter 53
4082 27 Aug 21 peter 54   int NodeBase::generation(void) const
4082 27 Aug 21 peter 55   {
4082 27 Aug 21 peter 56     if (parent_)
4082 27 Aug 21 peter 57       return 1 + parent_->generation();
4082 27 Aug 21 peter 58     return 0;
4082 27 Aug 21 peter 59   }
4082 27 Aug 21 peter 60
4082 27 Aug 21 peter 61
4082 27 Aug 21 peter 62   void NodeBase::increment_size(void)
4082 27 Aug 21 peter 63   {
4082 27 Aug 21 peter 64     ++size_;
4082 27 Aug 21 peter 65     if (parent_)
4082 27 Aug 21 peter 66       parent_->increment_size();
4082 27 Aug 21 peter 67   }
4082 27 Aug 21 peter 68
4082 27 Aug 21 peter 69
4082 27 Aug 21 peter 70   void NodeBase::decrement_size(void)
4082 27 Aug 21 peter 71   {
4082 27 Aug 21 peter 72     assert(size_ > 0);
4082 27 Aug 21 peter 73     --size_;
4082 27 Aug 21 peter 74     if (parent_)
4082 27 Aug 21 peter 75       parent_->decrement_size();
4082 27 Aug 21 peter 76   }
4082 27 Aug 21 peter 77
4082 27 Aug 21 peter 78
4082 27 Aug 21 peter 79   bool NodeBase::is_head_node(void) const
4082 27 Aug 21 peter 80   {
4082 27 Aug 21 peter 81     return !parent_;
4082 27 Aug 21 peter 82   }
4082 27 Aug 21 peter 83
4082 27 Aug 21 peter 84
4082 27 Aug 21 peter 85   bool NodeBase::is_left_node(void) const
4082 27 Aug 21 peter 86   {
4082 27 Aug 21 peter 87     return parent_ && this == parent_->left_;
4082 27 Aug 21 peter 88   }
4082 27 Aug 21 peter 89
4082 27 Aug 21 peter 90
4082 27 Aug 21 peter 91   bool NodeBase::is_right_node(void) const
4082 27 Aug 21 peter 92   {
4082 27 Aug 21 peter 93     return parent_ && this == parent_->right_ && !parent_->is_head_node();
4082 27 Aug 21 peter 94   }
4082 27 Aug 21 peter 95
4082 27 Aug 21 peter 96
4082 27 Aug 21 peter 97   bool NodeBase::is_root_node(void) const
4082 27 Aug 21 peter 98   {
4082 27 Aug 21 peter 99     return parent_ && parent_->is_head_node();
4082 27 Aug 21 peter 100   }
4082 27 Aug 21 peter 101
4082 27 Aug 21 peter 102
4082 27 Aug 21 peter 103   NodeBase* NodeBase::left_most(void)
4082 27 Aug 21 peter 104   {
4082 27 Aug 21 peter 105     NodeBase* node = this;
4082 27 Aug 21 peter 106     while (node->left_)
4082 27 Aug 21 peter 107       node = node->left_;
4082 27 Aug 21 peter 108     return node;
4082 27 Aug 21 peter 109   }
4082 27 Aug 21 peter 110
4082 27 Aug 21 peter 111
4082 27 Aug 21 peter 112   NodeBase* NodeBase::right_most(void)
4082 27 Aug 21 peter 113   {
4082 27 Aug 21 peter 114     NodeBase* node = this;
4082 27 Aug 21 peter 115     while (node->right_)
4082 27 Aug 21 peter 116       node = node->right_;
4082 27 Aug 21 peter 117     return node;
4082 27 Aug 21 peter 118   }
4082 27 Aug 21 peter 119
4082 27 Aug 21 peter 120
4082 27 Aug 21 peter 121   const NodeBase* NodeBase::left_most(void) const
4082 27 Aug 21 peter 122   {
4082 27 Aug 21 peter 123     const NodeBase* node = this;
4082 27 Aug 21 peter 124     while (node->left_)
4082 27 Aug 21 peter 125       node = node->left_;
4082 27 Aug 21 peter 126     return node;
4082 27 Aug 21 peter 127   }
4082 27 Aug 21 peter 128
4082 27 Aug 21 peter 129
4082 27 Aug 21 peter 130   const NodeBase* NodeBase::right_most(void) const
4082 27 Aug 21 peter 131   {
4082 27 Aug 21 peter 132     const NodeBase* node = this;
4082 27 Aug 21 peter 133     while (node->right_)
4082 27 Aug 21 peter 134       node = node->right_;
4082 27 Aug 21 peter 135     return node;
4082 27 Aug 21 peter 136   }
4082 27 Aug 21 peter 137
4082 27 Aug 21 peter 138
4082 27 Aug 21 peter 139   void NodeBase::update_height(void)
4082 27 Aug 21 peter 140   {
4082 27 Aug 21 peter 141     if (is_head_node())
4082 27 Aug 21 peter 142       height_ = height(left_) + 1;
4082 27 Aug 21 peter 143     else
4082 27 Aug 21 peter 144       height_ = std::max(height(left_), height(right_)) + 1;
4082 27 Aug 21 peter 145   }
4082 27 Aug 21 peter 146
4082 27 Aug 21 peter 147
4082 27 Aug 21 peter 148   void NodeBase::update_height_recursively(void)
4082 27 Aug 21 peter 149   {
4082 27 Aug 21 peter 150     if (is_head_node()) {
4082 27 Aug 21 peter 151       height_ = height(left_) + 1;
4082 27 Aug 21 peter 152       return;
4082 27 Aug 21 peter 153     }
4082 27 Aug 21 peter 154     unsigned int h = std::max(height(left_), height(right_)) + 1;
4082 27 Aug 21 peter 155     if (height_ != h) {
4082 27 Aug 21 peter 156       height_ = h;
4082 27 Aug 21 peter 157       if (parent_)
4082 27 Aug 21 peter 158         parent_->update_height_recursively();
4082 27 Aug 21 peter 159     }
4082 27 Aug 21 peter 160   }
4082 27 Aug 21 peter 161
4082 27 Aug 21 peter 162
4082 27 Aug 21 peter 163   void NodeBase::update_size(void)
4082 27 Aug 21 peter 164   {
4082 27 Aug 21 peter 165     if (is_head_node())
4082 27 Aug 21 peter 166       size_ = 1 + size(left_);
4082 27 Aug 21 peter 167     else
4082 27 Aug 21 peter 168       size_ = 1 + size(left_) + size(right_);
4082 27 Aug 21 peter 169   }
4082 27 Aug 21 peter 170
4082 27 Aug 21 peter 171
4082 27 Aug 21 peter 172   bool NodeBase::validate(bool head) const
4082 27 Aug 21 peter 173   {
4082 27 Aug 21 peter 174     bool result = true;
4082 27 Aug 21 peter 175     if (head)
4082 27 Aug 21 peter 176       assert(is_head_node());
4082 27 Aug 21 peter 177
4082 27 Aug 21 peter 178     if (this == left_) {
4082 27 Aug 21 peter 179       std::cerr << "left == this\n";
4082 27 Aug 21 peter 180       result = false;
4082 27 Aug 21 peter 181     }
4082 27 Aug 21 peter 182
4082 27 Aug 21 peter 183     // head_.right_ is a shortcut to the leftmost node in the tree,
4082 27 Aug 21 peter 184     // but that node si typically not a proper child node of head, so
4082 27 Aug 21 peter 185     // some tests are not relevant.
4082 27 Aug 21 peter 186     if (!head) {
4082 27 Aug 21 peter 187       if (this == right_) {
4082 27 Aug 21 peter 188         std::cerr << "right == this\n";
4082 27 Aug 21 peter 189         result = false;
4082 27 Aug 21 peter 190       }
4082 27 Aug 21 peter 191
4082 27 Aug 21 peter 192       if (!is_left_node() && !is_right_node()) {
4082 27 Aug 21 peter 193         std::cerr << "node is neither left nor right node\n";
4082 27 Aug 21 peter 194         result = false;
4082 27 Aug 21 peter 195       }
4082 27 Aug 21 peter 196
4082 27 Aug 21 peter 197       assert(parent_);
4082 27 Aug 21 peter 198       if (this!=parent_->left_ && this!=parent_->right_) {
4082 27 Aug 21 peter 199         std::cerr << "node is not parent's child\n";
4082 27 Aug 21 peter 200         result = false;
4082 27 Aug 21 peter 201       }
4082 27 Aug 21 peter 202
4082 27 Aug 21 peter 203       if (right_) {
4082 27 Aug 21 peter 204         if (!right_->is_right_node()) {
4082 27 Aug 21 peter 205           std::cerr << "->right_ is not a right node\n";
4082 27 Aug 21 peter 206           result = false;
4082 27 Aug 21 peter 207         }
4082 27 Aug 21 peter 208         assert(this == right_->parent_);
4082 27 Aug 21 peter 209       }
4082 27 Aug 21 peter 210     }
4082 27 Aug 21 peter 211
4082 27 Aug 21 peter 212     if (left_) {
4082 27 Aug 21 peter 213       if (!left_->is_left_node()) {
4082 27 Aug 21 peter 214         std::cerr << "->left_ is not a left node\n";
4082 27 Aug 21 peter 215         result = false;
4082 27 Aug 21 peter 216       }
4082 27 Aug 21 peter 217       assert(this == left_->parent_);
4082 27 Aug 21 peter 218     }
4082 27 Aug 21 peter 219
4082 27 Aug 21 peter 220     if (head) {
4082 27 Aug 21 peter 221       if (size_ != size(left_) + 1) {
4082 27 Aug 21 peter 222         result = false;
4082 27 Aug 21 peter 223         std::cerr << "incorrect size: " << size_ << " for head node; "
4082 27 Aug 21 peter 224                   << "left size: " << size(left_) << "\n";
4082 27 Aug 21 peter 225       }
4082 27 Aug 21 peter 226
4082 27 Aug 21 peter 227       if (height_ != height(left_)+1) {
4082 27 Aug 21 peter 228         result = false;
4082 27 Aug 21 peter 229         std::cerr << "incorrect height: " << height_ << " for head; "
4082 27 Aug 21 peter 230                   << "left height: " << height(left_) << "\n";
4082 27 Aug 21 peter 231       }
4082 27 Aug 21 peter 232     }
4082 27 Aug 21 peter 233     else {
4082 27 Aug 21 peter 234       if (size_ != size(left_) + size(right_) + 1) {
4082 27 Aug 21 peter 235         result = false;
4082 27 Aug 21 peter 236         std::cerr << "incorrect size: " << size_ << " for " << this << "; "
4082 27 Aug 21 peter 237                   << "left size: " << size(left_) << "; "
4082 27 Aug 21 peter 238                   << "right size: " << size(right_) << "\n";
4082 27 Aug 21 peter 239       }
4082 27 Aug 21 peter 240
4082 27 Aug 21 peter 241       if (height_ != std::max(height(left_), height(right_))+1) {
4082 27 Aug 21 peter 242         result = false;
4082 27 Aug 21 peter 243         std::cerr << "incorrect height: " << height_ << " for " << this << "; "
4082 27 Aug 21 peter 244                   << "left height: " << height(left_) << "; "
4082 27 Aug 21 peter 245                   << "right height: " << height(right_) << "\n";
4082 27 Aug 21 peter 246       }
4082 27 Aug 21 peter 247
4082 27 Aug 21 peter 248       if (std::abs(balance())>1) {
4082 27 Aug 21 peter 249         result = false;
4082 27 Aug 21 peter 250         std::cerr << "node " << this << " is unbalanced\n"
4082 27 Aug 21 peter 251                   << "left height: " << height(left_) << "; "
4082 27 Aug 21 peter 252                   << "right height: " << height(right_) << "\n";
4082 27 Aug 21 peter 253       }
4082 27 Aug 21 peter 254     }
4082 27 Aug 21 peter 255     return result;
4082 27 Aug 21 peter 256   }
4082 27 Aug 21 peter 257
4082 27 Aug 21 peter 258
4082 27 Aug 21 peter 259   size_t height(const NodeBase* node)
4082 27 Aug 21 peter 260   {
4082 27 Aug 21 peter 261     return node ? node->height_ : 0;
4082 27 Aug 21 peter 262   }
4082 27 Aug 21 peter 263
4082 27 Aug 21 peter 264
4082 27 Aug 21 peter 265   size_t size(const NodeBase* node)
4082 27 Aug 21 peter 266   {
4082 27 Aug 21 peter 267     return node ? node->size_ : 0;
4082 27 Aug 21 peter 268   }
4082 27 Aug 21 peter 269
4082 27 Aug 21 peter 270 }
4082 27 Aug 21 peter 271 }}} // of namespace utility, yat, and theplu

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