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

// $Id: Impl.cc 4071 2021-08-18 02:31:29Z 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();
    if (from.head_.parent_)
      move_data(std::move(from));
  }


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


  void Impl::move_data(Impl&& from)
  {
    assert(head_.parent_ == nullptr);
    head_.parent_ = from.head_.parent_;
    head_.left_ = from.head_.left_;
    assert(head_.right_ == &head_);
    head_.parent_->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
  {
    if (node->is_head_node())
      return size(node->parent_);

    // root node
    if (node->parent_ == nullptr)
      return size(node->left_);

    // 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 + size(node->right_));

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


  void Impl::reset(void)
  {
    // FIXME do we need to destruct parent and rest of tree?
    head_.parent_ = nullptr;
    head_.left_ = &head_;
    head_.right_ = &head_;
    // we don't count the head node
    head_.height_ = 0;
    head_.size_ = 0;
    assert(validate());
  }


  bool Impl::validate(void) const
  {
    if (head_.parent_ == nullptr) {
      assert(head_.left_ == &head_);
      assert(head_.right_ == &head_);
      assert(head_.is_head_node());
    }
    else {
      assert(head_.parent_);
      assert(head_.left_);
      if (head_.parent_->right_ != &head_) {
        return false;
      }
    }

    if (head_.parent_) {
      if (head_.parent_->left_most() != head_.left_) {
        std::cerr << "head_.left incorrect\n";
        return false;
      }
      if (!head_.parent_->recursive_validate())
        return false;
    }
    else if (!head_.validate())
      return false;

    return true;
  }

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