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