source: mainline/uspace/lib/cpp/include/__bits/adt/rbtree_policies.hpp@ 34b2f54d

Last change on this file since 34b2f54d was b57ba05, checked in by Jiří Zárevúcky <zarevucky.jiri@…>, 4 years ago

Update headers in C++ files
  • Property mode set to 100644
File size: 13.2 KB
Line 
1/*
2 * SPDX-FileCopyrightText: 2018 Jaroslav Jindrak
3 *
4 * SPDX-License-Identifier: BSD-3-Clause
5 */
6
7#ifndef LIBCPP_BITS_ADT_RBTREE_POLICIES
8#define LIBCPP_BITS_ADT_RBTREE_POLICIES
9
10#include <__bits/adt/rbtree_node.hpp>
11#include <utility>
12
13namespace std::aux
14{
15 struct rbtree_single_policy
16 {
17 template<class Tree, class Key>
18 static typename Tree::size_type count(const Tree& tree, const Key& key)
19 {
20 return tree.find(key) == tree.end() ? 0 : 1;
21 }
22
23 template<class Tree, class Key>
24 static typename Tree::size_type erase(Tree& tree, const Key& key)
25 {
26 using size_type = typename Tree::size_type;
27
28 auto it = tree.find(key);
29 if (it == tree.end())
30 return size_type{};
31 else
32 tree.delete_node(it.node());
33 return size_type{1};
34 }
35
36 template<class Tree, class Key>
37 static typename Tree::iterator lower_bound(const Tree& tree, const Key& key)
38 {
39 using iterator = typename Tree::iterator;
40 using node_type = typename Tree::node_type;
41
42 auto it = lower_bound_const(tree, key);
43
44 return iterator{const_cast<node_type*>(it.node()), it.end()};
45 }
46
47 template<class Tree, class Key>
48 static typename Tree::const_iterator lower_bound_const(const Tree& tree, const Key& key)
49 {
50 using const_iterator = typename Tree::const_iterator;
51
52 auto node = tree.find_parent_for_insertion(key);
53 const_iterator it{node, false};
54 auto beg = tree.begin();
55 auto end = tree.end();
56
57 if (tree.key_compare_(tree.get_key(*it), key))
58 {
59 // Predecessor.
60 if (it != end)
61 return ++it;
62 else
63 return it;
64 }
65 else if (tree.key_compare_(key, tree.get_key(*it)))
66 {
67 // Successor.
68 if (it != beg)
69 return --it;
70 else
71 return it;
72 }
73 else // Perfect match.
74 return it;
75
76 return it;
77 }
78
79 template<class Tree, class Key>
80 static typename Tree::iterator upper_bound(const Tree& tree, const Key& key)
81 {
82 using iterator = typename Tree::iterator;
83 using node_type = typename Tree::node_type;
84
85 auto it = upper_bound_const(tree, key);
86
87 return iterator{const_cast<node_type*>(it.node()), it.end()};
88 }
89
90 template<class Tree, class Key>
91 static typename Tree::const_iterator upper_bound_const(const Tree& tree, const Key& key)
92 {
93 /**
94 * If key isn't in the tree, we get it's
95 * predecessor or tree.end(). If key is
96 * in the tree, we get it. So unless it
97 * is equal to end(), we can increment it
98 * to get the upper bound.
99 */
100 auto it = lower_bound_const(tree, key);
101 if (it == tree.end())
102 return it;
103 else
104 return ++it;
105 }
106
107 template<class Tree, class Key>
108 static pair<
109 typename Tree::iterator,
110 typename Tree::iterator
111 > equal_range(Tree& tree, const Key& key)
112 {
113 return make_pair(
114 lower_bound(tree, key),
115 upper_bound(tree, key)
116 );
117 }
118
119 template<class Tree, class Key>
120 static pair<
121 typename Tree::const_iterator,
122 typename Tree::const_iterator
123 > equal_range_const(const Tree& tree, const Key& key)
124 {
125 return make_pair(
126 lower_bound_const(tree, key),
127 upper_bound_const(tree, key)
128 );
129 }
130
131 /**
132 * Note: We have to duplicate code for emplace, insert(const&)
133 * and insert(&&) here, because the node (which makes distinction
134 * between the arguments) is only created if the value isn't
135 * in the tree already.
136 */
137
138 template<class Tree, class... Args>
139 static pair<
140 typename Tree::iterator, bool
141 > emplace(Tree& tree, Args&&... args)
142 {
143 using value_type = typename Tree::value_type;
144 using iterator = typename Tree::iterator;
145 using node_type = typename Tree::node_type;
146
147 auto val = value_type{forward<Args>(args)...};
148 auto parent = tree.find_parent_for_insertion(tree.get_key(val));
149
150 if (parent && tree.keys_equal(tree.get_key(parent->value), tree.get_key(val)))
151 return make_pair(iterator{parent, false}, false);
152
153 auto node = new node_type{move(val)};
154
155 return insert(tree, node, parent);
156 }
157
158 template<class Tree, class Value>
159 static pair<
160 typename Tree::iterator, bool
161 > insert(Tree& tree, const Value& val)
162 {
163 using iterator = typename Tree::iterator;
164 using node_type = typename Tree::node_type;
165
166 auto parent = tree.find_parent_for_insertion(tree.get_key(val));
167 if (parent && tree.keys_equal(tree.get_key(parent->value), tree.get_key(val)))
168 return make_pair(iterator{parent, false}, false);
169
170 auto node = new node_type{val};
171
172 return insert(tree, node, parent);
173 }
174
175 template<class Tree, class Value>
176 static pair<
177 typename Tree::iterator, bool
178 > insert(Tree& tree, Value&& val)
179 {
180 using iterator = typename Tree::iterator;
181 using node_type = typename Tree::node_type;
182
183 auto parent = tree.find_parent_for_insertion(tree.get_key(val));
184 if (parent && tree.keys_equal(tree.get_key(parent->value), tree.get_key(val)))
185 return make_pair(iterator{parent, false}, false);
186
187 auto node = new node_type{forward<Value>(val)};
188
189 return insert(tree, node, parent);
190 }
191
192 template<class Tree>
193 static pair<
194 typename Tree::iterator, bool
195 > insert(
196 Tree& tree, typename Tree::node_type* node,
197 typename Tree::node_type* parent
198 )
199 {
200 using iterator = typename Tree::iterator;
201
202 if (!node)
203 return make_pair(tree.end(), false);
204
205 ++tree.size_;
206 if (!parent)
207 {
208 node->color = rbcolor::black;
209 tree.root_ = node;
210 }
211 else
212 {
213 if (tree.keys_comp(tree.get_key(node->value), parent->value))
214 parent->add_left_child(node);
215 else
216 parent->add_right_child(node);
217
218 tree.repair_after_insert_(node);
219 tree.update_root_(node);
220 }
221
222 return make_pair(iterator{node, false}, true);
223 }
224 };
225
226 struct rbtree_multi_policy
227 {
228 template<class Tree, class Key>
229 static typename Tree::size_type count(const Tree& tree, const Key& key)
230 {
231 using size_type = typename Tree::size_type;
232
233 auto it = tree.find(key);
234 if (it == tree.end())
235 return size_type{};
236
237 size_type res{};
238 while (it != tree.end() && tree.keys_equal(tree.get_key(*it), key))
239 {
240 ++res;
241 ++it;
242 }
243
244 return res;
245 }
246
247 template<class Tree, class Key>
248 static typename Tree::size_type erase(Tree& tree, const Key& key)
249 {
250 using size_type = typename Tree::size_type;
251
252 auto it = tree.find(key);
253 if (it == tree.end())
254 return size_type{};
255
256 size_type res{};
257 while (it != tree.end() && tree.keys_equal(tree.get_key(*it), key))
258 {
259 ++res;
260 it = tree.erase(it);
261 }
262
263 return res;
264 }
265
266 template<class Tree, class Key>
267 static typename Tree::iterator lower_bound(const Tree& tree, const Key& key)
268 {
269 auto it = lower_bound_const(tree, key);
270
271 return typename Tree::iterator{
272 const_cast<typename Tree::node_type*>(it.node()), it.end()
273 };
274 }
275
276 template<class Tree, class Key>
277 static typename Tree::const_iterator lower_bound_const(const Tree& tree, const Key& key)
278 {
279 using const_iterator = typename Tree::const_iterator;
280
281 auto node = tree.find_parent_for_insertion(key);
282 const_iterator it{node, false};
283 auto beg = tree.begin();
284 auto end = tree.end();
285
286 if (tree.keys_comp(key, *it))
287 --it; // Incase we are on a successor.
288 while (tree.keys_equal(tree.get_key(*it), key) && it != beg)
289 --it; // Skip keys that are equal.
290 if (it != beg)
291 ++it; // If we moved all the way to the start, key is the smallest.
292
293 if (tree.key_compare_(tree.get_key(*it), key))
294 {
295 // Predecessor.
296 if (it != end)
297 return ++it;
298 else
299 return it;
300 }
301
302 return it;
303 }
304
305 template<class Tree, class Key>
306 static typename Tree::iterator upper_bound(const Tree& tree, const Key& key)
307 {
308 auto it = upper_bound_const(tree, key);
309
310 return typename Tree::iterator{
311 const_cast<typename Tree::node_type*>(it.node()), it.end()
312 };
313 }
314
315 template<class Tree, class Key>
316 static typename Tree::const_iterator upper_bound_const(const Tree& tree, const Key& key)
317 {
318 /**
319 * If key isn't in the tree, we get it's
320 * predecessor or tree.end(). If key is
321 * in the tree, we get it. So unless it
322 * is equal to end(), we keep incrementing
323 * until we get to the next key.
324 */
325 auto it = lower_bound(tree, key);
326 if (it == tree.end())
327 return it;
328 else if (tree.keys_equal(tree.get_key(*it), key))
329 {
330 while (it != tree.end() && tree.keys_equal(tree.get_key(*it), key))
331 ++it;
332
333 return it;
334 }
335
336 return it;
337 }
338
339 template<class Tree, class Key>
340 static pair<
341 typename Tree::iterator,
342 typename Tree::iterator
343 > equal_range(const Tree& tree, const Key& key)
344 {
345 return make_pair(
346 lower_bound(tree, key),
347 upper_bound(tree, key)
348 );
349 }
350
351 template<class Tree, class Key>
352 static pair<
353 typename Tree::const_iterator,
354 typename Tree::const_iterator
355 > equal_range_const(const Tree& tree, const Key& key)
356 {
357 return make_pair(
358 lower_bound_const(tree, key),
359 upper_bound_const(tree, key)
360 );
361 }
362
363 template<class Tree, class... Args>
364 static typename Tree::iterator emplace(Tree& tree, Args&&... args)
365 {
366 using node_type = typename Tree::node_type;
367
368 auto node = new node_type{forward<Args>(args)...};
369
370 return insert(tree, node);
371 }
372
373 template<class Tree, class Value>
374 static typename Tree::iterator insert(Tree& tree, const Value& val)
375 {
376 using node_type = typename Tree::node_type;
377
378 auto node = new node_type{val};
379
380 return insert(tree, node);
381 }
382
383 template<class Tree, class Value>
384 static typename Tree::iterator insert(Tree& tree, Value&& val)
385 {
386 using node_type = typename Tree::node_type;
387
388 auto node = new node_type{forward<Value>(val)};
389
390 return insert(tree, node);
391 }
392
393 template<class Tree>
394 static typename Tree::iterator insert(
395 Tree& tree, typename Tree::node_type* node,
396 typename Tree::node_type* = nullptr
397 )
398 {
399 using iterator = typename Tree::iterator;
400
401 if (!node)
402 return tree.end();
403
404 auto parent = tree.find_parent_for_insertion(tree.get_key(node->value));
405
406 ++tree.size_;
407 if (!parent)
408 {
409 node->color = rbcolor::black;
410 tree.root_ = node;
411 }
412 else
413 {
414 if (tree.keys_comp(tree.get_key(node->value), parent->value))
415 parent->add_left_child(node);
416 else if (tree.keys_comp(tree.get_key(parent->value), node->value))
417 parent->add_right_child(node);
418 else
419 {
420 parent->add(node); // List of nodes with equivalent keys.
421 tree.update_root_(parent);
422
423 return iterator{node, false};
424 }
425
426 tree.repair_after_insert_(node);
427 tree.update_root_(node);
428 }
429
430 return iterator{node, false};
431 }
432 };
433}
434
435#endif
436
Note: See TracBrowser for help on using the repository browser.