Chris@16: //  (C) Copyright Gennadiy Rozental 2004-2008.
Chris@16: //  Distributed under the Boost Software License, Version 1.0.
Chris@16: //  (See accompanying file LICENSE_1_0.txt or copy at 
Chris@16: //  http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: //  See http://www.boost.org/libs/test for the library home page.
Chris@16: //
Chris@16: //  File        : $RCSfile$
Chris@16: //
Chris@101: //  Version     : $Revision$
Chris@16: //
Chris@16: //  Description : addition to STL algorithms
Chris@16: // ***************************************************************************
Chris@16: 
Chris@16: #ifndef BOOST_ALGORITHM_HPP_062304GER
Chris@16: #define BOOST_ALGORITHM_HPP_062304GER
Chris@16: 
Chris@16: #include <utility>
Chris@16: #include <algorithm> // std::find
Chris@16: #include <functional> // std::bind1st
Chris@16: 
Chris@16: #include <boost/test/detail/suppress_warnings.hpp>
Chris@16: 
Chris@16: //____________________________________________________________________________//
Chris@16: 
Chris@16: namespace boost {
Chris@16: 
Chris@16: namespace unit_test {
Chris@16: 
Chris@16: /// @brief this algorithm search through two collections for first mismatch position that get returned as a pair
Chris@16: /// of iterators, first pointing to the mismatch position in first collection, second iterator in second one
Chris@16: 
Chris@16: /// @param first1 - first collection begin iterator
Chris@16: /// @param last1 - first collection end iterator
Chris@16: /// @param first2 - second collection begin iterator
Chris@16: /// @param last2 - second collection end iterator
Chris@16: template <class InputIter1, class InputIter2>
Chris@16: inline std::pair<InputIter1, InputIter2>
Chris@16: mismatch( InputIter1 first1, InputIter1 last1,
Chris@16:           InputIter2 first2, InputIter2 last2 )
Chris@16: {
Chris@16:     while( first1 != last1 && first2 != last2 && *first1 == *first2 ) {
Chris@16:         ++first1;
Chris@16:         ++first2;
Chris@16:     }
Chris@16: 
Chris@16:     return std::pair<InputIter1, InputIter2>(first1, first2);
Chris@16: }
Chris@16: 
Chris@16: //____________________________________________________________________________//
Chris@16: 
Chris@16: /// @brief this algorithm search through two collections for first mismatch position that get returned as a pair
Chris@16: /// of iterators, first pointing to the mismatch position in first collection, second iterator in second one. This algorithms
Chris@16: /// uses supplied predicate for collection elements comparison
Chris@16: 
Chris@16: /// @param first1 - first collection begin iterator
Chris@16: /// @param last1 - first collection end iterator
Chris@16: /// @param first2 - second collection begin iterator
Chris@16: /// @param last2 - second collection end iterator
Chris@16: /// @param pred - predicate to be used for search
Chris@16: template <class InputIter1, class InputIter2, class Predicate>
Chris@16: inline std::pair<InputIter1, InputIter2>
Chris@16: mismatch( InputIter1 first1, InputIter1 last1,
Chris@16:           InputIter2 first2, InputIter2 last2,
Chris@16:           Predicate pred )
Chris@16: {
Chris@16:     while( first1 != last1 && first2 != last2 && pred( *first1, *first2 ) ) {
Chris@16:         ++first1;
Chris@16:         ++first2;
Chris@16:     }
Chris@16: 
Chris@16:     return std::pair<InputIter1, InputIter2>(first1, first2);
Chris@16: }
Chris@16: 
Chris@16: //____________________________________________________________________________//
Chris@16: 
Chris@16: /// @brief this algorithm search through first collection for first element that does not belong a second one
Chris@16: 
Chris@16: /// @param first1 - first collection begin iterator
Chris@16: /// @param last1 - first collection end iterator
Chris@16: /// @param first2 - second collection begin iterator
Chris@16: /// @param last2 - second collection end iterator
Chris@16: template<class ForwardIterator1, class ForwardIterator2>
Chris@16: inline ForwardIterator1
Chris@16: find_first_not_of( ForwardIterator1 first1, ForwardIterator1 last1, 
Chris@16:                    ForwardIterator2 first2, ForwardIterator2 last2 )
Chris@16: {
Chris@16:     while( first1 != last1 ) {
Chris@16:         if( std::find( first2, last2, *first1 ) == last2 )
Chris@16:             break;
Chris@16:         ++first1;
Chris@16:     }
Chris@16: 
Chris@16:     return first1;
Chris@16: }
Chris@16: 
Chris@16: //____________________________________________________________________________//
Chris@16: 
Chris@16: /// @brief this algorithm search through first collection for first element that does not satisfy binary 
Chris@16: /// predicate in conjunction will any element in second collection
Chris@16: 
Chris@16: /// @param first1 - first collection begin iterator
Chris@16: /// @param last1 - first collection end iterator
Chris@16: /// @param first2 - second collection begin iterator
Chris@16: /// @param last2 - second collection end iterator
Chris@16: /// @param pred - predicate to be used for search
Chris@16: template<class ForwardIterator1, class ForwardIterator2, class Predicate>
Chris@16: inline ForwardIterator1
Chris@16: find_first_not_of( ForwardIterator1 first1, ForwardIterator1 last1, 
Chris@16:                    ForwardIterator2 first2, ForwardIterator2 last2, 
Chris@16:                    Predicate pred )
Chris@16: {
Chris@16:     while( first1 != last1 ) {
Chris@16:         if( std::find_if( first2, last2, std::bind1st( pred, *first1 ) ) == last2 )
Chris@16:             break;
Chris@16:         ++first1;
Chris@16:     }
Chris@16: 
Chris@16:     return first1;
Chris@16: }
Chris@16: 
Chris@16: //____________________________________________________________________________//
Chris@16: 
Chris@16: /// @brief this algorithm search through first collection for last element that belongs to a second one
Chris@16: 
Chris@16: /// @param first1 - first collection begin iterator
Chris@16: /// @param last1 - first collection end iterator
Chris@16: /// @param first2 - second collection begin iterator
Chris@16: /// @param last2 - second collection end iterator
Chris@16: template<class BidirectionalIterator1, class ForwardIterator2>
Chris@16: inline BidirectionalIterator1
Chris@16: find_last_of( BidirectionalIterator1 first1, BidirectionalIterator1 last1, 
Chris@16:               ForwardIterator2 first2, ForwardIterator2 last2 )
Chris@16: {
Chris@16:     if( first1 == last1 || first2 == last2 )
Chris@16:         return last1;
Chris@16: 
Chris@16:     BidirectionalIterator1 it1 = last1;
Chris@16:     while( --it1 != first1 && std::find( first2, last2, *it1 ) == last2 ) {}
Chris@16: 
Chris@16:     return it1 == first1 && std::find( first2, last2, *it1 ) == last2 ? last1 : it1;
Chris@16: }
Chris@16: 
Chris@16: //____________________________________________________________________________//
Chris@16: 
Chris@16: /// @brief this algorithm search through first collection for last element that satisfy binary 
Chris@16: /// predicate in conjunction will at least one element in second collection
Chris@16: 
Chris@16: /// @param first1 - first collection begin iterator
Chris@16: /// @param last1 - first collection end iterator
Chris@16: /// @param first2 - second collection begin iterator
Chris@16: /// @param last2 - second collection end iterator
Chris@16: /// @param pred - predicate to be used for search
Chris@16: template<class BidirectionalIterator1, class ForwardIterator2, class Predicate>
Chris@16: inline BidirectionalIterator1
Chris@16: find_last_of( BidirectionalIterator1 first1, BidirectionalIterator1 last1, 
Chris@16:               ForwardIterator2 first2, ForwardIterator2 last2, 
Chris@16:               Predicate pred )
Chris@16: {
Chris@16:     if( first1 == last1 || first2 == last2 )
Chris@16:         return last1;
Chris@16: 
Chris@16:     BidirectionalIterator1 it1 = last1;
Chris@16:     while( --it1 != first1 && std::find_if( first2, last2, std::bind1st( pred, *it1 ) ) == last2 ) {}
Chris@16: 
Chris@16:     return it1 == first1 && std::find_if( first2, last2, std::bind1st( pred, *it1 ) ) == last2 ? last1 : it1;
Chris@16: }
Chris@16: 
Chris@16: //____________________________________________________________________________//
Chris@16: 
Chris@16: /// @brief this algorithm search through first collection for last element that does not belong to a second one
Chris@16: 
Chris@16: /// @param first1 - first collection begin iterator
Chris@16: /// @param last1 - first collection end iterator
Chris@16: /// @param first2 - second collection begin iterator
Chris@16: /// @param last2 - second collection end iterator
Chris@16: template<class BidirectionalIterator1, class ForwardIterator2>
Chris@16: inline BidirectionalIterator1
Chris@16: find_last_not_of( BidirectionalIterator1 first1, BidirectionalIterator1 last1, 
Chris@16:                   ForwardIterator2 first2, ForwardIterator2 last2 )
Chris@16: {
Chris@16:     if( first1 == last1 || first2 == last2 )
Chris@16:         return last1;
Chris@16: 
Chris@16:     BidirectionalIterator1 it1 = last1;
Chris@16:     while( --it1 != first1 && std::find( first2, last2, *it1 ) != last2 ) {}
Chris@16: 
Chris@16:     return it1 == first1 && std::find( first2, last2, *it1 ) != last2 ? last1 : it1;
Chris@16: }
Chris@16: 
Chris@16: //____________________________________________________________________________//
Chris@16: 
Chris@16: /// @brief this algorithm search through first collection for last element that does not satisfy binary 
Chris@16: /// predicate in conjunction will any element in second collection
Chris@16: 
Chris@16: /// @param first1 - first collection begin iterator
Chris@16: /// @param last1 - first collection end iterator
Chris@16: /// @param first2 - second collection begin iterator
Chris@16: /// @param last2 - second collection end iterator
Chris@16: /// @param pred - predicate to be used for search
Chris@16: template<class BidirectionalIterator1, class ForwardIterator2, class Predicate>
Chris@16: inline BidirectionalIterator1
Chris@16: find_last_not_of( BidirectionalIterator1 first1, BidirectionalIterator1 last1, 
Chris@16:                   ForwardIterator2 first2, ForwardIterator2 last2, 
Chris@16:                   Predicate pred )
Chris@16: {
Chris@16:     if( first1 == last1 || first2 == last2 )
Chris@16:         return last1;
Chris@16: 
Chris@16:     BidirectionalIterator1 it1 = last1;
Chris@16:     while( --it1 != first1 && std::find_if( first2, last2, std::bind1st( pred, *it1 ) ) != last2 ) {}
Chris@16: 
Chris@16:     return it1 == first1 && std::find_if( first2, last2, std::bind1st( pred, *it1 ) ) == last2 ? last1 : it1;
Chris@16: }
Chris@16: 
Chris@16: //____________________________________________________________________________//
Chris@16: 
Chris@16: } // namespace unit_test
Chris@16: 
Chris@16: } // namespace boost
Chris@16: 
Chris@16: //____________________________________________________________________________//
Chris@16: 
Chris@16: #include <boost/test/detail/enable_warnings.hpp>
Chris@16: 
Chris@16: #endif // BOOST_ALGORITHM_HPP_062304GER
Chris@16: 
Chris@16: