1 | /* |
2 | Copyright (c) Marshall Clow 2011-2012. |
3 | |
4 | Distributed under the Boost Software License, Version 1.0. (See accompanying |
5 | file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) |
6 | |
7 | For more information, see http://www.boost.org |
8 | */ |
9 | |
10 | #include <iostream> |
11 | |
12 | #include <boost/config.hpp> |
13 | #include <boost/algorithm/cxx11/is_permutation.hpp> |
14 | #include <boost/algorithm/cxx14/is_permutation.hpp> |
15 | |
16 | #define BOOST_TEST_MAIN |
17 | #include <boost/test/unit_test.hpp> |
18 | |
19 | #include <string> |
20 | #include <vector> |
21 | #include <list> |
22 | |
23 | #include "iterator_test.hpp" |
24 | |
25 | template <typename T> |
26 | bool eq ( const T& a, const T& b ) { return a == b; } |
27 | |
28 | template <typename T> |
29 | bool never_eq ( const T&, const T& ) { return false; } |
30 | |
31 | namespace ba = boost::algorithm; |
32 | |
33 | void test_sequence1 () { |
34 | int num[] = { 1, 1, 2, 3, 5 }; |
35 | const int sz = sizeof (num)/sizeof(num[0]); |
36 | |
37 | // Empty sequences |
38 | BOOST_CHECK ( |
39 | ba::is_permutation ( |
40 | forward_iterator<int *>(num), forward_iterator<int *>(num), |
41 | forward_iterator<int *>(num))); |
42 | BOOST_CHECK ( |
43 | ba::is_permutation ( |
44 | forward_iterator<int *>(num), forward_iterator<int *>(num), |
45 | forward_iterator<int *>(num), forward_iterator<int *>(num))); |
46 | BOOST_CHECK ( |
47 | ba::is_permutation ( |
48 | random_access_iterator<int *>(num), random_access_iterator<int *>(num), |
49 | random_access_iterator<int *>(num), random_access_iterator<int *>(num))); |
50 | BOOST_CHECK ( |
51 | ba::is_permutation ( |
52 | forward_iterator<int *>(num), forward_iterator<int *>(num), |
53 | forward_iterator<int *>(num), |
54 | never_eq<int> )); // Since the sequences are empty, the pred is never called |
55 | |
56 | // Empty vs. non-empty |
57 | BOOST_CHECK ( ! |
58 | ba::is_permutation ( |
59 | forward_iterator<int *>(num), forward_iterator<int *>(num), |
60 | forward_iterator<int *>(num), forward_iterator<int *>(num + 1))); |
61 | |
62 | BOOST_CHECK ( ! |
63 | ba::is_permutation ( |
64 | forward_iterator<int *>(num + 1), forward_iterator<int *>(num + 2), |
65 | forward_iterator<int *>(num), forward_iterator<int *>(num))); |
66 | |
67 | BOOST_CHECK ( ! |
68 | ba::is_permutation ( |
69 | random_access_iterator<int *>(num + 1), random_access_iterator<int *>(num + 2), |
70 | random_access_iterator<int *>(num), random_access_iterator<int *>(num))); |
71 | |
72 | BOOST_CHECK ( ! |
73 | ba::is_permutation ( |
74 | random_access_iterator<int *>(num), random_access_iterator<int *>(num), |
75 | random_access_iterator<int *>(num + 1), random_access_iterator<int *>(num + 2))); |
76 | |
77 | // Something should be a permutation of itself |
78 | BOOST_CHECK ( |
79 | ba::is_permutation ( |
80 | forward_iterator<int *>(num), forward_iterator<int *>(num + sz), |
81 | forward_iterator<int *>(num))); |
82 | BOOST_CHECK ( |
83 | ba::is_permutation ( |
84 | forward_iterator<int *>(num), forward_iterator<int *>(num + sz), |
85 | forward_iterator<int *>(num), eq<int> )); |
86 | BOOST_CHECK ( |
87 | ba::is_permutation ( |
88 | forward_iterator<int *>(num), forward_iterator<int *>(num + sz), |
89 | forward_iterator<int *>(num), forward_iterator<int *>(num + sz ))); |
90 | BOOST_CHECK ( |
91 | ba::is_permutation ( |
92 | forward_iterator<int *>(num), forward_iterator<int *>(num + sz), |
93 | forward_iterator<int *>(num), forward_iterator<int *>(num + sz ), |
94 | eq<int> )); |
95 | |
96 | BOOST_CHECK ( |
97 | ba::is_permutation ( |
98 | random_access_iterator<int *>(num), random_access_iterator<int *>(num + sz), |
99 | random_access_iterator<int *>(num), random_access_iterator<int *>(num + sz))); |
100 | BOOST_CHECK ( |
101 | ba::is_permutation ( |
102 | random_access_iterator<int *>(num), random_access_iterator<int *>(num + sz), |
103 | random_access_iterator<int *>(num), random_access_iterator<int *>(num + sz), |
104 | eq<int> )); |
105 | BOOST_CHECK ( |
106 | ba::is_permutation ( |
107 | random_access_iterator<int *>(num), random_access_iterator<int *>(num + sz), |
108 | forward_iterator<int *>(num), forward_iterator<int *>(num + sz), |
109 | eq<int> )); |
110 | |
111 | |
112 | std::vector<int> v, v1; |
113 | |
114 | v.clear (); |
115 | for ( std::size_t i = 5; i < 15; ++i ) |
116 | v.push_back ( x: i ); |
117 | v1 = v; |
118 | BOOST_CHECK ( ba::is_permutation ( v.begin (), v.end (), v.begin ())); // better be a permutation of itself! |
119 | BOOST_CHECK ( ba::is_permutation ( v.begin (), v.end (), v1.begin ())); |
120 | |
121 | // With bidirectional iterators. |
122 | std::list<int> l; |
123 | std::copy ( first: v.begin (), last: v.end (), result: std::back_inserter ( x&: l )); |
124 | BOOST_CHECK ( ba::is_permutation ( l.begin (), l.end (), l.begin ())); // better be a permutation of itself! |
125 | BOOST_CHECK ( ba::is_permutation ( l.begin (), l.end (), v1.begin ())); |
126 | for ( std::size_t i = 0; i < l.size (); ++i ) { |
127 | l.push_back ( x: *l.begin ()); l.pop_front (); // rotation |
128 | BOOST_CHECK ( ba::is_permutation ( l.begin (), l.end (), v1.begin ())); |
129 | } |
130 | } |
131 | |
132 | |
133 | BOOST_AUTO_TEST_CASE( test_main ) |
134 | { |
135 | test_sequence1 (); |
136 | } |
137 | |