1 // Range v3 library
2 //
3 // Copyright Eric Niebler 2014-present
4 //
5 // Use, modification and distribution is subject to the
6 // Boost Software License, Version 1.0. (See accompanying
7 // file LICENSE_1_0.txt or copy at
8 // http://www.boost.org/LICENSE_1_0.txt)
9 //
10 // Project home: https://github.com/ericniebler/range-v3
11 //
12 // Copyright 2005 - 2007 Adobe Systems Incorporated
13 // Distributed under the MIT License(see accompanying file LICENSE_1_0_0.txt
14 // or a copy at http://stlab.adobe.com/licenses.html)
15
16 //===----------------------------------------------------------------------===//
17 //
18 // The LLVM Compiler Infrastructure
19 //
20 // This file is dual licensed under the MIT and the University of Illinois Open
21 // Source Licenses. See LICENSE.TXT for details.
22 //
23 //===----------------------------------------------------------------------===//
24
25 #include <cstring>
26 #include <utility>
27 #include <algorithm>
28 #include <range/v3/core.hpp>
29 #include <range/v3/algorithm/permutation.hpp>
30 #include "../simple_test.hpp"
31 #include "../test_utils.hpp"
32 #include "../test_iterators.hpp"
33
factorial(int x)34 int factorial(int x)
35 {
36 int r = 1;
37 for (; x; --x)
38 r *= x;
39 return r;
40 }
41
42 template<typename Iter, typename Sent = Iter>
test_iter()43 void test_iter()
44 {
45 int ia[] = {1, 2, 3, 4, 5, 6};
46 const int sa = sizeof(ia)/sizeof(ia[0]);
47 int prev[sa];
48 for (int e = 0; e <= sa; ++e)
49 {
50 int count = 0;
51 bool x;
52 do
53 {
54 std::copy(ia, ia+e, prev);
55 x = ranges::next_permutation(Iter(ia), Sent(ia+e));
56 if(e > 1)
57 {
58 if(x)
59 CHECK(std::lexicographical_compare(prev, prev+e, ia, ia+e));
60 else
61 CHECK(std::lexicographical_compare(ia, ia+e, prev, prev+e));
62 }
63 ++count;
64 } while(x);
65 CHECK(count == factorial(e));
66 }
67 }
68
69 template<typename Iter, typename Sent = Iter>
test_range()70 void test_range()
71 {
72 int ia[] = {1, 2, 3, 4, 5, 6};
73 const int sa = sizeof(ia)/sizeof(ia[0]);
74 int prev[sa];
75 for (int e = 0; e <= sa; ++e)
76 {
77 int count = 0;
78 bool x;
79 do
80 {
81 std::copy(ia, ia+e, prev);
82 x = ranges::next_permutation(ranges::make_subrange(Iter(ia), Sent(ia+e)));
83 if(e > 1)
84 {
85 if(x)
86 CHECK(std::lexicographical_compare(prev, prev+e, ia, ia+e));
87 else
88 CHECK(std::lexicographical_compare(ia, ia+e, prev, prev+e));
89 }
90 ++count;
91 } while(x);
92 CHECK(count == factorial(e));
93 }
94 }
95
96 template<typename Iter, typename Sent = Iter>
test_iter_comp()97 void test_iter_comp()
98 {
99 typedef std::greater<int> C;
100 int ia[] = {6, 5, 4, 3, 2, 1};
101 const int sa = sizeof(ia)/sizeof(ia[0]);
102 int prev[sa];
103 for(int e = 0; e <= sa; ++e)
104 {
105 int count = 0;
106 bool x;
107 do
108 {
109 std::copy(ia, ia+e, prev);
110 x = ranges::next_permutation(Iter(ia), Sent(ia+e), C());
111 if(e > 1)
112 {
113 if (x)
114 CHECK(std::lexicographical_compare(prev, prev+e, ia, ia+e, C()));
115 else
116 CHECK(std::lexicographical_compare(ia, ia+e, prev, prev+e, C()));
117 }
118 ++count;
119 } while (x);
120 CHECK(count == factorial(e));
121 }
122 }
123
124 template<typename Iter, typename Sent = Iter>
test_range_comp()125 void test_range_comp()
126 {
127 typedef std::greater<int> C;
128 int ia[] = {6, 5, 4, 3, 2, 1};
129 const int sa = sizeof(ia)/sizeof(ia[0]);
130 int prev[sa];
131 for(int e = 0; e <= sa; ++e)
132 {
133 int count = 0;
134 bool x;
135 do
136 {
137 std::copy(ia, ia+e, prev);
138 x = ranges::next_permutation(ranges::make_subrange(Iter(ia), Sent(ia+e)), C());
139 if(e > 1)
140 {
141 if (x)
142 CHECK(std::lexicographical_compare(prev, prev+e, ia, ia+e, C()));
143 else
144 CHECK(std::lexicographical_compare(ia, ia+e, prev, prev+e, C()));
145 }
146 ++count;
147 } while (x);
148 CHECK(count == factorial(e));
149 }
150 }
151
152 struct c_str
153 {
154 char const * value;
155
operator ==(c_str a,c_str b)156 friend bool operator==(c_str a, c_str b)
157 {
158 return 0 == std::strcmp(a.value, b.value);
159 }
160
operator !=(c_str a,c_str b)161 friend bool operator!=(c_str a, c_str b)
162 {
163 return !(a == b);
164 }
165 };
166
167 // For debugging the projection test
operator <<(std::ostream & sout,std::pair<int,c_str> p)168 std::ostream &operator<<(std::ostream& sout, std::pair<int, c_str> p)
169 {
170 return sout << "{" << p.first << "," << p.second.value << "}";
171 }
172
main()173 int main()
174 {
175 test_iter<BidirectionalIterator<int*> >();
176 test_iter<RandomAccessIterator<int*> >();
177 test_iter<int*>();
178
179 test_iter<BidirectionalIterator<int*>, Sentinel<int*> >();
180 test_iter<RandomAccessIterator<int*>, Sentinel<int*> >();
181
182 test_iter_comp<BidirectionalIterator<int*> >();
183 test_iter_comp<RandomAccessIterator<int*> >();
184 test_iter_comp<int*>();
185
186 test_iter_comp<BidirectionalIterator<int*>, Sentinel<int*> >();
187 test_iter_comp<RandomAccessIterator<int*>, Sentinel<int*> >();
188
189 test_range<BidirectionalIterator<int*> >();
190 test_range<RandomAccessIterator<int*> >();
191 test_range<int*>();
192
193 test_range<BidirectionalIterator<int*>, Sentinel<int*> >();
194 test_range<RandomAccessIterator<int*>, Sentinel<int*> >();
195
196 test_range_comp<BidirectionalIterator<int*> >();
197 test_range_comp<RandomAccessIterator<int*> >();
198 test_range_comp<int*>();
199
200 test_range_comp<BidirectionalIterator<int*>, Sentinel<int*> >();
201 test_range_comp<RandomAccessIterator<int*>, Sentinel<int*> >();
202
203 // Test projection
204
205 using C = std::greater<int>;
206 using I = std::initializer_list<std::pair<int, c_str>>;
207 std::pair<int, c_str> ia[] = {{6, {"six"}}, {5,{"five"}}, {4,{"four"}}, {3,{"three"}}, {2,{"two"}}, {1,{"one"}}};
208 CHECK(ranges::next_permutation(ia, C(), &std::pair<int,c_str>::first));
209 ::check_equal(ia, I{{6, {"six"}}, {5,{"five"}}, {4,{"four"}}, {3,{"three"}}, {1,{"one"}}, {2,{"two"}}});
210 CHECK(ranges::next_permutation(ia, C(), &std::pair<int,c_str>::first));
211 ::check_equal(ia, I{{6, {"six"}}, {5,{"five"}}, {4,{"four"}}, {2,{"two"}}, {3,{"three"}}, {1,{"one"}}});
212 CHECK(ranges::next_permutation(ia, C(), &std::pair<int,c_str>::first));
213 ::check_equal(ia, I{{6, {"six"}}, {5,{"five"}}, {4,{"four"}}, {2,{"two"}}, {1,{"one"}}, {3,{"three"}}});
214 // etc..
215
216 return ::test_result();
217 }
218