← Back to branch summary

~ubuntu-branches/ubuntu/wily/bombono-dvd/wily

« back to all changes in this revision

Viewing changes to libs/boost-lib/boost/range/iterator_range_core.hpp

  • Committer: Bazaar Package Importer
  • Author(s): Alessio Treglia
  • Date: 2010-11-04 11:46:25 UTC
  • mto: This revision was merged to the branch mainline in revision 8.
  • Revision ID: james.westby@ubuntu.com-20101104114625-8xfdhvhpsm51i0nu
Tags: upstream-0.8.0
Import upstream version 0.8.0

Show diffs side-by-side

added added

removed removed

Lines of Context:
libs/boost-lib/boost/range/iterator_range_core.hpp
 
1
// Boost.Range library
 
2
//
 
3
//  Copyright Neil Groves & Thorsten Ottosen & Pavol Droba 2003-2004.
 
4
//  Use, modification and distribution is subject to the Boost Software
 
5
//  License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
 
6
//  http://www.boost.org/LICENSE_1_0.txt)
 
7
//
 
8
// For more information, see http://www.boost.org/libs/range/
 
9
//
 
10
#ifndef BOOST_RANGE_ITERATOR_RANGE_CORE_HPP_INCLUDED
 
11
#define BOOST_RANGE_ITERATOR_RANGE_CORE_HPP_INCLUDED
 
12
 
 
13
#include <boost/config.hpp> // Define __STL_CONFIG_H, if appropriate.
 
14
#include <boost/detail/workaround.hpp>
 
15
 
 
16
#if BOOST_WORKAROUND(BOOST_MSVC, BOOST_TESTED_AT(1500))
 
17
    #pragma warning( push )
 
18
    #pragma warning( disable : 4996 )
 
19
#endif
 
20
 
 
21
#include <boost/assert.hpp>
 
22
#include <boost/iterator/iterator_traits.hpp>
 
23
#include <boost/iterator/iterator_facade.hpp>
 
24
#include <boost/type_traits/is_abstract.hpp>
 
25
#include <boost/type_traits/is_pointer.hpp>
 
26
#include <boost/range/functions.hpp>
 
27
#include <boost/range/iterator.hpp>
 
28
#include <boost/range/difference_type.hpp>
 
29
#include <boost/range/algorithm/equal.hpp>
 
30
#include <boost/utility/enable_if.hpp>
 
31
#include <iterator>
 
32
#include <algorithm>
 
33
#include <cstddef>
 
34
 
 
35
/*! \file
 
36
    Defines the \c iterator_class and related functions.
 
37
    \c iterator_range is a simple wrapper of iterator pair idiom. It provides
 
38
    a rich subset of Container interface.
 
39
*/
 
40
 
 
41
 
 
42
namespace boost
 
43
{
 
44
    namespace iterator_range_detail
 
45
    {
 
46
        //
 
47
        // The functions adl_begin and adl_end are implemented in a separate
 
48
        // class for gcc-2.9x
 
49
        //
 
50
        template<class IteratorT>
 
51
        struct iterator_range_impl {
 
52
            template< class ForwardRange >
 
53
            static IteratorT adl_begin( ForwardRange& r )
 
54
            {
 
55
                return IteratorT( boost::begin( r ) );
 
56
            }
 
57
 
 
58
            template< class ForwardRange >
 
59
            static IteratorT adl_end( ForwardRange& r )
 
60
            {
 
61
                return IteratorT( boost::end( r ) );
 
62
            }
 
63
        };
 
64
 
 
65
        template< class Left, class Right >
 
66
        inline bool less_than( const Left& l, const Right& r )
 
67
        {
 
68
            return std::lexicographical_compare( boost::begin(l),
 
69
                                                 boost::end(l),
 
70
                                                 boost::begin(r),
 
71
                                                 boost::end(r) );
 
72
        }
 
73
 
 
74
        // This version is maintained since it is used in other boost libraries
 
75
        // such as Boost.Assign
 
76
        template< class Left, class Right >
 
77
        inline bool equal(const Left& l, const Right& r)
 
78
        {
 
79
            return boost::equal(l, r);
 
80
        }
 
81
 
 
82
        struct range_tag { };
 
83
        struct const_range_tag { };
 
84
 
 
85
    }
 
86
 
 
87
//  iterator range template class -----------------------------------------//
 
88
 
 
89
        //! iterator_range class
 
90
        /*!
 
91
            An \c iterator_range delimits a range in a sequence by beginning and ending iterators.
 
92
            An iterator_range can be passed to an algorithm which requires a sequence as an input.
 
93
            For example, the \c toupper() function may be used most frequently on strings,
 
94
            but can also be used on iterator_ranges:
 
95
 
 
96
            \code
 
97
                boost::tolower( find( s, "UPPERCASE STRING" ) );
 
98
            \endcode
 
99
 
 
100
            Many algorithms working with sequences take a pair of iterators,
 
101
            delimiting a working range, as an arguments. The \c iterator_range class is an
 
102
            encapsulation of a range identified by a pair of iterators.
 
103
            It provides a collection interface,
 
104
            so it is possible to pass an instance to an algorithm requiring a collection as an input.
 
105
        */
 
106
        template<class IteratorT>
 
107
        class iterator_range
 
108
        {
 
109
        protected: // Used by sub_range
 
110
            //! implementation class
 
111
            typedef iterator_range_detail::iterator_range_impl<IteratorT> impl;
 
112
        public:
 
113
 
 
114
            //! this type
 
115
            typedef iterator_range<IteratorT> type;
 
116
            //BOOST_BROKEN_COMPILER_TYPE_TRAITS_SPECIALIZATION(value_type);
 
117
 
 
118
            //! Encapsulated value type
 
119
            typedef BOOST_DEDUCED_TYPENAME
 
120
                iterator_value<IteratorT>::type value_type;
 
121
 
 
122
            //! Difference type
 
123
            typedef BOOST_DEDUCED_TYPENAME
 
124
                iterator_difference<IteratorT>::type difference_type;
 
125
 
 
126
            //! Size type
 
127
            typedef std::size_t size_type; // note: must be unsigned
 
128
 
 
129
            //! This type
 
130
            typedef iterator_range<IteratorT> this_type;
 
131
 
 
132
            //! Reference type
 
133
            //
 
134
            // Needed because value-type is the same for
 
135
            // const and non-const iterators
 
136
            //
 
137
            typedef BOOST_DEDUCED_TYPENAME
 
138
                iterator_reference<IteratorT>::type reference;
 
139
 
 
140
            //! const_iterator type
 
141
            /*!
 
142
                There is no distinction between const_iterator and iterator.
 
143
                These typedefs are provides to fulfill container interface
 
144
            */
 
145
            typedef IteratorT const_iterator;
 
146
            //! iterator type
 
147
            typedef IteratorT iterator;
 
148
 
 
149
        private: // for return value of operator()()
 
150
            typedef BOOST_DEDUCED_TYPENAME
 
151
                boost::mpl::if_< boost::is_abstract<value_type>,
 
152
                                 reference, value_type >::type abstract_value_type;
 
153
 
 
154
        public:
 
155
            iterator_range() : m_Begin( iterator() ), m_End( iterator() )
 
156
            { }
 
157
 
 
158
            //! Constructor from a pair of iterators
 
159
            template< class Iterator >
 
160
            iterator_range( Iterator Begin, Iterator End ) :
 
161
                m_Begin(Begin), m_End(End)
 
162
            {}
 
163
 
 
164
            //! Constructor from a Range
 
165
            template< class Range >
 
166
            iterator_range( const Range& r ) :
 
167
                m_Begin( impl::adl_begin( r ) ), m_End( impl::adl_end( r ) )
 
168
            {}
 
169
 
 
170
            //! Constructor from a Range
 
171
            template< class Range >
 
172
            iterator_range( Range& r ) :
 
173
                m_Begin( impl::adl_begin( r ) ), m_End( impl::adl_end( r ) )
 
174
            {}
 
175
 
 
176
            //! Constructor from a Range
 
177
            template< class Range >
 
178
            iterator_range( const Range& r, iterator_range_detail::const_range_tag ) :
 
179
                m_Begin( impl::adl_begin( r ) ), m_End( impl::adl_end( r ) )
 
180
            {}
 
181
 
 
182
            //! Constructor from a Range
 
183
            template< class Range >
 
184
            iterator_range( Range& r, iterator_range_detail::range_tag ) :
 
185
                m_Begin( impl::adl_begin( r ) ), m_End( impl::adl_end( r ) )
 
186
            {}
 
187
 
 
188
            #if !BOOST_WORKAROUND(BOOST_MSVC, < 1300)
 
189
            this_type& operator=( const this_type& r )
 
190
            {
 
191
                m_Begin  = r.begin();
 
192
                m_End    = r.end();
 
193
                return *this;
 
194
            }
 
195
            #endif
 
196
 
 
197
            template< class Iterator >
 
198
            iterator_range& operator=( const iterator_range<Iterator>& r )
 
199
            {
 
200
                m_Begin  = r.begin();
 
201
                m_End    = r.end();
 
202
                return *this;
 
203
            }
 
204
 
 
205
            template< class ForwardRange >
 
206
            iterator_range& operator=( ForwardRange& r )
 
207
            {
 
208
                m_Begin  = impl::adl_begin( r );
 
209
                m_End    = impl::adl_end( r );
 
210
                return *this;
 
211
            }
 
212
 
 
213
            template< class ForwardRange >
 
214
            iterator_range& operator=( const ForwardRange& r )
 
215
            {
 
216
                m_Begin  = impl::adl_begin( r );
 
217
                m_End    = impl::adl_end( r );
 
218
                return *this;
 
219
            }
 
220
 
 
221
            IteratorT begin() const
 
222
            {
 
223
                return m_Begin;
 
224
            }
 
225
 
 
226
            IteratorT end() const
 
227
            {
 
228
                return m_End;
 
229
            }
 
230
 
 
231
            difference_type size() const
 
232
            {
 
233
                return m_End - m_Begin;
 
234
            }
 
235
 
 
236
            bool empty() const
 
237
            {
 
238
                return m_Begin == m_End;
 
239
            }
 
240
 
 
241
#if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x564))
 
242
            operator bool() const
 
243
            {
 
244
                return !empty();
 
245
            }
 
246
#else
 
247
            typedef iterator (iterator_range::*unspecified_bool_type) () const;
 
248
            operator unspecified_bool_type() const
 
249
            {
 
250
                return empty() ? 0: &iterator_range::end;
 
251
            }
 
252
#endif
 
253
 
 
254
            bool equal( const iterator_range& r ) const
 
255
            {
 
256
                return m_Begin == r.m_Begin && m_End == r.m_End;
 
257
            }
 
258
 
 
259
 
 
260
#ifdef BOOST_NO_FUNCTION_TEMPLATE_ORDERING
 
261
 
 
262
            bool operator==( const iterator_range& r ) const
 
263
            {
 
264
                return boost::equal( *this, r );
 
265
            }
 
266
 
 
267
            bool operator!=( const iterator_range& r ) const
 
268
            {
 
269
                return !operator==(r);
 
270
            }
 
271
 
 
272
           bool operator<( const iterator_range& r ) const
 
273
           {
 
274
               return iterator_range_detail::less_than( *this, r );
 
275
           }
 
276
 
 
277
#endif
 
278
 
 
279
        public: // convenience
 
280
           reference front() const
 
281
           {
 
282
               BOOST_ASSERT( !empty() );
 
283
               return *m_Begin;
 
284
           }
 
285
 
 
286
           reference back() const
 
287
           {
 
288
               BOOST_ASSERT( !empty() );
 
289
               IteratorT last( m_End );
 
290
               return *--last;
 
291
           }
 
292
 
 
293
           reference operator[]( difference_type at ) const
 
294
           {
 
295
               BOOST_ASSERT( at >= 0 && at < size() );
 
296
               return m_Begin[at];
 
297
           }
 
298
 
 
299
           //
 
300
           // When storing transform iterators, operator[]()
 
301
           // fails because it returns by reference. Therefore
 
302
           // operator()() is provided for these cases.
 
303
           //
 
304
           abstract_value_type operator()( difference_type at ) const
 
305
           {
 
306
               BOOST_ASSERT( at >= 0 && at < size() );
 
307
               return m_Begin[at];
 
308
           }
 
309
 
 
310
           iterator_range& advance_begin( difference_type n )
 
311
           {
 
312
               std::advance( m_Begin, n );
 
313
               return *this;
 
314
           }
 
315
 
 
316
           iterator_range& advance_end( difference_type n )
 
317
           {
 
318
               std::advance( m_End, n );
 
319
               return *this;
 
320
           }
 
321
 
 
322
        private:
 
323
            // begin and end iterators
 
324
            IteratorT m_Begin;
 
325
            IteratorT m_End;
 
326
 
 
327
        protected:
 
328
            //
 
329
            // Allow subclasses an easy way to access the
 
330
            // base type
 
331
            //
 
332
            typedef iterator_range iterator_range_;
 
333
        };
 
334
 
 
335
//  iterator range free-standing operators ---------------------------//
 
336
 
 
337
        /////////////////////////////////////////////////////////////////////
 
338
        // comparison operators
 
339
        /////////////////////////////////////////////////////////////////////
 
340
 
 
341
        template< class IteratorT, class ForwardRange >
 
342
        inline bool operator==( const ForwardRange& l,
 
343
                                const iterator_range<IteratorT>& r )
 
344
        {
 
345
            return boost::equal( l, r );
 
346
        }
 
347
 
 
348
        template< class IteratorT, class ForwardRange >
 
349
        inline bool operator!=( const ForwardRange& l,
 
350
                                const iterator_range<IteratorT>& r )
 
351
        {
 
352
            return !boost::equal( l, r );
 
353
        }
 
354
 
 
355
        template< class IteratorT, class ForwardRange >
 
356
        inline bool operator<( const ForwardRange& l,
 
357
                               const iterator_range<IteratorT>& r )
 
358
        {
 
359
            return iterator_range_detail::less_than( l, r );
 
360
        }
 
361
 
 
362
#ifdef BOOST_NO_FUNCTION_TEMPLATE_ORDERING
 
363
#else
 
364
        template< class Iterator1T, class Iterator2T >
 
365
        inline bool operator==( const iterator_range<Iterator1T>& l,
 
366
                                const iterator_range<Iterator2T>& r )
 
367
        {
 
368
            return boost::equal( l, r );
 
369
        }
 
370
 
 
371
        template< class IteratorT, class ForwardRange >
 
372
        inline bool operator==( const iterator_range<IteratorT>& l,
 
373
                                const ForwardRange& r )
 
374
        {
 
375
            return boost::equal( l, r );
 
376
        }
 
377
 
 
378
 
 
379
        template< class Iterator1T, class Iterator2T >
 
380
        inline bool operator!=( const iterator_range<Iterator1T>& l,
 
381
                                const iterator_range<Iterator2T>& r )
 
382
        {
 
383
            return !boost::equal( l, r );
 
384
        }
 
385
 
 
386
        template< class IteratorT, class ForwardRange >
 
387
        inline bool operator!=( const iterator_range<IteratorT>& l,
 
388
                                const ForwardRange& r )
 
389
        {
 
390
            return !boost::equal( l, r );
 
391
        }
 
392
 
 
393
 
 
394
        template< class Iterator1T, class Iterator2T >
 
395
        inline bool operator<( const iterator_range<Iterator1T>& l,
 
396
                               const iterator_range<Iterator2T>& r )
 
397
        {
 
398
            return iterator_range_detail::less_than( l, r );
 
399
        }
 
400
 
 
401
        template< class IteratorT, class ForwardRange >
 
402
        inline bool operator<( const iterator_range<IteratorT>& l,
 
403
                               const ForwardRange& r )
 
404
        {
 
405
            return iterator_range_detail::less_than( l, r );
 
406
        }
 
407
 
 
408
#endif // BOOST_NO_FUNCTION_TEMPLATE_ORDERING
 
409
 
 
410
//  iterator range utilities -----------------------------------------//
 
411
 
 
412
        //! iterator_range construct helper
 
413
        /*!
 
414
            Construct an \c iterator_range from a pair of iterators
 
415
 
 
416
            \param Begin A begin iterator
 
417
            \param End An end iterator
 
418
            \return iterator_range object
 
419
        */
 
420
        template< typename IteratorT >
 
421
        inline iterator_range< IteratorT >
 
422
        make_iterator_range( IteratorT Begin, IteratorT End )
 
423
        {
 
424
            return iterator_range<IteratorT>( Begin, End );
 
425
        }
 
426
 
 
427
#ifdef BOOST_NO_FUNCTION_TEMPLATE_ORDERING
 
428
 
 
429
        template< typename Range >
 
430
        inline iterator_range< BOOST_DEDUCED_TYPENAME range_iterator<Range>::type >
 
431
        make_iterator_range( Range& r )
 
432
        {
 
433
            return iterator_range< BOOST_DEDUCED_TYPENAME range_iterator<Range>::type >
 
434
                ( boost::begin( r ), boost::end( r ) );
 
435
        }
 
436
 
 
437
#else
 
438
        //! iterator_range construct helper
 
439
        /*!
 
440
            Construct an \c iterator_range from a \c Range containing the begin
 
441
            and end iterators.
 
442
        */
 
443
        template< class ForwardRange >
 
444
        inline iterator_range< BOOST_DEDUCED_TYPENAME range_iterator<ForwardRange>::type >
 
445
        make_iterator_range( ForwardRange& r )
 
446
        {
 
447
           return iterator_range< BOOST_DEDUCED_TYPENAME range_iterator<ForwardRange>::type >
 
448
                ( r, iterator_range_detail::range_tag() );
 
449
        }
 
450
 
 
451
        template< class ForwardRange >
 
452
        inline iterator_range< BOOST_DEDUCED_TYPENAME range_iterator<const ForwardRange>::type >
 
453
        make_iterator_range( const ForwardRange& r )
 
454
        {
 
455
           return iterator_range< BOOST_DEDUCED_TYPENAME range_iterator<const ForwardRange>::type >
 
456
                ( r, iterator_range_detail::const_range_tag() );
 
457
        }
 
458
 
 
459
#endif // BOOST_NO_FUNCTION_TEMPLATE_ORDERING
 
460
 
 
461
        namespace iterator_range_detail
 
462
        {
 
463
            template< class Range >
 
464
            inline iterator_range< BOOST_DEDUCED_TYPENAME range_iterator<Range>::type >
 
465
            make_range_impl( Range& r,
 
466
                             BOOST_DEDUCED_TYPENAME range_difference<Range>::type advance_begin,
 
467
                             BOOST_DEDUCED_TYPENAME range_difference<Range>::type advance_end )
 
468
            {
 
469
                //
 
470
                // Not worth the effort
 
471
                //
 
472
                //if( advance_begin == 0 && advance_end == 0 )
 
473
                //    return make_iterator_range( r );
 
474
                //
 
475
 
 
476
                BOOST_DEDUCED_TYPENAME range_iterator<Range>::type
 
477
                    new_begin = boost::begin( r ),
 
478
                    new_end   = boost::end( r );
 
479
                std::advance( new_begin, advance_begin );
 
480
                std::advance( new_end, advance_end );
 
481
                return make_iterator_range( new_begin, new_end );
 
482
            }
 
483
        }
 
484
 
 
485
#ifdef BOOST_NO_FUNCTION_TEMPLATE_ORDERING
 
486
 
 
487
        template< class Range >
 
488
        inline iterator_range< BOOST_DEDUCED_TYPENAME range_iterator<Range>::type >
 
489
        make_iterator_range( Range& r,
 
490
                    BOOST_DEDUCED_TYPENAME range_difference<Range>::type advance_begin,
 
491
                    BOOST_DEDUCED_TYPENAME range_difference<Range>::type advance_end )
 
492
        {
 
493
            //BOOST_ASSERT( advance_begin - advance_end <= size(r) && "creating invalid range" );
 
494
            return iterator_range_detail::make_range_impl( r, advance_begin, advance_end );
 
495
        }
 
496
 
 
497
#else
 
498
 
 
499
        template< class Range >
 
500
        inline iterator_range< BOOST_DEDUCED_TYPENAME range_iterator<Range>::type >
 
501
        make_iterator_range( Range& r,
 
502
                    BOOST_DEDUCED_TYPENAME range_difference<Range>::type advance_begin,
 
503
                    BOOST_DEDUCED_TYPENAME range_difference<Range>::type advance_end )
 
504
        {
 
505
            //BOOST_ASSERT( advance_begin - advance_end <= size(r) && "creating invalid range" );
 
506
            return iterator_range_detail::make_range_impl( r, advance_begin, advance_end );
 
507
        }
 
508
 
 
509
        template< class Range >
 
510
        inline iterator_range< BOOST_DEDUCED_TYPENAME range_iterator<const Range>::type >
 
511
        make_iterator_range( const Range& r,
 
512
                    BOOST_DEDUCED_TYPENAME range_difference<Range>::type advance_begin,
 
513
                    BOOST_DEDUCED_TYPENAME range_difference<Range>::type advance_end )
 
514
        {
 
515
            //BOOST_ASSERT( advance_begin - advance_end <= size(r) && "creating invalid range" );
 
516
            return iterator_range_detail::make_range_impl( r, advance_begin, advance_end );
 
517
        }
 
518
 
 
519
#endif // BOOST_NO_FUNCTION_TEMPLATE_ORDERING
 
520
 
 
521
        //! copy a range into a sequence
 
522
        /*!
 
523
            Construct a new sequence of the specified type from the elements
 
524
            in the given range
 
525
 
 
526
            \param Range An input range
 
527
            \return New sequence
 
528
        */
 
529
        template< typename SeqT, typename Range >
 
530
        inline SeqT copy_range( const Range& r )
 
531
        {
 
532
            return SeqT( boost::begin( r ), boost::end( r ) );
 
533
        }
 
534
 
 
535
} // namespace 'boost'
 
536
 
 
537
#if BOOST_WORKAROUND(BOOST_MSVC, BOOST_TESTED_AT(1500))
 
538
    #pragma warning( pop )
 
539
#endif
 
540
 
 
541
#endif
 
542