1 // (C) Copyright Jeremy Siek and David Abrahams 2000-2001. Permission to copy,
2 // use, modify, sell and distribute this software is granted provided this
3 // copyright notice appears in all copies. This software is provided "as is"
4 // without express or implied warranty, and with no claim as to its suitability
8 // 11 Feb 2001 Use new iterator_adaptor interface, Fixes for Borland.
10 // 04 Feb 2001 Support for user-defined iterator categories (Dave Abrahams)
11 // 30 Jan 2001 Initial Checkin (Dave Abrahams)
13 #ifndef BOOST_HALF_OPEN_RANGE_HPP_
14 # define BOOST_HALF_OPEN_RANGE_HPP_
16 # include <boost/counting_iterator.hpp>
17 # include <functional>
19 # include <boost/operators.hpp>
28 // Template class choose_finish -- allows us to maintain the invariant that
29 // start() <= finish() on half_open_range specializations that support random
33 const T& choose_finish(const T&, const T& finish, std::input_iterator_tag)
39 const T& choose_finish(const T&, const T& finish, std::output_iterator_tag)
45 const T& choose_finish(const T& start, const T& finish, std::random_access_iterator_tag)
47 return finish < start ? start : finish;
50 template <bool is_random_access> struct finish_chooser;
53 struct finish_chooser<false>
58 static T choose(const T&, const T& finish)
64 struct finish_chooser<true>
69 static T choose(const T& start, const T& finish)
70 { return finish < start ? start : finish; }
74 template <class Category, class Incrementable>
77 static const Incrementable choose(const Incrementable& start, const Incrementable& finish)
79 return finish_chooser<(
80 ::boost::is_convertible<Category*,std::random_access_iterator_tag*>::value
81 )>::template rebind<Incrementable>::choose(start, finish);
87 template <class Incrementable>
88 struct half_open_range
90 typedef typename counting_iterator_generator<Incrementable>::type iterator;
92 private: // utility type definitions
93 // Using iter_t prevents compiler confusion with boost::iterator
94 typedef typename counting_iterator_generator<Incrementable>::type iter_t;
96 typedef std::less<Incrementable> less_value;
97 typedef typename iter_t::iterator_category category;
98 typedef half_open_range<Incrementable> self;
101 typedef iter_t const_iterator;
102 typedef typename iterator::value_type value_type;
103 typedef typename iterator::difference_type difference_type;
104 typedef typename iterator::reference reference;
105 typedef typename iterator::reference const_reference;
106 typedef typename iterator::pointer pointer;
107 typedef typename iterator::pointer const_pointer;
109 // It would be nice to select an unsigned type, but this is appropriate
110 // since the library makes an attempt to select a difference_type which can
111 // hold the difference between any two iterators.
112 typedef typename iterator::difference_type size_type;
114 half_open_range(Incrementable start, Incrementable finish)
118 detail::choose_finish<category,Incrementable>::choose(start, finish)
120 detail::choose_finish(start, finish, category())
125 // Implicit conversion from std::pair<Incrementable,Incrementable> allows us
126 // to accept the results of std::equal_range(), for example.
127 half_open_range(const std::pair<Incrementable,Incrementable>& x)
131 detail::choose_finish<category,Incrementable>::choose(x.first, x.second)
133 detail::choose_finish(x.first, x.second, category())
138 half_open_range& operator=(const self& x)
141 m_finish = x.m_finish;
145 half_open_range& operator=(const std::pair<Incrementable,Incrementable>& x)
150 detail::choose_finish<category,Incrementable>::choose(x.first, x.second);
152 detail::choose_finish(x.first, x.second, category();
156 iterator begin() const { return iterator(m_start); }
157 iterator end() const { return iterator(m_finish); }
159 Incrementable front() const { assert(!this->empty()); return m_start; }
160 Incrementable back() const { assert(!this->empty()); return boost::prior(m_finish); }
162 Incrementable start() const { return m_start; }
163 Incrementable finish() const { return m_finish; }
165 size_type size() const { return boost::detail::distance(begin(), end()); }
169 return m_finish == m_start;
172 void swap(half_open_range& x) {
173 std::swap(m_start, x.m_start);
174 std::swap(m_finish, x.m_finish);
177 public: // functions requiring random access elements
179 // REQUIRES: x is reachable from this->front()
180 bool contains(const value_type& x) const
182 BOOST_STATIC_ASSERT((boost::is_same<category, std::random_access_iterator_tag>::value));
183 return !less_value()(x, m_start) && less_value()(x, m_finish);
186 bool contains(const half_open_range& x) const
188 BOOST_STATIC_ASSERT((boost::is_same<category, std::random_access_iterator_tag>::value));
189 return x.empty() || !less_value()(x.m_start, m_start) && !less_value()(m_finish, x.m_finish);
192 bool intersects(const half_open_range& x) const
194 BOOST_STATIC_ASSERT((boost::is_same<category, std::random_access_iterator_tag>::value));
196 less_value()(this->m_start, x.m_start) ? x.m_start : this->m_start,
197 less_value()(this->m_finish, x.m_finish) ? this->m_finish : x.m_finish);
200 half_open_range& operator&=(const half_open_range& x)
202 BOOST_STATIC_ASSERT((boost::is_same<category, std::random_access_iterator_tag>::value));
204 if (less_value()(this->m_start, x.m_start))
205 this->m_start = x.m_start;
207 if (less_value()(x.m_finish, this->m_finish))
208 this->m_finish = x.m_finish;
210 if (less_value()(this->m_finish, this->m_start))
211 this->m_start = this->m_finish;
216 half_open_range& operator|=(const half_open_range& x)
218 BOOST_STATIC_ASSERT((boost::is_same<category, std::random_access_iterator_tag>::value));
228 if (less_value()(x.m_start, this->m_start))
229 this->m_start = x.m_start;
231 if (less_value()(this->m_finish, x.m_finish))
232 this->m_finish = x.m_finish;
238 // REQUIRES: x is reachable from this->front()
239 const_iterator find(const value_type& x) const
241 BOOST_STATIC_ASSERT((boost::is_same<category, std::random_access_iterator_tag>::value));
243 return const_iterator(this->contains(x) ? x : m_finish);
246 // REQUIRES: index >= 0 && index < size()
247 value_type operator[](size_type index) const
249 assert(index >= 0 && index < size());
250 return m_start + index;
253 value_type at(size_type index) const
255 if (index < 0 || index >= size())
256 throw std::out_of_range(std::string("half_open_range"));
257 return m_start + index;
260 private: // data members
261 Incrementable m_start, m_finish;
264 template <class Incrementable>
265 half_open_range<Incrementable> operator|(
266 half_open_range<Incrementable> x,
267 const half_open_range<Incrementable>& y)
272 template <class Incrementable>
273 half_open_range<Incrementable> operator&(
274 half_open_range<Incrementable> x,
275 const half_open_range<Incrementable>& y)
280 template <class Incrementable>
281 inline bool operator==(
282 const half_open_range<Incrementable>& x,
283 const half_open_range<Incrementable>& y)
285 const bool y_empty = y.empty();
286 return x.empty() ? y_empty : !y_empty && x.start() == y.start() && x.finish() == y.finish();
289 template <class Incrementable>
290 inline bool operator!=(
291 const half_open_range<Incrementable>& x,
292 const half_open_range<Incrementable>& y)
297 template <class Incrementable>
298 inline half_open_range<Incrementable>
299 make_half_open_range(Incrementable first, Incrementable last)
301 return half_open_range<Incrementable>(first, last);
304 template <class Incrementable>
306 const half_open_range<Incrementable>& x,
307 const half_open_range<Incrementable>& y)
309 return x.intersects(y);
312 template <class Incrementable>
314 const half_open_range<Incrementable>& x,
315 const half_open_range<Incrementable>& y)
317 return x.contains(y);
322 #ifndef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
325 template <class Incrementable> struct less<boost::half_open_range<Incrementable> >
327 boost::half_open_range<Incrementable>,
328 boost::half_open_range<Incrementable>,bool>
331 const boost::half_open_range<Incrementable>& x,
332 const boost::half_open_range<Incrementable>& y) const
334 less<Incrementable> cmp;
335 return !y.empty() && (
336 cmp(x.start(), y.start())
337 || !cmp(y.start(), x.start())
338 && cmp(x.finish(), y.finish()));
342 template <class Incrementable> struct less_equal<boost::half_open_range<Incrementable> >
344 boost::half_open_range<Incrementable>,
345 boost::half_open_range<Incrementable>,bool>
348 const boost::half_open_range<Incrementable>& x,
349 const boost::half_open_range<Incrementable>& y) const
351 typedef boost::half_open_range<Incrementable> range;
356 template <class Incrementable> struct greater<boost::half_open_range<Incrementable> >
358 boost::half_open_range<Incrementable>,
359 boost::half_open_range<Incrementable>,bool>
362 const boost::half_open_range<Incrementable>& x,
363 const boost::half_open_range<Incrementable>& y) const
365 typedef boost::half_open_range<Incrementable> range;
371 template <class Incrementable> struct greater_equal<boost::half_open_range<Incrementable> >
373 boost::half_open_range<Incrementable>,
374 boost::half_open_range<Incrementable>,bool>
377 const boost::half_open_range<Incrementable>& x,
378 const boost::half_open_range<Incrementable>& y) const
380 typedef boost::half_open_range<Incrementable> range;
390 // Can't partially specialize std::less et al, so we must provide the operators
391 template <class Incrementable>
392 bool operator<(const half_open_range<Incrementable>& x,
393 const half_open_range<Incrementable>& y)
395 return !y.empty() && (
396 x.empty() || std::less<Incrementable>()(x.start(), y.start())
397 || !std::less<Incrementable>()(y.start(), x.start())
398 && std::less<Incrementable>()(x.finish(), y.finish()));
401 template <class Incrementable>
402 bool operator>(const half_open_range<Incrementable>& x,
403 const half_open_range<Incrementable>& y)
408 template <class Incrementable>
409 bool operator<=(const half_open_range<Incrementable>& x,
410 const half_open_range<Incrementable>& y)
415 template <class Incrementable>
416 bool operator>=(const half_open_range<Incrementable>& x,
417 const half_open_range<Incrementable>& y)
426 #endif // BOOST_HALF_OPEN_RANGE_HPP_