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

#ifndef theplu_yat_utility_detail_node_base
#define theplu_yat_utility_detail_node_base

// $Id: NodeBase.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 <cstddef>

namespace theplu {
namespace yat {
namespace utility {

  /// \cond IGNORE_DOXYGEN

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

    class NodeBase
    {
    public:
      NodeBase(void);
      virtual ~NodeBase(void);
      NodeBase* parent_;
      NodeBase* left_;
      NodeBase* right_;
      unsigned int height_; // max distance to leaf (plus 1)
      // number of total offsprings including myself
      size_t size_;

      // return 0 for root, 1 for its children, etc
      int generation(void) const;

      // increase size of node and parent node, recursively.
      void increment_size(void);
      // decrease size of node and parent node, recursively.
      void decrement_size(void);

      void update_height(void);

      // return true if head node
      bool is_head_node(void) const;
      // return true if having a parent and its left child is this
      bool is_left_node(void) const;
      // return true if having a parent and its right child is this
      bool is_right_node(void) const;
      // return true if having no parent
      bool is_root_node(void) const;
      // return traverse up in the tree following the left branch
      // until a node has no left branch and we return that leaf node.
      NodeBase* left_most(void);
      const NodeBase* left_most(void) const;
      // same as left_most but follow right branch
      NodeBase* right_most(void);
      const NodeBase* right_most(void) const;
      // Only used to validate that the tree is valid, used in debug
      // code and assertions.
      bool validate(void) const;
      bool recursive_validate(void) const;
    };

    size_t height(const NodeBase* node);
    size_t size(const NodeBase* node);

  } // end of namespace ranking

  /// \endcond

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