Back to home page

EIC code displayed by LXR

 
 

    


File indexing completed on 2025-01-30 10:02:49

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