Changeset 4072


Ignore:
Timestamp:
Aug 20, 2021, 7:40:18 AM (4 months ago)
Author:
Peter
Message:

rebalance tree after insertion/deletion in case it's needed; moved the head node from being a child of the root to now be the parent of the root.

Location:
branches/kendall-score
Files:
6 edited

Legend:

Unmodified
Added
Removed
  • branches/kendall-score/test/ranking.cc

    r4070 r4072  
    1818*/
    1919
     20#define YAT_DEBUG_RANKING 1
     21
    2022#include <config.h>
    2123
    2224#include "Suite.h"
    23 
    24 #define YAT_DEBUG_RANKING 1
    2525
    2626#include "yat/utility/Ranking.h"
     
    4949  }
    5050
    51   suite.out() << "::insert\n";
     51  suite.out() << "::insert 0\n";
    5252  ranking.insert(0);
    53   suite.out() << "::insert\n";
     53  suite.out() << "::insert 1\n";
    5454  ranking.insert(1);
    55   suite.out() << "::insert\n";
     55  suite.out() << "::insert 2\n";
    5656  ranking.insert(2);
    57   suite.out() << "::insert\n";
     57  suite.out() << "::insert 1\n";
    5858  ranking.insert(1);
    5959  if (ranking.size() != 4) {
  • branches/kendall-score/yat/utility/Ranking.h

    r4071 r4072  
    105105    iterator begin(void)
    106106    {
    107       return iterator(left_most());
     107      return iterator(impl_.left_most());
    108108    }
    109109
     
    123123    const_iterator cbegin(void) const
    124124    {
    125       return const_iterator(left_most());
     125      return const_iterator(impl_.left_most());
    126126    }
    127127
     
    213213    {
    214214      if (size()) {
    215         YAT_ASSERT(first_node() != &impl_.head_);
    216         erase(first_node());
     215        YAT_ASSERT(root_node() != head_node());
     216        erase(root_node());
    217217      }
    218218      impl_.reset();
     
    234234    bool empty(void) const
    235235    {
    236       return root_node() == nullptr;
     236      return impl_.empty();
    237237    }
    238238
     
    326326      if (empty())
    327327        return cend();
    328       return lower_bound(first_node(), last_node(), x);
     328      return lower_bound(root_node(), head_node(), x);
    329329    }
    330330
     
    337337      if (empty())
    338338        return cend();
    339       return upper_bound(first_node(), last_node(), x);
     339      return upper_bound(root_node(), head_node(), x);
    340340    }
    341341
     
    346346    size_t ranking(const_iterator it) const
    347347    {
     348      YAT_ASSERT(it.node_);
    348349      return impl_.ranking(it.node_);
    349350    }
     
    355356    size_t size(void) const
    356357    {
    357       return root_node() ? root_node()->size_ : 0;
     358      return impl_.size();
    358359    }
    359360
     
    373374        else
    374375          os << "H";
     376        os << ", H=" << ranking::height(p) << ", S=" << ranking::size(p);
    375377        os << ":   "
    376                   << p->parent_ << " "
    377                   << p << " "
    378                   << p->left_ << " "
    379                   << p->right_ << "\n";
     378           << p->parent_ << " "
     379           << p << " "
     380           << p->left_ << " "
     381           << p->right_ << "\n";
    380382        if (p->is_head_node()==false) {
    381383          print(p->left_, os);
     
    403405       Create a copy of root and return it
    404406     */
    405     ranking::NodeValue<T>*
    406     copy(const ranking::NodeValue<T>* root, ranking::NodeBase* h) const;
     407    ranking::NodeValue<T>* copy(const ranking::NodeValue<T>* root) const;
    407408
    408409    /**
     
    412413
    413414    // return the root node
    414     const ranking::NodeValue<T>* first_node(void) const
    415     {
    416       YAT_ASSERT(impl_.head_.parent_);
    417       return static_cast<const ranking::NodeValue<T>*>(impl_.head_.parent_);
    418     }
    419 
    420 
    421     ranking::NodeValue<T>* first_node(void)
    422     {
    423       YAT_ASSERT(impl_.head_.parent_);
    424       return static_cast<ranking::NodeValue<T>*>(impl_.head_.parent_);
    425     }
    426 
    427 
    428     const ranking::NodeBase* last_node(void) const
     415    const ranking::NodeValue<T>* root_node(void) const
     416    {
     417      return static_cast<const ranking::NodeValue<T>*>(impl_.root_node());
     418    }
     419
     420
     421    ranking::NodeValue<T>* root_node(void)
     422    {
     423      return static_cast<ranking::NodeValue<T>*>(impl_.root_node());
     424    }
     425
     426
     427    const ranking::NodeBase* head_node(void) const
    429428    {
    430429      return &impl_.head_;
     
    432431
    433432
    434     ranking::NodeBase* last_node(void)
     433    ranking::NodeBase* head_node(void)
    435434    {
    436435      return &impl_.head_;
     
    490489    {
    491490      iterator result(element.get());
     491
    492492      if (empty()) {
    493         YAT_ASSERT(root_node() == nullptr);
    494         root_node() = element.release();
    495         root_node()->right_ = &impl_.head_;
    496         root_node()->height_ = 1;
    497         root_node()->size_ = 1;
    498         impl_.head_.left_ = root_node();
    499 
    500         YAT_ASSERT(root_node()->validate());
    501         YAT_ASSERT(impl_.head_.validate());
     493        element->parent_ = &impl_.head_;
     494        impl_.root_node() = element.release();
     495        impl_.head_.left_ = impl_.root_node();
     496        impl_.head_.right_ = impl_.root_node();
     497        impl_.head_.update_height();
     498        impl_.head_.update_size();
     499
     500        YAT_ASSERT(impl_.root_node()->parent_);
     501        YAT_ASSERT(impl_.root_node()->parent_ == &impl_.head_);
     502        YAT_ASSERT(impl_.root_node()->is_left_node());
     503
    502504        YAT_ASSERT(validate());
    503505        return result;
    504506      }
    505507
    506       ranking::NodeBase* x = root_node();
     508      ranking::NodeBase* x = impl_.root_node();
    507509      YAT_ASSERT(x);
    508510      YAT_ASSERT(!x->is_head_node());
    509511
    510       // element right of root
    511       if (!compare_(element->value(), value(x))) {
    512         // make new root parent of head
    513         impl_.head_.parent_ = element.release();
    514         impl_.head_.parent_->right_ = &impl_.head_;
    515 
    516         // make old root and left child of new root
    517         x->right_ = nullptr;
    518         impl_.head_.parent_->left_ = x;
    519         x->parent_ = impl_.head_.parent_;
    520         YAT_ASSERT(x->size_ > 0);
    521 
    522         impl_.head_.parent_->size_ = x->size_ + 1;
    523         impl_.head_.parent_->height_ = x->height_ + 1;
    524 
    525         YAT_ASSERT(x->validate());
    526         YAT_ASSERT(impl_.head_.parent_);
    527         YAT_ASSERT(impl_.head_.parent_->validate());
    528         YAT_ASSERT(impl_.head_.left_);
    529         YAT_ASSERT(impl_.head_.left_->validate());
    530         YAT_ASSERT(validate());
    531         return result;
    532       }
    533 
    534       ranking::NodeBase* parent = nullptr;
    535       YAT_ASSERT(x);
    536512      while (true) {
    537         parent = x;
     513        ranking::NodeBase* parent = x;
    538514        if (compare_(element->value(), value(x))) {
    539515          x = x->left_;
    540516          if (x == nullptr) {
    541             element->parent_ = parent;
    542             parent->left_ = element.release();
    543             parent->increment_size();
    544             parent->update_height();
    545             if (impl_.head_.left_ == parent)
    546               impl_.head_.left_ = parent->left_;
     517            impl_.insert_and_rebalance(std::move(element), *parent,
     518                                       parent->left_);
     519            if (impl_.left_most() == parent)
     520              impl_.left_most() = parent->left_;
    547521            YAT_ASSERT(validate());
    548522            return result;
     
    552526          x = x->right_;
    553527          if (x == nullptr) {
    554             element->parent_ = parent;
    555             parent->right_ = element.release();
    556             parent->increment_size();
    557             parent->update_height();
     528            impl_.insert_and_rebalance(std::move(element), *parent,
     529                                       parent->right_);
    558530            YAT_ASSERT(validate());
    559531            return result;
    560532          }
    561533        }
    562         YAT_ASSERT(x != &impl_.head_);
    563         YAT_ASSERT(x != parent);
    564       }
    565     }
    566 
    567 
     534      }
     535      YAT_ASSERT(0);
     536      return result;
     537    }
     538
     539
     540    /*
     541      Find the first node that is greater or equal to key, i.e., all
     542      elements left of returned node are less than key.
     543     */
    568544    const_iterator
    569545    lower_bound(const ranking::NodeValue<T>* x, const ranking::NodeBase* y,
    570546                const T& key) const
    571547    {
    572       if (compare_(x->value(), key))
    573         return const_iterator(y);
     548      // x is used to traverse the tree
     549      // y holds the result
    574550
    575551      while (x) {
    576         // x value is greater than key, search in left branch
     552        // key is less (or equal) than x, store x as potential result
     553        // and search in left branch
    577554        if (!compare_(x->value(), key)) {
    578555          y = x;
    579           // asign x->left_ as NodeValue*
    580556          x = left(x);
    581557        }
    582         else { // x value <= key, search in right branch but don't update y
    583           YAT_ASSERT(x->right_ != &impl_.head_);
    584           // asign x->right_ as NodeValue*
     558        // key is greater than x, the lower bound is not x; it is
     559        // either in the right branch or a previously assigned
     560        // ancestor. Do not store x as potential result, but search
     561        // branch.
     562        else
    585563          x = right(x);
    586         }
    587       }
     564      }
     565      // x has reached a leaf, and the result should be stored in y
     566
     567      // returned node is not smaller than key
     568      YAT_ASSERT(y==head_node() || !compare_(value(y), key));
     569      // all nodes left of returned node are smaller than key
     570      YAT_ASSERT(y->left_==nullptr ||
     571                 compare_(value(y->left_->right_most()), key));
    588572      return const_iterator(y);
    589     }
    590 
    591 
    592     /**
    593        \return the root of the tree
    594      */
    595     ranking::NodeBase*& root_node(void)
    596     {
    597       return impl_.head_.parent_;
    598     }
    599 
    600 
    601     const ranking::NodeBase* const root_node(void) const
    602     {
    603       return impl_.head_.parent_;
    604     }
    605 
    606 
    607     ranking::NodeBase* left_most(void)
    608     {
    609       return impl_.head_.left_;
    610     }
    611 
    612 
    613     const ranking::NodeBase* left_most(void) const
    614     {
    615       return impl_.head_.left_;
    616573    }
    617574
     
    636593
    637594    /*
    638     ranking::NodeBase* right_most(void)
    639     {
    640       head_.right_;
    641     }
    642 
    643 
    644     const ranking::NodeBase* right_most(void) const
    645     {
    646       head_.right_;
    647     }
    648     */
    649 
     595      Find the first node that is greater than key, i.e., all
     596      elements left of returned node are less or equal to key.
     597     */
    650598    const_iterator
    651599    upper_bound(const ranking::NodeValue<T>* x, const ranking::NodeBase* y,
    652600                const T& key) const
    653601    {
    654       if (!compare_(key, x->value()))
    655         return const_iterator(y);
    656 
     602      // x is used to traverse the tree
     603      // y holds the result
    657604
    658605      while (x) {
    659         // key is less than x value, search in left
     606        // key is less than x value, x is a potential upper_bound,
     607        // store and search in left
    660608        if (compare_(key, x->value())) {
    661609          y = x;
     
    663611        }
    664612        else {
    665           YAT_ASSERT(x->right_ != &impl_.head_);
     613          // key is greater (or equal) than x, x is not the upper
     614          // bound. It is either in the right branch or in a
     615          // previously assigned ancestor (current y).
    666616          x = right(x);
    667617        }
    668618      }
     619      // x has reached a leaf, and the result should be stored in y
     620
     621      // key is less than returned node
     622      YAT_ASSERT(y==head_node() || compare_(key, value(y)));
     623      // all nodes left of returned node are smaller (or equal) than
     624      // key, i.e., key is not smaller than any of the nodes to the
     625      // left of returned node.
     626      YAT_ASSERT(y->left_==nullptr ||
     627                 !compare_(key, value(y->left_->right_most())));
    669628      return const_iterator(y);
    670629    }
     
    681640    bool validate(void) const
    682641    {
    683 #ifdef YAT_DEBUG_RANKING
    684       if (!impl_.validate())
     642#ifndef YAT_DEBUG_RANKING
     643      return true;
     644#else
     645      if (!impl_.validate()) {
     646        std::cerr << "Impl::validate failed\n";
    685647        return false;
     648      }
     649
    686650      bool ok = true;
    687651      size_t rank = 0;
     652      YAT_ASSERT(cbegin().node_);
     653      YAT_ASSERT(cend().node_);
    688654      for (auto it = cbegin(); it!=cend(); ++it) {
    689655        size_t r = ranking(it);
     
    699665      }
    700666      return ok;
    701 #else
    702       return true;
    703667#endif
    704668    }
     
    716680  {
    717681    if (!other.empty())
    718       root_node() = copy(other);
     682      impl_.root_node() = copy(other);
    719683    YAT_ASSERT(validate());
    720684  }
     
    753717  ranking::NodeValue<T>* Ranking<T,C>::copy(const Ranking& other)
    754718  {
    755     YAT_ASSERT(validate());
    756     YAT_ASSERT(impl_.head_.parent_ == nullptr);
    757     YAT_ASSERT(other.first_node());
    758     ranking::NodeValue<T>* root = copy(other.first_node(), last_node());
    759     root->parent_ = nullptr;
    760     root->right_ = last_node();
    761     last_node()->left_ = root->left_most();
    762     last_node()->parent_ = root;
     719    YAT_ASSERT(other.root_node());
     720    ranking::NodeValue<T>* root = copy(other.root_node());
     721    root->parent_ = head_node();
     722    head_node()->left_ = root;
     723    head_node()->right_ = root->left_most();
     724    head_node()->update_height();
     725    head_node()->update_size();
    763726    YAT_ASSERT(validate());
    764727    return root;
     
    767730
    768731  template<typename T, typename C>
    769   ranking::NodeValue<T>* Ranking<T,C>::copy(const ranking::NodeValue<T>* x,
    770                                             ranking::NodeBase* parent) const
     732  ranking::NodeValue<T>*
     733  Ranking<T,C>::copy(const ranking::NodeValue<T>* x) const
    771734  {
    772735    YAT_ASSERT(x);
    773736    ranking::NodeValue<T>* root = clone_node(x);
     737    YAT_ASSERT(root);
    774738    root->height_ = x->height_;
    775739    root->size_ = x->size_;
    776     YAT_ASSERT(root);
    777     root->parent_ = parent;
     740
    778741    try {
    779       if (x->right_ && !x->right_->is_head_node()) {
    780         YAT_ASSERT(x != right(x));
    781         YAT_ASSERT(x->right_ != &impl_.head_);
    782         root->right_ = copy(right(x), root);
    783       }
    784 
    785       parent = root;
    786       x = left(x);
    787       while (x) {
    788         ranking::NodeValue<T>* y = clone_node(x);
    789         y->height_ = x->height_;
    790         y->size_ = x->size_;
    791         parent->left_ = y;
    792         y->parent_ = parent;
    793         if (x->right_) {
    794           YAT_ASSERT(x->right_ != &impl_.head_);
    795           y->right_ = copy(right(x), y);
    796         }
    797         parent = y;
    798         x = left(x);
     742      if (x->left_) {
     743        root->left_ = copy(left(x));
     744        root->left_->parent_ = root;
     745      }
     746      if (x->right_) {
     747        root->right_ = copy(right(x));
     748        root->right_->parent_ = root;
    799749      }
    800750    }
     
    803753      std::rethrow_exception(std::current_exception());
    804754    }
    805 
    806755    return root;
    807756  }
     
    826775    YAT_ASSERT(p != end());
    827776    const ranking::NodeBase* node = p.node_;
    828     //    std::cerr << "erase_node: " << node << "\n";
    829777    YAT_ASSERT(node);
    830778
    831     // two children
    832     if (node->left_ && node->right_) {
    833       // When node has two branches, we take the most leftmost node in
    834       // the right branch and place in nodes place.
    835       ranking::NodeBase* leftmost = node->right_->left_most();
    836       YAT_ASSERT(leftmost->left_ == nullptr);
    837 
    838       // If the leftmost node has a kid, we need to relink the kid
    839       // with its grand parent
    840       if (leftmost->parent_ != node) {
    841         impl_.relink(leftmost, leftmost->right_);
    842       }
    843       impl_.relink(node, leftmost);
    844       YAT_ASSERT(leftmost->left_ == node->left_);
    845       YAT_ASSERT(!leftmost->left_ || leftmost->left_->parent_==leftmost);
    846       leftmost->update_height();
    847       leftmost->size_ =
    848         1 + ranking::size(leftmost->left_) + ranking::size(leftmost->right_);
    849       leftmost->parent_->decrement_size();
    850       YAT_ASSERT(validate());
    851     }
    852     else {
    853       // single child node is simple, the child takes the node's place
    854       impl_.relink(node, node->left_ ? node->left_ : node->right_);
    855       node->parent_->decrement_size();
    856       node->parent_->update_height();
    857       YAT_ASSERT(validate());
    858     }
     779    impl_.erase_and_rebalance(node);
    859780    // FIXME we need to delete the node, but be careful to not delete
    860781    // any of ots children; perhaps const_cast first?
    861 
     782    YAT_ASSERT(validate());
     783    return;
    862784  }
    863785
  • branches/kendall-score/yat/utility/ranking/Impl.cc

    r4071 r4072  
    4242  {
    4343    reset();
    44     if (from.head_.parent_)
    45       move_data(std::move(from));
     44    move_data(std::move(from));
    4645  }
    4746
     
    5655
    5756
     57  bool Impl::empty(void) const
     58  {
     59    return !root_node();
     60  }
     61
     62
     63  size_t Impl::size(void) const
     64  {
     65    assert(head_.size_ > 0);
     66    return head_.size_ - 1;
     67  }
     68
     69
    5870  void Impl::move_data(Impl&& from)
    5971  {
    60     assert(head_.parent_ == nullptr);
     72    // FIXME we need to clean up before the move
     73
    6174    head_.parent_ = from.head_.parent_;
    6275    head_.left_ = from.head_.left_;
    63     assert(head_.right_ == &head_);
    64     head_.parent_->right_ = &head_;
     76    if (head_.left_) {
     77      head_.left_->parent_ = &head_;
     78      head_.right_ = from.head_.right_;
     79    }
     80    else
     81      head_.right_ = &head_;
    6582    head_.height_ = from.head_.height_;
    6683    head_.size_ = from.head_.size_;
     
    112129  size_t Impl::ranking(const NodeBase* node) const
    113130  {
     131    assert(node);
    114132    if (node->is_head_node())
    115       return size(node->parent_);
    116 
    117     // root node
    118     if (node->parent_ == nullptr)
    119       return size(node->left_);
    120 
     133      return size();
     134
     135    assert(node->parent_);
    121136    // The rank of the parent is the sum of the rank of the
    122137    // left->child, the child itself, and the size of the child's
    123138    // right branch.
    124139    if (node->is_left_node())
    125       return ranking(node->parent_) - (1 + size(node->right_));
     140      return ranking(node->parent_) - (1 + ranking::size(node->right_));
    126141
    127142    // right node
    128     return ranking(node->parent_) + 1 + size(node->left_);
     143    return ranking(node->parent_) + 1 + ranking::size(node->left_);
    129144  }
    130145
     
    134149    // FIXME do we need to destruct parent and rest of tree?
    135150    head_.parent_ = nullptr;
    136     head_.left_ = &head_;
    137     head_.right_ = &head_;
    138     // we don't count the head node
    139     head_.height_ = 0;
    140     head_.size_ = 0;
     151    head_.left_ = nullptr;
     152    head_.right_ = &head_; // most left node
     153    head_.update_height();
     154    head_.update_size();
    141155    assert(validate());
    142156  }
    143157
    144158
     159  void Impl::erase_and_rebalance(const NodeBase* node)
     160  {
     161    // two children
     162    if (node->left_ && node->right_) {
     163      // When node has two branches, we take the most leftmost node in
     164      // the right branch and place in nodes place.
     165      ranking::NodeBase* leftmost = node->right_->left_most();
     166      assert(leftmost->left_ == nullptr);
     167
     168      // If the leftmost node has a kid, we need to relink the kid
     169      // with its grand parent
     170      if (leftmost->parent_ != node)
     171        relink(leftmost, leftmost->right_);
     172      relink(node, leftmost);
     173      assert(leftmost->left_ == node->left_);
     174      assert(!leftmost->left_ || leftmost->left_->parent_==leftmost);
     175      leftmost->update_height();
     176      leftmost->parent_->update_height_recursively();
     177      leftmost->update_size();
     178      leftmost->parent_->decrement_size();
     179      erase_rebalance(leftmost);
     180    }
     181    else {
     182      // single child node is simple, the child takes the node's place
     183      relink(node, node->left_ ? node->left_ : node->right_);
     184      node->parent_->decrement_size();
     185      node->parent_->update_height_recursively();
     186      erase_rebalance(node->parent_);
     187    }
     188  }
     189
     190
     191  void Impl::insert_and_rebalance(std::unique_ptr<NodeBase>&& element,
     192                                  NodeBase& parent, NodeBase*& child)
     193  {
     194    assert(child == nullptr);
     195    child = element.release();
     196    child->parent_ = &parent;
     197    parent.increment_size();
     198    parent.update_height_recursively();
     199
     200    insert_rebalance(&parent, child);
     201  }
     202
     203
     204  void Impl::erase_rebalance(NodeBase* node)
     205  {
     206    assert(node);
     207    if (node->is_root_node())
     208      return;
     209
     210    int balance = node->balance();
     211
     212    if (std::abs(balance) > 1) {
     213      assert(0);
     214    }
     215
     216    NodeBase* parent = node->parent_;
     217    assert(parent);
     218    erase_rebalance(parent);
     219  }
     220
     221
     222  void Impl::insert_rebalance(NodeBase* node, NodeBase* child)
     223  {
     224    assert(node);
     225    assert(child);
     226    assert(child->parent_ == node);
     227    assert(child == node->left_ || child == node->right_);
     228
     229    NodeBase* parent = node->parent_;
     230    assert(parent);
     231    if (parent->is_head_node())
     232      return;
     233
     234    // left height minus right height
     235    int balance = parent->balance();
     236
     237    /*
     238      If parent is unbalanced, we have four cases.
     239
     240      Below parent is denoted z
     241      node is denoted y
     242      child is denoted x
     243
     244      and all three are ancestors of the just inserted node.
     245
     246      a) Left Left Case
     247
     248      T1, T2, T3 and T4 are subtrees.
     249            z                                      y
     250           / \                                   /   \
     251          y   T4      Right Rotate (z)          x      z
     252         / \          - - - - - - - - ->      /  \    /  \
     253        x   T3                               T1  T2  T3  T4
     254       / \
     255      T1  T2
     256
     257      b) Left Right Case
     258
     259            z                              z                           x
     260           / \                            / \                        /   \
     261          y   T4  Left Rotate (y)        x   T4  Right Rotate(z)    y     z
     262         / \      - - - - - - - - ->    / \     - - - - - - - ->   / \   / \
     263        T1  x                          y   T3                     T1 T2 T3 T4
     264           / \                        / \
     265          T2 T3                     T1   T2
     266
     267      c) Right Right Case
     268
     269          z                              y
     270         / \                            /  \
     271        T1  y     Left Rotate(z)       z    x
     272           / \    - - - - - - - ->    / \  / \
     273          T2  x                      T1 T2T3 T4
     274             / \
     275            T3 T4
     276
     277      d) Right Left Case
     278
     279        z                            z                            x
     280       / \                          / \                         /   \
     281      T1  y   Right Rotate (y)    T1   x    Left Rotate(z)     z     y
     282         / \  - - - - - - - - ->      / \   - - - - - - - ->  / \   / \
     283        x   T4                      T2   y                  T1  T2 T3  T4
     284       / \                              / \
     285      T2  T3                           T3  T4
     286    */
     287
     288    if (balance < -1) {
     289      assert(height(parent->right_) > height(parent->left_));
     290      assert(parent->right_ == node);
     291      // right right case
     292      if (node->right_ == child) {
     293        left_rotate(parent);
     294        return;
     295      }
     296      // right left case
     297      assert(node->left_ == child);
     298      right_rotate(node);
     299      left_rotate(parent);
     300      return;
     301    }
     302    else if (balance > 1) {
     303      // left right case
     304      if (node->right_ == child) {
     305        left_rotate(node);
     306        right_rotate(parent);
     307        return;
     308      }
     309      // left left case
     310      assert(node->left_ == child);
     311      right_rotate(parent);
     312      return;
     313    }
     314
     315    assert(parent->parent_);
     316    insert_rebalance(parent, node);
     317  }
     318
     319
     320  NodeBase* Impl::left_rotate(NodeBase* x)
     321  {
     322    assert(x);
     323    NodeBase* y = x->right_;
     324    assert(y);
     325    NodeBase* T2 = y->left_;
     326
     327    // rotate
     328    if (x->is_left_node())
     329      x->parent_->left_ = y;
     330    else {
     331      assert(x->is_right_node());
     332      x->parent_->right_ = y;
     333    }
     334    y->parent_ = x->parent_;
     335
     336    y->left_ = x;
     337    x->parent_ = y;
     338
     339    x->right_ = T2;
     340    if (T2)
     341      T2->parent_ = x;
     342
     343    // update height - always update from leaf and to root
     344    x->update_height();
     345    y->update_height();
     346    assert(y->parent_);
     347    y->parent_->update_height_recursively();
     348
     349    // update size
     350    x->update_size();
     351    y->update_size();
     352
     353    return y;
     354  }
     355
     356
     357  NodeBase* Impl::rebalance_old_root(NodeBase* node)
     358  {
     359    if (node->balance() > 1) {
     360      // height(y) > height(T4) + 1
     361      // i.e. height(x) > height(T4)
     362
     363      // left left case
     364      if (node->left_->balance() >= 0) {
     365        assert(height(node->left_) > height(node->right_) + 1);
     366        // height(x) > height(T4)
     367        assert(height(node->left_->left_) > height(node->right_));
     368        // y is balanced, so:
     369        //  height(T3) <= height(x) <= height(T3)+1
     370        assert(height(node->left_->left_) >= height(node->left_->right_));
     371        assert(height(node->left_->left_) <= height(node->left_->right_)+1);
     372        // x is balanced, so |height(T1)-height(T2)| <= 1
     373
     374        node = right_rotate(node);
     375      }
     376      else { // left right case
     377        left_rotate(node->left_);
     378        node = right_rotate(node);
     379      }
     380      return rebalance_old_root(node);
     381    }
     382
     383    if (node->balance() >= -1)
     384      return node;
     385
     386    assert(0);
     387    return node;
     388  }
     389
     390
     391  NodeBase* Impl::right_rotate(NodeBase* y)
     392  {
     393    NodeBase* x = y->left_;
     394    assert(x);
     395    NodeBase* T2 = x->right_;
     396
     397    // rotate
     398    if (y->is_left_node())
     399      y->parent_->left_ = x;
     400    else {
     401      assert(y->is_right_node());
     402      y->parent_->right_ = x;
     403    }
     404    x->parent_ = y->parent_;
     405
     406    x->right_ = y;
     407    y->parent_ = x;
     408
     409    y->left_ = T2;
     410    if (T2)
     411      T2->parent_ = y;
     412
     413    // update height
     414    y->update_height();
     415    x->update_height();
     416    assert(x->parent_);
     417    x->parent_->update_height_recursively();
     418
     419    // update size
     420    y->update_size();
     421    x->update_size();
     422
     423    return x;
     424  }
     425
     426
    145427  bool Impl::validate(void) const
    146428  {
    147     if (head_.parent_ == nullptr) {
    148       assert(head_.left_ == &head_);
    149       assert(head_.right_ == &head_);
    150       assert(head_.is_head_node());
    151     }
    152     else {
    153       assert(head_.parent_);
    154       assert(head_.left_);
    155       if (head_.parent_->right_ != &head_) {
     429#ifdef NDEBUG
     430    return true;
     431#else
     432    if (!head_.validate(true)) {
     433      std::cerr << "Impl: head failed\n";
     434      return false;
     435    }
     436    assert(left_most() == head_.left_most());
     437
     438    if (root_node()) {
     439      if (root_node()->is_left_node() == false) {
     440        std::cerr << "error: root is not a left node\n";
    156441        return false;
    157442      }
    158     }
    159 
    160     if (head_.parent_) {
    161       if (head_.parent_->left_most() != head_.left_) {
    162         std::cerr << "head_.left incorrect\n";
     443      if (root_node()->is_right_node()) {
     444        std::cerr << "error: root is a right node\n";
    163445        return false;
    164446      }
    165       if (!head_.parent_->recursive_validate())
     447    }
     448
     449    if (!validate(root_node())) {
     450      std::cerr << "Impl: validate(root_node()) failed\n";
     451      return false;
     452    }
     453
     454
     455    /*
     456    if (root_node()) {
     457      if (root_node()->left_most() != head_.right_) {
     458        std::cerr << "head_.right incorrect\n";
     459        return false;
     460      }
     461      if (!root_node()->recursive_validate())
    166462        return false;
    167463    }
    168464    else if (!head_.validate())
    169465      return false;
    170 
     466    */
    171467    return true;
    172   }
     468#endif
     469  }
     470
     471
     472  bool Impl::validate(const NodeBase* node) const
     473  {
     474    if (node == nullptr)
     475      return true;
     476    node->validate();
     477    validate(node->left_);
     478    validate(node->right_);
     479    return true;
     480  }
     481
     482
     483  NodeBase*& Impl::left_most(void)
     484  {
     485    return head_.right_;
     486  }
     487
     488
     489  const NodeBase* Impl::left_most(void) const
     490  {
     491    return head_.right_;
     492  }
     493
     494
     495  NodeBase*& Impl::root_node(void)
     496  {
     497    return head_.left_;
     498  }
     499
     500
     501  const NodeBase* Impl::root_node(void) const
     502  {
     503    return head_.left_;
     504  }
     505
    173506
    174507}
  • branches/kendall-score/yat/utility/ranking/Impl.h

    r4071 r4072  
    2828
    2929#include <cstddef>
     30#include <memory>
    3031
    3132namespace theplu {
     
    4748      Impl& operator=(Impl&& rhs);
    4849
     50      // FIXME
    4951      // Head is the only node with no value. Its parent is the root
    5052      // node and the rest of the tree is in the left branch from the
     
    5254      // corresponds to begin()
    5355      NodeBase head_;
     56
     57      bool empty(void) const;
     58      size_t size(void) const;
     59
     60      NodeBase*& root_node(void);
     61      const NodeBase* root_node(void) const;
     62      NodeBase*& left_most(void);
     63      const NodeBase* left_most(void) const;
     64
     65
     66      /*
     67
     68       */
     69      NodeBase* rebalance_old_root(NodeBase* node);
     70
     71      /*
     72        Node \a child is a child of \a parent. The child which is required
     73        to be a nullptr is assigned as \a element. and parent is updated
     74        as appropriate (height, size, etc) and rebalanced if needed
     75        including that balance of ancestors is checked.
     76      */
     77      void insert_and_rebalance(std::unique_ptr<NodeBase>&& element,
     78                                NodeBase& parent, NodeBase*& child);
     79
     80      /*
     81        Examine the balance of node->parent. If the height of its left
     82        branch and right branch differs more than one,
     83        rebalance. Otherwise or if recursive is true, call with parent
     84        and node as arguments.
     85       */
     86      void insert_rebalance(NodeBase* node, NodeBase* child);
     87
     88      //
     89      void erase_and_rebalance(const NodeBase* node);
     90
    5491      // typically only called with assert, YAT_ASSERT or similar
    5592      bool validate(void) const;
     93      bool validate(const NodeBase*) const;
    5694      // return number of nodes left of node, i.e., number of nodes
    5795      // with value less than node->value.
     
    69107      */
    70108      void relink(const NodeBase* node, NodeBase* child);
     109
     110      /*
     111            y                               x
     112           / \                             / \
     113          x  T3                           T1  y
     114         / \       < - - - - - - -           / \
     115        T1 T2      Left Rotation            T2 T3
     116
     117        \return new root in the subtree, i.e., y.
     118       */
     119      NodeBase* left_rotate(NodeBase* x);
     120
     121      /*
     122            y                               x
     123           / \                             / \
     124          x  T3                           T1  y
     125         / \       - - - - - - - >           / \
     126        T1 T2      Right Rotation           T2 T3
     127
     128        \return new root in the subtree, i.e., x.
     129       */
     130      NodeBase* right_rotate(NodeBase* y);
    71131    private:
    72132      void move_data(Impl&&);
     133      void erase_rebalance(NodeBase* node);
     134      void erase_rebalance(NodeBase* parent, NodeBase* node);
     135
    73136    };
    74137  } // end of namespace ranking
  • branches/kendall-score/yat/utility/ranking/Iterator.h

    r4070 r4072  
    5151    {
    5252    public:
    53       explicit Iterator(const NodeBase* node = nullptr);
     53      Iterator(void);
     54      explicit Iterator(const NodeBase* node);
    5455      const NodeBase* node_;
    5556    private:
     
    6364    /// Implementations
    6465    template<typename T>
     66    Iterator<T>::Iterator(void)
     67      : node_(nullptr)
     68    {
     69    }
     70
     71
     72    template<typename T>
    6573    Iterator<T>::Iterator(const NodeBase* node)
    6674      : node_(node)
    6775    {
     76      YAT_ASSERT(node);
    6877    }
    6978
     
    92101      YAT_ASSERT(node_);
    93102      YAT_ASSERT(!node_->is_head_node());
    94       if (node_->is_root_node()) {
    95         node_ = node_->right_;
    96         return;
    97       }
    98       // since node_ is not root, it must have a parent and be either
    99       // left or right.
    100       YAT_ASSERT(node_->parent_);
    101       YAT_ASSERT(node_->is_left_node() || node_->is_right_node());
     103      YAT_ASSERT(node_->validate());
    102104
    103105      // If we have a right branch, go to the leftmost leaf in it.
     
    111113      const NodeBase* child = node_;
    112114      YAT_ASSERT(child->parent_);
    113       YAT_ASSERT(child->is_left_node() || child->is_right_node());
    114115      while (child->is_right_node()) {
    115         YAT_ASSERT(!child->is_left_node());
    116         YAT_ASSERT(!child->is_root_node());
    117         YAT_ASSERT(!child->is_head_node());
    118         child = child->parent_;
    119         YAT_ASSERT(child);
     116        child = child->parent_; // traverse up
     117        YAT_ASSERT(child->parent_);
     118        YAT_ASSERT(child->validate());
    120119      }
    121120
    122       YAT_ASSERT(!child->is_right_node());
    123       YAT_ASSERT(!child->is_root_node());
    124       YAT_ASSERT(child->is_left_node());
    125121      node_ = child->parent_;
    126122      YAT_ASSERT(node_);
     
    131127    void Iterator<T>::decrement(void)
    132128    {
    133       // only head node is without parent and it is not dereferencable
    134129      YAT_ASSERT(node_);
    135130
    136131      if (node_->is_head_node()) {
    137         // this check fails if tree is empty, in which case behaviour
    138         // of decrementing is undefined anyway.
    139         YAT_ASSERT(node_->parent_);
    140         node_ = node_->parent_;
     132        node_ = node_->left_->right_most();
    141133        return;
    142134      }
     
    152144      YAT_ASSERT(child->parent_);
    153145      while (child->is_left_node()) {
    154         YAT_ASSERT(!child->is_right_node());
    155         YAT_ASSERT(!child->is_root_node());
    156         YAT_ASSERT(!child->is_head_node());
    157146        child = child->parent_;
    158         YAT_ASSERT(child);
     147        YAT_ASSERT(child->parent_);
    159148      }
    160149
    161       YAT_ASSERT(!child->is_left_node());
    162       YAT_ASSERT(!child->is_root_node());
    163       YAT_ASSERT(child->is_right_node());
    164150      node_ = child->parent_;
    165151      YAT_ASSERT(node_);
  • branches/kendall-score/yat/utility/ranking/NodeBase.h

    r4071 r4072  
    4848      size_t size_;
    4949
     50      // return left height minus right height
     51      int balance(void) const;
     52
    5053      // return 0 for root, 1 for its children, etc
    5154      int generation(void) const;
     
    5659      void decrement_size(void);
    5760
     61      // set size to 1 + size of left + size of right
     62      void update_size(void);
     63      // set height to max of left height and right height plus 1
    5864      void update_height(void);
     65      // set height as in update_height. If heigh is updated, call
     66      // parent as well.
     67      void update_height_recursively(void);
    5968
    6069      // return true if head node
     
    7382      NodeBase* right_most(void);
    7483      const NodeBase* right_most(void) const;
    75       // Only used to validate that the tree is valid, used in debug
    76       // code and assertions.
    77       bool validate(void) const;
    78       bool recursive_validate(void) const;
     84      bool validate(bool head=false) const;
    7985    };
    8086
Note: See TracChangeset for help on using the changeset viewer.