Changeset 73e3791 in mainline for uspace/lib/cpp/include/internal/rbtree_iterators.hpp
- Timestamp:
- 2018-07-05T21:41:23Z (7 years ago)
- Branches:
- lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
- Children:
- 27f1bc0
- Parents:
- 6175b78
- git-author:
- Dzejrou <dzejrou@…> (2018-05-13 22:57:14)
- git-committer:
- Dzejrou <dzejrou@…> (2018-07-05 21:41:23)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
uspace/lib/cpp/include/internal/rbtree_iterators.hpp
r6175b78 r73e3791 45 45 */ 46 46 47 template<class Value, class Reference, class Pointer, class Size >47 template<class Value, class Reference, class Pointer, class Size, class Node> 48 48 class rbtree_iterator 49 49 { … … 57 57 using iterator_category = bidirectional_iterator_tag; 58 58 59 rbtree_iterator(rbtree_node<value_type>* current = nullptr, bool end = true) 59 using node_type = Node; 60 61 rbtree_iterator(node_type* current = nullptr, bool end = true) 60 62 : current_{current}, end_{end} 61 63 { /* DUMMY BODY */ } … … 78 80 if (current_) 79 81 { 80 auto bckp = current_;81 if ( current_->right)82 current_ = current_->right->find_smallest();82 auto next = current_->successor(); 83 if (next) 84 current_ = next; 83 85 else 84 { 85 while (!current_->is_left_child()) 86 { 87 current_ = current_->parent; 88 89 if (!current_ || !current_->parent) 90 { 91 /** 92 * We've gone back to root without 93 * being a left child, which means we 94 * were the last node. 95 */ 96 end_ = true; 97 current_ = bckp; 98 99 return *this; 100 } 101 } 102 103 /** 104 * Now we are a left child, 105 * so the next node we have to visit 106 * is our parent. 107 */ 108 current_ = current_->parent; 109 } 86 end_ = true; 110 87 } 111 88 … … 132 109 if (current_) 133 110 { 134 if (current_->left) 135 current_ = current_->left->find_largest(); 136 else if (current_->parent) 137 { 138 while (current_->is_left_child()) 139 current_ = current_->parent; 140 141 /** 142 * We know parent exists here 143 * because we went up from the 144 * left and stopped being left 145 * child (if at any point we happened 146 * to become root then this branch 147 * wouldn't happen). 148 */ 149 current_ = current_->parent; 150 } 151 else // We are root without a left child. 111 auto next = current_->predecessor(); 112 if (next) 113 current_ = next; 114 else 152 115 end_ = true; 153 116 } … … 164 127 } 165 128 166 const rbtree_node<value_type>* node() const129 const node_type* node() const 167 130 { 168 131 return current_; 169 132 } 170 133 171 rbtree_node<value_type>* node()134 node_type* node() 172 135 { 173 136 return current_; … … 180 143 181 144 private: 182 rbtree_node<value_type>* current_;145 node_type* current_; 183 146 bool end_; 184 147 … … 197 160 }; 198 161 199 template<class Val, class Ref, class Ptr, class Sz >200 bool operator==(const rbtree_iterator<Val, Ref, Ptr, Sz >& lhs,201 const rbtree_iterator<Val, Ref, Ptr, Sz >& rhs)162 template<class Val, class Ref, class Ptr, class Sz, class N> 163 bool operator==(const rbtree_iterator<Val, Ref, Ptr, Sz, N>& lhs, 164 const rbtree_iterator<Val, Ref, Ptr, Sz, N>& rhs) 202 165 { 203 166 return (lhs.node() == rhs.node()) && (lhs.end() == rhs.end()); 204 167 } 205 168 206 template<class Val, class Ref, class Ptr, class Sz >207 bool operator!=(const rbtree_iterator<Val, Ref, Ptr, Sz >& lhs,208 const rbtree_iterator<Val, Ref, Ptr, Sz >& rhs)169 template<class Val, class Ref, class Ptr, class Sz, class N> 170 bool operator!=(const rbtree_iterator<Val, Ref, Ptr, Sz, N>& lhs, 171 const rbtree_iterator<Val, Ref, Ptr, Sz, N>& rhs) 209 172 { 210 173 return !(lhs == rhs); 211 174 } 212 175 213 template<class Value, class ConstReference, class ConstPointer, class Size >176 template<class Value, class ConstReference, class ConstPointer, class Size, class Node> 214 177 class rbtree_const_iterator 215 178 { 216 179 using non_const_iterator_type = rbtree_iterator< 217 180 Value, get_non_const_ref_t<ConstReference>, 218 get_non_const_ptr_t<ConstPointer>, Size 181 get_non_const_ptr_t<ConstPointer>, Size, Node 219 182 >; 220 183 … … 228 191 using iterator_category = bidirectional_iterator_tag; 229 192 230 rbtree_const_iterator(const rbtree_node<value_type>* current = nullptr, bool end = true) 193 using node_type = Node; 194 195 rbtree_const_iterator(const node_type* current = nullptr, bool end = true) 231 196 : current_{current}, end_{end} 232 197 { /* DUMMY BODY */ } … … 261 226 if (current_) 262 227 { 263 auto bckp = current_;264 if ( current_->right)265 current_ = current_->right->find_smallest();228 auto next = current_->successor(); 229 if (next) 230 current_ = next; 266 231 else 267 { 268 while (!current_->is_left_child()) 269 { 270 current_ = current_->parent; 271 272 if (!current_->parent) 273 { 274 /** 275 * We've gone back to root without 276 * being a left child, which means we 277 * were the last node. 278 */ 279 end_ = true; 280 current_ = bckp; 281 282 return *this; 283 } 284 } 285 286 /** 287 * Now we are a left child, 288 * so the next node we have to visit 289 * is our parent. 290 */ 291 current_ = current_->parent; 292 } 232 end_ = true; 293 233 } 294 234 … … 315 255 if (current_) 316 256 { 317 if (current_->left) 318 current_ = current_->left->find_largest(); 319 else if (current_->parent) 320 { 321 while (current_->is_left_child()) 322 current_ = current_->parent; 323 324 /** 325 * We know parent exists here 326 * because we went up from the 327 * left and stopped being left 328 * child (if at any point we happened 329 * to become root then this branch 330 * wouldn't happen). 331 */ 332 current_ = current_->parent; 333 } 334 else // We are root without a left child. 335 current_ = nullptr; 257 auto next = current_->predecessor(); 258 if (next) 259 current_ = next; 260 else 261 end_ = true; 336 262 } 337 263 … … 347 273 } 348 274 349 const rbtree_node<value_type>* node() const275 const node_type* node() const 350 276 { 351 277 return current_; … … 358 284 359 285 private: 360 const rbtree_node<value_type>* current_;286 const node_type* current_; 361 287 bool end_; 362 288 … … 375 301 }; 376 302 377 template<class Val, class CRef, class CPtr, class Sz >378 bool operator==(const rbtree_const_iterator<Val, CRef, CPtr, Sz >& lhs,379 const rbtree_const_iterator<Val, CRef, CPtr, Sz >& rhs)303 template<class Val, class CRef, class CPtr, class Sz, class N> 304 bool operator==(const rbtree_const_iterator<Val, CRef, CPtr, Sz, N>& lhs, 305 const rbtree_const_iterator<Val, CRef, CPtr, Sz, N>& rhs) 380 306 { 381 307 return (lhs.node() == rhs.node()) && (lhs.end() == rhs.end()); 382 308 } 383 309 384 template<class Val, class CRef, class CPtr, class Sz >385 bool operator!=(const rbtree_const_iterator<Val, CRef, CPtr, Sz >& lhs,386 const rbtree_const_iterator<Val, CRef, CPtr, Sz >& rhs)310 template<class Val, class CRef, class CPtr, class Sz, class N> 311 bool operator!=(const rbtree_const_iterator<Val, CRef, CPtr, Sz, N>& lhs, 312 const rbtree_const_iterator<Val, CRef, CPtr, Sz, N>& rhs) 387 313 { 388 314 return !(lhs == rhs); 389 315 } 390 316 391 template<class Val, class Ref, class Ptr, class CRef, class CPtr, class Sz >392 bool operator==(const rbtree_iterator<Val, Ref, Ptr, Sz >& lhs,393 const rbtree_const_iterator<Val, CRef, CPtr, Sz >& rhs)317 template<class Val, class Ref, class Ptr, class CRef, class CPtr, class Sz, class N> 318 bool operator==(const rbtree_iterator<Val, Ref, Ptr, Sz, N>& lhs, 319 const rbtree_const_iterator<Val, CRef, CPtr, Sz, N>& rhs) 394 320 { 395 321 return (lhs.node() == rhs.node()) && (lhs.end() == rhs.end()); 396 322 } 397 323 398 template<class Val, class Ref, class Ptr, class CRef, class CPtr, class Sz >399 bool operator!=(const rbtree_iterator<Val, Ref, Ptr, Sz >& lhs,400 const rbtree_const_iterator<Val, CRef, CPtr, Sz >& rhs)324 template<class Val, class Ref, class Ptr, class CRef, class CPtr, class Sz, class N> 325 bool operator!=(const rbtree_iterator<Val, Ref, Ptr, Sz, N>& lhs, 326 const rbtree_const_iterator<Val, CRef, CPtr, Sz, N>& rhs) 401 327 { 402 328 return !(lhs == rhs); 403 329 } 404 330 405 template<class Val, class CRef, class CPtr, class Ref, class Ptr, class Sz >406 bool operator==(const rbtree_const_iterator<Val, CRef, CPtr, Sz >& lhs,407 const rbtree_iterator<Val, Ref, Ptr, Sz >& rhs)331 template<class Val, class CRef, class CPtr, class Ref, class Ptr, class Sz, class N> 332 bool operator==(const rbtree_const_iterator<Val, CRef, CPtr, Sz, N>& lhs, 333 const rbtree_iterator<Val, Ref, Ptr, Sz, N>& rhs) 408 334 { 409 335 return (lhs.node() == rhs.node()) && (lhs.end() == rhs.end()); 410 336 } 411 337 412 template<class Val, class CRef, class CPtr, class Ref, class Ptr, class Sz >413 bool operator!=(const rbtree_const_iterator<Val, CRef, CPtr, Sz >& lhs,414 const rbtree_iterator<Val, Ref, Ptr, Sz >& rhs)338 template<class Val, class CRef, class CPtr, class Ref, class Ptr, class Sz, class N> 339 bool operator!=(const rbtree_const_iterator<Val, CRef, CPtr, Sz, N>& lhs, 340 const rbtree_iterator<Val, Ref, Ptr, Sz, N>& rhs) 415 341 { 416 342 return !(lhs == rhs);
Note:
See TracChangeset
for help on using the changeset viewer.
