Impl.h

#ifndef theplu_yat_utility_ranking_impl
#define theplu_yat_utility_ranking_impl

// $Id: Impl.h 4087 2021-08-30 02:00:02Z 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/>.
*/

// This is a private file used by "yat/utility/Ranking.h"

#include "NodeBase.h"

#include <cstddef>
#include <memory>

namespace theplu {
namespace yat {
namespace utility {


  // namespace for internal classes used in class Ranking
  namespace ranking {

    class Impl
    {
    public:
      Impl(void);
      Impl(const Impl& other) = delete;
      Impl(Impl&& other);
      Impl& operator=(const Impl& rhs) = delete;
      Impl& operator=(Impl&& rhs);

      // Head is the only node with no parent; it is also the node
      // with no value. All other nodes are NodeValue<T> pointers. Its
      // left child is the root node and it also holds a short cut to
      // the leftmost node to allow constant access and creating of
      // the begin() iterator.
      NodeBase head_;

      bool empty(void) const;
      size_t size(void) const;

      NodeBase*& root_node(void);
      const NodeBase* root_node(void) const;
      NodeBase*& left_most(void);
      const NodeBase* left_most(void) const;
      NodeBase*& right_most(void);
      const NodeBase* right_most(void) const;

      /*
        Node \a child is a child of \a parent. The child which is required
        to be a nullptr is assigned as \a element. and parent is updated
        as appropriate (height, size, etc) and rebalanced if needed
        including that balance of ancestors is checked.
      */
      void insert_and_rebalance(std::unique_ptr<NodeBase>&& element,
                                NodeBase& parent, bool left);

      /*
        Examine the balance of node->parent. If the height of its left
        branch and right branch differs more than one,
        rebalance. Otherwise or if recursive is true, call with parent
        and node as arguments.
       */
      void insert_rebalance(NodeBase* node, NodeBase* child);

      //
      void erase_and_rebalance(const NodeBase* node);

      // typically only called with assert, YAT_ASSERT or similar
      bool validate(void) const;
      bool validate(const NodeBase*) const;
      // return number of nodes left of node, i.e., number of nodes
      // with value less than node->value.
      size_t ranking(const NodeBase* node) const;
      void reset(void);
      /*
        \brief replace node with child

       Function assumes that child can replace node without collision
       or destrying the order in the tree, which means
       if there is a node->left its value is <= child->value
       if there is a node->right its value is <= child->value
       if there is a node->left (ecl child) there is no child->left
       if there is a node->right (excl child) there is no child->right
      */
      void relink(const NodeBase* node, NodeBase* child);

      /*
            y                               x
           / \                             / \
          x  T3                           T1  y
         / \       < - - - - - - -           / \
        T1 T2      Left Rotation            T2 T3

        \return new root in the subtree, i.e., y.
       */
      NodeBase* left_rotate(NodeBase* x);

      /*
            y                               x
           / \                             / \
          x  T3                           T1  y
         / \       - - - - - - - >           / \
        T1 T2      Right Rotation           T2 T3

        \return new root in the subtree, i.e., x.
       */
      NodeBase* right_rotate(NodeBase* y);
    private:
      NodeBase* right_most_;
      void move_data(Impl&&);
      void erase_rebalance(NodeBase* node);
      void erase_rebalance(NodeBase* parent, NodeBase* node);

    };
  } // end of namespace ranking


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