NodeBase.h

#ifndef theplu_yat_utility_detail_node_base
#define theplu_yat_utility_detail_node_base

// $Id: NodeBase.h 4072 2021-08-20 05:40:18Z 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 {


  // 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 left height minus right height
      int balance(void) const;

      // 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);

      // set size to 1 + size of left + size of right
      void update_size(void);
      // set height to max of left height and right height plus 1
      void update_height(void);
      // set height as in update_height. If heigh is updated, call
      // parent as well.
      void update_height_recursively(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;
      bool validate(bool head=false) const;
    };

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

  } // end of namespace ranking


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