File indexing completed on 2025-01-30 10:02:49
0001
0002
0003
0004
0005
0006
0007
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
0081 const auto count_in_range_2 =
0082 count_sentinel( first_2, end_2, *cursor, cmp );
0083
0084
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
0111
0112
0113 while (first_1 != end_1 && first_2 != end_2 && cmp(*first_1, *first_2)) {
0114 ++first_1;
0115 ++first_2;
0116 }
0117
0118
0119 if (first_1 == end_1 || first_2 == end_2) {
0120 return first_1 == end_1 && first_2 == end_2;
0121 }
0122
0123
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
0130
0131
0132 return check_element_counts( first_1, end_1, first_2, end_2, cmp );
0133 }
0134
0135 }
0136 }
0137
0138 #endif