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

#ifndef theplu_yat_utility_ranking
#define theplu_yat_utility_ranking

// $Id: Ranking.h 4079 2021-08-26 08:38:04Z 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 <iostream>
#include <iterator>
#include <memory>

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;

    /**
       \brief Destructor
     */
    ~Ranking(void)
    {
      clear();
    }

    /**
       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, i.e., the
       node with the smallest value.
     */
    iterator begin(void)
    {
      return iterator(impl_.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(impl_.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, i.e., the
       node with the largest value.
     */
    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(root_node() != head_node());
        erase(root_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 impl_.empty();
    }


    /**
       Remove node 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

       If \c hint will follow the inserted element, the insertion is done
       in constant time. Otherwise, the usual insert function is
       called which takes logN.
     */
    iterator insert(const_iterator hint, const T& element)
    {
      std::unique_ptr<ranking::NodeValue<T>>
        newnode(new ranking::NodeValue<T>(element));
      return insert(hint, std::move(newnode));
    }


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


    /**
       \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(root_node(), head_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(root_node(), head_node(), x);
    }


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


    /**
       \return number of elements in container
     */
    size_t size(void) const
    {
      return impl_.size();
    }

  private:
    Compare compare_;
    ranking::Impl impl_;

    iterator
    insert_and_rebalance(std::unique_ptr<ranking::NodeValue<T>>&& element,
                         ranking::NodeBase& parent, bool left)
    {
      iterator result(element.get());
      impl_.insert_and_rebalance(std::move(element), parent, left);
      YAT_ASSERT(validate());
      return result;
    }



    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 << ", H=" << ranking::height(p) << ", S=" << ranking::size(p);
        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) const;

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

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


    ranking::NodeValue<T>* root_node(void)
    {
      return static_cast<ranking::NodeValue<T>*>(impl_.root_node());
    }


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


    ranking::NodeBase* head_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_)
          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)
    {

      if (empty()) {
        element->parent_ = &impl_.head_;
        impl_.root_node() = element.release();
        impl_.head_.left_ = impl_.root_node();
        impl_.head_.right_ = impl_.root_node();
        impl_.right_most() = impl_.root_node();
        impl_.head_.update_height();
        impl_.head_.update_size();

        YAT_ASSERT(impl_.root_node()->parent_);
        YAT_ASSERT(impl_.root_node()->parent_ == &impl_.head_);
        YAT_ASSERT(impl_.root_node()->is_left_node());

        YAT_ASSERT(validate());
        return iterator(root_node());
      }

      return insert(impl_.root_node(), std::move(element));
    }


    // Insert \a element into the subtree in which x is the root.
    iterator insert(ranking::NodeBase* x,
                    std::unique_ptr<ranking::NodeValue<T>>&& element)
    {
      YAT_ASSERT(x);
      YAT_ASSERT(!x->is_head_node());

      while (true) {
        ranking::NodeBase* parent = x;
        if (compare_(element->value(), value(x))) {
          x = x->left_;
          if (x == nullptr)
            return insert_and_rebalance(std::move(element), *parent, true);
        }
        else {
          x = x->right_;
          if (x == nullptr)
            return insert_and_rebalance(std::move(element), *parent, false);
        }
      }
      YAT_ASSERT(0 && "we can't reach here");
      return iterator(element.get());
    }


    iterator insert(const_iterator hint,
                    std::unique_ptr<ranking::NodeValue<T>>&& element)
    {
      // special case when hint == end()
      if (hint.node_ == head_node()) {
        YAT_ASSERT(hint == cend());
        if (empty() || compare_(element->value(), value(impl_.right_most())))
          return insert(std::move(element));
        return insert_and_rebalance(std::move(element), *impl_.right_most(),
                                    false);
      }

      YAT_ASSERT(hint != end());

      // value <= hint i.e. !(hint<value)
      if (!compare_(*hint, element->value())) {
        // if hint == begin
        if (hint.node_ == impl_.left_most()) {
          YAT_ASSERT(hint == cbegin());
          return insert_and_rebalance(std::move(element),
                                      *impl_.left_most(),
                                      true);
        }

        // prev <= value <= hint insert
        YAT_ASSERT(hint != cbegin());
        auto before = std::prev(hint);
        if (!compare_(element->value(), *before)) {
          return insert(const_cast<ranking::NodeBase*>(hint.node_),
                        std::move(element));
        }
        else {
          return insert(std::move(element));
        }
      }
      // else value > hint
      else {
        YAT_ASSERT(compare_(*hint, element->value()));
        // hint == rightmost
        if (hint.node_ == impl_.right_most()) {
          return insert_and_rebalance(std::move(element),
                                      *impl_.right_most(),
                                      false);
        }
        auto after = std::next(hint);
        YAT_ASSERT(after != cend());
        // hint < value <= after
        if (!compare_(*after, element->value())) {
          return insert(const_cast<ranking::NodeBase*>(after.node_),
                        std::move(element));
        }
      }

      return insert(std::move(element));
    }


    /*
      Find the first node that is greater or equal to key, i.e., all
      elements left of returned node are less than key.
     */
    const_iterator
    lower_bound(const ranking::NodeValue<T>* x, const ranking::NodeBase* y,
                const T& key) const
    {
      // x is used to traverse the tree
      // y holds the result

      while (x) {
        // key is less (or equal) than x, store x as potential result
        // and search in left branch
        if (!compare_(x->value(), key)) {
          y = x;
          x = left(x);
        }
        // key is greater than x, the lower bound is not x; it is
        // either in the right branch or a previously assigned
        // ancestor. Do not store x as potential result, but search
        // branch.
        else
          x = right(x);
      }
      // x has reached a leaf, and the result should be stored in y

      // returned node is not smaller than key
      YAT_ASSERT(y==head_node() || !compare_(value(y), key));
      // all nodes left of returned node are smaller than key
      YAT_ASSERT(y->left_==nullptr ||
                 compare_(value(y->left_->right_most()), key));
      return const_iterator(y);
    }


    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_);
    }


    /*
      Find the first node that is greater than key, i.e., all
      elements left of returned node are less or equal to key.
     */
    const_iterator
    upper_bound(const ranking::NodeValue<T>* x, const ranking::NodeBase* y,
                const T& key) const
    {
      // x is used to traverse the tree
      // y holds the result

      while (x) {
        // key is less than x value, x is a potential upper_bound,
        // store and search in left
        if (compare_(key, x->value())) {
          y = x;
          x = left(x);
        }
        else {
          // key is greater (or equal) than x, x is not the upper
          // bound. It is either in the right branch or in a
          // previously assigned ancestor (current y).
          x = right(x);
        }
      }
      // x has reached a leaf, and the result should be stored in y

      // key is less than returned node
      YAT_ASSERT(y==head_node() || compare_(key, value(y)));
      // all nodes left of returned node are smaller (or equal) than
      // key, i.e., key is not smaller than any of the nodes to the
      // left of returned node.
      YAT_ASSERT(y->left_==nullptr ||
                 !compare_(key, value(y->left_->right_most())));
      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
    {
#ifndef YAT_DEBUG_RANKING
      return true;
#else
      if (!impl_.validate()) {
        std::cerr << "Impl::validate failed\n";
        return false;
      }

      bool ok = true;
      size_t rank = 0;
      YAT_ASSERT(cbegin().node_);
      YAT_ASSERT(cend().node_);
      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;
#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())
      impl_.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(other.root_node());
    ranking::NodeValue<T>* root = copy(other.root_node());
    root->parent_ = head_node();
    head_node()->left_ = root;
    head_node()->right_ = root->left_most();
    head_node()->update_height();
    head_node()->update_size();
    if (root_node())
      impl_.right_most() = root_node()->right_most();
    else
      impl_.right_most() = head_node();
    YAT_ASSERT(validate());
    return root;
  }


  template<typename T, typename C>
  ranking::NodeValue<T>*
  Ranking<T,C>::copy(const ranking::NodeValue<T>* x) const
  {
    YAT_ASSERT(x);
    ranking::NodeValue<T>* root = clone_node(x);
    YAT_ASSERT(root);
    root->height_ = x->height_;
    root->size_ = x->size_;

    try {
      if (x->left_) {
        root->left_ = copy(left(x));
        root->left_->parent_ = root;
      }
      if (x->right_) {
        root->right_ = copy(right(x));
        root->right_->parent_ = root;
      }
    }
    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_;
    YAT_ASSERT(node);

    impl_.erase_and_rebalance(node);
    delete node;
    YAT_ASSERT(validate());
    return;
  }


  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