forest.hpp (39395B)
1 /* 2 Copyright 2013 Adobe 3 Distributed under the Boost Software License, Version 1.0. 4 (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) 5 */ 6 /**************************************************************************************************/ 7 8 #ifndef STLAB_FOREST_HPP 9 #define STLAB_FOREST_HPP 10 11 /**************************************************************************************************/ 12 13 #include <cassert> 14 #include <cstddef> 15 #include <functional> 16 #include <iterator> 17 18 #include <stlab/algorithm/reverse.hpp> 19 #include <stlab/iterator/set_next.hpp> 20 21 /**************************************************************************************************/ 22 23 namespace stlab { 24 25 /**************************************************************************************************/ 26 27 enum class forest_edge : bool { trailing, leading }; 28 29 constexpr auto forest_trailing_edge{forest_edge::trailing}; 30 constexpr auto forest_leading_edge{forest_edge::leading}; 31 32 /**************************************************************************************************/ 33 34 constexpr auto pivot(forest_edge e) { return forest_edge(static_cast<bool>(e) ^ 1); } 35 36 template <class I> // I models FullorderIterator 37 void pivot(I& i) { 38 i.edge() = pivot(i.edge()); 39 } 40 41 template <class I> // I models FullorderIterator 42 auto pivot_of(I i) { 43 pivot(i); 44 return i; 45 } 46 47 /**************************************************************************************************/ 48 49 template <class I> // I models a FullorderIterator 50 auto leading_of(I i) { 51 i.edge() = forest_edge::leading; 52 return i; 53 } 54 55 template <class I> // I models a FullorderIterator 56 auto trailing_of(I i) { 57 i.edge() = forest_edge::trailing; 58 return i; 59 } 60 61 /**************************************************************************************************/ 62 63 constexpr auto is_leading(forest_edge e) { 64 return e == forest_edge::leading; 65 } 66 67 template <class I> // I models a FullorderIterator 68 auto is_leading(const I& i) { 69 return is_leading(i.edge()); 70 } 71 72 constexpr auto is_trailing(forest_edge e) { 73 return e == forest_edge::trailing; 74 } 75 76 template <class I> // I models a FullorderIterator 77 auto is_trailing(const I& i) { 78 return is_trailing(i.edge()); 79 } 80 81 /**************************************************************************************************/ 82 83 template <class I> // I models FullorderIterator 84 I find_parent(I i) { 85 do { 86 i = std::next(trailing_of(i)); 87 } while (i.edge() != forest_edge::trailing); 88 return i; 89 } 90 91 /**************************************************************************************************/ 92 93 template <class I> // I models FullorderIterator 94 bool has_children(const I& i) { 95 return !i.equal_node(std::next(leading_of(i))); 96 } 97 98 /**************************************************************************************************/ 99 100 template <class I> // I models FullorderIterator 101 struct child_iterator { 102 using value_type = typename std::iterator_traits<I>::value_type; 103 using difference_type = typename std::iterator_traits<I>::difference_type; 104 using reference = typename std::iterator_traits<I>::reference; 105 using pointer = typename std::iterator_traits<I>::pointer; 106 using iterator_category = typename std::iterator_traits<I>::iterator_category; 107 108 child_iterator() = default; 109 explicit child_iterator(I x) : _x(std::move(x)) {} 110 template <class U> 111 child_iterator(const child_iterator<U>& u) : _x(u.base()) {} 112 113 I base() const { return _x; } 114 115 reference operator*() { return dereference(); } 116 pointer operator->() { return &dereference(); } 117 auto& operator++() { 118 increment(); 119 return *this; 120 } 121 auto operator++(int) { 122 auto result{*this}; 123 increment(); 124 return result; 125 } 126 auto& operator--() { 127 decrement(); 128 return *this; 129 } 130 auto operator--(int) { 131 auto result{*this}; 132 decrement(); 133 return result; 134 } 135 136 friend bool operator==(const child_iterator& a, const child_iterator& b) { 137 return a.base() == b.base(); 138 } 139 friend bool operator!=(const child_iterator& a, const child_iterator& b) { return !(a == b); } 140 141 private: 142 I _x; 143 144 void increment() { 145 pivot(_x); 146 ++_x; 147 } 148 void decrement() { 149 --_x; 150 pivot(_x); 151 } 152 153 reference dereference() { return *_x; } 154 }; 155 156 /**************************************************************************************************/ 157 158 template <class I> // I models FullorderIterator 159 I find_edge(I x, forest_edge edge) { 160 while (x.edge() != edge) 161 ++x; 162 return x; 163 } 164 165 template <class I> // I models FullorderIterator 166 I find_edge_reverse(I x, forest_edge edge) { 167 while (x.edge() != edge) 168 --x; 169 return x; 170 } 171 172 /**************************************************************************************************/ 173 174 template <class I, forest_edge Edge> // I models FullorderIterator 175 struct edge_iterator { 176 using value_type = typename std::iterator_traits<I>::value_type; 177 using difference_type = typename std::iterator_traits<I>::difference_type; 178 using reference = typename std::iterator_traits<I>::reference; 179 using pointer = typename std::iterator_traits<I>::pointer; 180 using iterator_category = typename std::iterator_traits<I>::iterator_category; 181 182 edge_iterator() = default; 183 explicit edge_iterator(I x) : _x(find_edge(x, Edge)) {} 184 template <class U> 185 edge_iterator(const edge_iterator<U, Edge>& u) : _x(u.base()) {} 186 187 I base() const { return _x; } 188 189 reference operator*() { return dereference(); } 190 pointer operator->() { return &dereference(); } 191 auto& operator++() { 192 increment(); 193 return *this; 194 } 195 auto operator++(int) { 196 auto result{*this}; 197 increment(); 198 return result; 199 } 200 auto& operator--() { 201 decrement(); 202 return *this; 203 } 204 auto operator--(int) { 205 auto result{*this}; 206 decrement(); 207 return result; 208 } 209 210 friend bool operator==(const edge_iterator& a, const edge_iterator& b) { 211 return a.base() == b.base(); 212 } 213 friend bool operator!=(const edge_iterator& a, const edge_iterator& b) { return !(a == b); } 214 215 private: 216 I _x; 217 218 void increment() { _x = find_edge(std::next(_x), Edge); } 219 220 void decrement() { _x = find_edge_reverse(std::prev(_x), Edge); } 221 222 reference dereference() { return *_x; } 223 }; 224 225 /**************************************************************************************************/ 226 227 template <class I, // I models a Forest 228 class P> // P models UnaryPredicate of value_type(I) 229 struct filter_fullorder_iterator { 230 using value_type = typename std::iterator_traits<I>::value_type; 231 using difference_type = typename std::iterator_traits<I>::difference_type; 232 using reference = typename std::iterator_traits<I>::reference; 233 using pointer = typename std::iterator_traits<I>::pointer; 234 using iterator_category = typename std::iterator_traits<I>::iterator_category; 235 236 filter_fullorder_iterator() = default; 237 238 filter_fullorder_iterator(I f, I l, P p) : 239 _x(skip_forward(f, l, p)), _inside(true), _first(f), _last(l), _predicate(p) {} 240 241 filter_fullorder_iterator(I f, I l) : 242 _x(skip_forward(f, l, P())), _inside(true), _first(f), _last(l) {} 243 244 template <class U> 245 filter_fullorder_iterator(const filter_fullorder_iterator<U, P>& x) : 246 _x(x.base()), _inside(x._inside), _first(x._first), _last(x._last), 247 _predicate(x._predicate) {} 248 249 P predicate() const { return _predicate; } 250 251 forest_edge edge() const { return this->base().edge(); } 252 forest_edge& edge() { return this->base_reference().edge(); } 253 254 bool equal_node(const filter_fullorder_iterator& y) const { 255 return this->base().equal_node(y.base()); 256 } 257 258 I base() const { return _x; } 259 260 reference operator*() { return dereference(); } 261 pointer operator->() { return &dereference(); } 262 auto& operator++() { 263 increment(); 264 return *this; 265 } 266 auto operator++(int) { 267 auto result{*this}; 268 increment(); 269 return result; 270 } 271 auto& operator--() { 272 decrement(); 273 return *this; 274 } 275 auto operator--(int) { 276 auto result{*this}; 277 decrement(); 278 return result; 279 } 280 281 friend bool operator==(const filter_fullorder_iterator& a, const filter_fullorder_iterator& b) { 282 return a.base() == b.base(); 283 } 284 friend bool operator!=(const filter_fullorder_iterator& a, const filter_fullorder_iterator& b) { 285 return !(a == b); 286 } 287 288 private: 289 I _x; 290 bool _inside; 291 I _first; 292 I _last; 293 P _predicate; 294 295 void increment() { 296 I i = this->base(); 297 298 if (i == _last) _inside = false; 299 ++i; 300 if (i == _first) _inside = true; 301 if (_inside) i = skip_forward(i, _last, _predicate); 302 this->base_reference() = i; 303 } 304 305 static I skip_forward(I f, I l, P p) 306 // Precondition: l is on a leading edge 307 { 308 while ((f.edge() == forest_edge::leading) && (f != l) && !p(*f)) { 309 f.edge() = forest_edge::trailing; 310 ++f; 311 } 312 return f; 313 } 314 315 static I skip_backward(I f, I l, P p) 316 // Precondition: f is on a trailing edge 317 { 318 while ((l.edge() == forest_edge::trailing) && (f != l) && !p(*l)) { 319 l.edge() = forest_edge::leading; 320 --l; 321 } 322 return l; 323 } 324 325 void decrement() { 326 I i = this->base(); 327 328 if (i == _first) _inside = false; 329 --i; 330 if (i == _last) _inside = true; 331 if (_inside) i = skip_backward(_first, i, _predicate); 332 this->base_reference() = i; 333 } 334 335 reference dereference() { return *_x; } 336 }; 337 338 /**************************************************************************************************/ 339 340 template <class I> // I models a FullorderIterator 341 struct reverse_fullorder_iterator { 342 using iterator_type = I; 343 344 using value_type = typename std::iterator_traits<I>::value_type; 345 using difference_type = typename std::iterator_traits<I>::difference_type; 346 using reference = typename std::iterator_traits<I>::reference; 347 using pointer = typename std::iterator_traits<I>::pointer; 348 using iterator_category = typename std::iterator_traits<I>::iterator_category; 349 350 reverse_fullorder_iterator() : _edge(forest_edge::trailing) {} 351 explicit reverse_fullorder_iterator(I x) : _base(--x), _edge(pivot(_base.edge())) {} 352 template <class U> 353 reverse_fullorder_iterator(const reverse_fullorder_iterator<U>& x) : 354 _base(--x.base()), _edge(pivot(_base.edge())) {} 355 356 iterator_type base() const { return std::next(_base); } 357 358 forest_edge edge() const { return _edge; } 359 forest_edge& edge() { return _edge; } 360 361 bool equal_node(const reverse_fullorder_iterator& y) const { return _base.equal_node(y._base); } 362 363 reference operator*() { return dereference(); } 364 pointer operator->() { return &dereference(); } 365 auto& operator++() { 366 increment(); 367 return *this; 368 } 369 auto operator++(int) { 370 auto result{*this}; 371 increment(); 372 return result; 373 } 374 auto& operator--() { 375 decrement(); 376 return *this; 377 } 378 auto operator--(int) { 379 auto result{*this}; 380 decrement(); 381 return result; 382 } 383 384 friend bool operator==(const reverse_fullorder_iterator& a, 385 const reverse_fullorder_iterator& b) { 386 return a.equal(b); 387 } 388 friend bool operator!=(const reverse_fullorder_iterator& a, 389 const reverse_fullorder_iterator& b) { 390 return !(a == b); 391 } 392 393 private: 394 I _base; 395 forest_edge _edge; 396 397 void increment() { 398 _base.edge() = pivot(_edge); 399 --_base; 400 _edge = pivot(_base.edge()); 401 } 402 void decrement() { 403 _base.edge() = pivot(_edge); 404 ++_base; 405 _edge = pivot(_base.edge()); 406 } 407 reference dereference() const { return *_base; } 408 409 bool equal(const reverse_fullorder_iterator& y) const { 410 return (_base == y._base) && (_edge == y._edge); 411 } 412 }; 413 414 /**************************************************************************************************/ 415 416 template <class I> // I models FullorderIterator 417 struct depth_fullorder_iterator { 418 using value_type = typename std::iterator_traits<I>::value_type; 419 using difference_type = typename std::iterator_traits<I>::difference_type; 420 using reference = typename std::iterator_traits<I>::reference; 421 using pointer = typename std::iterator_traits<I>::pointer; 422 using iterator_category = typename std::iterator_traits<I>::iterator_category; 423 424 depth_fullorder_iterator(difference_type d = 0) : _depth(d) {} 425 explicit depth_fullorder_iterator(I x, difference_type d = 0) : _x(x), _depth(d) {} 426 template <class U> 427 depth_fullorder_iterator(const depth_fullorder_iterator<U>& x) : 428 _x(x.base()), _depth(x._depth) {} 429 430 difference_type depth() const { return _depth; } 431 forest_edge edge() const { return this->base().edge(); } 432 forest_edge& edge() { return _x.edge(); } 433 bool equal_node(depth_fullorder_iterator const& y) const { 434 return this->base().equal_node(y.base()); 435 } 436 437 I base() const { return _x; } 438 439 reference operator*() { return dereference(); } 440 pointer operator->() { return &dereference(); } 441 auto& operator++() { 442 increment(); 443 return *this; 444 } 445 auto operator++(int) { 446 auto result{*this}; 447 increment(); 448 return result; 449 } 450 auto& operator--() { 451 decrement(); 452 return *this; 453 } 454 auto operator--(int) { 455 auto result{*this}; 456 decrement(); 457 return result; 458 } 459 460 friend bool operator==(const depth_fullorder_iterator& a, const depth_fullorder_iterator& b) { 461 return a.base() == b.base(); 462 } 463 friend bool operator!=(const depth_fullorder_iterator& a, const depth_fullorder_iterator& b) { 464 return !(a == b); 465 } 466 467 private: 468 I _x; 469 difference_type _depth; 470 471 void increment() { 472 forest_edge old_edge(edge()); 473 ++_x; 474 if (old_edge == edge()) 475 _depth += difference_type(static_cast<std::size_t>(old_edge) << 1) - 1; 476 } 477 478 void decrement() { 479 forest_edge old_edge(edge()); 480 --_x; 481 if (old_edge == edge()) 482 _depth -= difference_type(static_cast<std::size_t>(old_edge) << 1) - 1; 483 } 484 485 reference dereference() { return *_x; } 486 }; 487 488 /**************************************************************************************************/ 489 490 template <class Forest> 491 class child_adaptor; 492 template <class T> 493 class forest; 494 495 /**************************************************************************************************/ 496 497 namespace detail { 498 499 /**************************************************************************************************/ 500 501 template <class D> // derived class 502 struct node_base { 503 enum next_prior_t { prior_s, next_s }; 504 505 using node_ptr = D*; 506 using reference = node_ptr&; 507 508 node_ptr& link(forest_edge edge, next_prior_t link) { 509 return _nodes[static_cast<std::size_t>(edge)][static_cast<std::size_t>(link)]; 510 } 511 512 node_ptr link(forest_edge edge, next_prior_t link) const { 513 return _nodes[static_cast<std::size_t>(edge)][static_cast<std::size_t>(link)]; 514 } 515 516 node_ptr _nodes[2][2]; 517 518 node_base() : 519 _nodes{{static_cast<node_ptr>(this), static_cast<node_ptr>(this)}, 520 {static_cast<node_ptr>(this), static_cast<node_ptr>(this)}} {} 521 }; 522 523 template <class T> // T models Regular 524 struct node : public node_base<node<T>> { 525 using value_type = T; 526 527 explicit node(const value_type& data) : _data(data) {} 528 529 value_type _data; 530 }; 531 532 /**************************************************************************************************/ 533 534 template <class T> 535 struct forest_const_iterator; 536 537 template <class T> // T is value_type 538 struct forest_iterator { 539 using value_type = T; 540 using difference_type = std::ptrdiff_t; 541 using reference = T&; 542 using pointer = T*; 543 using iterator_category = std::bidirectional_iterator_tag; 544 545 forest_iterator() = default; 546 547 forest_iterator(const forest_iterator& x) : _node(x._node), _edge(x._edge) {} 548 549 forest_iterator& operator=(const forest_iterator&) = default; 550 551 forest_edge edge() const { return _edge; } 552 forest_edge& edge() { return _edge; } 553 554 bool equal_node(forest_iterator const& y) const { return _node == y._node; } 555 556 reference operator*() const { return dereference(); } 557 pointer operator->() const { return &dereference(); } 558 auto& operator++() { 559 increment(); 560 return *this; 561 } 562 auto operator++(int) { 563 auto result{*this}; 564 increment(); 565 return result; 566 } 567 auto& operator--() { 568 decrement(); 569 return *this; 570 } 571 auto operator--(int) { 572 auto result{*this}; 573 decrement(); 574 return result; 575 } 576 577 friend bool operator==(const forest_iterator& a, const forest_iterator& b) { 578 return a.equal(b); 579 } 580 friend bool operator!=(const forest_iterator& a, const forest_iterator& b) { return !(a == b); } 581 582 private: 583 friend class stlab::forest<value_type>; 584 template <class> 585 friend struct forest_iterator; 586 template <class> 587 friend struct forest_const_iterator; 588 friend struct unsafe::set_next_fn<forest_iterator>; 589 590 using node_t = node<T>; 591 592 reference dereference() const { return _node->_data; } 593 594 void increment() { 595 node_t* next(_node->link(_edge, node_t::next_s)); 596 597 if (is_leading(_edge)) 598 _edge = forest_edge(next != _node); 599 else 600 _edge = forest_edge(next->link(forest_edge::leading, node_t::prior_s) == _node); 601 602 _node = next; 603 } 604 605 void decrement() { 606 node_t* next(_node->link(_edge, node_t::prior_s)); 607 608 if (is_leading(_edge)) 609 _edge = forest_edge(next->link(forest_edge::trailing, node_t::next_s) != _node); 610 else 611 _edge = forest_edge(next == _node); 612 613 _node = next; 614 } 615 616 bool equal(const forest_iterator& y) const { return (_node == y._node) && (_edge == y._edge); } 617 618 node_t* _node{nullptr}; 619 forest_edge _edge{forest_edge::leading}; 620 621 forest_iterator(node_t* node, forest_edge edge) : _node(node), _edge(edge) {} 622 }; 623 624 /**************************************************************************************************/ 625 626 template <class T> // T is value_type 627 struct forest_const_iterator { 628 using value_type = const T; 629 using difference_type = std::ptrdiff_t; 630 using reference = const T&; 631 using pointer = const T*; 632 using iterator_category = std::bidirectional_iterator_tag; 633 634 forest_const_iterator() = default; 635 636 forest_const_iterator(const forest_const_iterator& x) : _node(x._node), _edge(x._edge) {} 637 638 forest_const_iterator& operator=(const forest_const_iterator&) = default; 639 640 forest_const_iterator(const forest_iterator<T>& x) : _node(x._node), _edge(x._edge) {} 641 642 forest_edge edge() const { return _edge; } 643 forest_edge& edge() { return _edge; } 644 bool equal_node(forest_const_iterator const& y) const { return _node == y._node; } 645 646 reference operator*() const { return dereference(); } 647 pointer operator->() const { return &dereference(); } 648 auto& operator++() { 649 increment(); 650 return *this; 651 } 652 auto operator++(int) { 653 auto result{*this}; 654 increment(); 655 return result; 656 } 657 auto& operator--() { 658 decrement(); 659 return *this; 660 } 661 auto operator--(int) { 662 auto result{*this}; 663 decrement(); 664 return result; 665 } 666 667 friend bool operator==(const forest_const_iterator& a, const forest_const_iterator& b) { 668 return a.equal(b); 669 } 670 friend bool operator!=(const forest_const_iterator& a, const forest_const_iterator& b) { 671 return !(a == b); 672 } 673 674 private: 675 template <class> 676 friend class stlab::forest; 677 template <class> 678 friend struct forest_const_iterator; 679 friend struct unsafe::set_next_fn<forest_const_iterator>; 680 681 using node_t = const node<T>; 682 683 reference dereference() const { return _node->_data; } 684 685 void increment() { 686 node_t* next(_node->link(_edge, node_t::next_s)); 687 688 if (is_leading(_edge)) 689 _edge = forest_edge(next != _node); 690 else 691 _edge = forest_edge(next->link(forest_edge::leading, node_t::prior_s) == _node); 692 693 _node = next; 694 } 695 696 void decrement() { 697 node_t* next(_node->link(_edge, node_t::prior_s)); 698 699 if (is_leading(_edge)) 700 _edge = forest_edge(next->link(forest_edge::trailing, node_t::next_s) != _node); 701 else 702 _edge = forest_edge(next == _node); 703 704 _node = next; 705 } 706 707 bool equal(const forest_const_iterator& y) const { 708 return (_node == y._node) && (_edge == y._edge); 709 } 710 711 node_t* _node{nullptr}; 712 forest_edge _edge{forest_edge::leading}; 713 714 forest_const_iterator(node_t* node, forest_edge edge) : _node(node), _edge(edge) {} 715 }; 716 717 /**************************************************************************************************/ 718 719 } // namespace detail 720 721 /**************************************************************************************************/ 722 723 namespace unsafe { 724 725 /**************************************************************************************************/ 726 727 template <class T> // T is node<T> 728 struct set_next_fn<detail::forest_iterator<T>> { 729 void operator()(detail::forest_iterator<T> x, detail::forest_iterator<T> y) const { 730 using node_t = typename detail::node<T>; 731 732 x._node->link(x.edge(), node_t::next_s) = y._node; 733 y._node->link(y.edge(), node_t::prior_s) = x._node; 734 } 735 }; 736 737 /**************************************************************************************************/ 738 739 } // namespace unsafe 740 741 /**************************************************************************************************/ 742 743 template <class T> 744 class forest { 745 private: 746 using node_t = detail::node<T>; 747 friend class child_adaptor<forest<T>>; 748 749 public: 750 // types 751 using reference = T&; 752 using const_reference = const T&; 753 using iterator = detail::forest_iterator<T>; 754 using const_iterator = detail::forest_const_iterator<T>; 755 using size_type = std::size_t; 756 using difference_type = std::ptrdiff_t; 757 using value_type = T; 758 using pointer = T*; 759 using const_pointer = const T*; 760 using reverse_iterator = reverse_fullorder_iterator<iterator>; 761 using const_reverse_iterator = reverse_fullorder_iterator<const_iterator>; 762 763 /* qualification needed since: A name N used in a class S shall refer to the same declaration 764 in its context and when re-evaluated in the completed scope of 765 S. */ 766 using child_iterator = stlab::child_iterator<iterator>; 767 using const_child_iterator = stlab::child_iterator<const_iterator>; 768 using reverse_child_iterator = std::reverse_iterator<child_iterator>; 769 770 using preorder_iterator = edge_iterator<iterator, forest_edge::leading>; 771 using const_preorder_iterator = edge_iterator<const_iterator, forest_edge::leading>; 772 using postorder_iterator = edge_iterator<iterator, forest_edge::trailing>; 773 using const_postorder_iterator = edge_iterator<const_iterator, forest_edge::trailing>; 774 775 forest() = default; 776 ~forest() { clear(); } 777 778 forest(const forest& x) : forest() { 779 insert(end(), const_child_iterator(x.begin()), const_child_iterator(x.end())); 780 } 781 forest(forest&& x) noexcept : forest() { splice(end(), x); } 782 forest& operator=(const forest& x) { 783 return *this = forest(x); 784 } 785 forest& operator=(forest&& x) noexcept { 786 auto tmp{move(x)}; // this is `release()` 787 clear(); // these two lines are `reset()` 788 splice(end(), tmp); 789 return *this; 790 } 791 792 void swap(forest& x) { std::swap(*this, x); } 793 794 size_type size() const; 795 size_type max_size() const { return size_type(-1); } 796 bool size_valid() const { return _size != 0 || empty(); } 797 bool empty() const { return begin() == end(); } // Don't test size which may be expensive 798 799 // iterators 800 iterator root() { return iterator(tail(), forest_edge::leading); } 801 const_iterator root() const { return const_iterator(tail(), forest_edge::leading); } 802 803 iterator begin() { return ++root(); } 804 iterator end() { return iterator(tail(), forest_edge::trailing); } 805 const_iterator begin() const { return ++root(); } 806 const_iterator end() const { return const_iterator(tail(), forest_edge::trailing); } 807 808 reverse_iterator rbegin() { return reverse_iterator(end()); } 809 reverse_iterator rend() { return reverse_iterator(begin()); } 810 const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); } 811 const_reverse_iterator rend() const { return const_reverse_iterator(begin()); } 812 813 reference front() { 814 assert(!empty()); 815 return *begin(); 816 } 817 const_reference front() const { 818 assert(!empty()); 819 return *begin(); 820 } 821 reference back() { 822 assert(!empty()); 823 return *(--end()); 824 } 825 const_reference back() const { 826 assert(!empty()); 827 return *(--end()); 828 } 829 830 // modifiers 831 void clear() { 832 erase(begin(), end()); 833 assert(empty()); // Make sure our erase is correct 834 } 835 836 iterator erase(const iterator& position); 837 iterator erase(const iterator& first, const iterator& last); 838 839 iterator insert(const iterator& position, T x) { 840 iterator result(new node_t(std::move(x)), forest_edge::leading); 841 842 if (size_valid()) ++_size; 843 844 unsafe::set_next(std::prev(position), result); 845 unsafe::set_next(std::next(result), position); 846 847 return result; 848 } 849 850 void push_front(const T& x) { insert(begin(), x); } 851 void push_back(const T& x) { insert(end(), x); } 852 void pop_front() { 853 assert(!empty()); 854 erase(begin()); 855 } 856 void pop_back() { 857 assert(!empty()); 858 erase(--end()); 859 } 860 861 iterator insert(iterator position, const_child_iterator first, const_child_iterator last); 862 863 iterator splice(iterator position, forest<T>& x); 864 iterator splice(iterator position, forest<T>& x, iterator i); 865 iterator splice(iterator position, forest<T>& x, child_iterator first, child_iterator last); 866 iterator splice(iterator position, 867 forest<T>& x, 868 child_iterator first, 869 child_iterator last, 870 size_type count); 871 872 iterator insert_parent(child_iterator front, child_iterator back, const T& x); 873 void reverse(child_iterator first, child_iterator last); 874 875 private: 876 friend struct detail::forest_iterator<value_type>; 877 friend struct detail::forest_const_iterator<value_type>; 878 friend struct unsafe::set_next_fn<iterator>; 879 880 mutable size_type _size{0}; 881 detail::node_base<node_t> _tail; 882 883 node_t* tail() { return static_cast<node_t*>(&_tail); } 884 const node_t* tail() const { return static_cast<const node_t*>(&_tail); } 885 }; 886 887 /**************************************************************************************************/ 888 889 template <class T> 890 bool operator==(const forest<T>& x, const forest<T>& y) { 891 if (x.size() != y.size()) return false; 892 893 for (auto first(x.begin()), last(x.end()), pos(y.begin()); first != last; ++first, ++pos) { 894 if (first.edge() != pos.edge()) return false; 895 if (is_leading(first) && (*first != *pos)) return false; 896 } 897 898 return true; 899 } 900 901 template <class T> 902 bool operator!=(const forest<T>& x, const forest<T>& y) { 903 return !(x == y); 904 } 905 906 /**************************************************************************************************/ 907 908 namespace unsafe { 909 910 /**************************************************************************************************/ 911 912 template <class I> // I models a FullorderIterator 913 struct set_next_fn<child_iterator<I>> { 914 void operator()(child_iterator<I> x, child_iterator<I> y) { 915 unsafe::set_next(pivot_of(x.base()), y.base()); 916 } 917 }; 918 919 /**************************************************************************************************/ 920 921 } // namespace unsafe 922 923 /**************************************************************************************************/ 924 925 template <class T> 926 typename forest<T>::size_type forest<T>::size() const { 927 if (!size_valid()) { 928 const_preorder_iterator first(begin()); 929 const_preorder_iterator last(end()); 930 931 _size = size_type(std::distance(first, last)); 932 } 933 934 return _size; 935 } 936 937 /**************************************************************************************************/ 938 939 template <class T> 940 typename forest<T>::iterator forest<T>::erase(const iterator& first, const iterator& last) { 941 difference_type stack_depth(0); 942 iterator position(first); 943 944 while (position != last) { 945 if (position.edge() == forest_edge::leading) { 946 ++stack_depth; 947 ++position; 948 } else { 949 if (stack_depth > 0) 950 position = erase(position); 951 else 952 ++position; 953 stack_depth = std::max<difference_type>(0, stack_depth - 1); 954 } 955 } 956 return last; 957 } 958 959 /**************************************************************************************************/ 960 961 template <class T> 962 typename forest<T>::iterator forest<T>::erase(const iterator& position) { 963 /* 964 NOTE (sparent) : After the first call to set_next() the invariants of the forest are 965 violated and we can't determing leading/trailing if we navigate from the affected node. 966 So we gather all the iterators up front then do the set_next calls. 967 */ 968 969 if (size_valid()) --_size; 970 971 iterator leading_prior(std::prev(leading_of(position))); 972 iterator leading_next(std::next(leading_of(position))); 973 iterator trailing_prior(std::prev(trailing_of(position))); 974 iterator trailing_next(std::next(trailing_of(position))); 975 976 if (has_children(position)) { 977 unsafe::set_next(leading_prior, leading_next); 978 unsafe::set_next(trailing_prior, trailing_next); 979 } else { 980 unsafe::set_next(leading_prior, trailing_next); 981 } 982 983 delete position._node; 984 985 return is_leading(position) ? std::next(leading_prior) : trailing_next; 986 } 987 988 /**************************************************************************************************/ 989 990 template <class T> 991 typename forest<T>::iterator forest<T>::splice(iterator position, forest<T>& x) { 992 return splice(position, x, child_iterator(x.begin()), child_iterator(x.end()), 993 x.size_valid() ? x.size() : 0); 994 } 995 996 /**************************************************************************************************/ 997 998 template <class T> 999 typename forest<T>::iterator forest<T>::splice(iterator position, forest<T>& x, iterator i) { 1000 i.edge() = forest_edge::leading; 1001 return splice(position, x, child_iterator(i), ++child_iterator(i), has_children(i) ? 0 : 1); 1002 } 1003 1004 /**************************************************************************************************/ 1005 1006 template <class T> 1007 typename forest<T>::iterator forest<T>::insert(iterator pos, 1008 const_child_iterator f, 1009 const_child_iterator l) { 1010 for (const_iterator first(f.base()), last(l.base()); first != last; ++first, ++pos) { 1011 if (is_leading(first)) pos = insert(pos, *first); 1012 } 1013 1014 return pos; 1015 } 1016 1017 /**************************************************************************************************/ 1018 1019 template <class T> 1020 typename forest<T>::iterator forest<T>::splice( 1021 iterator pos, forest<T>& x, child_iterator first, child_iterator last, size_type count) { 1022 if (first == last || first.base() == pos) return pos; 1023 1024 if (&x != this) { 1025 if (count) { 1026 if (size_valid()) _size += count; 1027 if (x.size_valid()) x._size -= count; 1028 } else { 1029 _size = 0; 1030 x._size = 0; 1031 } 1032 } 1033 1034 iterator back(std::prev(last.base())); 1035 1036 unsafe::set_next(std::prev(first), last); 1037 1038 unsafe::set_next(std::prev(pos), first.base()); 1039 unsafe::set_next(back, pos); 1040 1041 return first.base(); 1042 } 1043 1044 /**************************************************************************************************/ 1045 1046 template <class T> 1047 typename forest<T>::iterator forest<T>::splice(iterator pos, 1048 forest<T>& x, 1049 child_iterator first, 1050 child_iterator last) { 1051 return splice(pos, x, first, last, 0); 1052 } 1053 1054 /**************************************************************************************************/ 1055 1056 template <class T> 1057 typename forest<T>::iterator forest<T>::insert_parent(child_iterator first, 1058 child_iterator last, 1059 const T& x) { 1060 iterator result(insert(last.base(), x)); 1061 if (first == last) return result; 1062 splice(trailing_of(result), *this, first, child_iterator(result)); 1063 return result; 1064 } 1065 1066 /**************************************************************************************************/ 1067 1068 template <class T> 1069 void forest<T>::reverse(child_iterator first, child_iterator last) { 1070 iterator prior(first.base()); 1071 --prior; 1072 first = unsafe::reverse_nodes(first, last); 1073 unsafe::set_next(prior, first.base()); 1074 } 1075 1076 /**************************************************************************************************/ 1077 1078 template <class I> // I models FullorderIterator 1079 child_iterator<I> child_begin(const I& x) { 1080 return child_iterator<I>(std::next(leading_of(x))); 1081 } 1082 1083 /**************************************************************************************************/ 1084 1085 template <class I> // I models FullorderIterator 1086 child_iterator<I> child_end(const I& x) { 1087 return child_iterator<I>(trailing_of(x)); 1088 } 1089 1090 /**************************************************************************************************/ 1091 1092 template <class Forest> 1093 class child_adaptor { 1094 public: 1095 using forest_type = Forest; 1096 using value_type = typename Forest::value_type; 1097 using iterator_type = typename Forest::iterator; 1098 using reference = typename Forest::reference; 1099 using const_reference = typename Forest::const_reference; 1100 using difference_type = typename Forest::difference_type; 1101 using iterator = typename Forest::child_iterator; 1102 1103 child_adaptor(forest_type& f, iterator_type& i) : _forest(f), _iterator(i) {} 1104 1105 value_type& back() { return *(--child_end(_iterator)); } 1106 value_type& front() { return *(child_begin(_iterator)); } 1107 1108 void push_back(const value_type& x) { _forest.insert(child_end(_iterator).base(), x); } 1109 void push_front(const value_type& x) { _forest.insert(child_begin(_iterator).base(), x); } 1110 1111 void pop_back() { _forest.erase(--child_end(_iterator).base()); } 1112 void pop_front() { _forest.erase(child_begin(_iterator).base()); } 1113 1114 private: 1115 child_adaptor(); // not defined 1116 1117 forest_type& _forest; 1118 iterator_type& _iterator; 1119 }; 1120 1121 /**************************************************************************************************/ 1122 1123 template <class I> 1124 struct forest_range { 1125 I _f; 1126 I _l; 1127 1128 auto begin() const { return _f; } 1129 auto end() const { return _l; } 1130 }; 1131 1132 /**************************************************************************************************/ 1133 1134 template <class I> // I models FullorderIterator 1135 auto child_range(const I& x) { 1136 return forest_range<child_iterator<I>>{child_begin(x), child_end(x)}; 1137 } 1138 1139 /**************************************************************************************************/ 1140 1141 template <class R, typename P> // R models FullorderRange 1142 auto filter_fullorder_range(R& x, P p) { 1143 using iterator = filter_fullorder_iterator<typename R::iterator, P>; 1144 1145 return forest_range<iterator>{iterator(std::begin(x), std::end(x), p), 1146 iterator(std::end(x), std::end(x), p)}; 1147 } 1148 1149 template <class R, typename P> // R models FullorderRange 1150 auto filter_fullorder_range(const R& x, P p) { 1151 using iterator = filter_fullorder_iterator<typename R::const_iterator, P>; 1152 1153 return forest_range<iterator>{iterator(std::begin(x), std::end(x), p), 1154 iterator(std::end(x), std::end(x), p)}; 1155 } 1156 1157 /**************************************************************************************************/ 1158 1159 template <class R> // R models FullorderRange 1160 auto reverse_fullorder_range(R& x) { 1161 using iterator = reverse_fullorder_iterator<typename R::iterator>; 1162 1163 return forest_range<iterator>{iterator(std::end(x)), iterator(std::begin(x))}; 1164 } 1165 1166 template <class R> // R models FullorderRange 1167 auto reverse_fullorder_range(const R& x) { 1168 using iterator = reverse_fullorder_iterator<typename R::const_iterator>; 1169 1170 return forest_range<iterator>{iterator(std::end(x)), iterator(std::begin(x))}; 1171 } 1172 1173 /**************************************************************************************************/ 1174 1175 template <class R> // R models FullorderRange 1176 auto depth_range(R& x) { 1177 using iterator = depth_fullorder_iterator<typename R::iterator>; 1178 1179 return forest_range<iterator>{iterator(std::begin(x)), iterator(std::end(x))}; 1180 } 1181 1182 template <class R> // R models FullorderRange 1183 auto depth_range(const R& x) { 1184 using iterator = depth_fullorder_iterator<typename R::const_iterator>; 1185 1186 return forest_range<iterator>{iterator(std::begin(x)), iterator(std::end(x))}; 1187 } 1188 1189 /**************************************************************************************************/ 1190 1191 template <class R> // R models FullorderRange 1192 auto postorder_range(R& x) { 1193 using iterator = edge_iterator<typename R::iterator, forest_edge::trailing>; 1194 1195 return forest_range<iterator>{iterator(std::begin(x)), iterator(std::end(x))}; 1196 } 1197 1198 template <class R> // R models FullorderRange 1199 auto postorder_range(const R& x) { 1200 using iterator = edge_iterator<typename R::const_iterator, forest_edge::trailing>; 1201 1202 return forest_range<iterator>{iterator(std::begin(x)), iterator(std::end(x))}; 1203 } 1204 1205 /**************************************************************************************************/ 1206 1207 template <class R> // R models FullorderRange 1208 auto preorder_range(R& x) { 1209 using iterator = edge_iterator<typename R::iterator, forest_edge::leading>; 1210 1211 return forest_range<iterator>{iterator(std::begin(x)), iterator(std::end(x))}; 1212 } 1213 1214 template <class R> // R models FullorderRange 1215 auto preorder_range(const R& x) { 1216 using iterator = edge_iterator<typename R::const_iterator, forest_edge::leading>; 1217 1218 return forest_range<iterator>{iterator(std::begin(x)), iterator(std::end(x))}; 1219 } 1220 1221 /**************************************************************************************************/ 1222 1223 } // namespace stlab 1224 1225 /**************************************************************************************************/ 1226 1227 #endif // STLAB_FOREST_HPP 1228 1229 /**************************************************************************************************/