source: branches/kendall-score/yat/utility/Ranking.h @ 4071

#ifndef theplu_yat_utility_ranking
#define theplu_yat_utility_ranking

// $Id: Ranking.h 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 "ranking/Impl.h"
#include "ranking/Iterator.h"
#include "ranking/NodeBase.h"
#include "ranking/NodeValue.h"

#include "yat_assert.h"

#include <cstddef>
#include <functional>
#include <memory>

#include <iostream> // debug
namespace theplu {
namespace yat {
namespace utility {

  /**
     Class is a binary tree with the special extension that it allow
     fast access to the rank of an element in the tree.

     \since New in yat 0.19
   */
  template<typename T, class Compare = std::less<T> >
  class Ranking
  {
  public:
    /// value type
    typedef T value_type;
    /// type used to compare elements
    typedef Compare key_compare;
    /// size type
    typedef size_t size_type;
    /// iterator
    typedef ranking::Iterator<T> iterator;
    /// iterator
    typedef ranking::Iterator<T> const_iterator;
    /// reverse iterator
    typedef std::reverse_iterator<iterator> reverse_iterator;
    /// reverse iterator
    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

    /**
       \brief Default constructor
     */
    Ranking(void) = default;

    /**
       Construct empty container with comparison function \c c.
     */
    Ranking(const Compare& c)
      : compare_(c)
    {
      YAT_ASSERT(validate());
    }


    /**
       \brief Copy constructor
     */
    Ranking(const Ranking& other);

    /**
       \brief move constructor
     */
    Ranking(Ranking&& other);

    /**
       \brief assignment operator
     */
    Ranking& operator=(const Ranking& other);

    /**
       \brief move assignment
     */
    Ranking& operator=(Ranking&& other);


    /**
       \return iterator pointing to the first element
     */
    iterator begin(void)
    {
      return iterator(left_most());
    }


    /**
       \return iterator pointing to the first element
     */
    const_iterator begin(void) const
    {
      return cbegin();
    }


    /**
       \return iterator pointing to the first element
     */
    const_iterator cbegin(void) const
    {
      return const_iterator(left_most());
    }


    /**
       \return iterator pointing to one-passed-last element
     */
    iterator end(void)
    {
      return iterator(&impl_.head_);
    }


    /**
       \return iterator pointing to one-passed-last element
     */
    const_iterator end(void) const
    {
      return cend();
    }


    /**
       \return iterator pointing to one-passed-last element
     */
    const_iterator cend(void) const
    {
      return const_iterator(&impl_.head_);
    }


    /**
       \return reverse iterator pointing to first element
     */
    reverse_iterator rbegin(void)
    {
      return reverse_iterator(end());
    }


    /**
       \return reverse iterator pointing to one-passed-last element
     */
    reverse_iterator rend(void)
    {
      return reverse_iterator(begin());
    }


    /**
       \return reverse iterator pointing to one-passed-last element
     */
    const_reverse_iterator rend(void) const
    {
      return crend();
    }


    /**
       \return reverse iterator pointing to first element
     */
    const_reverse_iterator rbegin(void) const
    {
      return crbegin();
    }


    /**
       \return reverse iterator pointing to first element
     */
    const_reverse_iterator crbegin(void) const
    {
      return const_reverse_iterator(cend());
    }

    /**
       \return reverse iterator pointing to the one-passed-last element
     */
    const_reverse_iterator crend(void) const
    {
      return const_reverse_iterator(cbegin());
    }


    /**
       Remove all nodes
     */
    void clear(void)
    {
      if (size()) {
        YAT_ASSERT(first_node() != &impl_.head_);
        erase(first_node());
      }
      impl_.reset();
    }


    /**
       access comparison function which is used to sort elements
     */
    const Compare& compare(void) const
    {
      return compare_;
    }


    /**
       \return true if (and only if) container has zero elements
     */
    bool empty(void) const
    {
      return root_node() == nullptr;
    }


    /**
       Remove element pointed to by \c position.

       \return An iterator pointing to the element that follows the
       last element removed.
     */
    iterator erase(const_iterator position);

    /**
       Erase all elements that are equivalent with \c value
       \return number of elements removed
     */
    size_type erase(const T& value);

    /**
       Remove elements in range [first, last).

       \return An iterator pointing to the element that follows the
       last element removed.
     */
    iterator erase(const_iterator first, const_iterator last);

    /**
       Find an element that is equivalent to x
     */
    const_iterator find(const T& x) const;


    /**
       \brief insert an element
     */
    iterator insert(const T& element)
    {
      std::unique_ptr<ranking::NodeValue<T>>
        newnode(new ranking::NodeValue<T>(element));
      return insert(std::move(newnode));
    }


    /**
       \brief insert an element
     */
    iterator insert(T&& element)
    {
      std::unique_ptr<ranking::NodeValue<T>>
        newnode(new ranking::NodeValue<T>(std::move(element)));
      return insert(std::move(newnode));
    }


    /**
       \brief insert with hint
     */
    iterator insert(const_iterator hint, const T& element)
    {
      // FIXME use the hint
      return insert(element);
    }


    /**
       \brief insert with hint
     */
    iterator insert(const_iterator hint,  T&& element)
    {
      // FIXME use the hint
      return insert(std::move(element));
    }


    /**
       \brief insert range
     */
    template<typename InputIterator>
    void insert(InputIterator first, InputIterator last)
    {
      for (; first!=last; ++first)
        insert(end(), *first);
    }


    /**
       \return the first element which is equal (or greater) to \c x
     */
    const_iterator lower_bound(const T& x) const
    {
      if (empty())
        return cend();
      return lower_bound(first_node(), last_node(), x);
    }


    /**
       \return the first element which is greater than \c x
     */
    const_iterator upper_bound(const T& x) const
    {
      if (empty())
        return cend();
      return upper_bound(first_node(), last_node(), x);
    }


    /**
       \return number of elements smaller than \c it
     */
    size_t ranking(const_iterator it) const
    {
      return impl_.ranking(it.node_);
    }


    /**
       \return number of elements in container
     */
    size_t size(void) const
    {
      return root_node() ? root_node()->size_ : 0;
    }

  private:
    Compare compare_;
    ranking::Impl impl_;

    void print(const ranking::NodeBase* p, std::ostream& os) const
    {
      if (p) {
        if (p->is_head_node()==false) {
          print(p->right_, os);
        }
        os << std::string(p->generation()*4, ' ');
        if (!p->is_head_node())
          os << value(p);
        else
          os << "H";
        os << ":   "
                  << p->parent_ << " "
                  << p << " "
                  << p->left_ << " "
                  << p->right_ << "\n";
        if (p->is_head_node()==false) {
          print(p->left_, os);
        }
        if (p->parent_ && !p->is_left_node() && !p->is_right_node()) {
          os << "print error: " << p << "\n";
          exit(1);
        }
      }
    }

    // return a copy of x but with children and parent set to nullptr.
    ranking::NodeValue<T>*
    clone_node(const ranking::NodeValue<T>* x) const;

    /**
       copy data in other.Impl_ into impl_

       Basically copy constructor of Impl but nodes (except for head
       node) are copied as NodeValue<T> and Impl is not aware of T.
     */
    ranking::NodeValue<T>* copy(const Ranking& other);

    /**
       Create a copy of root and return it
     */
    ranking::NodeValue<T>*
    copy(const ranking::NodeValue<T>* root, ranking::NodeBase* h) const;

    /**
       Remove node position is pointing to
     */
    void erase_node(const_iterator position);

    // return the root node
    const ranking::NodeValue<T>* first_node(void) const
    {
      YAT_ASSERT(impl_.head_.parent_);
      return static_cast<const ranking::NodeValue<T>*>(impl_.head_.parent_);
    }


    ranking::NodeValue<T>* first_node(void)
    {
      YAT_ASSERT(impl_.head_.parent_);
      return static_cast<ranking::NodeValue<T>*>(impl_.head_.parent_);
    }


    const ranking::NodeBase* last_node(void) const
    {
      return &impl_.head_;
    }


    ranking::NodeBase* last_node(void)
    {
      return &impl_.head_;
    }


    const ranking::NodeValue<T>*
    left(const ranking::NodeBase* x) const
    {
      YAT_ASSERT(x->left_ != &impl_.head_);
      return static_cast<const ranking::NodeValue<T>*>(x->left_);
    }


    ranking::NodeValue<T>*
    left(ranking::NodeBase* x) const
    {
      YAT_ASSERT(x->left_ != &impl_.head_);
      return static_cast<ranking::NodeValue<T>*>(x->left_);
    }


    const ranking::NodeValue<T>*
    right(const ranking::NodeBase* x) const
    {
      YAT_ASSERT(x->right_ != &impl_.head_);
      return static_cast<const ranking::NodeValue<T>*>(x->right_);
    }


    ranking::NodeValue<T>*
    right(ranking::NodeBase* x) const
    {
      YAT_ASSERT(x->right_ != &impl_.head_);
      return static_cast<ranking::NodeValue<T>*>(x->right_);
    }


    // delete x and its offsprings
    void erase(ranking::NodeValue<T>* x) const
    {
      while (x) {
        if (x->right_ && x->right_ !=  &impl_.head_)
          erase(right(x));
        ranking::NodeValue<T>* tmp = left(x);
        delete x;
        x = tmp;
      }
    }


    /**
       traverse the tree and find a suitable leaf where we can insert
       \c element and keep the tree sorted.
     */
    iterator insert(std::unique_ptr<ranking::NodeValue<T>>&& element)
    {
      iterator result(element.get());
      if (empty()) {
        YAT_ASSERT(root_node() == nullptr);
        root_node() = element.release();
        root_node()->right_ = &impl_.head_;
        root_node()->height_ = 1;
        root_node()->size_ = 1;
        impl_.head_.left_ = root_node();

        YAT_ASSERT(root_node()->validate());
        YAT_ASSERT(impl_.head_.validate());
        YAT_ASSERT(validate());
        return result;
      }

      ranking::NodeBase* x = root_node();
      YAT_ASSERT(x);
      YAT_ASSERT(!x->is_head_node());

      // element right of root
      if (!compare_(element->value(), value(x))) {
        // make new root parent of head
        impl_.head_.parent_ = element.release();
        impl_.head_.parent_->right_ = &impl_.head_;

        // make old root and left child of new root
        x->right_ = nullptr;
        impl_.head_.parent_->left_ = x;
        x->parent_ = impl_.head_.parent_;
        YAT_ASSERT(x->size_ > 0);

        impl_.head_.parent_->size_ = x->size_ + 1;
        impl_.head_.parent_->height_ = x->height_ + 1;

        YAT_ASSERT(x->validate());
        YAT_ASSERT(impl_.head_.parent_);
        YAT_ASSERT(impl_.head_.parent_->validate());
        YAT_ASSERT(impl_.head_.left_);
        YAT_ASSERT(impl_.head_.left_->validate());
        YAT_ASSERT(validate());
        return result;
      }

      ranking::NodeBase* parent = nullptr;
      YAT_ASSERT(x);
      while (true) {
        parent = x;
        if (compare_(element->value(), value(x))) {
          x = x->left_;
          if (x == nullptr) {
            element->parent_ = parent;
            parent->left_ = element.release();
            parent->increment_size();
            parent->update_height();
            if (impl_.head_.left_ == parent)
              impl_.head_.left_ = parent->left_;
            YAT_ASSERT(validate());
            return result;
          }
        }
        else {
          x = x->right_;
          if (x == nullptr) {
            element->parent_ = parent;
            parent->right_ = element.release();
            parent->increment_size();
            parent->update_height();
            YAT_ASSERT(validate());
            return result;
          }
        }
        YAT_ASSERT(x != &impl_.head_);
        YAT_ASSERT(x != parent);
      }
    }


    const_iterator
    lower_bound(const ranking::NodeValue<T>* x, const ranking::NodeBase* y,
                const T& key) const
    {
      if (compare_(x->value(), key))
        return const_iterator(y);

      while (x) {
        // x value is greater than key, search in left branch
        if (!compare_(x->value(), key)) {
          y = x;
          // asign x->left_ as NodeValue*
          x = left(x);
        }
        else { // x value <= key, search in right branch but don't update y
          YAT_ASSERT(x->right_ != &impl_.head_);
          // asign x->right_ as NodeValue*
          x = right(x);
        }
      }
      return const_iterator(y);
    }


    /**
       \return the root of the tree
     */
    ranking::NodeBase*& root_node(void)
    {
      return impl_.head_.parent_;
    }


    const ranking::NodeBase* const root_node(void) const
    {
      return impl_.head_.parent_;
    }


    ranking::NodeBase* left_most(void)
    {
      return impl_.head_.left_;
    }


    const ranking::NodeBase* left_most(void) const
    {
      return impl_.head_.left_;
    }


    const ranking::NodeValue<T>* parent(const ranking::NodeBase* x) const
    {
      YAT_ASSERT(x);
      YAT_ASSERT(x->parent_);
      YAT_ASSERT(x->parent_ != &impl_.head_);
      return static_cast<const ranking::NodeValue<T>*>(x->parent_);
    }


    ranking::NodeValue<T>* parent(ranking::NodeBase* x) const
    {
      YAT_ASSERT(x);
      YAT_ASSERT(x->parent_);
      YAT_ASSERT(x->parent_ != &impl_.head_);
      return static_cast<ranking::NodeValue<T>*>(x->parent_);
    }


    /*
    ranking::NodeBase* right_most(void)
    {
      head_.right_;
    }


    const ranking::NodeBase* right_most(void) const
    {
      head_.right_;
    }
    */

    const_iterator
    upper_bound(const ranking::NodeValue<T>* x, const ranking::NodeBase* y,
                const T& key) const
    {
      if (!compare_(key, x->value()))
        return const_iterator(y);


      while (x) {
        // key is less than x value, search in left
        if (compare_(key, x->value())) {
          y = x;
          x = left(x);
        }
        else {
          YAT_ASSERT(x->right_ != &impl_.head_);
          x = right(x);
        }
      }
      return const_iterator(y);
    }


    const T& value(const ranking::NodeBase* p) const
    {
      YAT_ASSERT(p);
      YAT_ASSERT(!p->is_head_node());
      return static_cast<const ranking::NodeValue<T>*>(p)->value();
    }


    bool validate(void) const
    {
#ifdef YAT_DEBUG_RANKING
      if (!impl_.validate())
        return false;
      bool ok = true;
      size_t rank = 0;
      for (auto it = cbegin(); it!=cend(); ++it) {
        size_t r = ranking(it);
        if (r != rank) {
          std::cerr << "ranking: " << r << "; expected: " << rank << "\n";
          std::cerr << "size: " << it.node_->size_ << "\n";
          std::cerr << it.node_->parent_ << " "
                    << it.node_->is_left_node() << " "
                    << it.node_->is_right_node() << "\n---\n";
          ok = false;
        }
        ++rank;
      }
      return ok;
#else
      return true;
#endif
    }
  };

  // avoid doxygen reading code below as it has problems to to match
  // declarations and implementations unless matching perfectly.

  /// \cond IGNORE_DOXYGEN

  // implementations
  template<typename T, typename C>
  Ranking<T,C>::Ranking(const Ranking& other)
    : compare_(other.compare())
  {
    if (!other.empty())
      root_node() = copy(other);
    YAT_ASSERT(validate());
  }


  template<typename T, typename C>
  Ranking<T,C>::Ranking(Ranking&& other)
    : compare_(std::move(other.compare())), impl_(std::move(other.impl_))
  {
    YAT_ASSERT(validate());
  }


  template<typename T, typename C>
  Ranking<T, C>& Ranking<T, C>::operator=(const Ranking& other)
  {
    if (this != &other) {
      Ranking tmp(other);
      *this = std::move(tmp);
    }
    return *this;
  }


  template<typename T, typename C>
  Ranking<T, C>& Ranking<T, C>::operator=(Ranking&& other)
  {
    clear();
    compare_ = std::move(other.compare_);
    impl_ = std::move(other.impl_);
    return *this;
  }


  template<typename T, typename C>
  ranking::NodeValue<T>* Ranking<T,C>::copy(const Ranking& other)
  {
    YAT_ASSERT(validate());
    YAT_ASSERT(impl_.head_.parent_ == nullptr);
    YAT_ASSERT(other.first_node());
    ranking::NodeValue<T>* root = copy(other.first_node(), last_node());
    root->parent_ = nullptr;
    root->right_ = last_node();
    last_node()->left_ = root->left_most();
    last_node()->parent_ = root;
    YAT_ASSERT(validate());
    return root;
  }


  template<typename T, typename C>
  ranking::NodeValue<T>* Ranking<T,C>::copy(const ranking::NodeValue<T>* x,
                                            ranking::NodeBase* parent) const
  {
    YAT_ASSERT(x);
    ranking::NodeValue<T>* root = clone_node(x);
    root->height_ = x->height_;
    root->size_ = x->size_;
    YAT_ASSERT(root);
    root->parent_ = parent;
    try {
      if (x->right_ && !x->right_->is_head_node()) {
        YAT_ASSERT(x != right(x));
        YAT_ASSERT(x->right_ != &impl_.head_);
        root->right_ = copy(right(x), root);
      }

      parent = root;
      x = left(x);
      while (x) {
        ranking::NodeValue<T>* y = clone_node(x);
        y->height_ = x->height_;
        y->size_ = x->size_;
        parent->left_ = y;
        y->parent_ = parent;
        if (x->right_) {
          YAT_ASSERT(x->right_ != &impl_.head_);
          y->right_ = copy(right(x), y);
        }
        parent = y;
        x = left(x);
      }
    }
    catch (std::exception& e) {
      erase(root);
      std::rethrow_exception(std::current_exception());
    }

    return root;
  }


  template<typename T, typename C>
  ranking::NodeValue<T>*
  Ranking<T,C>::clone_node(const ranking::NodeValue<T>* x) const
  {
    YAT_ASSERT(x);
    ranking::NodeValue<T>* res = new ranking::NodeValue<T>(x->value());
    res->left_ = nullptr;
    res->right_ = nullptr;
    res->parent_ = nullptr;
    return res;
  }


  template<typename T, typename C>
  void Ranking<T, C>::erase_node(typename Ranking<T, C>::const_iterator p)
  {
    YAT_ASSERT(p != end());
    const ranking::NodeBase* node = p.node_;
    //    std::cerr << "erase_node: " << node << "\n";
    YAT_ASSERT(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();
      YAT_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) {
        impl_.relink(leftmost, leftmost->right_);
      }
      impl_.relink(node, leftmost);
      YAT_ASSERT(leftmost->left_ == node->left_);
      YAT_ASSERT(!leftmost->left_ || leftmost->left_->parent_==leftmost);
      leftmost->update_height();
      leftmost->size_ =
        1 + ranking::size(leftmost->left_) + ranking::size(leftmost->right_);
      leftmost->parent_->decrement_size();
      YAT_ASSERT(validate());
    }
    else {
      // single child node is simple, the child takes the node's place
      impl_.relink(node, node->left_ ? node->left_ : node->right_);
      node->parent_->decrement_size();
      node->parent_->update_height();
      YAT_ASSERT(validate());
    }
    // FIXME we need to delete the node, but be careful to not delete
    // any of ots children; perhaps const_cast first?

  }


  template<typename T, typename C>
  typename Ranking<T, C>::iterator
  Ranking<T, C>::erase(typename Ranking<T, C>::const_iterator p)
  {
    YAT_ASSERT(p != end());
    const_iterator res = p;
    ++res;
    erase_node(p);
    // iterator and const_iterator are same at the moment
    return res;
  }


  template<typename T, typename C>
  typename Ranking<T, C>::size_type Ranking<T, C>::erase(const T& value)
  {
    auto it = lower_bound(value);
    typename Ranking<T, C>::size_type n = 0;
    while (it!=end() && !compare_(value, *it)) {
      erase_node(it++);
      ++n;
    }
    return n;
  }


  template<typename T, typename C>
  typename Ranking<T, C>::iterator
  Ranking<T, C>::erase(typename Ranking<T, C>::const_iterator first,
                       typename Ranking<T, C>::const_iterator last)
  {
    if (first == cbegin() && last == cend())
      clear();
    else
      while (first != last) {
        erase_node(first++);
      }
    return last;
  }


  template<typename T, typename C>
  typename Ranking<T, C>::const_iterator Ranking<T, C>::find(const T& x) const
  {
    auto it = lower_bound(x);
    if (it != cend() && compare_(x, *it))
      it = cend();
    return it;
  }

  /// \endcond

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