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>
eq(const T & a,const T & b)26 bool eq ( const T& a, const T& b ) { return a == b; }
27
28 template <typename T>
never_eq(const T &,const T &)29 bool never_eq ( const T&, const T& ) { return false; }
30
31 namespace ba = boost::algorithm;
32
test_sequence1()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 ( 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 ( v.begin (), v.end (), std::back_inserter ( 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 ( *l.begin ()); l.pop_front (); // rotation
128 BOOST_CHECK ( ba::is_permutation ( l.begin (), l.end (), v1.begin ()));
129 }
130 }
131
132
BOOST_AUTO_TEST_CASE(test_main)133 BOOST_AUTO_TEST_CASE( test_main )
134 {
135 test_sequence1 ();
136 }
137