boost/algorithm/is_partitioned_until.hpp

0001 /*
0002    Copyright (c) Alexander Zaitsev <zamazan4ik@gmail.by>, 2017.
0003
0004    Distributed under the Boost Software License, Version 1.0. (See accompanying
0005    file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
0006 */
0007
0008 /// \file  is_partitioned_until.hpp
0009 /// \brief Tell if a sequence is partitioned
0010 /// \author Alexander Zaitsev
0011
0012 #ifndef BOOST_ALGORITHM_IS_PARTITIONED_UNTIL_HPP
0013 #define BOOST_ALGORITHM_IS_PARTITIONED_UNTIL_HPP
0014
0015 #include <boost/config.hpp>
0016 #include <boost/range/begin.hpp>
0017 #include <boost/range/end.hpp>
0018
0019 namespace boost { namespace algorithm {
0020
0021 /// \fn is_partitioned_until ( InputIterator first, InputIterator last, UnaryPredicate p )
0022 /// \brief Tests to see if a sequence is partitioned according to a predicate.
0023 ///    In other words, all the items in the sequence that satisfy the predicate are at the beginning of the sequence.
0024 ///
0025 /// \param first    The start of the input sequence
0026 /// \param last     One past the end of the input sequence
0027 /// \param p        The predicate to test the values with
0028 ///
0029 /// \note Returns the first iterator 'it' in the sequence [first, last) for which is_partitioned(first, it, p) is false.
0030 ///     Returns last if the entire sequence is partitioned.
0031 ///     Complexity: O(N).
0032 template <typename InputIterator, typename UnaryPredicate>
0033 InputIterator is_partitioned_until ( InputIterator first, InputIterator last, UnaryPredicate p )
0034 {
0035 //  Run through the part that satisfy the predicate
0036     for ( ; first != last; ++first )
0037         if ( !p (*first))
0038             break;
0039 //  Now the part that does not satisfy the predicate
0040     for ( ; first != last; ++first )
0041         if ( p (*first))
0042             return first;
0043     return last;
0044 }
0045
0046 /// \fn is_partitioned_until ( const Range &r, UnaryPredicate p )
0047 /// \brief Tests to see if a sequence is partitioned according to a predicate.
0048 ///    In other words, all the items in the sequence that satisfy the predicate are at the beginning of the sequence.
0049 ///
0050 /// \param r        The input range
0051 /// \param p        The predicate to test the values with
0052 ///
0053 /// \note Returns the first iterator 'it' in the sequence [first, last) for which is_partitioned(first, it, p) is false.
0054 ///     Returns last if the entire sequence is partitioned.
0055 ///     Complexity: O(N).
0056 template <typename Range, typename UnaryPredicate>
0057 typename boost::range_iterator<const Range>::type is_partitioned_until ( const Range &r, UnaryPredicate p )
0058 {
0059     return boost::algorithm::is_partitioned_until (boost::begin(r), boost::end(r), p);
0060 }
0061
0062 }}
0063
0064 #endif  // BOOST_ALGORITHM_IS_PARTITIONED_UNTIL_HPP