v3/algorithm/stable_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_STABLE_PARTITION_HPP
0022 #define RANGES_V3_ALGORITHM_STABLE_PARTITION_HPP
0023
0024 #include <functional>
0025 #include <memory>
0026 #include <type_traits>
0027
0028 #include <meta/meta.hpp>
0029
0030 #include <range/v3/range_fwd.hpp>
0031
0032 #include <range/v3/algorithm/move.hpp>
0033 #include <range/v3/algorithm/partition_copy.hpp>
0034 #include <range/v3/algorithm/rotate.hpp>
0035 #include <range/v3/functional/identity.hpp>
0036 #include <range/v3/functional/invoke.hpp>
0037 #include <range/v3/iterator/concepts.hpp>
0038 #include <range/v3/iterator/move_iterators.hpp>
0039 #include <range/v3/iterator/operations.hpp>
0040 #include <range/v3/iterator/traits.hpp>
0041 #include <range/v3/range/access.hpp>
0042 #include <range/v3/range/concepts.hpp>
0043 #include <range/v3/range/dangling.hpp>
0044 #include <range/v3/range/traits.hpp>
0045 #include <range/v3/utility/memory.hpp>
0046 #include <range/v3/utility/static_const.hpp>
0047 #include <range/v3/utility/swap.hpp>
0048
0049 #include <range/v3/detail/prologue.hpp>
0050
0051 namespace ranges
0052 {
0053     /// \addtogroup group-algorithms
0054     /// @{
0055
0056     /// \cond
0057     namespace detail
0058     {
0059         template<typename I, typename C, typename P, typename D, typename Pair>
0060         I stable_partition_impl(I first, I last, C pred, P proj, D len, Pair const p,
0061                                 std::forward_iterator_tag fi)
0062         {
0063             // *first is known to be false
0064             // len >= 1
0065             if(len == 1)
0066                 return first;
0067             if(len == 2)
0068             {
0069                 I tmp = first;
0070                 if(invoke(pred, invoke(proj, *++tmp)))
0071                 {
0072                     ranges::iter_swap(first, tmp);
0073                     return tmp;
0074                 }
0075                 return first;
0076             }
0077             if(len <= p.second)
0078             { // The buffer is big enough to use
0079                 // Move the falses into the temporary buffer, and the trues to the front
0080                 // of the line Update first to always point to the last of the trues
0081                 auto tmpbuf = make_raw_buffer(p.first);
0082                 auto buf = tmpbuf.begin();
0083                 *buf = iter_move(first);
0084                 ++buf;
0085                 auto res = partition_copy(make_move_iterator(next(first)),
0086                                           make_move_sentinel(last),
0087                                           first,
0088                                           buf,
0089                                           std::ref(pred),
0090                                           std::ref(proj));
0091                 // All trues now at start of range, all falses in buffer
0092                 // Move falses back into range, but don't mess up first which points to
0093                 // first false
0094                 ranges::move(p.first, res.out2.base().base(), res.out1);
0095                 // h destructs moved-from values out of the temp buffer, but doesn't
0096                 // deallocate buffer
0097                 return res.out1;
0098             }
0099             // Else not enough buffer, do in place
0100             // len >= 3
0101             D half = len / 2; // half >= 2
0102             I middle = next(first, half);
0103             // recurse on [first, middle), *first know to be false
0104             // F?????????????????
0105             // f       m         l
0106             I begin_false =
0107                 detail::stable_partition_impl(first, middle, pred, proj, half, p, fi);
0108             // TTTFFFFF??????????
0109             // f  ff   m         l
0110             // recurse on [middle, last], except increase middle until *(middle) is false,
0111             // *last know to be true
0112             I m1 = middle;
0113             D len_half = len - half;
0114             while(invoke(pred, invoke(proj, *m1)))
0115             {
0116                 if(++m1 == last)
0117                     return ranges::rotate(begin_false, middle, last).begin();
0118                 --len_half;
0119             }
0120             // TTTFFFFFTTTF??????
0121             // f  ff   m  m1     l
0122             I end_false =
0123                 detail::stable_partition_impl(m1, last, pred, proj, len_half, p, fi);
0124             // TTTFFFFFTTTTTFFFFF
0125             // f  ff   m    sf   l
0126             return ranges::rotate(begin_false, middle, end_false).begin();
0127             // TTTTTTTTFFFFFFFFFF
0128             //         |
0129         }
0130
0131         template<typename I, typename S, typename C, typename P>
0132         I stable_partition_impl(I first, S last, C pred, P proj,
0133                                 std::forward_iterator_tag fi)
0134         {
0135             using difference_type = iter_difference_t<I>;
0136             difference_type const alloc_limit = 3; // might want to make this a function
0137                                                    // of trivial assignment.
0138             // Either prove all true and return first or point to first false
0139             while(true)
0140             {
0141                 if(first == last)
0142                     return first;
0143                 if(!invoke(pred, invoke(proj, *first)))
0144                     break;
0145                 ++first;
0146             }
0147             // We now have a reduced range [first, last)
0148             // *first is known to be false
0149             using value_type = iter_value_t<I>;
0150             auto len_end = enumerate(first, last);
0151             auto p = len_end.first >= alloc_limit
0152                          ? detail::get_temporary_buffer<value_type>(len_end.first)
0153                          : detail::value_init{};
0154             std::unique_ptr<value_type, detail::return_temporary_buffer> const h{p.first};
0155             return detail::stable_partition_impl(
0156                 first, len_end.second, pred, proj, len_end.first, p, fi);
0157         }
0158
0159         template<typename I, typename C, typename P, typename D, typename Pair>
0160         I stable_partition_impl(I first, I last, C pred, P proj, D len, Pair p,
0161                                 std::bidirectional_iterator_tag bi)
0162         {
0163             // *first is known to be false
0164             // *last is known to be true
0165             // len >= 2
0166             if(len == 2)
0167             {
0168                 ranges::iter_swap(first, last);
0169                 return last;
0170             }
0171             if(len == 3)
0172             {
0173                 I tmp = first;
0174                 if(invoke(pred, invoke(proj, *++tmp)))
0175                 {
0176                     ranges::iter_swap(first, tmp);
0177                     ranges::iter_swap(tmp, last);
0178                     return last;
0179                 }
0180                 ranges::iter_swap(tmp, last);
0181                 ranges::iter_swap(first, tmp);
0182                 return tmp;
0183             }
0184             if(len <= p.second)
0185             { // The buffer is big enough to use
0186                 // Move the falses into the temporary buffer, and the trues to the front
0187                 // of the line Update first to always point to the last of the trues
0188                 auto tmpbuf = ranges::make_raw_buffer(p.first);
0189                 auto buf = tmpbuf.begin();
0190                 *buf = iter_move(first);
0191                 ++buf;
0192                 auto res = partition_copy(make_move_iterator(next(first)),
0193                                           make_move_sentinel(last),
0194                                           first,
0195                                           buf,
0196                                           std::ref(pred),
0197                                           std::ref(proj));
0198                 first = res.out1;
0199                 // move *last, known to be true
0200                 *first = iter_move(res.in);
0201                 ++first;
0202                 // All trues now at start of range, all falses in buffer
0203                 // Move falses back into range, but don't mess up first which points to
0204                 // first false
0205                 ranges::move(p.first, res.out2.base().base(), first);
0206                 // h destructs moved-from values out of the temp buffer, but doesn't
0207                 // deallocate buffer
0208                 return first;
0209             }
0210             // Else not enough buffer, do in place
0211             // len >= 4
0212             I middle = first;
0213             D half = len / 2; // half >= 2
0214             advance(middle, half);
0215             // recurse on [first, middle-1], except reduce middle-1 until *(middle-1) is
0216             // true, *first know to be false F????????????????T f       m        l
0217             I m1 = middle;
0218             I begin_false = first;
0219             D len_half = half;
0220             while(!invoke(pred, invoke(proj, *--m1)))
0221             {
0222                 if(m1 == first)
0223                     goto first_half_done;
0224                 --len_half;
0225             }
0226             // F???TFFF?????????T
0227             // f   m1  m        l
0228             begin_false =
0229                 detail::stable_partition_impl(first, m1, pred, proj, len_half, p, bi);
0230         first_half_done:
0231             // TTTFFFFF?????????T
0232             // f  ff   m        l
0233             // recurse on [middle, last], except increase middle until *(middle) is false,
0234             // *last know to be true
0235             m1 = middle;
0236             len_half = len - half;
0237             while(invoke(pred, invoke(proj, *m1)))
0238             {
0239                 if(++m1 == last)
0240                     return ranges::rotate(begin_false, middle, ++last).begin();
0241                 --len_half;
0242             }
0243             // TTTFFFFFTTTF?????T
0244             // f  ff   m  m1    l
0245             I end_false =
0246                 detail::stable_partition_impl(m1, last, pred, proj, len_half, p, bi);
0247             // TTTFFFFFTTTTTFFFFF
0248             // f  ff   m    sf  l
0249             return ranges::rotate(begin_false, middle, end_false).begin();
0250             // TTTTTTTTFFFFFFFFFF
0251             //         |
0252         }
0253
0254         template<typename I, typename S, typename C, typename P>
0255         I stable_partition_impl(I first, S end_, C pred, P proj,
0256                                 std::bidirectional_iterator_tag bi)
0257         {
0258             using difference_type = iter_difference_t<I>;
0259             using value_type = iter_value_t<I>;
0260             difference_type const alloc_limit =
0261                 4; // might want to make this a function of trivial assignment
0262             // Either prove all true and return first or point to first false
0263             while(true)
0264             {
0265                 if(first == end_)
0266                     return first;
0267                 if(!invoke(pred, invoke(proj, *first)))
0268                     break;
0269                 ++first;
0270             }
0271             // first points to first false, everything prior to first is already set.
0272             // Either prove [first, last) is all false and return first, or point last to
0273             // last true
0274             I last = ranges::next(first, end_);
0275             do
0276             {
0277                 if(first == --last)
0278                     return first;
0279             } while(!invoke(pred, invoke(proj, *last)));
0280             // We now have a reduced range [first, last]
0281             // *first is known to be false
0282             // *last is known to be true
0283             // len >= 2
0284             auto len = distance(first, last) + 1;
0285             auto p = len >= alloc_limit ? detail::get_temporary_buffer<value_type>(len)
0286                                         : detail::value_init{};
0287             std::unique_ptr<value_type, detail::return_temporary_buffer> const h{p.first};
0288             return detail::stable_partition_impl(first, last, pred, proj, len, p, bi);
0289         }
0290     } // namespace detail
0291     /// \endcond
0292
0293     RANGES_FUNC_BEGIN(stable_partition)
0294
0295         /// \brief function template \c stable_partition
0296         template(typename I, typename S, typename C, typename P = identity)(
0297             requires bidirectional_iterator<I> AND sentinel_for<S, I> AND
0298             indirect_unary_predicate<C, projected<I, P>> AND permutable<I>)
0299         I RANGES_FUNC(stable_partition)(I first, S last, C pred, P proj = P{})
0300         {
0301             return detail::stable_partition_impl(std::move(first),
0302                                                  std::move(last),
0303                                                  std::ref(pred),
0304                                                  std::ref(proj),
0305                                                  iterator_tag_of<I>());
0306         }
0307
0308         // BUGBUG Can this be optimized if Rng has O1 size?
0309         /// \overload
0310         template(typename Rng, typename C, typename P = identity)(
0311             requires bidirectional_range<Rng> AND
0312             indirect_unary_predicate<C, projected<iterator_t<Rng>, P>> AND
0313             permutable<iterator_t<Rng>>)
0314         borrowed_iterator_t<Rng> //
0315         RANGES_FUNC(stable_partition)(Rng && rng, C pred, P proj = P{}) //
0316         {
0317             return (*this)(begin(rng), end(rng), std::move(pred), std::move(proj));
0318         }
0319
0320     RANGES_FUNC_END(stable_partition)
0321
0322     namespace cpp20
0323     {
0324         using ranges::stable_partition;
0325     }
0326     /// @}
0327 } // namespace ranges
0328
0329 #include <range/v3/detail/epilogue.hpp>
0330
0331 #endif