Chris@16: // Boost.Range library
Chris@16: //
Chris@16: //  Copyright Neil Groves 2009.
Chris@16: //  Use, modification and distribution is subject to the Boost Software
Chris@16: //  License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
Chris@16: //  http://www.boost.org/LICENSE_1_0.txt)
Chris@16: //
Chris@16: // For more information, see http://www.boost.org/libs/range/
Chris@16: //
Chris@16: #ifndef BOOST_RANGE_ALGORITHM_EQUAL_HPP_INCLUDED
Chris@16: #define BOOST_RANGE_ALGORITHM_EQUAL_HPP_INCLUDED
Chris@16: 
Chris@16: #include <boost/config.hpp>
Chris@16: #include <boost/range/concepts.hpp>
Chris@16: #include <iterator>
Chris@16: 
Chris@16: namespace boost
Chris@16: {
Chris@16:     namespace range_detail
Chris@16:     {
Chris@16:         // An implementation of equality comparison that is optimized for iterator
Chris@16:         // traversal categories less than RandomAccessTraversal.
Chris@16:         template< class SinglePassTraversalReadableIterator1,
Chris@16:                   class SinglePassTraversalReadableIterator2,
Chris@16:                   class IteratorCategoryTag1,
Chris@16:                   class IteratorCategoryTag2 >
Chris@16:         inline bool equal_impl( SinglePassTraversalReadableIterator1 first1,
Chris@16:                                 SinglePassTraversalReadableIterator1 last1,
Chris@16:                                 SinglePassTraversalReadableIterator2 first2,
Chris@16:                                 SinglePassTraversalReadableIterator2 last2,
Chris@16:                                 IteratorCategoryTag1,
Chris@16:                                 IteratorCategoryTag2 )
Chris@16:         {
Chris@101:             for (;;)
Chris@16:             {
Chris@16:                 // If we have reached the end of the left range then this is
Chris@16:                 // the end of the loop. They are equal if and only if we have
Chris@16:                 // simultaneously reached the end of the right range.
Chris@16:                 if (first1 == last1)
Chris@16:                     return first2 == last2;
Chris@16: 
Chris@16:                 // If we have reached the end of the right range at this line
Chris@16:                 // it indicates that the right range is shorter than the left
Chris@16:                 // and hence the result is false.
Chris@16:                 if (first2 == last2)
Chris@16:                     return false;
Chris@16: 
Chris@16:                 // continue looping if and only if the values are equal
Chris@16:                 if (*first1 != *first2)
Chris@16:                     break;
Chris@16: 
Chris@16:                 ++first1;
Chris@16:                 ++first2;
Chris@16:             }
Chris@16: 
Chris@16:             // Reaching this line in the algorithm indicates that a value
Chris@16:             // inequality has been detected.
Chris@16:             return false;
Chris@16:         }
Chris@16: 
Chris@16:         template< class SinglePassTraversalReadableIterator1,
Chris@16:                   class SinglePassTraversalReadableIterator2,
Chris@16:                   class IteratorCategoryTag1,
Chris@16:                   class IteratorCategoryTag2,
Chris@16:                   class BinaryPredicate >
Chris@16:         inline bool equal_impl( SinglePassTraversalReadableIterator1 first1,
Chris@16:                                 SinglePassTraversalReadableIterator1 last1,
Chris@16:                                 SinglePassTraversalReadableIterator2 first2,
Chris@16:                                 SinglePassTraversalReadableIterator2 last2,
Chris@16:                                 BinaryPredicate                      pred,
Chris@16:                                 IteratorCategoryTag1,
Chris@16:                                 IteratorCategoryTag2 )
Chris@16:         {
Chris@101:             for (;;)
Chris@16:             {
Chris@16:                 // If we have reached the end of the left range then this is
Chris@16:                 // the end of the loop. They are equal if and only if we have
Chris@16:                 // simultaneously reached the end of the right range.
Chris@16:                 if (first1 == last1)
Chris@16:                     return first2 == last2;
Chris@16: 
Chris@16:                 // If we have reached the end of the right range at this line
Chris@16:                 // it indicates that the right range is shorter than the left
Chris@16:                 // and hence the result is false.
Chris@16:                 if (first2 == last2)
Chris@16:                     return false;
Chris@16: 
Chris@16:                 // continue looping if and only if the values are equal
Chris@16:                 if (!pred(*first1, *first2))
Chris@16:                     break;
Chris@16: 
Chris@16:                 ++first1;
Chris@16:                 ++first2;
Chris@16:             }
Chris@16: 
Chris@16:             // Reaching this line in the algorithm indicates that a value
Chris@16:             // inequality has been detected.
Chris@16:             return false;
Chris@16:         }
Chris@16: 
Chris@16:         // An implementation of equality comparison that is optimized for
Chris@16:         // random access iterators.
Chris@16:         template< class RandomAccessTraversalReadableIterator1,
Chris@16:                   class RandomAccessTraversalReadableIterator2 >
Chris@16:         inline bool equal_impl( RandomAccessTraversalReadableIterator1 first1,
Chris@16:                                 RandomAccessTraversalReadableIterator1 last1,
Chris@16:                                 RandomAccessTraversalReadableIterator2 first2,
Chris@16:                                 RandomAccessTraversalReadableIterator2 last2,
Chris@16:                                 std::random_access_iterator_tag,
Chris@16:                                 std::random_access_iterator_tag )
Chris@16:         {
Chris@16:             return ((last1 - first1) == (last2 - first2))
Chris@16:                 && std::equal(first1, last1, first2);
Chris@16:         }
Chris@16: 
Chris@16:         template< class RandomAccessTraversalReadableIterator1,
Chris@16:                   class RandomAccessTraversalReadableIterator2,
Chris@16:                   class BinaryPredicate >
Chris@16:         inline bool equal_impl( RandomAccessTraversalReadableIterator1 first1,
Chris@16:                                 RandomAccessTraversalReadableIterator1 last1,
Chris@16:                                 RandomAccessTraversalReadableIterator2 first2,
Chris@16:                                 RandomAccessTraversalReadableIterator2 last2,
Chris@101:                                 BinaryPredicate                        pred,
Chris@101:                                 std::random_access_iterator_tag,
Chris@101:                                 std::random_access_iterator_tag )
Chris@16:         {
Chris@16:             return ((last1 - first1) == (last2 - first2))
Chris@16:                 && std::equal(first1, last1, first2, pred);
Chris@16:         }
Chris@16: 
Chris@16:         template< class SinglePassTraversalReadableIterator1,
Chris@16:                   class SinglePassTraversalReadableIterator2 >
Chris@16:         inline bool equal( SinglePassTraversalReadableIterator1 first1,
Chris@16:                            SinglePassTraversalReadableIterator1 last1,
Chris@16:                            SinglePassTraversalReadableIterator2 first2,
Chris@16:                            SinglePassTraversalReadableIterator2 last2 )
Chris@16:         {
Chris@16:             BOOST_DEDUCED_TYPENAME std::iterator_traits< SinglePassTraversalReadableIterator1 >::iterator_category tag1;
Chris@16:             BOOST_DEDUCED_TYPENAME std::iterator_traits< SinglePassTraversalReadableIterator2 >::iterator_category tag2;
Chris@16: 
Chris@16:             return equal_impl(first1, last1, first2, last2, tag1, tag2);
Chris@16:         }
Chris@16: 
Chris@16:         template< class SinglePassTraversalReadableIterator1,
Chris@16:                   class SinglePassTraversalReadableIterator2,
Chris@16:                   class BinaryPredicate >
Chris@16:         inline bool equal( SinglePassTraversalReadableIterator1 first1,
Chris@16:                            SinglePassTraversalReadableIterator1 last1,
Chris@16:                            SinglePassTraversalReadableIterator2 first2,
Chris@16:                            SinglePassTraversalReadableIterator2 last2,
Chris@16:                            BinaryPredicate                      pred )
Chris@16:         {
Chris@16:             BOOST_DEDUCED_TYPENAME std::iterator_traits< SinglePassTraversalReadableIterator1 >::iterator_category tag1;
Chris@16:             BOOST_DEDUCED_TYPENAME std::iterator_traits< SinglePassTraversalReadableIterator2 >::iterator_category tag2;
Chris@16: 
Chris@16:             return equal_impl(first1, last1, first2, last2, pred, tag1, tag2);
Chris@16:         }
Chris@16: 
Chris@16:     } // namespace range_detail
Chris@16: 
Chris@16:     namespace range
Chris@16:     {
Chris@16: 
Chris@16:         /// \brief template function equal
Chris@16:         ///
Chris@16:         /// range-based version of the equal std algorithm
Chris@16:         ///
Chris@16:         /// \pre SinglePassRange1 is a model of the SinglePassRangeConcept
Chris@16:         /// \pre SinglePassRange2 is a model of the SinglePassRangeConcept
Chris@16:         /// \pre BinaryPredicate is a model of the BinaryPredicateConcept
Chris@16:         template< class SinglePassRange1, class SinglePassRange2 >
Chris@16:         inline bool equal( const SinglePassRange1& rng1, const SinglePassRange2& rng2 )
Chris@16:         {
Chris@16:             BOOST_RANGE_CONCEPT_ASSERT(( SinglePassRangeConcept<const SinglePassRange1> ));
Chris@16:             BOOST_RANGE_CONCEPT_ASSERT(( SinglePassRangeConcept<const SinglePassRange2> ));
Chris@16: 
Chris@16:             return ::boost::range_detail::equal(
Chris@16:                 ::boost::begin(rng1), ::boost::end(rng1),
Chris@16:                 ::boost::begin(rng2), ::boost::end(rng2) );
Chris@16:         }
Chris@16: 
Chris@16:         /// \overload
Chris@16:         template< class SinglePassRange1, class SinglePassRange2, class BinaryPredicate >
Chris@16:         inline bool equal( const SinglePassRange1& rng1, const SinglePassRange2& rng2,
Chris@16:                            BinaryPredicate pred )
Chris@16:         {
Chris@16:             BOOST_RANGE_CONCEPT_ASSERT(( SinglePassRangeConcept<const SinglePassRange1> ));
Chris@16:             BOOST_RANGE_CONCEPT_ASSERT(( SinglePassRangeConcept<const SinglePassRange2> ));
Chris@16: 
Chris@16:             return ::boost::range_detail::equal(
Chris@16:                 ::boost::begin(rng1), ::boost::end(rng1),
Chris@16:                 ::boost::begin(rng2), ::boost::end(rng2),
Chris@16:                 pred);
Chris@16:         }
Chris@16: 
Chris@16:     } // namespace range
Chris@16:     using ::boost::range::equal;
Chris@16: } // namespace boost
Chris@16: 
Chris@16: #endif // include guard