1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/epoc32/include/stdapis/boost/range/iterator_range.hpp Wed Mar 31 12:33:34 2010 +0100
1.3 @@ -0,0 +1,608 @@
1.4 +// Boost.Range library
1.5 +//
1.6 +// Copyright Thorsten Ottosen & Pavol Droba 2003-2004. Use, modification and
1.7 +// distribution is subject to the Boost Software License, Version
1.8 +// 1.0. (See accompanying file LICENSE_1_0.txt or copy at
1.9 +// http://www.boost.org/LICENSE_1_0.txt)
1.10 +//
1.11 +// For more information, see http://www.boost.org/libs/range/
1.12 +//
1.13 +
1.14 +#ifndef BOOST_RANGE_ITERATOR_RANGE_HPP
1.15 +#define BOOST_RANGE_ITERATOR_RANGE_HPP
1.16 +
1.17 +// From boost/dynamic_bitset.hpp; thanks to Matthias Troyer for Cray X1 patch.
1.18 +#include <boost/config.hpp> // Define __STL_CONFIG_H, if appropriate.
1.19 +#ifndef BOOST_OLD_IOSTREAMS
1.20 +# if defined(__STL_CONFIG_H) && \
1.21 + !defined (__STL_USE_NEW_IOSTREAMS) && !defined(__crayx1) \
1.22 + /**/
1.23 +# define BOOST_OLD_IOSTREAMS
1.24 +# endif
1.25 +#endif // #ifndef BOOST_OLD_IOSTREAMS
1.26 +
1.27 +#include <boost/detail/workaround.hpp>
1.28 +#include <boost/range/functions.hpp>
1.29 +#include <boost/range/result_iterator.hpp>
1.30 +#include <boost/range/difference_type.hpp>
1.31 +#include <boost/iterator/iterator_traits.hpp>
1.32 +#include <boost/assert.hpp>
1.33 +#include <iterator>
1.34 +#include <algorithm>
1.35 +#ifndef BOOST_OLD_IOSTREAMS
1.36 +# include <ostream>
1.37 +#else
1.38 +# include <ostream.h>
1.39 +#endif
1.40 +#include <cstddef>
1.41 +
1.42 +
1.43 +/*! \file
1.44 + Defines the \c iterator_class and related functions.
1.45 + \c iterator_range is a simple wrapper of iterator pair idiom. It provides
1.46 + a rich subset of Container interface.
1.47 +*/
1.48 +
1.49 +
1.50 +namespace boost
1.51 +{
1.52 + namespace iterator_range_detail
1.53 + {
1.54 + //
1.55 + // The functions adl_begin and adl_end are implemented in a separate
1.56 + // class for gcc-2.9x
1.57 + //
1.58 + template<typename IteratorT>
1.59 + struct iterator_range_impl {
1.60 + template< class ForwardRange >
1.61 + static IteratorT adl_begin( ForwardRange& r )
1.62 + {
1.63 + return IteratorT( boost::begin( r ) );
1.64 + }
1.65 +
1.66 + template< class ForwardRange >
1.67 + static IteratorT adl_end( ForwardRange& r )
1.68 + {
1.69 + return IteratorT( boost::end( r ) );
1.70 + }
1.71 + };
1.72 +
1.73 + template< class Left, class Right >
1.74 + inline bool equal( const Left& l, const Right& r )
1.75 + {
1.76 + typedef BOOST_DEDUCED_TYPENAME boost::range_size<Left>::type sz_type;
1.77 +
1.78 + sz_type l_size = boost::size( l ),
1.79 + r_size = boost::size( r );
1.80 +
1.81 + if( l_size != r_size )
1.82 + return false;
1.83 +
1.84 + return std::equal( boost::begin(l), boost::end(l),
1.85 + boost::begin(r) );
1.86 + }
1.87 +
1.88 + template< class Left, class Right >
1.89 + inline bool less_than( const Left& l, const Right& r )
1.90 + {
1.91 + return std::lexicographical_compare( boost::begin(l),
1.92 + boost::end(l),
1.93 + boost::begin(r),
1.94 + boost::end(r) );
1.95 + }
1.96 +
1.97 + struct range_tag { };
1.98 + struct const_range_tag { };
1.99 +
1.100 + }
1.101 +
1.102 +// iterator range template class -----------------------------------------//
1.103 +
1.104 + //! iterator_range class
1.105 + /*!
1.106 + An \c iterator_range delimits a range in a sequence by beginning and ending iterators.
1.107 + An iterator_range can be passed to an algorithm which requires a sequence as an input.
1.108 + For example, the \c toupper() function may be used most frequently on strings,
1.109 + but can also be used on iterator_ranges:
1.110 +
1.111 + \code
1.112 + boost::tolower( find( s, "UPPERCASE STRING" ) );
1.113 + \endcode
1.114 +
1.115 + Many algorithms working with sequences take a pair of iterators,
1.116 + delimiting a working range, as an arguments. The \c iterator_range class is an
1.117 + encapsulation of a range identified by a pair of iterators.
1.118 + It provides a collection interface,
1.119 + so it is possible to pass an instance to an algorithm requiring a collection as an input.
1.120 + */
1.121 + template<typename IteratorT>
1.122 + class iterator_range
1.123 + {
1.124 + protected: // Used by sub_range
1.125 + //! implementation class
1.126 + typedef iterator_range_detail::iterator_range_impl<IteratorT> impl;
1.127 + public:
1.128 +
1.129 + //! this type
1.130 + typedef iterator_range<IteratorT> type;
1.131 + //BOOST_BROKEN_COMPILER_TYPE_TRAITS_SPECIALIZATION(value_type);
1.132 +
1.133 + //! Encapsulated value type
1.134 + typedef BOOST_DEDUCED_TYPENAME
1.135 + iterator_value<IteratorT>::type value_type;
1.136 +
1.137 + //! Difference type
1.138 + typedef BOOST_DEDUCED_TYPENAME
1.139 + iterator_difference<IteratorT>::type difference_type;
1.140 +
1.141 + //! Size type
1.142 + typedef std::size_t size_type; // note: must be unsigned
1.143 +
1.144 + //! This type
1.145 + typedef iterator_range<IteratorT> this_type;
1.146 +
1.147 + //! Refence type
1.148 + //
1.149 + // Needed because value-type is the same for
1.150 + // const and non-const iterators
1.151 + //
1.152 + typedef BOOST_DEDUCED_TYPENAME
1.153 + iterator_reference<IteratorT>::type reference;
1.154 +
1.155 + //! const_iterator type
1.156 + /*!
1.157 + There is no distinction between const_iterator and iterator.
1.158 + These typedefs are provides to fulfill container interface
1.159 + */
1.160 + typedef IteratorT const_iterator;
1.161 + //! iterator type
1.162 + typedef IteratorT iterator;
1.163 +
1.164 + iterator_range() : m_Begin( iterator() ), m_End( iterator() ),
1.165 + singular( true )
1.166 + { }
1.167 +/*
1.168 +#if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x564))
1.169 + iterator_range( this_type r ) :
1.170 + : m_Begin(r.begin()), m_End(r.end())
1.171 + { }
1.172 +
1.173 + this_type& operator=( this_type r )
1.174 + {
1.175 + m_Begin = r.begin();
1.176 + m_End = r.end();
1.177 + return *this;
1.178 + }
1.179 +#endif
1.180 +*/
1.181 + //! Constructor from a pair of iterators
1.182 + template< class Iterator >
1.183 + iterator_range( Iterator Begin, Iterator End ) :
1.184 + m_Begin(Begin), m_End(End), singular(false) {}
1.185 +
1.186 + //! Constructor from a Range
1.187 + template< class Range >
1.188 + iterator_range( const Range& r ) :
1.189 + m_Begin( impl::adl_begin( r ) ), m_End( impl::adl_end( r ) ),
1.190 + singular(false) {}
1.191 +
1.192 + //! Constructor from a Range
1.193 + template< class Range >
1.194 + iterator_range( Range& r ) :
1.195 + m_Begin( impl::adl_begin( r ) ), m_End( impl::adl_end( r ) ),
1.196 + singular(false) {}
1.197 +
1.198 + //! Constructor from a Range
1.199 + template< class Range >
1.200 + iterator_range( const Range& r, iterator_range_detail::const_range_tag ) :
1.201 + m_Begin( impl::adl_begin( r ) ), m_End( impl::adl_end( r ) ),
1.202 + singular(false) {}
1.203 +
1.204 + //! Constructor from a Range
1.205 + template< class Range >
1.206 + iterator_range( Range& r, iterator_range_detail::range_tag ) :
1.207 + m_Begin( impl::adl_begin( r ) ), m_End( impl::adl_end( r ) ),
1.208 + singular(false) {}
1.209 +
1.210 + #if !BOOST_WORKAROUND(BOOST_MSVC, < 1300)
1.211 + this_type& operator=( const this_type& r )
1.212 + {
1.213 + m_Begin = r.begin();
1.214 + m_End = r.end();
1.215 + //
1.216 + // remark: this need not necessarily be true, but it does no harm
1.217 + //
1.218 + singular = r.singular;
1.219 + return *this;
1.220 + }
1.221 + #endif
1.222 +
1.223 + template< class Iterator >
1.224 + iterator_range& operator=( const iterator_range<Iterator>& r )
1.225 + {
1.226 + m_Begin = r.begin();
1.227 + m_End = r.end();
1.228 + //
1.229 + // remark: this need not necessarily be true, but it does no harm
1.230 + //
1.231 + singular = r.empty();
1.232 + return *this;
1.233 + }
1.234 +
1.235 + template< class ForwardRange >
1.236 + iterator_range& operator=( ForwardRange& r )
1.237 + {
1.238 + m_Begin = impl::adl_begin( r );
1.239 + m_End = impl::adl_end( r );
1.240 + singular = false;
1.241 + return *this;
1.242 + }
1.243 +
1.244 + template< class ForwardRange >
1.245 + iterator_range& operator=( const ForwardRange& r )
1.246 + {
1.247 + m_Begin = impl::adl_begin( r );
1.248 + m_End = impl::adl_end( r );
1.249 + singular = false;
1.250 + return *this;
1.251 + }
1.252 +
1.253 + IteratorT begin() const
1.254 + {
1.255 + return m_Begin;
1.256 + }
1.257 +
1.258 + IteratorT end() const
1.259 + {
1.260 + return m_End;
1.261 + }
1.262 +
1.263 + size_type size() const
1.264 + {
1.265 + if( singular )
1.266 + return 0;
1.267 +
1.268 +#if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x582))
1.269 + return std::distance<IteratorT>( m_Begin, m_End );
1.270 +#else
1.271 + return std::distance( m_Begin, m_End );
1.272 +#endif
1.273 + }
1.274 +
1.275 + bool empty() const
1.276 + {
1.277 + if( singular )
1.278 + return true;
1.279 +
1.280 + return m_Begin == m_End;
1.281 + }
1.282 +
1.283 +#if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x564))
1.284 + operator bool() const
1.285 + {
1.286 + return !empty();
1.287 + }
1.288 +#else
1.289 + typedef iterator (iterator_range::*unspecified_bool_type) () const;
1.290 + operator unspecified_bool_type() const
1.291 + {
1.292 + return empty() ? 0: &iterator_range::end;
1.293 + }
1.294 +#endif
1.295 +
1.296 + bool equal( const iterator_range& r ) const
1.297 + {
1.298 + return singular == r.singular && m_Begin == r.m_Begin && m_End == r.m_End;
1.299 + }
1.300 +
1.301 +
1.302 +#ifdef BOOST_NO_FUNCTION_TEMPLATE_ORDERING
1.303 +
1.304 + bool operator==( const iterator_range& r ) const
1.305 + {
1.306 + return iterator_range_detail::equal( *this, r );
1.307 + }
1.308 +
1.309 + bool operator!=( const iterator_range& r ) const
1.310 + {
1.311 + return !operator==(r);
1.312 + }
1.313 +
1.314 + bool operator<( const iterator_range& r ) const
1.315 + {
1.316 + return iterator_range_detail::less_than( *this, r );
1.317 + }
1.318 +
1.319 +#endif
1.320 +
1.321 + public: // convenience
1.322 + reference front() const
1.323 + {
1.324 + BOOST_ASSERT( !empty() );
1.325 + return *m_Begin;
1.326 + }
1.327 +
1.328 + reference back() const
1.329 + {
1.330 + BOOST_ASSERT( !empty() );
1.331 + IteratorT last( m_End );
1.332 + return *--last;
1.333 + }
1.334 +
1.335 + reference operator[]( size_type sz ) const
1.336 + {
1.337 + //BOOST_STATIC_ASSERT( is_random_access );
1.338 + BOOST_ASSERT( sz < size() );
1.339 + return m_Begin[sz];
1.340 + }
1.341 +
1.342 + iterator_range& advance_begin( difference_type n )
1.343 + {
1.344 + std::advance( m_Begin, n );
1.345 + return *this;
1.346 + }
1.347 +
1.348 + iterator_range& advance_end( difference_type n )
1.349 + {
1.350 + std::advance( m_End, n );
1.351 + return *this;
1.352 + }
1.353 +
1.354 + private:
1.355 + // begin and end iterators
1.356 + IteratorT m_Begin;
1.357 + IteratorT m_End;
1.358 + bool singular;
1.359 + };
1.360 +
1.361 +// iterator range free-standing operators ---------------------------//
1.362 +
1.363 +#ifdef BOOST_NO_FUNCTION_TEMPLATE_ORDERING
1.364 +#else
1.365 + template< class Iterator >
1.366 + inline bool empty( const iterator_range<Iterator>& r )
1.367 + {
1.368 + //
1.369 + // this will preserve the well-defined empty() even
1.370 + // though 'r' is singular.
1.371 + //
1.372 + return r.empty();
1.373 + }
1.374 +#endif
1.375 +
1.376 +#ifndef BOOST_OLD_IOSTREAMS
1.377 +
1.378 + //! iterator_range output operator
1.379 + /*!
1.380 + Output the range to an ostream. Elements are outputed
1.381 + in a sequence without separators.
1.382 + */
1.383 + template< typename IteratorT, typename Elem, typename Traits >
1.384 + inline std::basic_ostream<Elem,Traits>& operator<<(
1.385 + std::basic_ostream<Elem, Traits>& Os,
1.386 + const iterator_range<IteratorT>& r )
1.387 + {
1.388 + std::copy( r.begin(), r.end(),
1.389 + std::ostream_iterator< BOOST_DEDUCED_TYPENAME
1.390 + iterator_value<IteratorT>::type,
1.391 + Elem, Traits>(Os) );
1.392 + return Os;
1.393 + }
1.394 +
1.395 +#else
1.396 +
1.397 + //! iterator_range output operator
1.398 + /*!
1.399 + Output the range to an ostream. Elements are outputed
1.400 + in a sequence without separators.
1.401 + */
1.402 + template< typename IteratorT >
1.403 + inline std::ostream& operator<<(
1.404 + std::ostream& Os,
1.405 + const iterator_range<IteratorT>& r )
1.406 + {
1.407 + std::copy( r.begin(), r.end(), std::ostream_iterator<char>(Os));
1.408 + return Os;
1.409 + }
1.410 +
1.411 +#endif
1.412 +
1.413 + /////////////////////////////////////////////////////////////////////
1.414 + // comparison operators
1.415 + /////////////////////////////////////////////////////////////////////
1.416 +
1.417 + template< class IteratorT, class ForwardRange >
1.418 + inline bool operator==( const ForwardRange& l,
1.419 + const iterator_range<IteratorT>& r )
1.420 + {
1.421 + return iterator_range_detail::equal( l, r );
1.422 + }
1.423 +
1.424 + template< class IteratorT, class ForwardRange >
1.425 + inline bool operator!=( const ForwardRange& l,
1.426 + const iterator_range<IteratorT>& r )
1.427 + {
1.428 + return !iterator_range_detail::equal( l, r );
1.429 + }
1.430 +
1.431 + template< class IteratorT, class ForwardRange >
1.432 + inline bool operator<( const ForwardRange& l,
1.433 + const iterator_range<IteratorT>& r )
1.434 + {
1.435 + return iterator_range_detail::less_than( l, r );
1.436 + }
1.437 +
1.438 +#ifdef BOOST_NO_FUNCTION_TEMPLATE_ORDERING
1.439 +#else
1.440 + template< class Iterator1T, class Iterator2T >
1.441 + inline bool operator==( const iterator_range<Iterator1T>& l,
1.442 + const iterator_range<Iterator2T>& r )
1.443 + {
1.444 + return iterator_range_detail::equal( l, r );
1.445 + }
1.446 +
1.447 + template< class IteratorT, class ForwardRange >
1.448 + inline bool operator==( const iterator_range<IteratorT>& l,
1.449 + const ForwardRange& r )
1.450 + {
1.451 + return iterator_range_detail::equal( l, r );
1.452 + }
1.453 +
1.454 +
1.455 + template< class Iterator1T, class Iterator2T >
1.456 + inline bool operator!=( const iterator_range<Iterator1T>& l,
1.457 + const iterator_range<Iterator2T>& r )
1.458 + {
1.459 + return !iterator_range_detail::equal( l, r );
1.460 + }
1.461 +
1.462 + template< class IteratorT, class ForwardRange >
1.463 + inline bool operator!=( const iterator_range<IteratorT>& l,
1.464 + const ForwardRange& r )
1.465 + {
1.466 + return !iterator_range_detail::equal( l, r );
1.467 + }
1.468 +
1.469 +
1.470 + template< class Iterator1T, class Iterator2T >
1.471 + inline bool operator<( const iterator_range<Iterator1T>& l,
1.472 + const iterator_range<Iterator2T>& r )
1.473 + {
1.474 + return iterator_range_detail::less_than( l, r );
1.475 + }
1.476 +
1.477 + template< class IteratorT, class ForwardRange >
1.478 + inline bool operator<( const iterator_range<IteratorT>& l,
1.479 + const ForwardRange& r )
1.480 + {
1.481 + return iterator_range_detail::less_than( l, r );
1.482 + }
1.483 +
1.484 +#endif // BOOST_NO_FUNCTION_TEMPLATE_ORDERING
1.485 +
1.486 +// iterator range utilities -----------------------------------------//
1.487 +
1.488 + //! iterator_range construct helper
1.489 + /*!
1.490 + Construct an \c iterator_range from a pair of iterators
1.491 +
1.492 + \param Begin A begin iterator
1.493 + \param End An end iterator
1.494 + \return iterator_range object
1.495 + */
1.496 + template< typename IteratorT >
1.497 + inline iterator_range< IteratorT >
1.498 + make_iterator_range( IteratorT Begin, IteratorT End )
1.499 + {
1.500 + return iterator_range<IteratorT>( Begin, End );
1.501 + }
1.502 +
1.503 +#ifdef BOOST_NO_FUNCTION_TEMPLATE_ORDERING
1.504 +
1.505 + template< typename Range >
1.506 + inline iterator_range< BOOST_DEDUCED_TYPENAME range_result_iterator<Range>::type >
1.507 + make_iterator_range( Range& r )
1.508 + {
1.509 + return iterator_range< BOOST_DEDUCED_TYPENAME range_result_iterator<Range>::type >
1.510 + ( boost::begin( r ), boost::end( r ) );
1.511 + }
1.512 +
1.513 +#else
1.514 + //! iterator_range construct helper
1.515 + /*!
1.516 + Construct an \c iterator_range from a \c Range containing the begin
1.517 + and end iterators.
1.518 + */
1.519 + template< class ForwardRange >
1.520 + inline iterator_range< BOOST_DEDUCED_TYPENAME range_iterator<ForwardRange>::type >
1.521 + make_iterator_range( ForwardRange& r )
1.522 + {
1.523 + return iterator_range< BOOST_DEDUCED_TYPENAME range_iterator<ForwardRange>::type >
1.524 + ( r, iterator_range_detail::range_tag() );
1.525 + }
1.526 +
1.527 + template< class ForwardRange >
1.528 + inline iterator_range< BOOST_DEDUCED_TYPENAME range_const_iterator<ForwardRange>::type >
1.529 + make_iterator_range( const ForwardRange& r )
1.530 + {
1.531 + return iterator_range< BOOST_DEDUCED_TYPENAME range_const_iterator<ForwardRange>::type >
1.532 + ( r, iterator_range_detail::const_range_tag() );
1.533 + }
1.534 +
1.535 +#endif // BOOST_NO_FUNCTION_TEMPLATE_ORDERING
1.536 +
1.537 + namespace iterator_range_detail
1.538 + {
1.539 + template< class Range >
1.540 + inline iterator_range< BOOST_DEDUCED_TYPENAME range_result_iterator<Range>::type >
1.541 + make_range_impl( Range& r,
1.542 + BOOST_DEDUCED_TYPENAME range_difference<Range>::type advance_begin,
1.543 + BOOST_DEDUCED_TYPENAME range_difference<Range>::type advance_end )
1.544 + {
1.545 + if( advance_begin == 0 && advance_end == 0 )
1.546 + return make_iterator_range( r );
1.547 +
1.548 + BOOST_DEDUCED_TYPENAME range_result_iterator<Range>::type
1.549 + new_begin = boost::begin( r ),
1.550 + new_end = boost::end( r );
1.551 + std::advance( new_begin, advance_begin );
1.552 + std::advance( new_end, advance_end );
1.553 + return make_iterator_range( new_begin, new_end );
1.554 + }
1.555 + }
1.556 +
1.557 +#ifdef BOOST_NO_FUNCTION_TEMPLATE_ORDERING
1.558 +
1.559 + template< class Range >
1.560 + inline iterator_range< BOOST_DEDUCED_TYPENAME range_result_iterator<Range>::type >
1.561 + make_iterator_range( Range& r,
1.562 + BOOST_DEDUCED_TYPENAME range_difference<Range>::type advance_begin,
1.563 + BOOST_DEDUCED_TYPENAME range_difference<Range>::type advance_end )
1.564 + {
1.565 + //BOOST_ASSERT( advance_begin - advance_end <= size(r) && "creating invalid range" );
1.566 + return iterator_range_detail::make_range_impl( r, advance_begin, advance_end );
1.567 + }
1.568 +
1.569 +#else
1.570 +
1.571 + template< class Range >
1.572 + inline iterator_range< BOOST_DEDUCED_TYPENAME range_iterator<Range>::type >
1.573 + make_iterator_range( Range& r,
1.574 + BOOST_DEDUCED_TYPENAME range_difference<Range>::type advance_begin,
1.575 + BOOST_DEDUCED_TYPENAME range_difference<Range>::type advance_end )
1.576 + {
1.577 + //BOOST_ASSERT( advance_begin - advance_end <= size(r) && "creating invalid range" );
1.578 + return iterator_range_detail::make_range_impl( r, advance_begin, advance_end );
1.579 + }
1.580 +
1.581 + template< class Range >
1.582 + inline iterator_range< BOOST_DEDUCED_TYPENAME range_const_iterator<Range>::type >
1.583 + make_iterator_range( const Range& r,
1.584 + BOOST_DEDUCED_TYPENAME range_difference<Range>::type advance_begin,
1.585 + BOOST_DEDUCED_TYPENAME range_difference<Range>::type advance_end )
1.586 + {
1.587 + //BOOST_ASSERT( advance_begin - advance_end <= size(r) && "creating invalid range" );
1.588 + return iterator_range_detail::make_range_impl( r, advance_begin, advance_end );
1.589 + }
1.590 +
1.591 +#endif // BOOST_NO_FUNCTION_TEMPLATE_ORDERING
1.592 +
1.593 + //! copy a range into a sequence
1.594 + /*!
1.595 + Construct a new sequence of the specified type from the elements
1.596 + in the given range
1.597 +
1.598 + \param Range An input range
1.599 + \return New sequence
1.600 + */
1.601 + template< typename SeqT, typename Range >
1.602 + inline SeqT copy_range( const Range& r )
1.603 + {
1.604 + return SeqT( boost::begin( r ), boost::end( r ) );
1.605 + }
1.606 +
1.607 +} // namespace 'boost'
1.608 +
1.609 +#undef BOOST_OLD_IOSTREAMS
1.610 +
1.611 +#endif