v3/algorithm/partition.hpp

0001 /// \file
0002 // Range v3 library
0003 //
0004 //  Copyright Eric Niebler 2014-present
0005 //
0006 //  Use, modification and distribution is subject to the
0007 //  Boost Software License, Version 1.0. (See accompanying
0008 //  file LICENSE_1_0.txt or copy at
0009 //  http://www.boost.org/LICENSE_1_0.txt)
0010 //
0011 // Project home: https://github.com/ericniebler/range-v3
0012 //
0013 //===-------------------------- algorithm ---------------------------------===//
0014 //
0015 //                     The LLVM Compiler Infrastructure
0016 //
0017 // This file is dual licensed under the MIT and the University of Illinois Open
0018 // Source Licenses. See LICENSE.TXT for details.
0019 //
0020 //===----------------------------------------------------------------------===//
0021 #ifndef RANGES_V3_ALGORITHM_PARTITION_HPP
0022 #define RANGES_V3_ALGORITHM_PARTITION_HPP
0023
0024 #include <meta/meta.hpp>
0025
0026 #include <range/v3/range_fwd.hpp>
0027
0028 #include <range/v3/functional/identity.hpp>
0029 #include <range/v3/functional/invoke.hpp>
0030 #include <range/v3/iterator/concepts.hpp>
0031 #include <range/v3/iterator/operations.hpp>
0032 #include <range/v3/iterator/traits.hpp>
0033 #include <range/v3/range/access.hpp>
0034 #include <range/v3/range/concepts.hpp>
0035 #include <range/v3/range/dangling.hpp>
0036 #include <range/v3/range/traits.hpp>
0037 #include <range/v3/utility/static_const.hpp>
0038 #include <range/v3/utility/swap.hpp>
0039
0040 #include <range/v3/detail/prologue.hpp>
0041
0042 namespace ranges
0043 {
0044     /// \addtogroup group-algorithms
0045     /// @{
0046
0047     /// \cond
0048     namespace detail
0049     {
0050         template<typename I, typename S, typename C, typename P>
0051         constexpr I partition_impl(I first, S last, C pred, P proj, std::forward_iterator_tag)
0052         {
0053             while(true)
0054             {
0055                 if(first == last)
0056                     return first;
0057                 if(!invoke(pred, invoke(proj, *first)))
0058                     break;
0059                 ++first;
0060             }
0061             for(I p = first; ++p != last;)
0062             {
0063                 if(invoke(pred, invoke(proj, *p)))
0064                 {
0065                     ranges::iter_swap(first, p);
0066                     ++first;
0067                 }
0068             }
0069             return first;
0070         }
0071
0072         template<typename I, typename S, typename C, typename P>
0073         constexpr I partition_impl(I first, S end_, C pred, P proj, std::bidirectional_iterator_tag)
0074         {
0075             I last = ranges::next(first, end_);
0076             while(true)
0077             {
0078                 while(true)
0079                 {
0080                     if(first == last)
0081                         return first;
0082                     if(!invoke(pred, invoke(proj, *first)))
0083                         break;
0084                     ++first;
0085                 }
0086                 do
0087                 {
0088                     if(first == --last)
0089                         return first;
0090                 } while(!invoke(pred, invoke(proj, *last)));
0091                 ranges::iter_swap(first, last);
0092                 ++first;
0093             }
0094         }
0095     } // namespace detail
0096     /// \endcond
0097
0098     RANGES_FUNC_BEGIN(partition)
0099
0100         /// \brief function template \c partition
0101         template(typename I, typename S, typename C, typename P = identity)(
0102             requires permutable<I> AND sentinel_for<S, I> AND
0103             indirect_unary_predicate<C, projected<I, P>>)
0104         constexpr I RANGES_FUNC(partition)(I first, S last, C pred, P proj = P{})
0105         {
0106             return detail::partition_impl(std::move(first),
0107                                           std::move(last),
0108                                           std::move(pred),
0109                                           std::move(proj),
0110                                           iterator_tag_of<I>());
0111         }
0112
0113         /// \overload
0114         template(typename Rng, typename C, typename P = identity)(
0115             requires forward_range<Rng> AND permutable<iterator_t<Rng>> AND
0116             indirect_unary_predicate<C, projected<iterator_t<Rng>, P>>)
0117         constexpr borrowed_iterator_t<Rng> RANGES_FUNC(partition)(Rng && rng, C pred, P proj = P{})
0118         {
0119             return detail::partition_impl(begin(rng),
0120                                           end(rng),
0121                                           std::move(pred),
0122                                           std::move(proj),
0123                                           iterator_tag_of<iterator_t<Rng>>());
0124         }
0125
0126     RANGES_FUNC_END(partition)
0127
0128     namespace cpp20
0129     {
0130         using ranges::partition;
0131     }
0132     /// @}
0133 } // namespace ranges
0134
0135 #include <range/v3/detail/epilogue.hpp>
0136
0137 #endif