1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
|
// Copyright Catch2 Authors
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE.txt or copy at
// https://www.boost.org/LICENSE_1_0.txt)
// SPDX-License-Identifier: BSL-1.0
#ifndef CATCH_IS_PERMUTATION_HPP_INCLUDED
#define CATCH_IS_PERMUTATION_HPP_INCLUDED
#include <algorithm>
#include <iterator>
namespace Catch {
namespace Detail {
template <typename ForwardIter,
typename Sentinel,
typename T,
typename Comparator>
constexpr
ForwardIter find_sentinel( ForwardIter start,
Sentinel sentinel,
T const& value,
Comparator cmp ) {
while ( start != sentinel ) {
if ( cmp( *start, value ) ) { break; }
++start;
}
return start;
}
template <typename ForwardIter,
typename Sentinel,
typename T,
typename Comparator>
constexpr
std::ptrdiff_t count_sentinel( ForwardIter start,
Sentinel sentinel,
T const& value,
Comparator cmp ) {
std::ptrdiff_t count = 0;
while ( start != sentinel ) {
if ( cmp( *start, value ) ) { ++count; }
++start;
}
return count;
}
template <typename ForwardIter, typename Sentinel>
constexpr
std::enable_if_t<!std::is_same<ForwardIter, Sentinel>::value,
std::ptrdiff_t>
sentinel_distance( ForwardIter iter, const Sentinel sentinel ) {
std::ptrdiff_t dist = 0;
while ( iter != sentinel ) {
++iter;
++dist;
}
return dist;
}
template <typename ForwardIter>
constexpr std::ptrdiff_t sentinel_distance( ForwardIter first,
ForwardIter last ) {
return std::distance( first, last );
}
template <typename ForwardIter1,
typename Sentinel1,
typename ForwardIter2,
typename Sentinel2,
typename Comparator>
constexpr bool check_element_counts( ForwardIter1 first_1,
const Sentinel1 end_1,
ForwardIter2 first_2,
const Sentinel2 end_2,
Comparator cmp ) {
auto cursor = first_1;
while ( cursor != end_1 ) {
if ( find_sentinel( first_1, cursor, *cursor, cmp ) ==
cursor ) {
// we haven't checked this element yet
const auto count_in_range_2 =
count_sentinel( first_2, end_2, *cursor, cmp );
// Not a single instance in 2nd range, so it cannot be a
// permutation of 1st range
if ( count_in_range_2 == 0 ) { return false; }
const auto count_in_range_1 =
count_sentinel( cursor, end_1, *cursor, cmp );
if ( count_in_range_1 != count_in_range_2 ) {
return false;
}
}
++cursor;
}
return true;
}
template <typename ForwardIter1,
typename Sentinel1,
typename ForwardIter2,
typename Sentinel2,
typename Comparator>
constexpr bool is_permutation( ForwardIter1 first_1,
const Sentinel1 end_1,
ForwardIter2 first_2,
const Sentinel2 end_2,
Comparator cmp ) {
// TODO: no optimization for stronger iterators, because we would also have to constrain on sentinel vs not sentinel types
// TODO: Comparator has to be "both sides", e.g. a == b => b == a
// This skips shared prefix of the two ranges
while (first_1 != end_1 && first_2 != end_2 && cmp(*first_1, *first_2)) {
++first_1;
++first_2;
}
// We need to handle case where at least one of the ranges has no more elements
if (first_1 == end_1 || first_2 == end_2) {
return first_1 == end_1 && first_2 == end_2;
}
// pair counting is n**2, so we pay linear walk to compare the sizes first
auto dist_1 = sentinel_distance( first_1, end_1 );
auto dist_2 = sentinel_distance( first_2, end_2 );
if (dist_1 != dist_2) { return false; }
// Since we do not try to handle stronger iterators pair (e.g.
// bidir) optimally, the only thing left to do is to check counts in
// the remaining ranges.
return check_element_counts( first_1, end_1, first_2, end_2, cmp );
}
} // namespace Detail
} // namespace Catch
#endif // CATCH_IS_PERMUTATION_HPP_INCLUDED
|
