source: NonGTP/Boost/boost/range/iterator_range.hpp @ 857

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