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

// $Id: Impl.cc 4070 2021-08-09 06:32:59Z 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_;
    node_count_ = from.node_count_;
    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->right_ && node->right_!=child) {
        assert(!child->right_);
        child->right_ = node->right_;
      }
    }

    // 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());
  }


  void Impl::reset(void)
  {
    // FIXME do we need to destruct parent and rest of tree?
    head_.parent_ = nullptr;
    head_.left_ = &head_;
    head_.right_ = &head_;
    node_count_ = 0;
    assert(validate());
  }


  bool Impl::validate(void) const
  {
    if (node_count_ == 0) {
      assert(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