source: branches/kendall-score/yat/utility/ranking/Impl.cc @ 4077

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

implement insert with hint; refs #710

  • Property svn:eol-style set to native
  • Property svn:keywords set to Id
File size: 10.5 KB
Line 
1// $Id: Impl.cc 4077 2021-08-26 04:07:09Z peter $
2
3/*
4  Copyright (C) 2021 Peter Johansson
5
6  This file is part of the yat library, http://dev.thep.lu.se/yat
7
8  The yat library is free software; you can redistribute it and/or
9  modify it under the terms of the GNU General Public License as
10  published by the Free Software Foundation; either version 3 of the
11  License, or (at your option) any later version.
12
13  The yat library is distributed in the hope that it will be useful,
14  but WITHOUT ANY WARRANTY; without even the implied warranty of
15  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16  General Public License for more details.
17
18  You should have received a copy of the GNU General Public License
19  along with yat. If not, see <http://www.gnu.org/licenses/>.
20*/
21
22#include <config.h>
23
24#include "Ranking.h"
25
26#include <cassert>
27#include <cstddef>
28#include <iostream>
29
30namespace theplu {
31namespace yat {
32namespace utility {
33namespace ranking {
34
35  Impl::Impl(void)
36  {
37    reset();
38  }
39
40
41  Impl::Impl(Impl&& from)
42  {
43    reset();
44    move_data(std::move(from));
45  }
46
47
48  Impl& Impl::operator=(Impl&& rhs)
49  {
50    assert(!head_.parent_);
51    move_data(std::move(rhs));
52    assert(validate());
53    return *this;
54  }
55
56
57  bool Impl::empty(void) const
58  {
59    return !root_node();
60  }
61
62
63  size_t Impl::size(void) const
64  {
65    assert(head_.size_ > 0);
66    return head_.size_ - 1;
67  }
68
69
70  void Impl::move_data(Impl&& from)
71  {
72    assert(empty());
73
74    head_.parent_ = from.head_.parent_;
75    head_.left_ = from.head_.left_;
76    if (head_.left_) {
77      head_.left_->parent_ = &head_;
78      head_.right_ = from.head_.right_;
79    }
80    else
81      head_.right_ = &head_;
82    head_.height_ = from.head_.height_;
83    head_.size_ = from.head_.size_;
84    from.reset();
85    assert(validate());
86  }
87
88
89  void Impl::relink(const NodeBase* node, NodeBase* child)
90  {
91    assert(node->parent_);
92    assert(node != &head_);
93    assert(child != &head_);
94
95    // make child the child of node's parent
96    if (node->is_left_node())
97      node->parent_->left_ = child;
98    else if (node->is_right_node())
99      node->parent_->right_ = child;
100
101    // make node's parent the parent of child
102    if (child)
103      child->parent_ = node->parent_;
104
105    // inherit the kids
106    if (child) {
107      if (node->left_ && node->left_!=child) {
108        assert(!child->left_);
109        child->left_ = node->left_;
110        if (node->left_)
111          node->left_->parent_ = child;
112      }
113      if (node->right_ && node->right_!=child) {
114        assert(!child->right_);
115        child->right_ = node->right_;
116        if (node->right_)
117          node->right_->parent_ = child;
118      }
119    }
120
121    // update pointer to left_most node
122    if (head_.left_ == node) {
123      head_.left_ = child ? child : node->parent_;
124    }
125    assert(child==nullptr || child->is_left_node() || child->is_right_node());
126  }
127
128
129  size_t Impl::ranking(const NodeBase* node) const
130  {
131    assert(node);
132    if (node->is_head_node())
133      return size();
134
135    assert(node->parent_);
136    // The rank of the parent is the sum of the rank of the
137    // left->child, the child itself, and the size of the child's
138    // right branch.
139    if (node->is_left_node())
140      return ranking(node->parent_) - (1 + ranking::size(node->right_));
141
142    // right node
143    return ranking(node->parent_) + 1 + ranking::size(node->left_);
144  }
145
146
147  void Impl::reset(void)
148  {
149    head_.parent_ = nullptr;
150    head_.left_ = nullptr;
151    head_.right_ = &head_; // most left node
152    head_.update_height();
153    head_.update_size();
154    assert(validate());
155  }
156
157
158  void Impl::erase_and_rebalance(const NodeBase* node)
159  {
160    // two children
161    if (node->left_ && node->right_) {
162      // When node has two branches, we take the most leftmost node in
163      // the right branch and place in nodes place.
164      ranking::NodeBase* leftmost = node->right_->left_most();
165      assert(leftmost->left_ == nullptr);
166
167      // If the leftmost node has a kid, we need to relink the kid
168      // with its grand parent
169      if (leftmost->parent_ != node)
170        relink(leftmost, leftmost->right_);
171      relink(node, leftmost);
172      assert(leftmost->left_ == node->left_);
173      assert(!leftmost->left_ || leftmost->left_->parent_==leftmost);
174      leftmost->update_height();
175      leftmost->parent_->update_height_recursively();
176      leftmost->update_size();
177      leftmost->parent_->decrement_size();
178      erase_rebalance(leftmost);
179    }
180    else {
181      // single child node is simple, the child takes the node's place
182      relink(node, node->left_ ? node->left_ : node->right_);
183      node->parent_->decrement_size();
184      node->parent_->update_height_recursively();
185      erase_rebalance(node->parent_);
186    }
187  }
188
189
190  void Impl::insert_and_rebalance(std::unique_ptr<NodeBase>&& element,
191                                  NodeBase& parent, bool left)
192  {
193    NodeBase* child = nullptr;
194    if (left) {
195      parent.left_ = element.release();
196      child = parent.left_;
197      if (&parent == left_most())
198        left_most() = child;
199    }
200    else {
201      parent.right_ = element.release();
202      child = parent.right_;
203    }
204
205    child->parent_ = &parent;
206    parent.increment_size();
207    parent.update_height_recursively();
208    insert_rebalance(&parent, child);
209  }
210
211
212  void Impl::erase_rebalance(NodeBase* node)
213  {
214    assert(node);
215    if (node->is_root_node())
216      return;
217
218    int balance = node->balance();
219
220    if (std::abs(balance) > 1) {
221      assert(0);
222    }
223
224    NodeBase* parent = node->parent_;
225    assert(parent);
226    erase_rebalance(parent);
227  }
228
229
230  void Impl::insert_rebalance(NodeBase* node, NodeBase* child)
231  {
232    assert(node);
233    assert(child);
234    assert(child->parent_ == node);
235    assert(child == node->left_ || child == node->right_);
236
237    NodeBase* parent = node->parent_;
238    assert(parent);
239    if (parent->is_head_node())
240      return;
241
242    // left height minus right height
243    int balance = parent->balance();
244
245    /*
246      If parent is unbalanced, we have four cases.
247
248      Below parent is denoted z
249      node is denoted y
250      child is denoted x
251
252      and all three are ancestors of the just inserted node.
253
254      a) Left Left Case
255
256      T1, T2, T3 and T4 are subtrees.
257            z                                      y
258           / \                                   /   \
259          y   T4      Right Rotate (z)          x      z
260         / \          - - - - - - - - ->      /  \    /  \
261        x   T3                               T1  T2  T3  T4
262       / \
263      T1  T2
264
265      b) Left Right Case
266
267            z                              z                           x
268           / \                            / \                        /   \
269          y   T4  Left Rotate (y)        x   T4  Right Rotate(z)    y     z
270         / \      - - - - - - - - ->    / \     - - - - - - - ->   / \   / \
271        T1  x                          y   T3                     T1 T2 T3 T4
272           / \                        / \
273          T2 T3                     T1   T2
274
275      c) Right Right Case
276
277          z                              y
278         / \                            /  \
279        T1  y     Left Rotate(z)       z    x
280           / \    - - - - - - - ->    / \  / \
281          T2  x                      T1 T2T3 T4
282             / \
283            T3 T4
284
285      d) Right Left Case
286
287        z                            z                            x
288       / \                          / \                         /   \
289      T1  y   Right Rotate (y)    T1   x    Left Rotate(z)     z     y
290         / \  - - - - - - - - ->      / \   - - - - - - - ->  / \   / \
291        x   T4                      T2   y                  T1  T2 T3  T4
292       / \                              / \
293      T2  T3                           T3  T4
294    */
295
296    if (balance < -1) {
297      assert(height(parent->right_) > height(parent->left_));
298      assert(parent->right_ == node);
299      // right right case
300      if (node->right_ == child) {
301        left_rotate(parent);
302        return;
303      }
304      // right left case
305      assert(node->left_ == child);
306      right_rotate(node);
307      left_rotate(parent);
308      return;
309    }
310    else if (balance > 1) {
311      // left right case
312      if (node->right_ == child) {
313        left_rotate(node);
314        right_rotate(parent);
315        return;
316      }
317      // left left case
318      assert(node->left_ == child);
319      right_rotate(parent);
320      return;
321    }
322
323    assert(parent->parent_);
324    insert_rebalance(parent, node);
325  }
326
327
328  NodeBase* Impl::left_rotate(NodeBase* x)
329  {
330    assert(x);
331    NodeBase* y = x->right_;
332    assert(y);
333    NodeBase* T2 = y->left_;
334
335    // rotate
336    if (x->is_left_node())
337      x->parent_->left_ = y;
338    else {
339      assert(x->is_right_node());
340      x->parent_->right_ = y;
341    }
342    y->parent_ = x->parent_;
343
344    y->left_ = x;
345    x->parent_ = y;
346
347    x->right_ = T2;
348    if (T2)
349      T2->parent_ = x;
350
351    // update height - always update from leaf and to root
352    x->update_height();
353    y->update_height();
354    assert(y->parent_);
355    y->parent_->update_height_recursively();
356
357    // update size
358    x->update_size();
359    y->update_size();
360
361    return y;
362  }
363
364
365  NodeBase* Impl::right_rotate(NodeBase* y)
366  {
367    NodeBase* x = y->left_;
368    assert(x);
369    NodeBase* T2 = x->right_;
370
371    // rotate
372    if (y->is_left_node())
373      y->parent_->left_ = x;
374    else {
375      assert(y->is_right_node());
376      y->parent_->right_ = x;
377    }
378    x->parent_ = y->parent_;
379
380    x->right_ = y;
381    y->parent_ = x;
382
383    y->left_ = T2;
384    if (T2)
385      T2->parent_ = y;
386
387    // update height
388    y->update_height();
389    x->update_height();
390    assert(x->parent_);
391    x->parent_->update_height_recursively();
392
393    // update size
394    y->update_size();
395    x->update_size();
396
397    return x;
398  }
399
400
401  bool Impl::validate(void) const
402  {
403#ifdef NDEBUG
404    return true;
405#else
406    if (!head_.validate(true)) {
407      std::cerr << "Impl: head failed\n";
408      return false;
409    }
410    assert(left_most() == head_.left_most());
411
412    if (root_node()) {
413      if (root_node()->is_left_node() == false) {
414        std::cerr << "error: root is not a left node\n";
415        return false;
416      }
417      if (root_node()->is_right_node()) {
418        std::cerr << "error: root is a right node\n";
419        return false;
420      }
421    }
422
423    if (!validate(root_node())) {
424      std::cerr << "Impl: validate(root_node()) failed\n";
425      return false;
426    }
427
428
429    /*
430    if (root_node()) {
431      if (root_node()->left_most() != head_.right_) {
432        std::cerr << "head_.right incorrect\n";
433        return false;
434      }
435      if (!root_node()->recursive_validate())
436        return false;
437    }
438    else if (!head_.validate())
439      return false;
440    */
441    return true;
442#endif
443  }
444
445
446  bool Impl::validate(const NodeBase* node) const
447  {
448    if (node == nullptr)
449      return true;
450    node->validate();
451    validate(node->left_);
452    validate(node->right_);
453    return true;
454  }
455
456
457  NodeBase*& Impl::left_most(void)
458  {
459    return head_.right_;
460  }
461
462
463  const NodeBase* Impl::left_most(void) const
464  {
465    return head_.right_;
466  }
467
468
469  NodeBase* Impl::right_most(void)
470  {
471    // FIXME this scaled logN, make it constant time
472    return root_node()->right_most();
473  }
474
475
476  const NodeBase* Impl::right_most(void) const
477  {
478    // FIXME this scaled logN, make it constant time
479    return root_node()->right_most();
480  }
481
482
483  NodeBase*& Impl::root_node(void)
484  {
485    return head_.left_;
486  }
487
488
489  const NodeBase* Impl::root_node(void) const
490  {
491    return head_.left_;
492  }
493
494
495}
496}}} // of namespace utility, yat, and theplu
Note: See TracBrowser for help on using the repository browser.