Changeset 009d78b in mainline
- Timestamp:
- 2018-07-05T21:41:22Z (7 years ago)
- Branches:
- lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
- Children:
- d6bb78b
- Parents:
- f8bbaa0
- git-author:
- Dzejrou <dzejrou@…> (2018-04-29 19:22:57)
- git-committer:
- Dzejrou <dzejrou@…> (2018-07-05 21:41:22)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
uspace/lib/cpp/include/internal/rbtree.hpp
rf8bbaa0 r009d78b 61 61 using node_type = rbtree_node<value_type>; 62 62 63 // TODO: make find/bounds etc templated with key type 64 // for transparent comparators and leave their management for the 65 // outer containers 66 63 67 rbtree(const key_compare& kcmp = key_compare{}) 64 68 : root_{nullptr}, size_{}, key_compare_{}, … … 66 70 { /* DUMMY BODY */ } 67 71 68 rbtree(const rbtree& other); // TODO: 72 rbtree(const rbtree& other) 73 : rbtree{other.key_compare_} 74 { 75 for (const auto& x: other) 76 insert(x); 77 } 69 78 70 79 rbtree(rbtree&& other) … … 172 181 { 173 182 auto ret = Policy::emplace(*this, forward<Args>(args)...); 183 if (!ret.second) 184 return ret; 185 ++size_; 186 187 repair_after_insert_(ret.first.node()); 188 update_root_(ret.first.node()); 174 189 175 190 return ret; … … 181 196 if (!ret.second) 182 197 return ret; 198 ++size_; 183 199 184 200 repair_after_insert_(ret.first.node()); … … 193 209 if (!ret.second) 194 210 return ret; 211 ++size_; 195 212 196 213 repair_after_insert_(ret.first.node()); … … 202 219 size_type erase(const key_type& key) 203 220 { 204 auto ret = Policy::erase(*this, key); 205 if (ret == 0) 206 return ret; 207 // TODO: problem - we don't have a node ptr 208 // solution: return a pair<size_type, node_type*> 209 210 return ret; 221 return Policy::erase(*this, key); 211 222 } 212 223 213 224 iterator erase(const_iterator it) 214 225 { 215 // TODO: implement 226 if (it == cend()) 227 return end(); 228 229 auto node = const_cast<node_type*>(it.node()); 230 ++it; 231 232 delete_node(node); 233 return iterator{const_cast<node_type*>(it.node()), it.end()}; 216 234 } 217 235 … … 296 314 bool is_eq_to(const rbtree& other) const 297 315 { 298 // TODO: implement 299 return false; 316 if (size_ != other.size()) 317 return false; 318 319 auto it1 = begin(); 320 auto it2 = other.begin(); 321 322 while (keys_equal(*it1++, *it2++)) 323 { /* DUMMY BODY */ } 324 325 return (it1 == end()) && (it2 == other.end()); 300 326 } 301 327 … … 308 334 { 309 335 return key_compare_(key, key_extractor_(val)); 336 } 337 338 bool keys_equal(const key_type& k1, const key_type& k2) const 339 { 340 return !key_compare_(k1, k2) && !key_compare_(k2, k1); 310 341 } 311 342 … … 327 358 } 328 359 360 void delete_node(node_type* node) 361 { 362 if (!node) 363 return; 364 365 --size_; 366 367 if (node->left && node->right) 368 { 369 node->swap(node->successor()); 370 371 // Node now has at most one child. 372 delete_node(node); 373 374 return; 375 } 376 377 auto child = node->right ? node->right : node->left; 378 if (!child) 379 { 380 // Simply remove the node. 381 node->unlink(); 382 383 delete node; 384 } 385 else 386 { 387 // Replace with the child. 388 child->parent = node->parent; 389 if (node->is_left_child()) 390 child->parent->left = child; 391 else if (node->is_left_child()) 392 child->parent->right = child; 393 394 // Repair if needed. 395 repair_after_erase_(node, child); 396 update_root_(child); 397 } 398 } 399 329 400 private: 330 401 node_type* root_; … … 340 411 if (key_compare_(key, key_extractor_(current->value))) 341 412 current = current->left; 342 else if (key == key_extractor_(current->value)) 413 else if (key_compare_(key_extractor_(current->value), key)) 414 current = current->right; 415 else 343 416 return current; 344 else345 current = current->right;346 417 } 347 418 … … 380 451 } 381 452 382 void repair_after_erase_(node_type* node )453 void repair_after_erase_(node_type* node, node_type* child) 383 454 { 384 455 // TODO: implement
Note:
See TracChangeset
for help on using the changeset viewer.