Changeset d6bb78b 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:
- 89bc6460
- Parents:
- 009d78b
- git-author:
- Dzejrou <dzejrou@…> (2018-04-29 19:23:26)
- git-committer:
- Dzejrou <dzejrou@…> (2018-07-05 21:41:22)
- Location:
- uspace/lib/cpp/include/internal
- Files:
-
- 1 added
- 2 edited
-
hash_table_iterators.hpp (modified) (12 diffs)
-
iterator.hpp (added)
-
rbtree_iterators.hpp (modified) (5 diffs)
Legend:
- Unmodified
- Added
- Removed
-
uspace/lib/cpp/include/internal/hash_table_iterators.hpp
r009d78b rd6bb78b 30 30 #define LIBCPP_INTERNAL_HASH_TABLE_ITERATORS 31 31 32 #include <internal/iterator.hpp> 32 33 #include <internal/list.hpp> 33 34 #include <internal/hash_table_bucket.hpp> … … 36 37 namespace std::aux 37 38 { 38 template<class Value, class ConstReference, class ConstPointer, class Size>39 class hash_table_ const_iterator39 template<class Value, class Reference, class Pointer, class Size> 40 class hash_table_iterator 40 41 { 41 42 public: 42 43 using value_type = Value; 43 44 using size_type = Size; 44 using const_reference = ConstReference;45 using const_pointer = ConstPointer;45 using reference = Reference; 46 using pointer = Pointer; 46 47 using difference_type = ptrdiff_t; 47 48 48 49 using iterator_category = forward_iterator_tag; 49 50 50 hash_table_ const_iterator(consthash_table_bucket<value_type, size_type>* table = nullptr,51 52 constlist_node<value_type>* current = nullptr)51 hash_table_iterator(hash_table_bucket<value_type, size_type>* table = nullptr, 52 size_type idx = size_type{}, size_type max_idx = size_type{}, 53 list_node<value_type>* current = nullptr) 53 54 : table_{table}, idx_{idx}, max_idx_{max_idx}, current_{current} 54 55 { /* DUMMY BODY */ } 55 56 56 hash_table_ const_iterator(const hash_table_const_iterator&) = default;57 hash_table_ const_iterator& operator=(const hash_table_const_iterator&) = default;58 59 const_reference operator*() const57 hash_table_iterator(const hash_table_iterator&) = default; 58 hash_table_iterator& operator=(const hash_table_iterator&) = default; 59 60 reference operator*() 60 61 { 61 62 return current_->value; 62 63 } 63 64 64 const_pointer operator->() const65 pointer operator->() 65 66 { 66 67 return ¤t_->value; 67 68 } 68 69 69 hash_table_ const_iterator& operator++()70 hash_table_iterator& operator++() 70 71 { 71 72 current_ = current_->next; … … 89 90 } 90 91 91 hash_table_ const_iterator operator++(int)92 hash_table_iterator operator++(int) 92 93 { 93 94 auto tmp = *this; … … 99 100 list_node<value_type>* node() 100 101 { 101 return c onst_cast<list_node<value_type>*>(current_);102 return current_; 102 103 } 103 104 … … 113 114 114 115 private: 115 consthash_table_bucket<value_type, size_type>* table_;116 hash_table_bucket<value_type, size_type>* table_; 116 117 size_type idx_; 117 118 size_type max_idx_; 118 const list_node<value_type>* current_; 119 list_node<value_type>* current_; 120 121 template<class V, class CR, class CP, class S> 122 friend class hash_table_const_iterator; 119 123 }; 120 124 121 template<class Value, class ConstRef, class ConstPtr, class Size> 122 bool operator==(const hash_table_const_iterator<Value, ConstRef, ConstPtr, Size>& lhs, 123 const hash_table_const_iterator<Value, ConstRef, ConstPtr, Size>& rhs) 124 { 125 return lhs.node() == rhs.node(); 126 } 127 128 template<class Value, class ConstRef, class ConstPtr, class Size> 129 bool operator!=(const hash_table_const_iterator<Value, ConstRef, ConstPtr, Size>& lhs, 130 const hash_table_const_iterator<Value, ConstRef, ConstPtr, Size>& rhs) 131 { 132 return !(lhs == rhs); 133 } 134 135 template<class Value, class Reference, class Pointer, class Size> 136 class hash_table_iterator 137 { 125 template<class Value, class Ref, class Ptr, class Size> 126 bool operator==(const hash_table_iterator<Value, Ref, Ptr, Size>& lhs, 127 const hash_table_iterator<Value, Ref, Ptr, Size>& rhs) 128 { 129 return lhs.node() == rhs.node(); 130 } 131 132 template<class Value, class Ref, class Ptr, class Size> 133 bool operator!=(const hash_table_iterator<Value, Ref, Ptr, Size>& lhs, 134 const hash_table_iterator<Value, Ref, Ptr, Size>& rhs) 135 { 136 return !(lhs == rhs); 137 } 138 139 template<class Value, class ConstReference, class ConstPointer, class Size> 140 class hash_table_const_iterator 141 { 142 using non_const_iterator_type = hash_table_iterator< 143 Value, get_non_const_ref_t<ConstReference>, 144 get_non_const_ptr<ConstPointer>, Size 145 >; 146 138 147 public: 139 148 using value_type = Value; 140 149 using size_type = Size; 141 using reference =Reference;142 using pointer =Pointer;150 using const_reference = ConstReference; 151 using const_pointer = ConstPointer; 143 152 using difference_type = ptrdiff_t; 144 153 145 154 using iterator_category = forward_iterator_tag; 146 155 147 hash_table_ iterator(hash_table_bucket<value_type, size_type>* table = nullptr,148 size_type idx = size_type{}, size_type max_idx = size_type{},149 list_node<value_type>* current = nullptr)156 hash_table_const_iterator(const hash_table_bucket<value_type, size_type>* table = nullptr, 157 size_type idx = size_type{}, size_type max_idx = size_type{}, 158 const list_node<value_type>* current = nullptr) 150 159 : table_{table}, idx_{idx}, max_idx_{max_idx}, current_{current} 151 160 { /* DUMMY BODY */ } 152 161 153 hash_table_iterator(const hash_table_iterator&) = default; 154 hash_table_iterator& operator=(const hash_table_iterator&) = default; 155 156 reference operator*() 162 hash_table_const_iterator(const hash_table_const_iterator&) = default; 163 hash_table_const_iterator& operator=(const hash_table_const_iterator&) = default; 164 165 hash_table_const_iterator(const non_const_iterator_type& other) 166 : table_{other.table_}, idx_{other.idx_}, max_idx_{other.max_idx_}, 167 current_{other.current_} 168 { /* DUMMY BODY */ } 169 170 hash_table_const_iterator& operator=(const non_const_iterator_type& other) 171 { 172 table_ = other.table_; 173 idx_ = other.idx_; 174 max_idx_ = other.max_idx_; 175 current_ = other.current_; 176 177 return *this; 178 } 179 180 const_reference operator*() const 157 181 { 158 182 return current_->value; 159 183 } 160 184 161 pointer operator->()185 const_pointer operator->() const 162 186 { 163 187 return ¤t_->value; 164 188 } 165 189 166 hash_table_ iterator& operator++()190 hash_table_const_iterator& operator++() 167 191 { 168 192 current_ = current_->next; … … 186 210 } 187 211 188 hash_table_ iterator operator++(int)212 hash_table_const_iterator operator++(int) 189 213 { 190 214 auto tmp = *this; … … 196 220 list_node<value_type>* node() 197 221 { 198 return c urrent_;222 return const_cast<list_node<value_type>*>(current_); 199 223 } 200 224 … … 209 233 } 210 234 211 template<class ConstRef, class ConstPtr>212 operator hash_table_const_iterator<213 Value, ConstRef, ConstPtr, Size214 >() const215 {216 return hash_table_const_iterator<value_type, ConstRef, ConstPtr, size_type>{217 table_, idx_, max_idx_, current_218 };219 }220 221 235 private: 222 hash_table_bucket<value_type, size_type>* table_;236 const hash_table_bucket<value_type, size_type>* table_; 223 237 size_type idx_; 224 238 size_type max_idx_; 239 const list_node<value_type>* current_; 240 }; 241 242 template<class Value, class CRef, class CPtr, class Size> 243 bool operator==(const hash_table_const_iterator<Value, CRef, CPtr, Size>& lhs, 244 const hash_table_const_iterator<Value, CRef, CPtr, Size>& rhs) 245 { 246 return lhs.node() == rhs.node(); 247 } 248 249 template<class Value, class CRef, class CPtr, class Size> 250 bool operator!=(const hash_table_const_iterator<Value, CRef, CPtr, Size>& lhs, 251 const hash_table_const_iterator<Value, CRef, CPtr, Size>& rhs) 252 { 253 return !(lhs == rhs); 254 } 255 256 template<class Value, class Ref, class Ptr, class CRef, class CPtr, class Size> 257 bool operator==(const hash_table_iterator<Value, Ref, Ptr, Size>& lhs, 258 const hash_table_const_iterator<Value, CRef, CPtr, Size>& rhs) 259 { 260 return lhs.node() == rhs.node(); 261 } 262 263 template<class Value, class Ref, class Ptr, class CRef, class CPtr, class Size> 264 bool operator!=(const hash_table_iterator<Value, Ref, Ptr, Size>& lhs, 265 const hash_table_const_iterator<Value, CRef, CPtr, Size>& rhs) 266 { 267 return !(lhs == rhs); 268 } 269 270 template<class Value, class CRef, class CPtr, class Ref, class Ptr, class Size> 271 bool operator==(const hash_table_const_iterator<Value, CRef, CPtr, Size>& lhs, 272 const hash_table_iterator<Value, Ref, Ptr, Size>& rhs) 273 { 274 return lhs.node() == rhs.node(); 275 } 276 277 template<class Value, class CRef, class CPtr, class Ref, class Ptr, class Size> 278 bool operator!=(const hash_table_const_iterator<Value, CRef, CPtr, Size>& lhs, 279 const hash_table_iterator<Value, Ref, Ptr, Size>& rhs) 280 { 281 return !(lhs == rhs); 282 } 283 284 template<class Value, class Reference, class Pointer> 285 class hash_table_local_iterator 286 { 287 public: 288 using value_type = Value; 289 using reference = Reference; 290 using pointer = Pointer; 291 using difference_type = ptrdiff_t; 292 293 using iterator_category = forward_iterator_tag; 294 295 hash_table_local_iterator(list_node<value_type>* head = nullptr, 296 list_node<value_type>* current = nullptr) 297 : head_{head}, current_{current} 298 { /* DUMMY BODY */ } 299 300 hash_table_local_iterator(const hash_table_local_iterator&) = default; 301 hash_table_local_iterator& operator=(const hash_table_local_iterator&) = default; 302 303 reference operator*() 304 { 305 return current_->value; 306 } 307 308 pointer operator->() 309 { 310 return ¤t_->value; 311 } 312 313 hash_table_local_iterator& operator++() 314 { 315 current_ = current_->next; 316 if (current_ == head_) 317 current_ = nullptr; 318 319 return *this; 320 } 321 322 hash_table_local_iterator operator++(int) 323 { 324 auto tmp = *this; 325 ++(*this); 326 327 return tmp; 328 } 329 330 list_node<value_type>* node() 331 { 332 return current_; 333 } 334 335 const list_node<value_type>* node() const 336 { 337 return current_; 338 } 339 340 private: 341 list_node<value_type>* head_; 225 342 list_node<value_type>* current_; 343 344 template<class V, class CR, class CP> 345 friend class hash_table_const_local_iterator; 226 346 }; 227 347 228 template<class Value, class Ref, class Ptr , class Size>229 bool operator==(const hash_table_ iterator<Value, Ref, Ptr, Size>& lhs,230 const hash_table_ iterator<Value, Ref, Ptr, Size>& rhs)231 { 232 return lhs.node() == rhs.node(); 233 } 234 235 template<class Value, class Ref, class Ptr , class Size>236 bool operator!=(const hash_table_ iterator<Value, Ref, Ptr, Size>& lhs,237 const hash_table_ iterator<Value, Ref, Ptr, Size>& rhs)348 template<class Value, class Ref, class Ptr> 349 bool operator==(const hash_table_local_iterator<Value, Ref, Ptr>& lhs, 350 const hash_table_local_iterator<Value, Ref, Ptr>& rhs) 351 { 352 return lhs.node() == rhs.node(); 353 } 354 355 template<class Value, class Ref, class Ptr> 356 bool operator!=(const hash_table_local_iterator<Value, Ref, Ptr>& lhs, 357 const hash_table_local_iterator<Value, Ref, Ptr>& rhs) 238 358 { 239 359 return !(lhs == rhs); … … 243 363 class hash_table_const_local_iterator 244 364 { 365 using non_const_iterator_type = hash_table_local_iterator< 366 Value, get_non_const_ref_t<ConstReference>, 367 get_non_const_ptr_t<ConstPointer> 368 >; 369 245 370 public: 246 371 using value_type = Value; … … 260 385 hash_table_const_local_iterator& operator=(const hash_table_const_local_iterator&) = default; 261 386 387 hash_table_const_local_iterator(const non_const_iterator_type& other) 388 : head_{other.head_}, current_{other.current_} 389 { /* DUMMY BODY */ } 390 391 hash_table_const_local_iterator& operator=(const non_const_iterator_type& other) 392 { 393 head_ = other.head_; 394 current_ = other.current_; 395 396 return *this; 397 } 398 262 399 const_reference operator*() const 263 400 { … … 303 440 }; 304 441 305 template<class Value, class ConstRef, class ConstPtr> 306 bool operator==(const hash_table_const_local_iterator<Value, ConstRef, ConstPtr>& lhs, 307 const hash_table_const_local_iterator<Value, ConstRef, ConstPtr>& rhs) 308 { 309 return lhs.node() == rhs.node(); 310 } 311 312 template<class Value, class ConstRef, class ConstPtr> 313 bool operator!=(const hash_table_const_local_iterator<Value, ConstRef, ConstPtr>& lhs, 314 const hash_table_const_local_iterator<Value, ConstRef, ConstPtr>& rhs) 315 { 316 return !(lhs == rhs); 317 } 318 319 template<class Value, class Reference, class Pointer> 320 class hash_table_local_iterator 321 { 322 public: 323 using value_type = Value; 324 using reference = Reference; 325 using pointer = Pointer; 326 using difference_type = ptrdiff_t; 327 328 using iterator_category = forward_iterator_tag; 329 330 hash_table_local_iterator(list_node<value_type>* head = nullptr, 331 list_node<value_type>* current = nullptr) 332 : head_{head}, current_{current} 333 { /* DUMMY BODY */ } 334 335 hash_table_local_iterator(const hash_table_local_iterator&) = default; 336 hash_table_local_iterator& operator=(const hash_table_local_iterator&) = default; 337 338 reference operator*() 339 { 340 return current_->value; 341 } 342 343 pointer operator->() 344 { 345 return ¤t_->value; 346 } 347 348 hash_table_local_iterator& operator++() 349 { 350 current_ = current_->next; 351 if (current_ == head_) 352 current_ = nullptr; 353 354 return *this; 355 } 356 357 hash_table_local_iterator operator++(int) 358 { 359 auto tmp = *this; 360 ++(*this); 361 362 return tmp; 363 } 364 365 list_node<value_type>* node() 366 { 367 return current_; 368 } 369 370 const list_node<value_type>* node() const 371 { 372 return current_; 373 } 374 375 template<class ConstRef, class ConstPtr> 376 operator hash_table_const_local_iterator< 377 Value, ConstRef, ConstPtr 378 >() const 379 { 380 return hash_table_const_local_iterator< 381 value_type, ConstRef, ConstPtr 382 >{head_, current_}; 383 } 384 385 private: 386 list_node<value_type>* head_; 387 list_node<value_type>* current_; 388 }; 389 390 template<class Value, class Ref, class Ptr> 442 template<class Value, class CRef, class CPtr> 443 bool operator==(const hash_table_const_local_iterator<Value, CRef, CPtr>& lhs, 444 const hash_table_const_local_iterator<Value, CRef, CPtr>& rhs) 445 { 446 return lhs.node() == rhs.node(); 447 } 448 449 template<class Value, class CRef, class CPtr> 450 bool operator!=(const hash_table_const_local_iterator<Value, CRef, CPtr>& lhs, 451 const hash_table_const_local_iterator<Value, CRef, CPtr>& rhs) 452 { 453 return !(lhs == rhs); 454 } 455 456 template<class Value, class Ref, class Ptr, class CRef, class CPtr> 391 457 bool operator==(const hash_table_local_iterator<Value, Ref, Ptr>& lhs, 458 const hash_table_const_local_iterator<Value, CRef, CPtr>& rhs) 459 { 460 return lhs.node() == rhs.node(); 461 } 462 463 template<class Value, class Ref, class Ptr, class CRef, class CPtr> 464 bool operator!=(const hash_table_local_iterator<Value, Ref, Ptr>& lhs, 465 const hash_table_const_local_iterator<Value, CRef, CPtr>& rhs) 466 { 467 return !(lhs == rhs); 468 } 469 470 template<class Value, class CRef, class CPtr, class Ref, class Ptr> 471 bool operator==(const hash_table_const_local_iterator<Value, CRef, CPtr>& lhs, 392 472 const hash_table_local_iterator<Value, Ref, Ptr>& rhs) 393 473 { … … 395 475 } 396 476 397 template<class Value, class Ref, class Ptr>398 bool operator!=(const hash_table_ local_iterator<Value, Ref,Ptr>& lhs,477 template<class Value, class CRef, class CPtr, class Ref, class Ptr> 478 bool operator!=(const hash_table_const_local_iterator<Value, CRef, CPtr>& lhs, 399 479 const hash_table_local_iterator<Value, Ref, Ptr>& rhs) 400 480 { -
uspace/lib/cpp/include/internal/rbtree_iterators.hpp
r009d78b rd6bb78b 30 30 #define LIBCPP_INTERNAL_RBTREE_ITERATORS 31 31 32 #include <internal/iterator.hpp> 32 33 #include <internal/rbtree_node.hpp> 33 34 #include <iterator> … … 44 45 */ 45 46 47 template<class Value, class Reference, class Pointer, class Size> 48 class rbtree_iterator 49 { 50 public: 51 using value_type = Value; 52 using size_type = Size; 53 using reference = Reference; 54 using pointer = Pointer; 55 using difference_type = ptrdiff_t; 56 57 using iterator_category = bidirectional_iterator_tag; 58 59 rbtree_iterator(rbtree_node<value_type>* current = nullptr, bool end = true) 60 : current_{current}, end_{end} 61 { /* DUMMY BODY */ } 62 63 rbtree_iterator(const rbtree_iterator&) = default; 64 rbtree_iterator& operator=(const rbtree_iterator&) = default; 65 66 reference operator*() const 67 { 68 return current_->value; 69 } 70 71 pointer operator->() const 72 { 73 return ¤t_->value; 74 } 75 76 rbtree_iterator& operator++() 77 { 78 if (current_) 79 { 80 auto bckp = current_; 81 if (current_->right) 82 current_ = current_->right->find_smallest(); 83 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 } 110 } 111 112 return *this; 113 } 114 115 rbtree_iterator operator++(int) 116 { 117 auto tmp = *this; 118 ++(*this); 119 120 return tmp; 121 } 122 123 rbtree_iterator& operator--() 124 { 125 if (end_) 126 { 127 try_undo_end_(); 128 129 return *this; 130 } 131 132 if (current_) 133 { 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. 152 end_ = true; 153 } 154 155 return *this; 156 } 157 158 rbtree_iterator operator--(int) 159 { 160 auto tmp = *this; 161 --(*this); 162 163 return tmp; 164 } 165 166 const rbtree_node<value_type>* node() const 167 { 168 return current_; 169 } 170 171 rbtree_node<value_type>* node() 172 { 173 return current_; 174 } 175 176 bool end() const 177 { 178 return end_; 179 } 180 181 private: 182 rbtree_node<value_type>* current_; 183 bool end_; 184 185 void try_undo_end_() 186 { 187 if (!current_) 188 return; 189 190 /** 191 * We can do this if we are past end(). 192 * This means we are the largest. 193 */ 194 if (current_->find_largest() == current_) 195 end_ = false; 196 } 197 }; 198 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) 202 { 203 return (lhs.node() == rhs.node()) && (lhs.end() == rhs.end()); 204 } 205 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) 209 { 210 return !(lhs == rhs); 211 } 212 46 213 template<class Value, class ConstReference, class ConstPointer, class Size> 47 214 class rbtree_const_iterator 48 215 { 216 using non_const_iterator_type = rbtree_iterator< 217 Value, get_non_const_ref_t<ConstReference>, 218 get_non_const_ptr_t<ConstPointer>, Size 219 >; 220 49 221 public: 50 222 using value_type = Value; … … 62 234 rbtree_const_iterator(const rbtree_const_iterator&) = default; 63 235 rbtree_const_iterator& operator=(const rbtree_const_iterator&) = default; 236 237 rbtree_const_iterator(const non_const_iterator_type& other) 238 : current_{other.node()}, end_{other.end()} 239 { /* DUMMY BODY */ } 240 241 rbtree_const_iterator& operator=(const non_const_iterator_type& other) 242 { 243 current_ = other.node(); 244 end_ = other.end(); 245 246 return *this; 247 } 64 248 65 249 const_reference operator*() const … … 205 389 } 206 390 207 template<class Value, class Reference, class Pointer, class Size> 208 class rbtree_iterator 209 { 210 public: 211 using value_type = Value; 212 using size_type = Size; 213 using reference = Reference; 214 using pointer = Pointer; 215 using difference_type = ptrdiff_t; 216 217 using iterator_category = bidirectional_iterator_tag; 218 219 rbtree_iterator(rbtree_node<value_type>* current = nullptr, bool end = true) 220 : current_{current}, end_{end} 221 { /* DUMMY BODY */ } 222 223 rbtree_iterator(const rbtree_iterator&) = default; 224 rbtree_iterator& operator=(const rbtree_iterator&) = default; 225 226 reference operator*() const 227 { 228 return current_->value; 229 } 230 231 pointer operator->() const 232 { 233 return ¤t_->value; 234 } 235 236 rbtree_iterator& operator++() 237 { 238 if (current_) 239 { 240 auto bckp = current_; 241 if (current_->right) 242 current_ = current_->right->find_smallest(); 243 else 244 { 245 while (!current_->is_left_child()) 246 { 247 current_ = current_->parent; 248 249 if (!current_ || !current_->parent) 250 { 251 /** 252 * We've gone back to root without 253 * being a left child, which means we 254 * were the last node. 255 */ 256 end_ = true; 257 current_ = bckp; 258 259 return *this; 260 } 261 } 262 263 /** 264 * Now we are a left child, 265 * so the next node we have to visit 266 * is our parent. 267 */ 268 current_ = current_->parent; 269 } 270 } 271 272 return *this; 273 } 274 275 rbtree_iterator operator++(int) 276 { 277 auto tmp = *this; 278 ++(*this); 279 280 return tmp; 281 } 282 283 rbtree_iterator& operator--() 284 { 285 if (end_) 286 { 287 try_undo_end_(); 288 289 return *this; 290 } 291 292 if (current_) 293 { 294 if (current_->left) 295 current_ = current_->left->find_largest(); 296 else if (current_->parent) 297 { 298 while (current_->is_left_child()) 299 current_ = current_->parent; 300 301 /** 302 * We know parent exists here 303 * because we went up from the 304 * left and stopped being left 305 * child (if at any point we happened 306 * to become root then this branch 307 * wouldn't happen). 308 */ 309 current_ = current_->parent; 310 } 311 else // We are root without a left child. 312 end_ = true; 313 } 314 315 return *this; 316 } 317 318 rbtree_iterator operator--(int) 319 { 320 auto tmp = *this; 321 --(*this); 322 323 return tmp; 324 } 325 326 const rbtree_node<value_type>* node() const 327 { 328 return current_; 329 } 330 331 rbtree_node<value_type>* node() 332 { 333 return current_; 334 } 335 336 bool end() const 337 { 338 return end_; 339 } 340 341 private: 342 rbtree_node<value_type>* current_; 343 bool end_; 344 345 void try_undo_end_() 346 { 347 if (!current_) 348 return; 349 350 /** 351 * We can do this if we are past end(). 352 * This means we are the largest. 353 */ 354 if (current_->find_largest() == current_) 355 end_ = false; 356 } 357 }; 358 359 template<class Val, class Ref, class Ptr, class Sz> 391 template<class Val, class Ref, class Ptr, class CRef, class CPtr, class Sz> 360 392 bool operator==(const rbtree_iterator<Val, Ref, Ptr, Sz>& lhs, 393 const rbtree_const_iterator<Val, CRef, CPtr, Sz>& rhs) 394 { 395 return (lhs.node() == rhs.node()) && (lhs.end() == rhs.end()); 396 } 397 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) 401 { 402 return !(lhs == rhs); 403 } 404 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, 361 407 const rbtree_iterator<Val, Ref, Ptr, Sz>& rhs) 362 408 { … … 364 410 } 365 411 366 template<class Val, class Ref, class Ptr, class Sz>367 bool operator!=(const rbtree_ iterator<Val, Ref,Ptr, Sz>& lhs,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, 368 414 const rbtree_iterator<Val, Ref, Ptr, Sz>& rhs) 369 415 {
Note:
See TracChangeset
for help on using the changeset viewer.
