source: mainline/uspace/lib/cpp/include/internal/rbtree_policies.hpp@ f8bbaa0

lfn serial ticket/834-toolchain-update topic/msim-upgrade topic/simplify-dev-export
Last change on this file since f8bbaa0 was f8bbaa0, checked in by Dzejrou <dzejrou@…>, 7 years ago

cpp: added the rest of operations to the rbtree_single policy
  • Property mode set to 100644
File size: 9.8 KB
Line 
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
29#ifndef LIBCPP_INTERNAL_RBTREE_POLICIES
30#define LIBCPP_INTERNAL_RBTREE_POLICIES
31
32#include <internal/rbtree_node.hpp>
33#include <utility>
34
35namespace std::aux
36{
37 struct rbtree_single_policy
38 {
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>
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 // This is the multi version -.-
58 /* size_type res{}; */
59 /* while (tree.keys_equal(tree.get_key(*it), key)) */
60 /* { */
61 /* auto node = it.node(); */
62 /* ++it; */
63
64 /* tree->delete_node(node); */
65 /* ++res; */
66 /* } */
67
68 /* return res; */
69 }
70
71 template<class Tree, class Key>
72 static typename Tree::iterator lower_bound(Tree& tree, const Key& key)
73 {
74 using iterator = typename Tree::iterator;
75
76 auto node = tree.find_parent_for_insertion(key);
77 iterator it{node, false};
78 auto beg = tree.begin();
79 auto end = tree.end();
80
81 if (tree.key_compare_(tree.get_key(*it), key))
82 {
83 // Predecessor.
84 if (it != end)
85 return ++it;
86 else
87 return it;
88 }
89 else if (tree.key_compare_(key, tree.get_key(*it)))
90 {
91 // Successor.
92 if (it != beg)
93 return --it;
94 else
95 return it;
96 }
97 else // Perfect match.
98 return it;
99
100 return it;
101 }
102
103 template<class Tree, class Key>
104 static typename Tree::const_iterator lower_bound_const(const Tree& tree, const Key& key)
105 {
106 using const_iterator = typename Tree::const_iterator;
107
108 auto node = tree.find_parent_for_insertion(key);
109 const_iterator it{node, false};
110 auto beg = tree.begin();
111 auto end = tree.end();
112
113 if (tree.key_compare_(tree.get_key(*it), key))
114 {
115 // Predecessor.
116 if (it != end)
117 return ++it;
118 else
119 return it;
120 }
121 else if (tree.key_compare_(key, tree.get_key(*it)))
122 {
123 // Successor.
124 if (it != beg)
125 return --it;
126 else
127 return it;
128 }
129 else // Perfect match.
130 return it;
131
132 return it;
133 }
134
135 template<class Tree, class Key>
136 static typename Tree::iterator upper_bound(Tree& tree, const Key& key)
137 {
138 /**
139 * If key isn't in the tree, we get it's
140 * successor or tree.end(). If key is
141 * in the tree, we get it.
142 * In the first case, the successor is also
143 * the upper bound, so we just return it,
144 * otherwise (as long as it != end()) we
145 * increment.
146 */
147 auto it = lower_bound(tree, key);
148 if (it == tree.end())
149 return it;
150 else if (tree.keys_equal(key, *it))
151 return ++it;
152 else
153 return it;
154 }
155
156 template<class Tree, class Key>
157 static typename Tree::const_iterator upper_bound_const(const Tree& tree, const Key& key)
158 {
159 /**
160 * If key isn't in the tree, we get it's
161 * successor or tree.end(). If key is
162 * in the tree, we get it.
163 * In the first case, the successor is also
164 * the upper bound, so we just return it,
165 * otherwise (as long as it != end()) we
166 * increment.
167 */
168 auto it = lower_bound_const(tree, key);
169 if (it == tree.end())
170 return it;
171 else if (tree.keys_equal(key, *it))
172 return ++it;
173 else
174 return it;
175 }
176
177 template<class Tree, class Key>
178 static pair<
179 typename Tree::iterator,
180 typename Tree::iterator
181 > equal_range(Tree& tree, const Key& key)
182 {
183 return make_pair(
184 lower_bound(tree, key),
185 upper_bound(tree, key)
186 );
187 }
188
189 template<class Tree, class Key>
190 static pair<
191 typename Tree::const_iterator,
192 typename Tree::const_iterator
193 > equal_range_const(const Tree& tree, const Key& key)
194 {
195 return make_pair(
196 lower_bound_const(tree, key),
197 upper_bound_const(tree, key)
198 );
199 }
200
201 /**
202 * Note: We have to duplicate code for emplace, insert(const&)
203 * and insert(&&) here, because the node (which makes distinction
204 * between the arguments) is only created if the value isn't
205 * in the tree already.
206 */
207
208 template<class Tree, class... Args>
209 static pair<
210 typename Tree::iterator, bool
211 > emplace(Tree& tree, Args&&... args)
212 {
213 using value_type = typename Tree::value_type;
214 using iterator = typename Tree::iterator;
215 using node_type = typename Tree::node_type;
216
217 auto val = value_type{forward<Args>(args)...};
218 auto parent = tree.find_parent_for_insertion(val);
219 if (!parent)
220 {
221 tree.root_ = new node_type{move(val)};
222
223 return make_pair(iterator{tree.root_}, true);
224 }
225
226 if (tree.keys_equal(tree.get_key(parent->value), tree.get_key(val)))
227 return make_pair(iterator{parent}, false);
228
229 auto node = new node_type{move(val)};
230 if (tree.keys_comp(tree.get_key(val), parent->value))
231 parent->add_left_child(node);
232 else
233 parent->add_right_child(node);
234
235 return make_pair(iterator{node}, true);
236 }
237
238 template<class Tree, class Value>
239 static pair<
240 typename Tree::iterator, bool
241 > insert(Tree& tree, const Value& val)
242 {
243 using iterator = typename Tree::iterator;
244 using node_type = typename Tree::node_type;
245
246 auto parent = tree.find_parent_for_insertion(val);
247 if (!parent)
248 {
249 tree.root_ = new node_type{val};
250
251 return make_pair(iterator{tree.root_}, true);
252 }
253
254 if (tree.keys_equal(tree.get_key(parent->value), tree.get_key(val)))
255 return make_pair(iterator{parent}, false);
256
257 auto node = new node_type{val};
258 if (tree.keys_comp(tree.get_key(val), parent->value))
259 parent->add_left_child(node);
260 else
261 parent->add_right_child(node);
262
263 return make_pair(iterator{node}, true);
264 }
265
266 template<class Tree, class Value>
267 static pair<
268 typename Tree::iterator, bool
269 > insert(Tree& tree, Value&& val)
270 {
271 using iterator = typename Tree::iterator;
272 using node_type = typename Tree::node_type;
273
274 auto parent = tree.find_parent_for_insertion(val);
275 if (!parent)
276 {
277 tree.root_ = new node_type{forward<Value>(val)};
278
279 return make_pair(iterator{tree.root_}, true);
280 }
281
282 if (tree.keys_equal(tree.get_key(parent->value), tree.get_key(val)))
283 return make_pair(iterator{parent}, false);
284
285 auto node = new node_type{forward<Value>(val)};
286 if (tree.keys_comp(tree.get_key(val), parent->value))
287 parent->add_left_child(node);
288 else
289 parent->add_right_child(node);
290
291 return make_pair(iterator{node}, true);
292 }
293 };
294
295 struct rbtree_multi_policy
296 {
297 // TODO:
298 };
299}
300
301#endif
302
Note: See TracBrowser for help on using the repository browser.