← Back to branch summary

~ubuntu-branches/ubuntu/warty/aqsis/warty

« back to all changes in this revision

Viewing changes to boost/boost/half_open_range.hpp

  • Committer: Bazaar Package Importer
  • Author(s): LaMont Jones
  • Date: 2004-08-24 07:25:04 UTC
  • Revision ID: james.westby@ubuntu.com-20040824072504-zf993vnevvisdsvb
Tags: upstream-0.9.1
Import upstream version 0.9.1

Show diffs side-by-side

added added

removed removed

Lines of Context:
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_