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

Last change on this file since 4079 was 4079, checked in by Peter, 5 months ago

store the right_most node, so it can be accessed in constant time (rather than logarithmic); refs #710

  • Property svn:eol-style set to native
  • Property svn:keywords set to Id
File size: 4.2 KB
Line 
1#ifndef theplu_yat_utility_ranking_impl
2#define theplu_yat_utility_ranking_impl
3
4// $Id: Impl.h 4079 2021-08-26 08:38:04Z peter $
5
6/*
7  Copyright (C) 2021 Peter Johansson
8
9  This file is part of the yat library, http://dev.thep.lu.se/yat
10
11  The yat library is free software; you can redistribute it and/or
12  modify it under the terms of the GNU General Public License as
13  published by the Free Software Foundation; either version 3 of the
14  License, or (at your option) any later version.
15
16  The yat library is distributed in the hope that it will be useful,
17  but WITHOUT ANY WARRANTY; without even the implied warranty of
18  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
19  General Public License for more details.
20
21  You should have received a copy of the GNU General Public License
22  along with yat. If not, see <http://www.gnu.org/licenses/>.
23*/
24
25// This is a private file used by "yat/utility/Ranking.h"
26
27#include "NodeBase.h"
28
29#include <cstddef>
30#include <memory>
31
32namespace theplu {
33namespace yat {
34namespace utility {
35
36  /// \cond IGNORE_DOXYGEN
37
38  // namespace for internal classes used in class Ranking
39  namespace ranking {
40
41    class Impl
42    {
43    public:
44      Impl(void);
45      Impl(const Impl& other) = delete;
46      Impl(Impl&& other);
47      Impl& operator=(const Impl& rhs) = delete;
48      Impl& operator=(Impl&& rhs);
49
50      // Head is the only node with no parent; it is also the node
51      // with no value. All other nodes are NodeValue<T> pointers. Its
52      // left child is the root node and it also holds a short cut to
53      // the leftmost node to allow constant access and creating of
54      // the begin() iterator.
55      NodeBase head_;
56
57      bool empty(void) const;
58      size_t size(void) const;
59
60      NodeBase*& root_node(void);
61      const NodeBase* root_node(void) const;
62      NodeBase*& left_most(void);
63      const NodeBase* left_most(void) const;
64      NodeBase*& right_most(void);
65      const NodeBase* right_most(void) const;
66
67      /*
68        Node \a child is a child of \a parent. The child which is required
69        to be a nullptr is assigned as \a element. and parent is updated
70        as appropriate (height, size, etc) and rebalanced if needed
71        including that balance of ancestors is checked.
72      */
73      void insert_and_rebalance(std::unique_ptr<NodeBase>&& element,
74                                NodeBase& parent, bool left);
75
76      /*
77        Examine the balance of node->parent. If the height of its left
78        branch and right branch differs more than one,
79        rebalance. Otherwise or if recursive is true, call with parent
80        and node as arguments.
81       */
82      void insert_rebalance(NodeBase* node, NodeBase* child);
83
84      //
85      void erase_and_rebalance(const NodeBase* node);
86
87      // typically only called with assert, YAT_ASSERT or similar
88      bool validate(void) const;
89      bool validate(const NodeBase*) const;
90      // return number of nodes left of node, i.e., number of nodes
91      // with value less than node->value.
92      size_t ranking(const NodeBase* node) const;
93      void reset(void);
94      /*
95        \brief replace node with child
96
97       Function assumes that child can replace node without collision
98       or destrying the order in the tree, which means
99       if there is a node->left its value is <= child->value
100       if there is a node->right its value is <= child->value
101       if there is a node->left (ecl child) there is no child->left
102       if there is a node->right (excl child) there is no child->right
103      */
104      void relink(const NodeBase* node, NodeBase* child);
105
106      /*
107            y                               x
108           / \                             / \
109          x  T3                           T1  y
110         / \       < - - - - - - -           / \
111        T1 T2      Left Rotation            T2 T3
112
113        \return new root in the subtree, i.e., y.
114       */
115      NodeBase* left_rotate(NodeBase* x);
116
117      /*
118            y                               x
119           / \                             / \
120          x  T3                           T1  y
121         / \       - - - - - - - >           / \
122        T1 T2      Right Rotation           T2 T3
123
124        \return new root in the subtree, i.e., x.
125       */
126      NodeBase* right_rotate(NodeBase* y);
127    private:
128      NodeBase* right_most_;
129      void move_data(Impl&&);
130      void erase_rebalance(NodeBase* node);
131      void erase_rebalance(NodeBase* parent, NodeBase* node);
132
133    };
134  } // end of namespace ranking
135
136  /// \endcond
137
138}}} // of namespace utility, yat, and theplu
139#endif
Note: See TracBrowser for help on using the repository browser.