boost/boost/half_open_range.hpp

   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
   5 // for any purpose.
   6 //
   7 // Revision History:
   8 // 11 Feb 2001  Use new iterator_adaptor interface, Fixes for Borland.
   9 //              (Dave Abrahams)
  10 // 04 Feb 2001  Support for user-defined iterator categories (Dave Abrahams)
  11 // 30 Jan 2001  Initial Checkin (Dave Abrahams)
  12
  13 #ifndef BOOST_HALF_OPEN_RANGE_HPP_
  14 # define BOOST_HALF_OPEN_RANGE_HPP_
  15
  16 # include <boost/counting_iterator.hpp>
  17 # include <functional>
  18 # include <cassert>
  19 # include <boost/operators.hpp>
  20 # include <string>
  21 # include <stdexcept>
  22 # include <iterator>
  23
  24 namespace boost {
  25
  26 namespace detail {
  27
  28   // Template class choose_finish -- allows us to maintain the invariant that
  29   // start() <= finish() on half_open_range specializations that support random
  30   // access.
  31 #ifdef __MWERKS__
  32   template <class T>
  33   const T& choose_finish(const T&, const T& finish, std::input_iterator_tag)
  34   {
  35       return finish;
  36   }
  37
  38   template <class T>
  39   const T& choose_finish(const T&, const T& finish, std::output_iterator_tag)
  40   {
  41       return finish;
  42   }
  43
  44   template <class T>
  45   const T& choose_finish(const T& start, const T& finish, std::random_access_iterator_tag)
  46   {
  47       return finish < start ? start : finish;
  48   }
  49 #else
  50   template <bool is_random_access> struct finish_chooser;
  51
  52   template <>
  53   struct finish_chooser<false>
  54   {
  55       template <class T>
  56       struct rebind
  57       {
  58           static T choose(const T&, const T& finish)
  59               { return finish; }
  60       };
  61   };
  62
  63   template <>
  64   struct finish_chooser<true>
  65   {
  66       template <class T>
  67       struct rebind
  68       {
  69           static T choose(const T& start, const T& finish)
  70               { return finish < start ? start : finish; }
  71       };
  72   };
  73
  74   template <class Category, class Incrementable>
  75   struct choose_finish
  76   {
  77       static const Incrementable choose(const Incrementable& start, const Incrementable& finish)
  78       {
  79           return finish_chooser<(
  80               ::boost::is_convertible<Category*,std::random_access_iterator_tag*>::value
  81               )>::template rebind<Incrementable>::choose(start, finish);
  82       }
  83   };
  84 #endif
  85 }
  86
  87 template <class Incrementable>
  88 struct half_open_range
  89 {
  90     typedef typename counting_iterator_generator<Incrementable>::type iterator;
  91
  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;
  95
  96     typedef std::less<Incrementable> less_value;
  97     typedef typename iter_t::iterator_category category;
  98     typedef half_open_range<Incrementable> self;
  99
 100  public:
 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;
 108
 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;
 113
 114     half_open_range(Incrementable start, Incrementable finish)
 115         : m_start(start),
 116           m_finish(
 117 #ifndef __MWERKS__
 118             detail::choose_finish<category,Incrementable>::choose(start, finish)
 119 #else
 120             detail::choose_finish(start, finish, category())
 121 #endif
 122               )
 123         {}
 124
 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)
 128         : m_start(x.first),
 129           m_finish(
 130 #ifndef __MWERKS__
 131               detail::choose_finish<category,Incrementable>::choose(x.first, x.second)
 132 #else
 133             detail::choose_finish(x.first, x.second, category())
 134 #endif
 135               )
 136         {}
 137
 138     half_open_range& operator=(const self& x)
 139     {
 140         m_start = x.m_start;
 141         m_finish = x.m_finish;
 142         return *this;
 143     }
 144
 145     half_open_range& operator=(const std::pair<Incrementable,Incrementable>& x)
 146     {
 147         m_start = x.first;
 148         m_finish =
 149 #ifndef __MWERKS__
 150             detail::choose_finish<category,Incrementable>::choose(x.first, x.second);
 151 #else
 152             detail::choose_finish(x.first, x.second, category();
 153 #endif
 154     }
 155
 156     iterator begin() const { return iterator(m_start); }
 157     iterator end() const { return iterator(m_finish); }
 158
 159     Incrementable front() const { assert(!this->empty()); return m_start; }
 160     Incrementable back() const { assert(!this->empty()); return boost::prior(m_finish); }
 161
 162     Incrementable start() const { return m_start; }
 163     Incrementable finish() const { return m_finish; }
 164
 165     size_type size() const { return boost::detail::distance(begin(), end()); }
 166
 167     bool empty() const
 168     {
 169         return m_finish == m_start;
 170     }
 171
 172     void swap(half_open_range& x) {
 173         std::swap(m_start, x.m_start);
 174         std::swap(m_finish, x.m_finish);
 175     }
 176
 177  public: // functions requiring random access elements
 178
 179     // REQUIRES: x is reachable from this->front()
 180     bool contains(const value_type& x) const
 181     {
 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);
 184     }
 185
 186     bool contains(const half_open_range& x) const
 187     {
 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);
 190     }
 191
 192     bool intersects(const half_open_range& x) const
 193     {
 194         BOOST_STATIC_ASSERT((boost::is_same<category, std::random_access_iterator_tag>::value));
 195         return less_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);
 198     }
 199
 200     half_open_range& operator&=(const half_open_range& x)
 201     {
 202         BOOST_STATIC_ASSERT((boost::is_same<category, std::random_access_iterator_tag>::value));
 203
 204         if (less_value()(this->m_start, x.m_start))
 205             this->m_start = x.m_start;
 206
 207         if (less_value()(x.m_finish, this->m_finish))
 208             this->m_finish = x.m_finish;
 209
 210         if (less_value()(this->m_finish, this->m_start))
 211             this->m_start = this->m_finish;
 212
 213         return *this;
 214     }
 215
 216     half_open_range& operator|=(const half_open_range& x)
 217     {
 218         BOOST_STATIC_ASSERT((boost::is_same<category, std::random_access_iterator_tag>::value));
 219
 220         if (!x.empty())
 221         {
 222             if (this->empty())
 223             {
 224                 *this = x;
 225             }
 226             else
 227             {
 228                 if (less_value()(x.m_start, this->m_start))
 229                     this->m_start = x.m_start;
 230
 231                 if (less_value()(this->m_finish, x.m_finish))
 232                     this->m_finish = x.m_finish;
 233             }
 234         }
 235         return *this;
 236     }
 237
 238     // REQUIRES: x is reachable from this->front()
 239     const_iterator find(const value_type& x) const
 240     {
 241         BOOST_STATIC_ASSERT((boost::is_same<category, std::random_access_iterator_tag>::value));
 242
 243         return const_iterator(this->contains(x) ? x : m_finish);
 244     }
 245
 246     // REQUIRES: index >= 0 && index < size()
 247     value_type operator[](size_type index) const
 248     {
 249         assert(index >= 0 && index < size());
 250         return m_start + index;
 251     }
 252
 253     value_type at(size_type index) const
 254     {
 255         if (index < 0 || index >= size())
 256             throw std::out_of_range(std::string("half_open_range"));
 257         return m_start + index;
 258     }
 259
 260  private: // data members
 261     Incrementable m_start, m_finish;
 262 };
 263
 264 template <class Incrementable>
 265 half_open_range<Incrementable> operator|(
 266     half_open_range<Incrementable> x,
 267     const half_open_range<Incrementable>& y)
 268 {
 269     return x |= y;
 270 }
 271
 272 template <class Incrementable>
 273 half_open_range<Incrementable> operator&(
 274     half_open_range<Incrementable> x,
 275     const half_open_range<Incrementable>& y)
 276 {
 277     return x &= y;
 278 }
 279
 280 template <class Incrementable>
 281 inline bool operator==(
 282     const half_open_range<Incrementable>& x,
 283     const half_open_range<Incrementable>& y)
 284 {
 285     const bool y_empty = y.empty();
 286     return x.empty() ? y_empty : !y_empty && x.start() == y.start() && x.finish() == y.finish();
 287 }
 288
 289 template <class Incrementable>
 290 inline bool operator!=(
 291     const half_open_range<Incrementable>& x,
 292     const half_open_range<Incrementable>& y)
 293 {
 294     return !(x == y);
 295 }
 296
 297 template <class Incrementable>
 298 inline half_open_range<Incrementable>
 299 make_half_open_range(Incrementable first, Incrementable last)
 300 {
 301   return half_open_range<Incrementable>(first, last);
 302 }
 303
 304 template <class Incrementable>
 305 bool intersects(
 306     const half_open_range<Incrementable>& x,
 307     const half_open_range<Incrementable>& y)
 308 {
 309     return x.intersects(y);
 310 }
 311
 312 template <class Incrementable>
 313 bool contains(
 314     const half_open_range<Incrementable>& x,
 315     const half_open_range<Incrementable>& y)
 316 {
 317     return x.contains(y);
 318 }
 319
 320 } // namespace boost
 321
 322 #ifndef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
 323
 324 namespace std {
 325 template <class Incrementable> struct less<boost::half_open_range<Incrementable> >
 326         : binary_function<
 327             boost::half_open_range<Incrementable>,
 328             boost::half_open_range<Incrementable>,bool>
 329 {
 330     bool operator()(
 331         const boost::half_open_range<Incrementable>& x,
 332         const boost::half_open_range<Incrementable>& y) const
 333     {
 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()));
 339     }
 340 };
 341
 342 template <class Incrementable> struct less_equal<boost::half_open_range<Incrementable> >
 343         : binary_function<
 344             boost::half_open_range<Incrementable>,
 345             boost::half_open_range<Incrementable>,bool>
 346 {
 347     bool operator()(
 348         const boost::half_open_range<Incrementable>& x,
 349         const boost::half_open_range<Incrementable>& y) const
 350     {
 351         typedef boost::half_open_range<Incrementable> range;
 352         less<range> cmp;
 353         return !cmp(y,x);
 354     }
 355 };
 356 template <class Incrementable> struct greater<boost::half_open_range<Incrementable> >
 357         : binary_function<
 358             boost::half_open_range<Incrementable>,
 359             boost::half_open_range<Incrementable>,bool>
 360 {
 361     bool operator()(
 362         const boost::half_open_range<Incrementable>& x,
 363         const boost::half_open_range<Incrementable>& y) const
 364     {
 365         typedef boost::half_open_range<Incrementable> range;
 366         less<range> cmp;
 367         return cmp(y,x);
 368     }
 369 };
 370
 371 template <class Incrementable> struct greater_equal<boost::half_open_range<Incrementable> >
 372         : binary_function<
 373             boost::half_open_range<Incrementable>,
 374             boost::half_open_range<Incrementable>,bool>
 375 {
 376     bool operator()(
 377         const boost::half_open_range<Incrementable>& x,
 378         const boost::half_open_range<Incrementable>& y) const
 379     {
 380         typedef boost::half_open_range<Incrementable> range;
 381         less<range> cmp;
 382         return !cmp(x,y);
 383     }
 384 };
 385 } // namespace std
 386
 387 #else
 388
 389 namespace boost {
 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)
 394 {
 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()));
 399 }
 400
 401 template <class Incrementable>
 402 bool operator>(const half_open_range<Incrementable>& x,
 403                const half_open_range<Incrementable>& y)
 404 {
 405     return y < x;
 406 }
 407
 408 template <class Incrementable>
 409 bool operator<=(const half_open_range<Incrementable>& x,
 410                const half_open_range<Incrementable>& y)
 411 {
 412     return !(y < x);
 413 }
 414
 415 template <class Incrementable>
 416 bool operator>=(const half_open_range<Incrementable>& x,
 417                const half_open_range<Incrementable>& y)
 418 {
 419     return !(x < y);
 420 }
 421 } // namespace boost
 422
 423 #endif
 424
 425
 426 #endif // BOOST_HALF_OPEN_RANGE_HPP_