Line data Source code
1 : // Boost.Range library
2 : //
3 : // Copyright Neil Groves 2010. Use, modification and
4 : // distribution is subject to the Boost Software License, Version
5 : // 1.0. (See accompanying file LICENSE_1_0.txt or copy at
6 : // http://www.boost.org/LICENSE_1_0.txt)
7 : //
8 : //
9 : // For more information, see http://www.boost.org/libs/range/
10 : //
11 : #ifndef BOOST_RANGE_IRANGE_HPP_INCLUDED
12 : #define BOOST_RANGE_IRANGE_HPP_INCLUDED
13 :
14 : #include <boost/assert.hpp>
15 : #include <boost/iterator/iterator_facade.hpp>
16 : #include <boost/range/iterator_range.hpp>
17 :
18 : namespace boost
19 : {
20 : namespace range_detail
21 : {
22 : // integer_iterator is an iterator over an integer sequence that
23 : // is bounded only by the limits of the underlying integer
24 : // representation.
25 : //
26 : // This is useful for implementing the irange(first, last)
27 : // function.
28 : //
29 : // Note:
30 : // This use of this iterator and irange is appreciably less
31 : // performant than the corresponding hand-written integer
32 : // loop on many compilers.
33 : template<typename Integer>
34 : class integer_iterator
35 : : public boost::iterator_facade<
36 : integer_iterator<Integer>,
37 : Integer,
38 : boost::random_access_traversal_tag,
39 : Integer,
40 : std::ptrdiff_t
41 : >
42 : {
43 : typedef boost::iterator_facade<
44 : integer_iterator<Integer>,
45 : Integer,
46 : boost::random_access_traversal_tag,
47 : Integer,
48 : std::ptrdiff_t
49 : > base_t;
50 : public:
51 : typedef typename base_t::value_type value_type;
52 : typedef typename base_t::difference_type difference_type;
53 : typedef typename base_t::reference reference;
54 : typedef std::random_access_iterator_tag iterator_category;
55 :
56 0 : integer_iterator() : m_value() {}
57 0 : explicit integer_iterator(value_type x) : m_value(x) {}
58 :
59 : private:
60 0 : void increment()
61 : {
62 0 : ++m_value;
63 : }
64 :
65 : void decrement()
66 : {
67 : --m_value;
68 : }
69 :
70 : void advance(difference_type offset)
71 : {
72 : m_value += offset;
73 : }
74 :
75 0 : difference_type distance_to(const integer_iterator& other) const
76 : {
77 : return is_signed<value_type>::value
78 0 : ? (other.m_value - m_value)
79 : : (other.m_value >= m_value)
80 : ? static_cast<difference_type>(other.m_value - m_value)
81 : : -static_cast<difference_type>(m_value - other.m_value);
82 : }
83 :
84 0 : bool equal(const integer_iterator& other) const
85 : {
86 : return m_value == other.m_value;
87 : }
88 :
89 0 : reference dereference() const
90 : {
91 : return m_value;
92 : }
93 :
94 : friend class ::boost::iterator_core_access;
95 : value_type m_value;
96 : };
97 :
98 : // integer_iterator_with_step is similar in nature to the
99 : // integer_iterator but provides the ability to 'move' in
100 : // a number of steps specified at construction time.
101 : //
102 : // The three variable implementation provides the best guarantees
103 : // of loop termination upon various combinations of input.
104 : //
105 : // While this design is less performant than some less
106 : // safe alternatives, the use of ranges and iterators to
107 : // perform counting will never be optimal anyhow, hence
108 : // if optimal performance is desired a hand-coded loop
109 : // is the solution.
110 : template<typename Integer>
111 : class integer_iterator_with_step
112 : : public boost::iterator_facade<
113 : integer_iterator_with_step<Integer>,
114 : Integer,
115 : boost::random_access_traversal_tag,
116 : Integer,
117 : std::ptrdiff_t
118 : >
119 : {
120 : typedef boost::iterator_facade<
121 : integer_iterator_with_step<Integer>,
122 : Integer,
123 : boost::random_access_traversal_tag,
124 : Integer,
125 : std::ptrdiff_t
126 : > base_t;
127 : public:
128 : typedef typename base_t::value_type value_type;
129 : typedef typename base_t::difference_type difference_type;
130 : typedef typename base_t::reference reference;
131 : typedef std::random_access_iterator_tag iterator_category;
132 :
133 : integer_iterator_with_step(value_type first, difference_type step, value_type step_size)
134 : : m_first(first)
135 : , m_step(step)
136 : , m_step_size(step_size)
137 : {
138 : }
139 :
140 : private:
141 : void increment()
142 : {
143 : ++m_step;
144 : }
145 :
146 : void decrement()
147 : {
148 : --m_step;
149 : }
150 :
151 : void advance(difference_type offset)
152 : {
153 : m_step += offset;
154 : }
155 :
156 : difference_type distance_to(const integer_iterator_with_step& other) const
157 : {
158 : return other.m_step - m_step;
159 : }
160 :
161 : bool equal(const integer_iterator_with_step& other) const
162 : {
163 : return m_step == other.m_step;
164 : }
165 :
166 : reference dereference() const
167 : {
168 : return m_first + (m_step * m_step_size);
169 : }
170 :
171 : friend class ::boost::iterator_core_access;
172 : value_type m_first;
173 : difference_type m_step;
174 : difference_type m_step_size;
175 : };
176 :
177 : } // namespace range_detail
178 :
179 : template<typename Integer>
180 : class integer_range
181 : : public iterator_range< range_detail::integer_iterator<Integer> >
182 : {
183 : typedef range_detail::integer_iterator<Integer> iterator_t;
184 : typedef iterator_range<iterator_t> base_t;
185 : public:
186 0 : integer_range(Integer first, Integer last)
187 0 : : base_t(iterator_t(first), iterator_t(last))
188 : {
189 : }
190 : };
191 :
192 : template<typename Integer>
193 : class strided_integer_range
194 : : public iterator_range< range_detail::integer_iterator_with_step<Integer> >
195 : {
196 : typedef range_detail::integer_iterator_with_step<Integer> iterator_t;
197 : typedef iterator_range<iterator_t> base_t;
198 : public:
199 : template<typename Iterator>
200 : strided_integer_range(Iterator first, Iterator last)
201 : : base_t(first, last)
202 : {
203 : }
204 : };
205 :
206 : template<typename Integer>
207 : integer_range<Integer>
208 : irange(Integer first, Integer last)
209 : {
210 : BOOST_ASSERT( first <= last );
211 : return integer_range<Integer>(first, last);
212 : }
213 :
214 : template<typename Integer, typename StepSize>
215 : strided_integer_range<Integer>
216 : irange(Integer first, Integer last, StepSize step_size)
217 : {
218 : BOOST_ASSERT( step_size != 0 );
219 : BOOST_ASSERT( (step_size > 0) ? (last >= first) : (last <= first) );
220 :
221 : typedef typename range_detail::integer_iterator_with_step<Integer> iterator_t;
222 :
223 : const std::ptrdiff_t sz = static_cast<std::ptrdiff_t>(step_size >= 0 ? step_size : -step_size);
224 : const Integer l = step_size >= 0 ? last : first;
225 : const Integer f = step_size >= 0 ? first : last;
226 : const std::ptrdiff_t num_steps = (l - f) / sz + ((l - f) % sz ? 1 : 0);
227 : BOOST_ASSERT(num_steps >= 0);
228 :
229 : return strided_integer_range<Integer>(
230 : iterator_t(first, 0, step_size),
231 : iterator_t(first, num_steps, step_size));
232 : }
233 :
234 : template<typename Integer>
235 : integer_range<Integer>
236 : irange(Integer last)
237 : {
238 : return integer_range<Integer>(static_cast<Integer>(0), last);
239 : }
240 :
241 : } // namespace boost
242 :
243 : #endif // include guard
|
