source: branches/kendall-score/yat/utility/ranking/Impl.cc @ 4075

// $Id: Impl.cc 4075 2021-08-20 06:54:37Z peter $

/*
  Copyright (C) 2021 Peter Johansson

  This file is part of the yat library, http://dev.thep.lu.se/yat

  The yat library is free software; you can redistribute it and/or
  modify it under the terms of the GNU General Public License as
  published by the Free Software Foundation; either version 3 of the
  License, or (at your option) any later version.

  The yat library is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  General Public License for more details.

  You should have received a copy of the GNU General Public License
  along with yat. If not, see <http://www.gnu.org/licenses/>.
*/

#include <config.h>

#include "Ranking.h"

#include <cassert>
#include <cstddef>
#include <iostream>

namespace theplu {
namespace yat {
namespace utility {
namespace ranking {

  Impl::Impl(void)
  {
    reset();
  }


  Impl::Impl(Impl&& from)
  {
    reset();
    move_data(std::move(from));
  }


  Impl& Impl::operator=(Impl&& rhs)
  {
    assert(!head_.parent_);
    move_data(std::move(rhs));
    assert(validate());
    return *this;
  }


  bool Impl::empty(void) const
  {
    return !root_node();
  }


  size_t Impl::size(void) const
  {
    assert(head_.size_ > 0);
    return head_.size_ - 1;
  }


  void Impl::move_data(Impl&& from)
  {
    assert(empty());

    head_.parent_ = from.head_.parent_;
    head_.left_ = from.head_.left_;
    if (head_.left_) {
      head_.left_->parent_ = &head_;
      head_.right_ = from.head_.right_;
    }
    else
      head_.right_ = &head_;
    head_.height_ = from.head_.height_;
    head_.size_ = from.head_.size_;
    from.reset();
    assert(validate());
  }


  void Impl::relink(const NodeBase* node, NodeBase* child)
  {
    assert(node->parent_);
    assert(node != &head_);
    assert(child != &head_);

    // make child the child of node's parent
    if (node->is_left_node())
      node->parent_->left_ = child;
    else if (node->is_right_node())
      node->parent_->right_ = child;

    // make node's parent the parent of child
    if (child)
      child->parent_ = node->parent_;

    // inherit the kids
    if (child) {
      if (node->left_ && node->left_!=child) {
        assert(!child->left_);
        child->left_ = node->left_;
        if (node->left_)
          node->left_->parent_ = child;
      }
      if (node->right_ && node->right_!=child) {
        assert(!child->right_);
        child->right_ = node->right_;
        if (node->right_)
          node->right_->parent_ = child;
      }
    }

    // update pointer to left_most node
    if (head_.left_ == node) {
      head_.left_ = child ? child : node->parent_;
    }
    assert(child==nullptr || child->is_left_node() || child->is_right_node());
  }


  size_t Impl::ranking(const NodeBase* node) const
  {
    assert(node);
    if (node->is_head_node())
      return size();

    assert(node->parent_);
    // The rank of the parent is the sum of the rank of the
    // left->child, the child itself, and the size of the child's
    // right branch.
    if (node->is_left_node())
      return ranking(node->parent_) - (1 + ranking::size(node->right_));

    // right node
    return ranking(node->parent_) + 1 + ranking::size(node->left_);
  }


  void Impl::reset(void)
  {
    head_.parent_ = nullptr;
    head_.left_ = nullptr;
    head_.right_ = &head_; // most left node
    head_.update_height();
    head_.update_size();
    assert(validate());
  }


  void Impl::erase_and_rebalance(const NodeBase* node)
  {
    // two children
    if (node->left_ && node->right_) {
      // When node has two branches, we take the most leftmost node in
      // the right branch and place in nodes place.
      ranking::NodeBase* leftmost = node->right_->left_most();
      assert(leftmost->left_ == nullptr);

      // If the leftmost node has a kid, we need to relink the kid
      // with its grand parent
      if (leftmost->parent_ != node)
        relink(leftmost, leftmost->right_);
      relink(node, leftmost);
      assert(leftmost->left_ == node->left_);
      assert(!leftmost->left_ || leftmost->left_->parent_==leftmost);
      leftmost->update_height();
      leftmost->parent_->update_height_recursively();
      leftmost->update_size();
      leftmost->parent_->decrement_size();
      erase_rebalance(leftmost);
    }
    else {
      // single child node is simple, the child takes the node's place
      relink(node, node->left_ ? node->left_ : node->right_);
      node->parent_->decrement_size();
      node->parent_->update_height_recursively();
      erase_rebalance(node->parent_);
    }
  }


  void Impl::insert_and_rebalance(std::unique_ptr<NodeBase>&& element,
                                  NodeBase& parent, NodeBase*& child)
  {
    assert(child == nullptr);
    child = element.release();
    child->parent_ = &parent;
    parent.increment_size();
    parent.update_height_recursively();

    insert_rebalance(&parent, child);
  }


  void Impl::erase_rebalance(NodeBase* node)
  {
    assert(node);
    if (node->is_root_node())
      return;

    int balance = node->balance();

    if (std::abs(balance) > 1) {
      assert(0);
    }

    NodeBase* parent = node->parent_;
    assert(parent);
    erase_rebalance(parent);
  }


  void Impl::insert_rebalance(NodeBase* node, NodeBase* child)
  {
    assert(node);
    assert(child);
    assert(child->parent_ == node);
    assert(child == node->left_ || child == node->right_);

    NodeBase* parent = node->parent_;
    assert(parent);
    if (parent->is_head_node())
      return;

    // left height minus right height
    int balance = parent->balance();

    /*
      If parent is unbalanced, we have four cases.

      Below parent is denoted z
      node is denoted y
      child is denoted x

      and all three are ancestors of the just inserted node. 

      a) Left Left Case

      T1, T2, T3 and T4 are subtrees.
            z                                      y
           / \                                   /   \
          y   T4      Right Rotate (z)          x      z
         / \          - - - - - - - - ->      /  \    /  \
        x   T3                               T1  T2  T3  T4
       / \
      T1  T2

      b) Left Right Case

            z                              z                           x
           / \                            / \                        /   \
          y   T4  Left Rotate (y)        x   T4  Right Rotate(z)    y     z
         / \      - - - - - - - - ->    / \     - - - - - - - ->   / \   / \
        T1  x                          y   T3                     T1 T2 T3 T4
           / \                        / \
          T2 T3                     T1   T2

      c) Right Right Case

          z                              y
         / \                            /  \
        T1  y     Left Rotate(z)       z    x
           / \    - - - - - - - ->    / \  / \
          T2  x                      T1 T2T3 T4
             / \
            T3 T4

      d) Right Left Case

        z                            z                            x
       / \                          / \                         /   \
      T1  y   Right Rotate (y)    T1   x    Left Rotate(z)     z     y
         / \  - - - - - - - - ->      / \   - - - - - - - ->  / \   / \
        x   T4                      T2   y                  T1  T2 T3  T4
       / \                              / \
      T2  T3                           T3  T4
    */

    if (balance < -1) {
      assert(height(parent->right_) > height(parent->left_));
      assert(parent->right_ == node);
      // right right case
      if (node->right_ == child) {
        left_rotate(parent);
        return;
      }
      // right left case
      assert(node->left_ == child);
      right_rotate(node);
      left_rotate(parent);
      return;
    }
    else if (balance > 1) {
      // left right case
      if (node->right_ == child) {
        left_rotate(node);
        right_rotate(parent);
        return;
      }
      // left left case
      assert(node->left_ == child);
      right_rotate(parent);
      return;
    }

    assert(parent->parent_);
    insert_rebalance(parent, node);
  }


  NodeBase* Impl::left_rotate(NodeBase* x)
  {
    assert(x);
    NodeBase* y = x->right_;
    assert(y);
    NodeBase* T2 = y->left_;

    // rotate
    if (x->is_left_node())
      x->parent_->left_ = y;
    else {
      assert(x->is_right_node());
      x->parent_->right_ = y;
    }
    y->parent_ = x->parent_;

    y->left_ = x;
    x->parent_ = y;

    x->right_ = T2;
    if (T2)
      T2->parent_ = x;

    // update height - always update from leaf and to root
    x->update_height();
    y->update_height();
    assert(y->parent_);
    y->parent_->update_height_recursively();

    // update size
    x->update_size();
    y->update_size();

    return y;
  }


  NodeBase* Impl::right_rotate(NodeBase* y)
  {
    NodeBase* x = y->left_;
    assert(x);
    NodeBase* T2 = x->right_;

    // rotate
    if (y->is_left_node())
      y->parent_->left_ = x;
    else {
      assert(y->is_right_node());
      y->parent_->right_ = x;
    }
    x->parent_ = y->parent_;

    x->right_ = y;
    y->parent_ = x;

    y->left_ = T2;
    if (T2)
      T2->parent_ = y;

    // update height
    y->update_height();
    x->update_height();
    assert(x->parent_);
    x->parent_->update_height_recursively();

    // update size
    y->update_size();
    x->update_size();

    return x;
  }


  bool Impl::validate(void) const
  {
#ifdef NDEBUG
    return true;
#else
    if (!head_.validate(true)) {
      std::cerr << "Impl: head failed\n";
      return false;
    }
    assert(left_most() == head_.left_most());

    if (root_node()) {
      if (root_node()->is_left_node() == false) {
        std::cerr << "error: root is not a left node\n";
        return false;
      }
      if (root_node()->is_right_node()) {
        std::cerr << "error: root is a right node\n";
        return false;
      }
    }

    if (!validate(root_node())) {
      std::cerr << "Impl: validate(root_node()) failed\n";
      return false;
    }


    /*
    if (root_node()) {
      if (root_node()->left_most() != head_.right_) {
        std::cerr << "head_.right incorrect\n";
        return false;
      }
      if (!root_node()->recursive_validate())
        return false;
    }
    else if (!head_.validate())
      return false;
    */
    return true;
#endif
  }


  bool Impl::validate(const NodeBase* node) const
  {
    if (node == nullptr)
      return true;
    node->validate();
    validate(node->left_);
    validate(node->right_);
    return true;
  }


  NodeBase*& Impl::left_most(void)
  {
    return head_.right_;
  }


  const NodeBase* Impl::left_most(void) const
  {
    return head_.right_;
  }


  NodeBase*& Impl::root_node(void)
  {
    return head_.left_;
  }


  const NodeBase* Impl::root_node(void) const
  {
    return head_.left_;
  }


}
}}} // of namespace utility, yat, and theplu