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

#ifndef theplu_yat_utility_ranking_impl
#define theplu_yat_utility_ranking_impl

// $Id: Impl.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/>.
*/

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

#include "NodeBase.h"

#include <cstddef>

namespace theplu {
namespace yat {
namespace utility {

  /// \cond IGNORE_DOXYGEN

  // 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 value. Its parent is the root
      // node and the rest of the tree is in the left branch from the
      // root. Also, it holds a link to the leftmost node, which
      // corresponds to begin()
      NodeBase head_;
      // typically only called with assert, YAT_ASSERT or similar
      bool validate(void) 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);
    private:
      void move_data(Impl&&);
    };
  } // end of namespace ranking

  /// \endcond

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