yat/utility/ranking/NodeBase.h

Code
Comments
Other
Rev Date Author Line
4064 05 Aug 21 peter 1 #ifndef theplu_yat_utility_detail_node_base
4064 05 Aug 21 peter 2 #define theplu_yat_utility_detail_node_base
4064 05 Aug 21 peter 3
4064 05 Aug 21 peter 4 // $Id$
4064 05 Aug 21 peter 5
4064 05 Aug 21 peter 6 /*
4064 05 Aug 21 peter 7   Copyright (C) 2021 Peter Johansson
4064 05 Aug 21 peter 8
4064 05 Aug 21 peter 9   This file is part of the yat library, http://dev.thep.lu.se/yat
4064 05 Aug 21 peter 10
4064 05 Aug 21 peter 11   The yat library is free software; you can redistribute it and/or
4064 05 Aug 21 peter 12   modify it under the terms of the GNU General Public License as
4064 05 Aug 21 peter 13   published by the Free Software Foundation; either version 3 of the
4064 05 Aug 21 peter 14   License, or (at your option) any later version.
4064 05 Aug 21 peter 15
4064 05 Aug 21 peter 16   The yat library is distributed in the hope that it will be useful,
4064 05 Aug 21 peter 17   but WITHOUT ANY WARRANTY; without even the implied warranty of
4064 05 Aug 21 peter 18   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
4064 05 Aug 21 peter 19   General Public License for more details.
4064 05 Aug 21 peter 20
4064 05 Aug 21 peter 21   You should have received a copy of the GNU General Public License
4064 05 Aug 21 peter 22   along with yat. If not, see <http://www.gnu.org/licenses/>.
4064 05 Aug 21 peter 23 */
4064 05 Aug 21 peter 24
4065 05 Aug 21 peter 25 // This is a private file used by yat/utility/Ranking.h
4065 05 Aug 21 peter 26
4071 18 Aug 21 peter 27 #include <cstddef>
4071 18 Aug 21 peter 28
4064 05 Aug 21 peter 29 namespace theplu {
4064 05 Aug 21 peter 30 namespace yat {
4064 05 Aug 21 peter 31 namespace utility {
4064 05 Aug 21 peter 32
4065 05 Aug 21 peter 33   /// \cond IGNORE_DOXYGEN
4065 05 Aug 21 peter 34
4064 05 Aug 21 peter 35   // namespace for internal classes used in class Ranking
4064 05 Aug 21 peter 36   namespace ranking {
4064 05 Aug 21 peter 37
4064 05 Aug 21 peter 38     class NodeBase
4064 05 Aug 21 peter 39     {
4064 05 Aug 21 peter 40     public:
4064 05 Aug 21 peter 41       NodeBase(void);
4064 05 Aug 21 peter 42       virtual ~NodeBase(void);
4064 05 Aug 21 peter 43       NodeBase* parent_;
4064 05 Aug 21 peter 44       NodeBase* left_;
4064 05 Aug 21 peter 45       NodeBase* right_;
4071 18 Aug 21 peter 46       unsigned int height_; // max distance to leaf (plus 1)
4071 18 Aug 21 peter 47       // number of total offsprings including myself
4071 18 Aug 21 peter 48       size_t size_;
4064 05 Aug 21 peter 49
4072 20 Aug 21 peter 50       // return left height minus right height
4072 20 Aug 21 peter 51       int balance(void) const;
4072 20 Aug 21 peter 52
4070 09 Aug 21 peter 53       // return 0 for root, 1 for its children, etc
4070 09 Aug 21 peter 54       int generation(void) const;
4070 09 Aug 21 peter 55
4071 18 Aug 21 peter 56       // increase size of node and parent node, recursively.
4071 18 Aug 21 peter 57       void increment_size(void);
4071 18 Aug 21 peter 58       // decrease size of node and parent node, recursively.
4071 18 Aug 21 peter 59       void decrement_size(void);
4071 18 Aug 21 peter 60
4072 20 Aug 21 peter 61       // set size to 1 + size of left + size of right
4072 20 Aug 21 peter 62       void update_size(void);
4072 20 Aug 21 peter 63       // set height to max of left height and right height plus 1
4071 18 Aug 21 peter 64       void update_height(void);
4072 20 Aug 21 peter 65       // set height as in update_height. If heigh is updated, call
4072 20 Aug 21 peter 66       // parent as well.
4072 20 Aug 21 peter 67       void update_height_recursively(void);
4071 18 Aug 21 peter 68
4067 05 Aug 21 peter 69       // return true if head node
4064 05 Aug 21 peter 70       bool is_head_node(void) const;
4067 05 Aug 21 peter 71       // return true if having a parent and its left child is this
4064 05 Aug 21 peter 72       bool is_left_node(void) const;
4067 05 Aug 21 peter 73       // return true if having a parent and its right child is this
4064 05 Aug 21 peter 74       bool is_right_node(void) const;
4067 05 Aug 21 peter 75       // return true if having no parent
4064 05 Aug 21 peter 76       bool is_root_node(void) const;
4067 05 Aug 21 peter 77       // return traverse up in the tree following the left branch
4067 05 Aug 21 peter 78       // until a node has no left branch and we return that leaf node.
4064 05 Aug 21 peter 79       NodeBase* left_most(void);
4067 05 Aug 21 peter 80       const NodeBase* left_most(void) const;
4067 05 Aug 21 peter 81       // same as left_most but follow right branch
4064 05 Aug 21 peter 82       NodeBase* right_most(void);
4064 05 Aug 21 peter 83       const NodeBase* right_most(void) const;
4072 20 Aug 21 peter 84       bool validate(bool head=false) const;
4064 05 Aug 21 peter 85     };
4071 18 Aug 21 peter 86
4071 18 Aug 21 peter 87     size_t height(const NodeBase* node);
4071 18 Aug 21 peter 88     size_t size(const NodeBase* node);
4071 18 Aug 21 peter 89
4064 05 Aug 21 peter 90   } // end of namespace ranking
4064 05 Aug 21 peter 91
4065 05 Aug 21 peter 92   /// \endcond
4065 05 Aug 21 peter 93
4064 05 Aug 21 peter 94 }}} // of namespace utility, yat, and theplu
4064 05 Aug 21 peter 95 #endif

Generated on Sat Oct 14 02:24:16 2023 (UTC) by svndigest 0.11.2pre (dev build 1672)