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

Last change on this file was b57a3ee, checked in by Dzejrou <dzejrou@…>, 7 years ago

cpp: refactored the library layout, everything from the impl directory was moved to the bits directory for the sake of consistency, updated copyright notices and include guards
  • Property mode set to 100644
File size: 14.5 KB
RevLine 
[4d65515]1/*
2 * Copyright (c) 2018 Jaroslav Jindrak
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *
9 * - Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * - Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 * - The name of the author may not be used to endorse or promote products
15 * derived from this software without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28
[b57a3ee]29#ifndef LIBCPP_BITS_ADT_RBTREE_POLICIES
30#define LIBCPP_BITS_ADT_RBTREE_POLICIES
[4d65515]31
[b57a3ee]32#include <__bits/adt/rbtree_node.hpp>
[4d65515]33#include <utility>
34
35namespace std::aux
36{
37 struct rbtree_single_policy
38 {
[2a482ee]39 template<class Tree, class Key>
40 static typename Tree::size_type count(const Tree& tree, const Key& key)
41 {
42 return tree.find(key) == tree.end() ? 0 : 1;
43 }
44
45 template<class Tree, class Key>
[f8bbaa0]46 static typename Tree::size_type erase(Tree& tree, const Key& key)
47 {
48 using size_type = typename Tree::size_type;
49
50 auto it = tree.find(key);
51 if (it == tree.end())
52 return size_type{};
53 else
54 tree.delete_node(it.node());
55 return size_type{1};
56 }
57
58 template<class Tree, class Key>
[647b756]59 static typename Tree::iterator lower_bound(const Tree& tree, const Key& key)
[f8bbaa0]60 {
[73e3791]61 using iterator = typename Tree::iterator;
62 using node_type = typename Tree::node_type;
[f8bbaa0]63
[647b756]64 auto it = lower_bound_const(tree, key);
[f8bbaa0]65
[73e3791]66 return iterator{const_cast<node_type*>(it.node()), it.end()};
[f8bbaa0]67 }
68
69 template<class Tree, class Key>
70 static typename Tree::const_iterator lower_bound_const(const Tree& tree, const Key& key)
[2a482ee]71 {
[f8bbaa0]72 using const_iterator = typename Tree::const_iterator;
73
74 auto node = tree.find_parent_for_insertion(key);
75 const_iterator it{node, false};
76 auto beg = tree.begin();
77 auto end = tree.end();
78
79 if (tree.key_compare_(tree.get_key(*it), key))
80 {
81 // Predecessor.
82 if (it != end)
83 return ++it;
84 else
85 return it;
86 }
87 else if (tree.key_compare_(key, tree.get_key(*it)))
88 {
89 // Successor.
90 if (it != beg)
91 return --it;
92 else
93 return it;
94 }
95 else // Perfect match.
96 return it;
97
98 return it;
[2a482ee]99 }
100
101 template<class Tree, class Key>
[647b756]102 static typename Tree::iterator upper_bound(const Tree& tree, const Key& key)
[2a482ee]103 {
[73e3791]104 using iterator = typename Tree::iterator;
105 using node_type = typename Tree::node_type;
[647b756]106
107 auto it = upper_bound_const(tree, key);
108
[73e3791]109 return iterator{const_cast<node_type*>(it.node()), it.end()};
[2a482ee]110 }
111
112 template<class Tree, class Key>
[f8bbaa0]113 static typename Tree::const_iterator upper_bound_const(const Tree& tree, const Key& key)
[2a482ee]114 {
[f8bbaa0]115 /**
116 * If key isn't in the tree, we get it's
[73e3791]117 * predecessor or tree.end(). If key is
118 * in the tree, we get it. So unless it
119 * is equal to end(), we can increment it
120 * to get the upper bound.
[f8bbaa0]121 */
122 auto it = lower_bound_const(tree, key);
123 if (it == tree.end())
124 return it;
125 else
[73e3791]126 return ++it;
[2a482ee]127 }
128
129 template<class Tree, class Key>
130 static pair<
131 typename Tree::iterator,
132 typename Tree::iterator
[f8bbaa0]133 > equal_range(Tree& tree, const Key& key)
[2a482ee]134 {
[f8bbaa0]135 return make_pair(
136 lower_bound(tree, key),
137 upper_bound(tree, key)
138 );
[2a482ee]139 }
140
141 template<class Tree, class Key>
142 static pair<
143 typename Tree::const_iterator,
144 typename Tree::const_iterator
145 > equal_range_const(const Tree& tree, const Key& key)
146 {
[f8bbaa0]147 return make_pair(
148 lower_bound_const(tree, key),
149 upper_bound_const(tree, key)
150 );
[2a482ee]151 }
152
153 /**
154 * Note: We have to duplicate code for emplace, insert(const&)
155 * and insert(&&) here, because the node (which makes distinction
156 * between the arguments) is only created if the value isn't
157 * in the tree already.
158 */
159
160 template<class Tree, class... Args>
161 static pair<
162 typename Tree::iterator, bool
163 > emplace(Tree& tree, Args&&... args)
164 {
165 using value_type = typename Tree::value_type;
166 using iterator = typename Tree::iterator;
167 using node_type = typename Tree::node_type;
168
169 auto val = value_type{forward<Args>(args)...};
[48f09f2f]170 auto parent = tree.find_parent_for_insertion(tree.get_key(val));
[2a482ee]171
[7644d6e]172 if (parent && tree.keys_equal(tree.get_key(parent->value), tree.get_key(val)))
[647b756]173 return make_pair(iterator{parent, false}, false);
[2a482ee]174
175 auto node = new node_type{move(val)};
[647b756]176
[73e3791]177 return insert(tree, node, parent);
[2a482ee]178 }
[4d65515]179
180 template<class Tree, class Value>
181 static pair<
182 typename Tree::iterator, bool
183 > insert(Tree& tree, const Value& val)
184 {
185 using iterator = typename Tree::iterator;
186 using node_type = typename Tree::node_type;
187
[48f09f2f]188 auto parent = tree.find_parent_for_insertion(tree.get_key(val));
[7644d6e]189 if (parent && tree.keys_equal(tree.get_key(parent->value), tree.get_key(val)))
[647b756]190 return make_pair(iterator{parent, false}, false);
[4d65515]191
192 auto node = new node_type{val};
[647b756]193
[73e3791]194 return insert(tree, node, parent);
[4d65515]195 }
196
197 template<class Tree, class Value>
198 static pair<
199 typename Tree::iterator, bool
200 > insert(Tree& tree, Value&& val)
201 {
202 using iterator = typename Tree::iterator;
203 using node_type = typename Tree::node_type;
204
[48f09f2f]205 auto parent = tree.find_parent_for_insertion(tree.get_key(val));
[7644d6e]206 if (parent && tree.keys_equal(tree.get_key(parent->value), tree.get_key(val)))
[647b756]207 return make_pair(iterator{parent, false}, false);
[4d65515]208
209 auto node = new node_type{forward<Value>(val)};
[73e3791]210
211 return insert(tree, node, parent);
212 }
213
214 template<class Tree>
215 static pair<
216 typename Tree::iterator, bool
217 > insert(
218 Tree& tree, typename Tree::node_type* node,
219 typename Tree::node_type* parent
220 )
221 {
222 using iterator = typename Tree::iterator;
223
224 if (!node)
225 return make_pair(tree.end(), false);
226
227 ++tree.size_;
228 if (!parent)
229 {
230 node->color = rbcolor::black;
231 tree.root_ = node;
232 }
233 else
234 {
235 if (tree.keys_comp(tree.get_key(node->value), parent->value))
236 parent->add_left_child(node);
237 else
238 parent->add_right_child(node);
239
240 tree.repair_after_insert_(node);
241 tree.update_root_(node);
242 }
[647b756]243
244 return make_pair(iterator{node, false}, true);
[4d65515]245 }
246 };
247
248 struct rbtree_multi_policy
249 {
[647b756]250 template<class Tree, class Key>
251 static typename Tree::size_type count(const Tree& tree, const Key& key)
252 {
253 using size_type = typename Tree::size_type;
254
255 auto it = tree.find(key);
256 if (it == tree.end())
257 return size_type{};
258
259 size_type res{};
[27f1bc0]260 while (it != tree.end() && tree.keys_equal(tree.get_key(*it), key))
[647b756]261 {
262 ++res;
263 ++it;
264 }
265
266 return res;
267 }
268
269 template<class Tree, class Key>
270 static typename Tree::size_type erase(Tree& tree, const Key& key)
271 {
272 using size_type = typename Tree::size_type;
273
274 auto it = tree.find(key);
275 if (it == tree.end())
276 return size_type{};
277
278 size_type res{};
[21d97e8]279 while (it != tree.end() && tree.keys_equal(tree.get_key(*it), key))
[647b756]280 {
281 ++res;
282 it = tree.erase(it);
283 }
284
285 return res;
286 }
287
288 template<class Tree, class Key>
289 static typename Tree::iterator lower_bound(const Tree& tree, const Key& key)
290 {
291 auto it = lower_bound_const(tree, key);
292
[21d97e8]293 return typename Tree::iterator{
294 const_cast<typename Tree::node_type*>(it.node()), it.end()
295 };
[647b756]296 }
297
298 template<class Tree, class Key>
299 static typename Tree::const_iterator lower_bound_const(const Tree& tree, const Key& key)
300 {
301 using const_iterator = typename Tree::const_iterator;
302
303 auto node = tree.find_parent_for_insertion(key);
304 const_iterator it{node, false};
305 auto beg = tree.begin();
306 auto end = tree.end();
307
308 if (tree.keys_comp(key, *it))
309 --it; // Incase we are on a successor.
310 while (tree.keys_equal(tree.get_key(*it), key) && it != beg)
311 --it; // Skip keys that are equal.
312 if (it != beg)
313 ++it; // If we moved all the way to the start, key is the smallest.
314
315 if (tree.key_compare_(tree.get_key(*it), key))
316 {
317 // Predecessor.
318 if (it != end)
319 return ++it;
320 else
321 return it;
322 }
323
324 return it;
325 }
326
327 template<class Tree, class Key>
328 static typename Tree::iterator upper_bound(const Tree& tree, const Key& key)
329 {
330 auto it = upper_bound_const(tree, key);
331
[21d97e8]332 return typename Tree::iterator{
333 const_cast<typename Tree::node_type*>(it.node()), it.end()
334 };
[647b756]335 }
336
337 template<class Tree, class Key>
338 static typename Tree::const_iterator upper_bound_const(const Tree& tree, const Key& key)
339 {
340 /**
341 * If key isn't in the tree, we get it's
[73e3791]342 * predecessor or tree.end(). If key is
343 * in the tree, we get it. So unless it
344 * is equal to end(), we keep incrementing
345 * until we get to the next key.
[647b756]346 */
347 auto it = lower_bound(tree, key);
348 if (it == tree.end())
349 return it;
350 else if (tree.keys_equal(tree.get_key(*it), key))
351 {
[73e3791]352 while (it != tree.end() && tree.keys_equal(tree.get_key(*it), key))
[647b756]353 ++it;
354
355 return it;
356 }
357
358 return it;
359 }
360
361 template<class Tree, class Key>
362 static pair<
363 typename Tree::iterator,
364 typename Tree::iterator
365 > equal_range(const Tree& tree, const Key& key)
366 {
367 return make_pair(
368 lower_bound(tree, key),
369 upper_bound(tree, key)
370 );
371 }
372
373 template<class Tree, class Key>
374 static pair<
375 typename Tree::const_iterator,
376 typename Tree::const_iterator
377 > equal_range_const(const Tree& tree, const Key& key)
378 {
379 return make_pair(
380 lower_bound_const(tree, key),
381 upper_bound_const(tree, key)
382 );
383 }
384
385 template<class Tree, class... Args>
386 static typename Tree::iterator emplace(Tree& tree, Args&&... args)
387 {
388 using node_type = typename Tree::node_type;
389
[27f1bc0]390 auto node = new node_type{forward<Args>(args)...};
[647b756]391
392 return insert(tree, node);
393 }
394
395 template<class Tree, class Value>
396 static typename Tree::iterator insert(Tree& tree, const Value& val)
397 {
398 using node_type = typename Tree::node_type;
399
400 auto node = new node_type{val};
401
402 return insert(tree, node);
403 }
404
405 template<class Tree, class Value>
406 static typename Tree::iterator insert(Tree& tree, Value&& val)
407 {
408 using node_type = typename Tree::node_type;
409
410 auto node = new node_type{forward<Value>(val)};
411
412 return insert(tree, node);
413 }
414
415 template<class Tree>
[73e3791]416 static typename Tree::iterator insert(
417 Tree& tree, typename Tree::node_type* node,
418 typename Tree::node_type* = nullptr
419 )
[647b756]420 {
421 using iterator = typename Tree::iterator;
422
[73e3791]423 if (!node)
424 return tree.end();
425
[48f09f2f]426 auto parent = tree.find_parent_for_insertion(tree.get_key(node->value));
[73e3791]427
428 ++tree.size_;
429 if (!parent)
430 {
431 node->color = rbcolor::black;
432 tree.root_ = node;
433 }
434 else
435 {
436 if (tree.keys_comp(tree.get_key(node->value), parent->value))
437 parent->add_left_child(node);
438 else if (tree.keys_comp(tree.get_key(parent->value), node->value))
439 parent->add_right_child(node);
440 else
441 {
442 parent->add(node); // List of nodes with equivalent keys.
443 tree.update_root_(parent);
444
445 return iterator{node, false};
446 }
447
448 tree.repair_after_insert_(node);
449 tree.update_root_(node);
450 }
[647b756]451
452 return iterator{node, false};
453 }
[4d65515]454 };
455}
456
457#endif
458
Note: See TracBrowser for help on using the repository browser.