v3/algorithm/permutation.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_PERMUTATION_HPP
0022 #define RANGES_V3_ALGORITHM_PERMUTATION_HPP
0023
0024 #include <meta/meta.hpp>
0025
0026 #include <range/v3/range_fwd.hpp>
0027
0028 #include <range/v3/algorithm/mismatch.hpp>
0029 #include <range/v3/algorithm/reverse.hpp>
0030 #include <range/v3/functional/comparisons.hpp>
0031 #include <range/v3/functional/identity.hpp>
0032 #include <range/v3/functional/invoke.hpp>
0033 #include <range/v3/iterator/concepts.hpp>
0034 #include <range/v3/iterator/operations.hpp>
0035 #include <range/v3/iterator/traits.hpp>
0036 #include <range/v3/range/access.hpp>
0037 #include <range/v3/range/concepts.hpp>
0038 #include <range/v3/range/traits.hpp>
0039 #include <range/v3/utility/static_const.hpp>
0040 #include <range/v3/utility/swap.hpp>
0041
0042 #include <range/v3/detail/prologue.hpp>
0043
0044 namespace ranges
0045 {
0046     /// \addtogroup group-algorithms
0047     /// @{
0048
0049     /// \cond
0050     namespace detail
0051     {
0052         template<typename I1, typename S1, typename I2, typename S2, typename C,
0053                  typename P1, typename P2>
0054         constexpr bool is_permutation_impl(I1 begin1,
0055                                            S1 end1,
0056                                            I2 begin2,
0057                                            S2 end2,
0058                                            C pred,
0059                                            P1 proj1,
0060                                            P2 proj2)
0061         {
0062             // shorten sequences as much as possible by lopping off any equal parts
0063             const auto mismatch =
0064                 ranges::mismatch(begin1, end1, begin2, end2, pred, proj1, proj2);
0065             begin1 = mismatch.in1;
0066             begin2 = mismatch.in2;
0067             if(begin1 == end1 || begin2 == end2)
0068             {
0069                 return begin1 == end1 && begin2 == end2;
0070             }
0071             // begin1 != end1 && begin2 != end2 && *begin1 != *begin2
0072             auto l1 = distance(begin1, end1);
0073             auto l2 = distance(begin2, end2);
0074             if(l1 != l2)
0075                 return false;
0076
0077             // For each element in [f1, l1) see if there are the same number of
0078             //    equal elements in [f2, l2)
0079             for(I1 i = begin1; i != end1; ++i)
0080             {
0081                 // Have we already counted the number of *i in [f1, l1)?
0082                 const auto should_continue = [&] {
0083                     for(I1 j = begin1; j != i; ++j)
0084                         if(invoke(pred, invoke(proj1, *j), invoke(proj1, *i)))
0085                             return true;
0086                     return false;
0087                 }();
0088                 if(should_continue)
0089                 {
0090                     continue;
0091                 }
0092                 // Count number of *i in [f2, l2)
0093                 iter_difference_t<I2> c2 = 0;
0094                 for(I2 j = begin2; j != end2; ++j)
0095                     if(invoke(pred, invoke(proj1, *i), invoke(proj2, *j)))
0096                         ++c2;
0097                 if(c2 == 0)
0098                     return false;
0099                 // Count number of *i in [i, l1) (we can start with 1)
0100                 iter_difference_t<I1> c1 = 1;
0101                 for(I1 j = next(i); j != end1; ++j)
0102                     if(invoke(pred, invoke(proj1, *i), invoke(proj1, *j)))
0103                         ++c1;
0104                 if(c1 != c2)
0105                     return false;
0106             }
0107             return true;
0108         }
0109     } // namespace detail
0110     /// \endcond
0111
0112     RANGES_FUNC_BEGIN(is_permutation)
0113
0114         /// \brief function template \c is_permutation
0115         template(typename I1,
0116                  typename S1,
0117                  typename I2,
0118                  typename C = equal_to,
0119                  typename P1 = identity,
0120                  typename P2 = identity)(
0121             requires forward_iterator<I1> AND sentinel_for<S1, I1> AND
0122                 forward_iterator<I2> AND indirectly_comparable<I1, I2, C, P1, P2>)
0123         RANGES_DEPRECATED(
0124             "Use the variant of ranges::is_permutation that takes an upper bound "
0125             "for both sequences")
0126         bool RANGES_FUNC(is_permutation)(I1 begin1,
0127                                          S1 end1,
0128                                          I2 begin2,
0129                                          C pred = C{},
0130                                          P1 proj1 = P1{},
0131                                          P2 proj2 = P2{}) //
0132         {
0133             // shorten sequences as much as possible by lopping off any equal parts
0134             for(; begin1 != end1; ++begin1, ++begin2)
0135                 if(!invoke(pred, invoke(proj1, *begin1), invoke(proj2, *begin2)))
0136                     goto not_done;
0137             return true;
0138         not_done:
0139             // begin1 != end1 && *begin1 != *begin2
0140             auto l1 = distance(begin1, end1);
0141             if(l1 == 1)
0142                 return false;
0143             I2 end2 = next(begin2, l1);
0144             // For each element in [f1, l1) see if there are the same number of
0145             //    equal elements in [f2, l2)
0146             for(I1 i = begin1; i != end1; ++i)
0147             {
0148                 // Have we already counted the number of *i in [f1, l1)?
0149                 for(I1 j = begin1; j != i; ++j)
0150                     if(invoke(pred, invoke(proj1, *j), invoke(proj1, *i)))
0151                         goto next_iter;
0152                 {
0153                     // Count number of *i in [f2, l2)
0154                     iter_difference_t<I2> c2 = 0;
0155                     for(I2 j = begin2; j != end2; ++j)
0156                         if(invoke(pred, invoke(proj1, *i), invoke(proj2, *j)))
0157                             ++c2;
0158                     if(c2 == 0)
0159                         return false;
0160                     // Count number of *i in [i, l1) (we can start with 1)
0161                     iter_difference_t<I1> c1 = 1;
0162                     for(I1 j = next(i); j != end1; ++j)
0163                         if(invoke(pred, invoke(proj1, *i), invoke(proj1, *j)))
0164                             ++c1;
0165                     if(c1 != c2)
0166                         return false;
0167                 }
0168             next_iter:;
0169             }
0170             return true;
0171         }
0172
0173         /// \overload
0174         template(typename I1,
0175                  typename S1,
0176                  typename I2,
0177                  typename S2,
0178                  typename C = equal_to,
0179                  typename P1 = identity,
0180                  typename P2 = identity)(
0181             requires forward_iterator<I1> AND sentinel_for<S1, I1> AND
0182                 forward_iterator<I2> AND sentinel_for<S2, I2> AND
0183                 indirectly_comparable<I1, I2, C, P1, P2>)
0184         constexpr bool RANGES_FUNC(is_permutation)(I1 begin1,
0185                                                    S1 end1,
0186                                                    I2 begin2,
0187                                                    S2 end2,
0188                                                    C pred = C{},
0189                                                    P1 proj1 = P1{},
0190                                                    P2 proj2 = P2{}) //
0191         {
0192             if(RANGES_CONSTEXPR_IF(sized_sentinel_for<S1, I1> &&
0193                                    sized_sentinel_for<S2, I2>))
0194             {
0195                 RANGES_DIAGNOSTIC_PUSH
0196                 RANGES_DIAGNOSTIC_IGNORE_DEPRECATED_DECLARATIONS
0197                 return distance(begin1, end1) == distance(begin2, end2) &&
0198                        (*this)(std::move(begin1),
0199                                std::move(end1),
0200                                std::move(begin2),
0201                                std::move(pred),
0202                                std::move(proj1),
0203                                std::move(proj2));
0204                 RANGES_DIAGNOSTIC_POP
0205             }
0206             return detail::is_permutation_impl(std::move(begin1),
0207                                                std::move(end1),
0208                                                std::move(begin2),
0209                                                std::move(end2),
0210                                                std::move(pred),
0211                                                std::move(proj1),
0212                                                std::move(proj2));
0213         }
0214
0215         /// \overload
0216         template(typename Rng1,
0217                      typename I2Ref,
0218                      typename C = equal_to,
0219                      typename P1 = identity,
0220                      typename P2 = identity)(
0221             requires forward_range<Rng1> AND forward_iterator<uncvref_t<I2Ref>> AND
0222                 indirectly_comparable<iterator_t<Rng1>, uncvref_t<I2Ref>, C, P1, P2>)
0223         RANGES_DEPRECATED(
0224             "Use the variant of ranges::is_permutation that takes an upper bound "
0225             "for both sequences")
0226         bool RANGES_FUNC(is_permutation)(Rng1 && rng1,
0227                                          I2Ref && begin2,
0228                                          C pred = C{},
0229                                          P1 proj1 = P1{},
0230                                          P2 proj2 = P2{}) //
0231         {
0232             RANGES_DIAGNOSTIC_PUSH
0233             RANGES_DIAGNOSTIC_IGNORE_DEPRECATED_DECLARATIONS
0234             return (*this)(begin(rng1),
0235                            end(rng1),
0236                            (I2Ref &&) begin2,
0237                            std::move(pred),
0238                            std::move(proj1),
0239                            std::move(proj2));
0240             RANGES_DIAGNOSTIC_POP
0241         }
0242
0243         /// \overload
0244         template(typename Rng1,
0245                      typename Rng2,
0246                      typename C = equal_to,
0247                      typename P1 = identity,
0248                      typename P2 = identity)(
0249             requires forward_range<Rng1> AND forward_range<Rng2> AND
0250                 indirectly_comparable<iterator_t<Rng1>, iterator_t<Rng2>, C, P1, P2>)
0251         constexpr bool RANGES_FUNC(is_permutation)(
0252             Rng1 && rng1, Rng2 && rng2, C pred = C{}, P1 proj1 = P1{}, P2 proj2 = P2{}) //
0253         {
0254             if(RANGES_CONSTEXPR_IF(sized_range<Rng1> && sized_range<Rng2>))
0255             {
0256                 RANGES_DIAGNOSTIC_PUSH
0257                 RANGES_DIAGNOSTIC_IGNORE_DEPRECATED_DECLARATIONS
0258                 return distance(rng1) == distance(rng2) && (*this)(begin(rng1),
0259                                                                    end(rng1),
0260                                                                    begin(rng2),
0261                                                                    std::move(pred),
0262                                                                    std::move(proj1),
0263                                                                    std::move(proj2));
0264                 RANGES_DIAGNOSTIC_POP
0265             }
0266             return detail::is_permutation_impl(begin(rng1),
0267                                                end(rng1),
0268                                                begin(rng2),
0269                                                end(rng2),
0270                                                std::move(pred),
0271                                                std::move(proj1),
0272                                                std::move(proj2));
0273         }
0274
0275     RANGES_FUNC_END(is_permutation)
0276
0277     RANGES_FUNC_BEGIN(next_permutation)
0278
0279         /// \brief function template \c next_permutation
0280         template(typename I, typename S, typename C = less, typename P = identity)(
0281             requires bidirectional_iterator<I> AND sentinel_for<S, I> AND
0282                 sortable<I, C, P>)
0283         constexpr bool RANGES_FUNC(next_permutation)(I first, S end_, C pred = C{}, P proj = P{}) //
0284         {
0285             if(first == end_)
0286                 return false;
0287             I last = ranges::next(first, end_), i = last;
0288             if(first == --i)
0289                 return false;
0290             while(true)
0291             {
0292                 I ip1 = i;
0293                 if(invoke(pred, invoke(proj, *--i), invoke(proj, *ip1)))
0294                 {
0295                     I j = last;
0296                     while(!invoke(pred, invoke(proj, *i), invoke(proj, *--j)))
0297                         ;
0298                     ranges::iter_swap(i, j);
0299                     ranges::reverse(ip1, last);
0300                     return true;
0301                 }
0302                 if(i == first)
0303                 {
0304                     ranges::reverse(first, last);
0305                     return false;
0306                 }
0307             }
0308         }
0309
0310         /// \overload
0311         template(typename Rng, typename C = less, typename P = identity)(
0312             requires bidirectional_range<Rng> AND sortable<iterator_t<Rng>, C, P>)
0313         constexpr bool RANGES_FUNC(next_permutation)(Rng && rng, C pred = C{}, P proj = P{}) //
0314         {
0315             return (*this)(begin(rng), end(rng), std::move(pred), std::move(proj));
0316         }
0317
0318     RANGES_FUNC_END(next_permutation)
0319
0320     RANGES_FUNC_BEGIN(prev_permutation)
0321
0322         /// \brief function template \c prev_permutation
0323         template(typename I, typename S, typename C = less, typename P = identity)(
0324             requires bidirectional_iterator<I> AND sentinel_for<S, I> AND
0325                 sortable<I, C, P>)
0326         constexpr bool RANGES_FUNC(prev_permutation)(I first, S end_, C pred = C{}, P proj = P{}) //
0327         {
0328             if(first == end_)
0329                 return false;
0330             I last = ranges::next(first, end_), i = last;
0331             if(first == --i)
0332                 return false;
0333             while(true)
0334             {
0335                 I ip1 = i;
0336                 if(invoke(pred, invoke(proj, *ip1), invoke(proj, *--i)))
0337                 {
0338                     I j = last;
0339                     while(!invoke(pred, invoke(proj, *--j), invoke(proj, *i)))
0340                         ;
0341                     ranges::iter_swap(i, j);
0342                     ranges::reverse(ip1, last);
0343                     return true;
0344                 }
0345                 if(i == first)
0346                 {
0347                     ranges::reverse(first, last);
0348                     return false;
0349                 }
0350             }
0351         }
0352
0353         /// \overload
0354         template(typename Rng, typename C = less, typename P = identity)(
0355             requires bidirectional_range<Rng> AND sortable<iterator_t<Rng>, C, P>)
0356         constexpr bool RANGES_FUNC(prev_permutation)(Rng && rng, C pred = C{}, P proj = P{}) //
0357         {
0358             return (*this)(begin(rng), end(rng), std::move(pred), std::move(proj));
0359         }
0360
0361     RANGES_FUNC_END(prev_permutation)
0362
0363     namespace cpp20
0364     {
0365         using ranges::is_permutation;
0366         using ranges::next_permutation;
0367         using ranges::prev_permutation;
0368     } // namespace cpp20
0369     /// @}
0370 } // namespace ranges
0371
0372 #include <range/v3/detail/epilogue.hpp>
0373
0374 #endif