catch2/internal/catch_is_permutation.hpp

0001
0002 //              Copyright Catch2 Authors
0003 // Distributed under the Boost Software License, Version 1.0.
0004 //   (See accompanying file LICENSE.txt or copy at
0005 //        https://www.boost.org/LICENSE_1_0.txt)
0006
0007 // SPDX-License-Identifier: BSL-1.0
0008 #ifndef CATCH_IS_PERMUTATION_HPP_INCLUDED
0009 #define CATCH_IS_PERMUTATION_HPP_INCLUDED
0010
0011 #include <algorithm>
0012 #include <iterator>
0013
0014 namespace Catch {
0015     namespace Detail {
0016
0017         template <typename ForwardIter,
0018                   typename Sentinel,
0019                   typename T,
0020                   typename Comparator>
0021         constexpr
0022         ForwardIter find_sentinel( ForwardIter start,
0023                                    Sentinel sentinel,
0024                                    T const& value,
0025                                    Comparator cmp ) {
0026             while ( start != sentinel ) {
0027                 if ( cmp( *start, value ) ) { break; }
0028                 ++start;
0029             }
0030             return start;
0031         }
0032
0033         template <typename ForwardIter,
0034                   typename Sentinel,
0035                   typename T,
0036                   typename Comparator>
0037         constexpr
0038         std::ptrdiff_t count_sentinel( ForwardIter start,
0039                                        Sentinel sentinel,
0040                                        T const& value,
0041                                        Comparator cmp ) {
0042             std::ptrdiff_t count = 0;
0043             while ( start != sentinel ) {
0044                 if ( cmp( *start, value ) ) { ++count; }
0045                 ++start;
0046             }
0047             return count;
0048         }
0049
0050         template <typename ForwardIter, typename Sentinel>
0051         constexpr
0052         std::enable_if_t<!std::is_same<ForwardIter, Sentinel>::value,
0053                          std::ptrdiff_t>
0054         sentinel_distance( ForwardIter iter, const Sentinel sentinel ) {
0055             std::ptrdiff_t dist = 0;
0056             while ( iter != sentinel ) {
0057                 ++iter;
0058                 ++dist;
0059             }
0060             return dist;
0061         }
0062
0063         template <typename ForwardIter>
0064         constexpr std::ptrdiff_t sentinel_distance( ForwardIter first,
0065                                                     ForwardIter last ) {
0066             return std::distance( first, last );
0067         }
0068
0069         template <typename ForwardIter1,
0070                   typename Sentinel1,
0071                   typename ForwardIter2,
0072                   typename Sentinel2,
0073                   typename Comparator>
0074         constexpr bool check_element_counts( ForwardIter1 first_1,
0075                                              const Sentinel1 end_1,
0076                                              ForwardIter2 first_2,
0077                                              const Sentinel2 end_2,
0078                                              Comparator cmp ) {
0079             auto cursor = first_1;
0080             while ( cursor != end_1 ) {
0081                 if ( find_sentinel( first_1, cursor, *cursor, cmp ) ==
0082                      cursor ) {
0083                     // we haven't checked this element yet
0084                     const auto count_in_range_2 =
0085                         count_sentinel( first_2, end_2, *cursor, cmp );
0086                     // Not a single instance in 2nd range, so it cannot be a
0087                     // permutation of 1st range
0088                     if ( count_in_range_2 == 0 ) { return false; }
0089
0090                     const auto count_in_range_1 =
0091                         count_sentinel( cursor, end_1, *cursor, cmp );
0092                     if ( count_in_range_1 != count_in_range_2 ) {
0093                         return false;
0094                     }
0095                 }
0096
0097                 ++cursor;
0098             }
0099
0100             return true;
0101         }
0102
0103         template <typename ForwardIter1,
0104                   typename Sentinel1,
0105                   typename ForwardIter2,
0106                   typename Sentinel2,
0107                   typename Comparator>
0108         constexpr bool is_permutation( ForwardIter1 first_1,
0109                                        const Sentinel1 end_1,
0110                                        ForwardIter2 first_2,
0111                                        const Sentinel2 end_2,
0112                                        Comparator cmp ) {
0113             // TODO: no optimization for stronger iterators, because we would also have to constrain on sentinel vs not sentinel types
0114             // TODO: Comparator has to be "both sides", e.g. a == b => b == a
0115             // This skips shared prefix of the two ranges
0116             while (first_1 != end_1 && first_2 != end_2 && cmp(*first_1, *first_2)) {
0117                 ++first_1;
0118                 ++first_2;
0119             }
0120
0121             // We need to handle case where at least one of the ranges has no more elements
0122             if (first_1 == end_1 || first_2 == end_2) {
0123                 return first_1 == end_1 && first_2 == end_2;
0124             }
0125
0126             // pair counting is n**2, so we pay linear walk to compare the sizes first
0127             auto dist_1 = sentinel_distance( first_1, end_1 );
0128             auto dist_2 = sentinel_distance( first_2, end_2 );
0129
0130             if (dist_1 != dist_2) { return false; }
0131
0132             // Since we do not try to handle stronger iterators pair (e.g.
0133             // bidir) optimally, the only thing left to do is to check counts in
0134             // the remaining ranges.
0135             return check_element_counts( first_1, end_1, first_2, end_2, cmp );
0136         }
0137
0138     } // namespace Detail
0139 } // namespace Catch
0140
0141 #endif // CATCH_IS_PERMUTATION_HPP_INCLUDED