bimap/intrusive_tree.cpp at master · sw1tcherrr/bimap · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include "intrusive_tree.h"

// only for sentinel
base_tree_element::base_tree_element(base_tree_element&& other) noexcept
    : base_tree_element() {
  move_from(other);
}

// only for sentinel
base_tree_element& base_tree_element::operator=(base_tree_element&& other) noexcept {
  move_from(other);
  return *this;
}

// only for sentinel
void base_tree_element::move_from(base_tree_element& other) noexcept {
  link_left(this, other.left);
  link_right(this, other.right);
  other.left = other.right = other.parent = nullptr;
}

bool base_tree_element::in_tree() const noexcept {
  return !(parent == nullptr && left == nullptr && right == nullptr);
}

base_tree_element::~base_tree_element() {
  unlink();
}

void base_tree_element::link_left(base_tree_element* parent, base_tree_element* left) {
  if (parent) {
    parent->left = left;
    if (left) {
      left->parent = parent;
    }
  }
}

void base_tree_element::link_right(base_tree_element* parent, base_tree_element* right) {
  if (parent) {
    parent->right = right;
    if (right) {
      right->parent = parent;
    }
  }
}

base_tree_element* base_tree_element::max_in_subtree(base_tree_element* p) {
  while (p->right) {
    p = p->right;
  }
  return p;
}

base_tree_element* base_tree_element::min_in_subtree(base_tree_element* p) {
  while (p->left) {
    p = p->left;
  }
  return p;
}

base_tree_element* base_tree_element::prev(base_tree_element* p) {
  if (p->left) {
    return max_in_subtree(p->left);
  } else {
    while (p->is_left_child()) {
      p = p->parent;
    }
    p = p->parent;
  }

  return p;
}

base_tree_element* base_tree_element::next(base_tree_element* p) {
  if (p->right) {
    return min_in_subtree(p->right);
  } else {
    while (!p->is_left_child()) {
      p = p->parent;
    }
    p = p->parent;
  }

  return p;
}

bool base_tree_element::is_leaf() const noexcept {
  return left == nullptr && right == nullptr;
}

bool base_tree_element::has_one_child() const noexcept {
  return (left != nullptr && right == nullptr) ||
         (left == nullptr && right != nullptr);
}

bool base_tree_element::is_left_child() const noexcept {
  return parent->left == this;
}

base_tree_element* base_tree_element::get_only_child() noexcept {
  return (left != nullptr) ? left : right;
}

void base_tree_element::link_with_parent(base_tree_element* node) noexcept {
  if (is_left_child()) {
    link_left(parent, node);
  } else {
    link_right(parent, node);
  }
}

void base_tree_element::unlink() noexcept {
  if (!in_tree()) {
    return;
  }

  if (is_leaf() || has_one_child()) {
    link_with_parent(get_only_child());
  } else {
    auto* n = next(this);
    n->unlink();
    link_left(n, left);
    link_right(n, right);
    link_with_parent(n);

    left = right = parent = nullptr;
  }
}