range/algorithm/equal.hpp

0001 // Boost.Range library
0002 //
0003 //  Copyright Neil Groves 2009.
0004 //  Use, modification and distribution is subject to the Boost Software
0005 //  License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0006 //  http://www.boost.org/LICENSE_1_0.txt)
0007 //
0008 // For more information, see http://www.boost.org/libs/range/
0009 //
0010 #ifndef BOOST_RANGE_ALGORITHM_EQUAL_HPP_INCLUDED
0011 #define BOOST_RANGE_ALGORITHM_EQUAL_HPP_INCLUDED
0012
0013 #include <boost/config.hpp>
0014 #include <boost/range/concepts.hpp>
0015 #include <iterator>
0016
0017 namespace boost
0018 {
0019     namespace range_detail
0020     {
0021         // An implementation of equality comparison that is optimized for iterator
0022         // traversal categories less than RandomAccessTraversal.
0023         template< class SinglePassTraversalReadableIterator1,
0024                   class SinglePassTraversalReadableIterator2,
0025                   class IteratorCategoryTag1,
0026                   class IteratorCategoryTag2 >
0027         inline bool equal_impl( SinglePassTraversalReadableIterator1 first1,
0028                                 SinglePassTraversalReadableIterator1 last1,
0029                                 SinglePassTraversalReadableIterator2 first2,
0030                                 SinglePassTraversalReadableIterator2 last2,
0031                                 IteratorCategoryTag1,
0032                                 IteratorCategoryTag2 )
0033         {
0034             for (;;)
0035             {
0036                 // If we have reached the end of the left range then this is
0037                 // the end of the loop. They are equal if and only if we have
0038                 // simultaneously reached the end of the right range.
0039                 if (first1 == last1)
0040                     return first2 == last2;
0041
0042                 // If we have reached the end of the right range at this line
0043                 // it indicates that the right range is shorter than the left
0044                 // and hence the result is false.
0045                 if (first2 == last2)
0046                     return false;
0047
0048                 // continue looping if and only if the values are equal
0049                 if (*first1 != *first2)
0050                     break;
0051
0052                 ++first1;
0053                 ++first2;
0054             }
0055
0056             // Reaching this line in the algorithm indicates that a value
0057             // inequality has been detected.
0058             return false;
0059         }
0060
0061         template< class SinglePassTraversalReadableIterator1,
0062                   class SinglePassTraversalReadableIterator2,
0063                   class IteratorCategoryTag1,
0064                   class IteratorCategoryTag2,
0065                   class BinaryPredicate >
0066         inline bool equal_impl( SinglePassTraversalReadableIterator1 first1,
0067                                 SinglePassTraversalReadableIterator1 last1,
0068                                 SinglePassTraversalReadableIterator2 first2,
0069                                 SinglePassTraversalReadableIterator2 last2,
0070                                 BinaryPredicate                      pred,
0071                                 IteratorCategoryTag1,
0072                                 IteratorCategoryTag2 )
0073         {
0074             for (;;)
0075             {
0076                 // If we have reached the end of the left range then this is
0077                 // the end of the loop. They are equal if and only if we have
0078                 // simultaneously reached the end of the right range.
0079                 if (first1 == last1)
0080                     return first2 == last2;
0081
0082                 // If we have reached the end of the right range at this line
0083                 // it indicates that the right range is shorter than the left
0084                 // and hence the result is false.
0085                 if (first2 == last2)
0086                     return false;
0087
0088                 // continue looping if and only if the values are equal
0089                 if (!pred(*first1, *first2))
0090                     break;
0091
0092                 ++first1;
0093                 ++first2;
0094             }
0095
0096             // Reaching this line in the algorithm indicates that a value
0097             // inequality has been detected.
0098             return false;
0099         }
0100
0101         // An implementation of equality comparison that is optimized for
0102         // random access iterators.
0103         template< class RandomAccessTraversalReadableIterator1,
0104                   class RandomAccessTraversalReadableIterator2 >
0105         inline bool equal_impl( RandomAccessTraversalReadableIterator1 first1,
0106                                 RandomAccessTraversalReadableIterator1 last1,
0107                                 RandomAccessTraversalReadableIterator2 first2,
0108                                 RandomAccessTraversalReadableIterator2 last2,
0109                                 std::random_access_iterator_tag,
0110                                 std::random_access_iterator_tag )
0111         {
0112             return ((last1 - first1) == (last2 - first2))
0113                 && std::equal(first1, last1, first2);
0114         }
0115
0116         template< class RandomAccessTraversalReadableIterator1,
0117                   class RandomAccessTraversalReadableIterator2,
0118                   class BinaryPredicate >
0119         inline bool equal_impl( RandomAccessTraversalReadableIterator1 first1,
0120                                 RandomAccessTraversalReadableIterator1 last1,
0121                                 RandomAccessTraversalReadableIterator2 first2,
0122                                 RandomAccessTraversalReadableIterator2 last2,
0123                                 BinaryPredicate                        pred,
0124                                 std::random_access_iterator_tag,
0125                                 std::random_access_iterator_tag )
0126         {
0127             return ((last1 - first1) == (last2 - first2))
0128                 && std::equal(first1, last1, first2, pred);
0129         }
0130
0131         template< class SinglePassTraversalReadableIterator1,
0132                   class SinglePassTraversalReadableIterator2 >
0133         inline bool equal( SinglePassTraversalReadableIterator1 first1,
0134                            SinglePassTraversalReadableIterator1 last1,
0135                            SinglePassTraversalReadableIterator2 first2,
0136                            SinglePassTraversalReadableIterator2 last2 )
0137         {
0138             BOOST_DEDUCED_TYPENAME std::iterator_traits< SinglePassTraversalReadableIterator1 >::iterator_category tag1;
0139             BOOST_DEDUCED_TYPENAME std::iterator_traits< SinglePassTraversalReadableIterator2 >::iterator_category tag2;
0140
0141             return equal_impl(first1, last1, first2, last2, tag1, tag2);
0142         }
0143
0144         template< class SinglePassTraversalReadableIterator1,
0145                   class SinglePassTraversalReadableIterator2,
0146                   class BinaryPredicate >
0147         inline bool equal( SinglePassTraversalReadableIterator1 first1,
0148                            SinglePassTraversalReadableIterator1 last1,
0149                            SinglePassTraversalReadableIterator2 first2,
0150                            SinglePassTraversalReadableIterator2 last2,
0151                            BinaryPredicate                      pred )
0152         {
0153             BOOST_DEDUCED_TYPENAME std::iterator_traits< SinglePassTraversalReadableIterator1 >::iterator_category tag1;
0154             BOOST_DEDUCED_TYPENAME std::iterator_traits< SinglePassTraversalReadableIterator2 >::iterator_category tag2;
0155
0156             return equal_impl(first1, last1, first2, last2, pred, tag1, tag2);
0157         }
0158
0159     } // namespace range_detail
0160
0161     namespace range
0162     {
0163
0164         /// \brief template function equal
0165         ///
0166         /// range-based version of the equal std algorithm
0167         ///
0168         /// \pre SinglePassRange1 is a model of the SinglePassRangeConcept
0169         /// \pre SinglePassRange2 is a model of the SinglePassRangeConcept
0170         /// \pre BinaryPredicate is a model of the BinaryPredicateConcept
0171         template< class SinglePassRange1, class SinglePassRange2 >
0172         inline bool equal( const SinglePassRange1& rng1, const SinglePassRange2& rng2 )
0173         {
0174             BOOST_RANGE_CONCEPT_ASSERT(( SinglePassRangeConcept<const SinglePassRange1> ));
0175             BOOST_RANGE_CONCEPT_ASSERT(( SinglePassRangeConcept<const SinglePassRange2> ));
0176
0177             return ::boost::range_detail::equal(
0178                 ::boost::begin(rng1), ::boost::end(rng1),
0179                 ::boost::begin(rng2), ::boost::end(rng2) );
0180         }
0181
0182         /// \overload
0183         template< class SinglePassRange1, class SinglePassRange2, class BinaryPredicate >
0184         inline bool equal( const SinglePassRange1& rng1, const SinglePassRange2& rng2,
0185                            BinaryPredicate pred )
0186         {
0187             BOOST_RANGE_CONCEPT_ASSERT(( SinglePassRangeConcept<const SinglePassRange1> ));
0188             BOOST_RANGE_CONCEPT_ASSERT(( SinglePassRangeConcept<const SinglePassRange2> ));
0189
0190             return ::boost::range_detail::equal(
0191                 ::boost::begin(rng1), ::boost::end(rng1),
0192                 ::boost::begin(rng2), ::boost::end(rng2),
0193                 pred);
0194         }
0195
0196     } // namespace range
0197     using ::boost::range::equal;
0198 } // namespace boost
0199
0200 #endif // include guard