boost/algorithm/is_partitioned_until.hpp

   1 /*
   2    Copyright (c) Alexander Zaitsev <zamazan4ik@gmail.by>, 2017.
   3
   4    Distributed under the Boost Software License, Version 1.0. (See accompanying
   5    file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
   6 */
   7
   8 /// \file  is_partitioned_until.hpp
   9 /// \brief Tell if a sequence is partitioned
  10 /// \author Alexander Zaitsev
  11
  12 #ifndef BOOST_ALGORITHM_IS_PARTITIONED_UNTIL_HPP
  13 #define BOOST_ALGORITHM_IS_PARTITIONED_UNTIL_HPP
  14
  15 #include <boost/config.hpp>
  16 #include <boost/range/begin.hpp>
  17 #include <boost/range/end.hpp>
  18
  19 namespace boost { namespace algorithm {
  20
  21 /// \fn is_partitioned_until ( InputIterator first, InputIterator last, UnaryPredicate p )
  22 /// \brief Tests to see if a sequence is partitioned according to a predicate.
  23 ///        In other words, all the items in the sequence that satisfy the predicate are at the beginning of the sequence.
  24 ///
  25 /// \param first    The start of the input sequence
  26 /// \param last     One past the end of the input sequence
  27 /// \param p        The predicate to test the values with
  28 ///
  29 /// \note Returns the first iterator 'it' in the sequence [first, last) for which is_partitioned(first, it, p) is false.
  30 ///     Returns last if the entire sequence is partitioned.
  31 ///     Complexity: O(N).
  32 template <typename InputIterator, typename UnaryPredicate>
  33 InputIterator is_partitioned_until ( InputIterator first, InputIterator last, UnaryPredicate p )
  34 {
  35 //  Run through the part that satisfy the predicate
  36     for ( ; first != last; ++first )
  37         if ( !p (*first))
  38             break;
  39 //  Now the part that does not satisfy the predicate
  40     for ( ; first != last; ++first )
  41         if ( p (*first))
  42             return first;
  43     return last;
  44 }
  45
  46 /// \fn is_partitioned_until ( const Range &r, UnaryPredicate p )
  47 /// \brief Tests to see if a sequence is partitioned according to a predicate.
  48 ///        In other words, all the items in the sequence that satisfy the predicate are at the beginning of the sequence.
  49 ///
  50 /// \param r        The input range
  51 /// \param p        The predicate to test the values with
  52 ///
  53 /// \note Returns the first iterator 'it' in the sequence [first, last) for which is_partitioned(first, it, p) is false.
  54 ///     Returns last if the entire sequence is partitioned.
  55 ///     Complexity: O(N).
  56 template <typename Range, typename UnaryPredicate>
  57 typename boost::range_iterator<const Range>::type is_partitioned_until ( const Range &r, UnaryPredicate p )
  58 {
  59     return boost::algorithm::is_partitioned_until (boost::begin(r), boost::end(r), p);
  60 }
  61
  62 }}
  63
  64 #endif  // BOOST_ALGORITHM_IS_PARTITIONED_UNTIL_HPP