1 //////////////////////////////////////////////////////////////////////////////
2 //
3 // \(C\) Copyright Benedek Thaler 2015-2016
4 // \(C\) Copyright Ion Gaztanaga 2019-2020. Distributed under the Boost
5 // Software License, Version 1.0. (See accompanying file
6 // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
7 //
8 // See http://erenon.hu/double_ended for documentation.
9 //
10 //////////////////////////////////////////////////////////////////////////////
11
12 /**
13 * Emulates input iterator, validates algorithm
14 * does a single pass only, removes visited elements.
15 *
16 * Container::erase(front_iterator) must not invalidate other iterators.
17 *
18 * The hack around `_erase_on_destroy` is required to make `*it++` work.
19 */
20 template <typename Container>
21 class input_iterator
22 {
23 typedef typename Container::iterator iterator;
24
25 public:
26
27 typedef std::input_iterator_tag iterator_category;
28 typedef typename Container::value_type value_type;
29 typedef typename Container::pointer pointer;
30 typedef typename Container::reference reference;
31 typedef typename Container::difference_type difference_type;
32
33 struct erase_on_destroy {};
34
35 public:
36
input_iterator()37 input_iterator()
38 : _container()
39 , _it()
40 , _erase_on_destroy()
41 {}
42
input_iterator(Container & c,iterator it)43 input_iterator(Container& c, iterator it)
44 :_container(&c)
45 , _it(it)
46 , _erase_on_destroy()
47 {}
48
input_iterator(const input_iterator & rhs)49 input_iterator(const input_iterator& rhs)
50 :_container(rhs._container),
51 _it(rhs._it),
52 _erase_on_destroy(rhs._erase_on_destroy)
53 {
54 rhs._erase_on_destroy = false;
55 }
56
operator =(const input_iterator & rhs)57 input_iterator & operator=(const input_iterator& rhs)
58 {
59 _container = rhs._container;
60 _it = rhs._it;
61 _erase_on_destroy = rhs._erase_on_destroy;
62 rhs._erase_on_destroy = false;
63 return *this;
64 }
65
input_iterator(const input_iterator & rhs,erase_on_destroy)66 input_iterator(const input_iterator& rhs, erase_on_destroy)
67 :_container(rhs._container),
68 _it(rhs._it),
69 _erase_on_destroy(true)
70 {}
71
~input_iterator()72 ~input_iterator()
73 {
74 if (_erase_on_destroy)
75 {
76 _container->erase(_it); // must not invalidate other iterators
77 }
78 }
79
operator *()80 const value_type& operator*()
81 {
82 return *_it;
83 }
84
operator ++()85 input_iterator operator++()
86 {
87 _container->erase(_it);
88 ++_it;
89 return *this;
90 }
91
operator ++(int)92 input_iterator operator++(int)
93 {
94 input_iterator old(*this, erase_on_destroy());
95 ++_it;
96 return old;
97 }
98
operator ==(const input_iterator a,const input_iterator b)99 friend bool operator==(const input_iterator a, const input_iterator b)
100 {
101 return a._it == b._it;
102 }
103
operator !=(const input_iterator a,const input_iterator b)104 friend bool operator!=(const input_iterator a, const input_iterator b)
105 {
106 return !(a == b);
107 }
108
109 private:
110 Container* _container;
111 iterator _it;
112 mutable bool _erase_on_destroy;
113 };
114
115 template <typename Container>
make_input_iterator(Container & c,typename Container::iterator it)116 input_iterator<Container> make_input_iterator(Container& c, typename Container::iterator it)
117 {
118 return input_iterator<Container>(c, it);
119 }
120