1 // Copyright 2017 The Abseil Authors.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #include "absl/algorithm/algorithm.h"
16
17 #include <algorithm>
18 #include <list>
19 #include <vector>
20
21 #include "gmock/gmock.h"
22 #include "gtest/gtest.h"
23
24 namespace {
25
TEST(EqualTest,DefaultComparisonRandomAccess)26 TEST(EqualTest, DefaultComparisonRandomAccess) {
27 std::vector<int> v1{1, 2, 3};
28 std::vector<int> v2 = v1;
29 std::vector<int> v3 = {1, 2};
30 std::vector<int> v4 = {1, 2, 4};
31
32 EXPECT_TRUE(absl::equal(v1.begin(), v1.end(), v2.begin(), v2.end()));
33 EXPECT_FALSE(absl::equal(v1.begin(), v1.end(), v3.begin(), v3.end()));
34 EXPECT_FALSE(absl::equal(v1.begin(), v1.end(), v4.begin(), v4.end()));
35 }
36
TEST(EqualTest,DefaultComparison)37 TEST(EqualTest, DefaultComparison) {
38 std::list<int> lst1{1, 2, 3};
39 std::list<int> lst2 = lst1;
40 std::list<int> lst3{1, 2};
41 std::list<int> lst4{1, 2, 4};
42
43 EXPECT_TRUE(absl::equal(lst1.begin(), lst1.end(), lst2.begin(), lst2.end()));
44 EXPECT_FALSE(absl::equal(lst1.begin(), lst1.end(), lst3.begin(), lst3.end()));
45 EXPECT_FALSE(absl::equal(lst1.begin(), lst1.end(), lst4.begin(), lst4.end()));
46 }
47
TEST(EqualTest,EmptyRange)48 TEST(EqualTest, EmptyRange) {
49 std::vector<int> v1{1, 2, 3};
50 std::vector<int> empty1;
51 std::vector<int> empty2;
52
53 EXPECT_FALSE(absl::equal(v1.begin(), v1.end(), empty1.begin(), empty1.end()));
54 EXPECT_FALSE(absl::equal(empty1.begin(), empty1.end(), v1.begin(), v1.end()));
55 EXPECT_TRUE(
56 absl::equal(empty1.begin(), empty1.end(), empty2.begin(), empty2.end()));
57 }
58
TEST(EqualTest,MixedIterTypes)59 TEST(EqualTest, MixedIterTypes) {
60 std::vector<int> v1{1, 2, 3};
61 std::list<int> lst1{v1.begin(), v1.end()};
62 std::list<int> lst2{1, 2, 4};
63 std::list<int> lst3{1, 2};
64
65 EXPECT_TRUE(absl::equal(v1.begin(), v1.end(), lst1.begin(), lst1.end()));
66 EXPECT_FALSE(absl::equal(v1.begin(), v1.end(), lst2.begin(), lst2.end()));
67 EXPECT_FALSE(absl::equal(v1.begin(), v1.end(), lst3.begin(), lst3.end()));
68 }
69
TEST(EqualTest,MixedValueTypes)70 TEST(EqualTest, MixedValueTypes) {
71 std::vector<int> v1{1, 2, 3};
72 std::vector<char> v2{1, 2, 3};
73 std::vector<char> v3{1, 2};
74 std::vector<char> v4{1, 2, 4};
75
76 EXPECT_TRUE(absl::equal(v1.begin(), v1.end(), v2.begin(), v2.end()));
77 EXPECT_FALSE(absl::equal(v1.begin(), v1.end(), v3.begin(), v3.end()));
78 EXPECT_FALSE(absl::equal(v1.begin(), v1.end(), v4.begin(), v4.end()));
79 }
80
TEST(EqualTest,WeirdIterators)81 TEST(EqualTest, WeirdIterators) {
82 std::vector<bool> v1{true, false};
83 std::vector<bool> v2 = v1;
84 std::vector<bool> v3{true};
85 std::vector<bool> v4{true, true, true};
86
87 EXPECT_TRUE(absl::equal(v1.begin(), v1.end(), v2.begin(), v2.end()));
88 EXPECT_FALSE(absl::equal(v1.begin(), v1.end(), v3.begin(), v3.end()));
89 EXPECT_FALSE(absl::equal(v1.begin(), v1.end(), v4.begin(), v4.end()));
90 }
91
TEST(EqualTest,CustomComparison)92 TEST(EqualTest, CustomComparison) {
93 int n[] = {1, 2, 3, 4};
94 std::vector<int*> v1{&n[0], &n[1], &n[2]};
95 std::vector<int*> v2 = v1;
96 std::vector<int*> v3{&n[0], &n[1], &n[3]};
97 std::vector<int*> v4{&n[0], &n[1]};
98
99 auto eq = [](int* a, int* b) { return *a == *b; };
100
101 EXPECT_TRUE(absl::equal(v1.begin(), v1.end(), v2.begin(), v2.end(), eq));
102 EXPECT_FALSE(absl::equal(v1.begin(), v1.end(), v3.begin(), v3.end(), eq));
103 EXPECT_FALSE(absl::equal(v1.begin(), v1.end(), v4.begin(), v4.end(), eq));
104 }
105
TEST(EqualTest,MoveOnlyPredicate)106 TEST(EqualTest, MoveOnlyPredicate) {
107 std::vector<int> v1{1, 2, 3};
108 std::vector<int> v2{4, 5, 6};
109
110 // move-only equality predicate
111 struct Eq {
112 Eq() = default;
113 Eq(Eq &&) = default;
114 Eq(const Eq &) = delete;
115 Eq &operator=(const Eq &) = delete;
116 bool operator()(const int a, const int b) const { return a == b; }
117 };
118
119 EXPECT_TRUE(absl::equal(v1.begin(), v1.end(), v1.begin(), v1.end(), Eq()));
120 EXPECT_FALSE(absl::equal(v1.begin(), v1.end(), v2.begin(), v2.end(), Eq()));
121 }
122
123 struct CountingTrivialPred {
124 int* count;
operator ()__anon5b50e2f70111::CountingTrivialPred125 bool operator()(int, int) const {
126 ++*count;
127 return true;
128 }
129 };
130
TEST(EqualTest,RandomAccessComplexity)131 TEST(EqualTest, RandomAccessComplexity) {
132 std::vector<int> v1{1, 1, 3};
133 std::vector<int> v2 = v1;
134 std::vector<int> v3{1, 2};
135
136 do {
137 int count = 0;
138 absl::equal(v1.begin(), v1.end(), v2.begin(), v2.end(),
139 CountingTrivialPred{&count});
140 EXPECT_LE(count, 3);
141 } while (std::next_permutation(v2.begin(), v2.end()));
142
143 int count = 0;
144 absl::equal(v1.begin(), v1.end(), v3.begin(), v3.end(),
145 CountingTrivialPred{&count});
146 EXPECT_EQ(count, 0);
147 }
148
149 class LinearSearchTest : public testing::Test {
150 protected:
LinearSearchTest()151 LinearSearchTest() : container_{1, 2, 3} {}
152
Is3(int n)153 static bool Is3(int n) { return n == 3; }
Is4(int n)154 static bool Is4(int n) { return n == 4; }
155
156 std::vector<int> container_;
157 };
158
TEST_F(LinearSearchTest,linear_search)159 TEST_F(LinearSearchTest, linear_search) {
160 EXPECT_TRUE(absl::linear_search(container_.begin(), container_.end(), 3));
161 EXPECT_FALSE(absl::linear_search(container_.begin(), container_.end(), 4));
162 }
163
TEST_F(LinearSearchTest,linear_searchConst)164 TEST_F(LinearSearchTest, linear_searchConst) {
165 const std::vector<int> *const const_container = &container_;
166 EXPECT_TRUE(
167 absl::linear_search(const_container->begin(), const_container->end(), 3));
168 EXPECT_FALSE(
169 absl::linear_search(const_container->begin(), const_container->end(), 4));
170 }
171
TEST(RotateTest,Rotate)172 TEST(RotateTest, Rotate) {
173 std::vector<int> v{0, 1, 2, 3, 4};
174 EXPECT_EQ(*absl::rotate(v.begin(), v.begin() + 2, v.end()), 0);
175 EXPECT_THAT(v, testing::ElementsAreArray({2, 3, 4, 0, 1}));
176
177 std::list<int> l{0, 1, 2, 3, 4};
178 EXPECT_EQ(*absl::rotate(l.begin(), std::next(l.begin(), 3), l.end()), 0);
179 EXPECT_THAT(l, testing::ElementsAreArray({3, 4, 0, 1, 2}));
180 }
181
182 } // namespace
183