source: trunk/yat/utility/ranking/Impl.cc @ 4085

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

fix include so it works in a vpath build

  • Property svn:eol-style set to native
  • Property svn:keywords set to Id
File size: 10.8 KB
Line 
1// $Id: Impl.cc 4085 2021-08-29 10:57:38Z 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 "yat/utility/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      right_most_ = root_node()->right_most();
80    }
81    else {
82      head_.right_ = &head_;
83      right_most() = &head_;
84    }
85    head_.height_ = from.head_.height_;
86    head_.size_ = from.head_.size_;
87    from.reset();
88    assert(validate());
89  }
90
91
92  void Impl::relink(const NodeBase* node, NodeBase* child)
93  {
94    assert(node->parent_);
95    assert(node != &head_);
96    assert(child != &head_);
97
98    // make child the child of node's parent
99    if (node->is_left_node())
100      node->parent_->left_ = child;
101    else if (node->is_right_node())
102      node->parent_->right_ = child;
103
104    // make node's parent the parent of child
105    if (child)
106      child->parent_ = node->parent_;
107
108    // inherit the kids
109    if (child) {
110      if (node->left_ && node->left_!=child) {
111        assert(!child->left_);
112        child->left_ = node->left_;
113        if (node->left_)
114          node->left_->parent_ = child;
115      }
116      if (node->right_ && node->right_!=child) {
117        assert(!child->right_);
118        child->right_ = node->right_;
119        if (node->right_)
120          node->right_->parent_ = child;
121      }
122    }
123
124    // update pointer to left_most node
125    if (left_most() == node)
126      left_most() = child ? child : node->parent_;
127    if (right_most() == node)
128      right_most() = child ? child : node->parent_;
129    assert(child==nullptr || child->is_left_node() || child->is_right_node());
130  }
131
132
133  size_t Impl::ranking(const NodeBase* node) const
134  {
135    assert(node);
136    if (node->is_head_node())
137      return size();
138
139    assert(node->parent_);
140    // The rank of the parent is the sum of the rank of the
141    // left->child, the child itself, and the size of the child's
142    // right branch.
143    if (node->is_left_node())
144      return ranking(node->parent_) - (1 + ranking::size(node->right_));
145
146    // right node
147    return ranking(node->parent_) + 1 + ranking::size(node->left_);
148  }
149
150
151  void Impl::reset(void)
152  {
153    head_.parent_ = nullptr;
154    head_.left_ = nullptr;
155    head_.right_ = &head_; // most left node
156    right_most_ = &head_;
157    head_.update_height();
158    head_.update_size();
159    assert(validate());
160  }
161
162
163  void Impl::erase_and_rebalance(const NodeBase* node)
164  {
165    // two children
166    if (node->left_ && node->right_) {
167      // When node has two branches, we take the most leftmost node in
168      // the right branch and place in nodes place.
169      ranking::NodeBase* leftmost = node->right_->left_most();
170      assert(leftmost->left_ == nullptr);
171
172      // If the leftmost node has a kid, we need to relink the kid
173      // with its grand parent
174      if (leftmost->parent_ != node)
175        relink(leftmost, leftmost->right_);
176      relink(node, leftmost);
177      assert(leftmost->left_ == node->left_);
178      assert(!leftmost->left_ || leftmost->left_->parent_==leftmost);
179      leftmost->update_height();
180      leftmost->parent_->update_height_recursively();
181      leftmost->update_size();
182      leftmost->parent_->decrement_size();
183      erase_rebalance(leftmost);
184    }
185    else {
186      // single child node is simple, the child takes the node's place
187      relink(node, node->left_ ? node->left_ : node->right_);
188      node->parent_->decrement_size();
189      node->parent_->update_height_recursively();
190      erase_rebalance(node->parent_);
191    }
192  }
193
194
195  void Impl::insert_and_rebalance(std::unique_ptr<NodeBase>&& element,
196                                  NodeBase& parent, bool left)
197  {
198    NodeBase* child = nullptr;
199    if (left) {
200      parent.left_ = element.release();
201      child = parent.left_;
202      if (&parent == left_most())
203        left_most() = child;
204    }
205    else {
206      parent.right_ = element.release();
207      child = parent.right_;
208      if (&parent == right_most())
209        right_most() = child;
210    }
211
212    child->parent_ = &parent;
213    parent.increment_size();
214    parent.update_height_recursively();
215    insert_rebalance(&parent, child);
216  }
217
218
219  void Impl::erase_rebalance(NodeBase* node)
220  {
221    assert(node);
222    if (node->is_root_node())
223      return;
224
225    int balance = node->balance();
226
227    if (std::abs(balance) > 1) {
228      assert(0);
229    }
230
231    NodeBase* parent = node->parent_;
232    assert(parent);
233    erase_rebalance(parent);
234  }
235
236
237  void Impl::insert_rebalance(NodeBase* node, NodeBase* child)
238  {
239    assert(node);
240    assert(child);
241    assert(child->parent_ == node);
242    assert(child == node->left_ || child == node->right_);
243
244    NodeBase* parent = node->parent_;
245    assert(parent);
246    if (parent->is_head_node())
247      return;
248
249    // left height minus right height
250    int balance = parent->balance();
251
252    /*
253      If parent is unbalanced, we have four cases.
254
255      Below parent is denoted z
256      node is denoted y
257      child is denoted x
258
259      and all three are ancestors of the just inserted node.
260
261      a) Left Left Case
262
263      T1, T2, T3 and T4 are subtrees.
264            z                                      y
265           / \                                   /   \
266          y   T4      Right Rotate (z)          x      z
267         / \          - - - - - - - - ->      /  \    /  \
268        x   T3                               T1  T2  T3  T4
269       / \
270      T1  T2
271
272      b) Left Right Case
273
274            z                              z                           x
275           / \                            / \                        /   \
276          y   T4  Left Rotate (y)        x   T4  Right Rotate(z)    y     z
277         / \      - - - - - - - - ->    / \     - - - - - - - ->   / \   / \
278        T1  x                          y   T3                     T1 T2 T3 T4
279           / \                        / \
280          T2 T3                     T1   T2
281
282      c) Right Right Case
283
284          z                              y
285         / \                            /  \
286        T1  y     Left Rotate(z)       z    x
287           / \    - - - - - - - ->    / \  / \
288          T2  x                      T1 T2T3 T4
289             / \
290            T3 T4
291
292      d) Right Left Case
293
294        z                            z                            x
295       / \                          / \                         /   \
296      T1  y   Right Rotate (y)    T1   x    Left Rotate(z)     z     y
297         / \  - - - - - - - - ->      / \   - - - - - - - ->  / \   / \
298        x   T4                      T2   y                  T1  T2 T3  T4
299       / \                              / \
300      T2  T3                           T3  T4
301    */
302
303    if (balance < -1) {
304      assert(height(parent->right_) > height(parent->left_));
305      assert(parent->right_ == node);
306      // right right case
307      if (node->right_ == child) {
308        left_rotate(parent);
309        return;
310      }
311      // right left case
312      assert(node->left_ == child);
313      right_rotate(node);
314      left_rotate(parent);
315      return;
316    }
317    else if (balance > 1) {
318      // left right case
319      if (node->right_ == child) {
320        left_rotate(node);
321        right_rotate(parent);
322        return;
323      }
324      // left left case
325      assert(node->left_ == child);
326      right_rotate(parent);
327      return;
328    }
329
330    assert(parent->parent_);
331    insert_rebalance(parent, node);
332  }
333
334
335  NodeBase* Impl::left_rotate(NodeBase* x)
336  {
337    assert(x);
338    NodeBase* y = x->right_;
339    assert(y);
340    NodeBase* T2 = y->left_;
341
342    // rotate
343    if (x->is_left_node())
344      x->parent_->left_ = y;
345    else {
346      assert(x->is_right_node());
347      x->parent_->right_ = y;
348    }
349    y->parent_ = x->parent_;
350
351    y->left_ = x;
352    x->parent_ = y;
353
354    x->right_ = T2;
355    if (T2)
356      T2->parent_ = x;
357
358    // update height - always update from leaf and to root
359    x->update_height();
360    y->update_height();
361    assert(y->parent_);
362    y->parent_->update_height_recursively();
363
364    // update size
365    x->update_size();
366    y->update_size();
367
368    return y;
369  }
370
371
372  NodeBase* Impl::right_rotate(NodeBase* y)
373  {
374    NodeBase* x = y->left_;
375    assert(x);
376    NodeBase* T2 = x->right_;
377
378    // rotate
379    if (y->is_left_node())
380      y->parent_->left_ = x;
381    else {
382      assert(y->is_right_node());
383      y->parent_->right_ = x;
384    }
385    x->parent_ = y->parent_;
386
387    x->right_ = y;
388    y->parent_ = x;
389
390    y->left_ = T2;
391    if (T2)
392      T2->parent_ = y;
393
394    // update height
395    y->update_height();
396    x->update_height();
397    assert(x->parent_);
398    x->parent_->update_height_recursively();
399
400    // update size
401    y->update_size();
402    x->update_size();
403
404    return x;
405  }
406
407
408  bool Impl::validate(void) const
409  {
410#ifdef NDEBUG
411    return true;
412#else
413    if (!head_.validate(true)) {
414      std::cerr << "Impl: head failed\n";
415      return false;
416    }
417    assert(left_most() == head_.left_most());
418
419    if (root_node()) {
420      if (root_node()->is_left_node() == false) {
421        std::cerr << "error: root is not a left node\n";
422        return false;
423      }
424      if (root_node()->is_right_node()) {
425        std::cerr << "error: root is a right node\n";
426        return false;
427      }
428    }
429
430    if (!validate(root_node())) {
431      std::cerr << "Impl: validate(root_node()) failed\n";
432      return false;
433    }
434
435    if (root_node()) {
436      if (left_most() != root_node()->left_most()) {
437        std::cerr << "leftmost incorrect\n";
438        return false;
439      }
440      if (right_most() != root_node()->right_most()) {
441        std::cerr << "rightmost incorrect\n";
442        return false;
443      }
444    }
445
446
447    /*
448    if (root_node()) {
449      if (root_node()->left_most() != head_.right_) {
450        std::cerr << "head_.right incorrect\n";
451        return false;
452      }
453      if (!root_node()->recursive_validate())
454        return false;
455    }
456    else if (!head_.validate())
457      return false;
458    */
459    return true;
460#endif
461  }
462
463
464  bool Impl::validate(const NodeBase* node) const
465  {
466    if (node == nullptr)
467      return true;
468    node->validate();
469    validate(node->left_);
470    validate(node->right_);
471    return true;
472  }
473
474
475  NodeBase*& Impl::left_most(void)
476  {
477    return head_.right_;
478  }
479
480
481  const NodeBase* Impl::left_most(void) const
482  {
483    return head_.right_;
484  }
485
486
487  NodeBase*& Impl::right_most(void)
488  {
489    return right_most_;
490  }
491
492
493  const NodeBase* Impl::right_most(void) const
494  {
495    return right_most_;
496  }
497
498
499  NodeBase*& Impl::root_node(void)
500  {
501    return head_.left_;
502  }
503
504
505  const NodeBase* Impl::root_node(void) const
506  {
507    return head_.left_;
508  }
509
510
511}
512}}} // of namespace utility, yat, and theplu
Note: See TracBrowser for help on using the repository browser.