"Fossies" - the Fresh Open Source Software Archive 
Member "abseil-cpp-20230802.1/absl/algorithm/algorithm_test.cc" (18 Sep 2023, 6157 Bytes) of package /linux/misc/abseil-cpp-20230802.1.tar.gz:
As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style:
standard) with prefixed line numbers and
code folding option.
Alternatively you can here
view or
download the uninterpreted source code file.
For more information about "algorithm_test.cc" see the
Fossies "Dox" file reference documentation.
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 #include "absl/base/config.h"
24
25 namespace {
26
27 TEST(EqualTest, DefaultComparisonRandomAccess) {
28 std::vector<int> v1{1, 2, 3};
29 std::vector<int> v2 = v1;
30 std::vector<int> v3 = {1, 2};
31 std::vector<int> v4 = {1, 2, 4};
32
33 EXPECT_TRUE(absl::equal(v1.begin(), v1.end(), v2.begin(), v2.end()));
34 EXPECT_FALSE(absl::equal(v1.begin(), v1.end(), v3.begin(), v3.end()));
35 EXPECT_FALSE(absl::equal(v1.begin(), v1.end(), v4.begin(), v4.end()));
36 }
37
38 TEST(EqualTest, DefaultComparison) {
39 std::list<int> lst1{1, 2, 3};
40 std::list<int> lst2 = lst1;
41 std::list<int> lst3{1, 2};
42 std::list<int> lst4{1, 2, 4};
43
44 EXPECT_TRUE(absl::equal(lst1.begin(), lst1.end(), lst2.begin(), lst2.end()));
45 EXPECT_FALSE(absl::equal(lst1.begin(), lst1.end(), lst3.begin(), lst3.end()));
46 EXPECT_FALSE(absl::equal(lst1.begin(), lst1.end(), lst4.begin(), lst4.end()));
47 }
48
49 TEST(EqualTest, EmptyRange) {
50 std::vector<int> v1{1, 2, 3};
51 std::vector<int> empty1;
52 std::vector<int> empty2;
53
54 // https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105705
55 #if ABSL_INTERNAL_HAVE_MIN_GNUC_VERSION(12, 0)
56 #pragma GCC diagnostic push
57 #pragma GCC diagnostic ignored "-Wnonnull"
58 #endif
59 EXPECT_FALSE(absl::equal(v1.begin(), v1.end(), empty1.begin(), empty1.end()));
60 #if ABSL_INTERNAL_HAVE_MIN_GNUC_VERSION(12, 0)
61 #pragma GCC diagnostic pop
62 #endif
63 EXPECT_FALSE(absl::equal(empty1.begin(), empty1.end(), v1.begin(), v1.end()));
64 EXPECT_TRUE(
65 absl::equal(empty1.begin(), empty1.end(), empty2.begin(), empty2.end()));
66 }
67
68 TEST(EqualTest, MixedIterTypes) {
69 std::vector<int> v1{1, 2, 3};
70 std::list<int> lst1{v1.begin(), v1.end()};
71 std::list<int> lst2{1, 2, 4};
72 std::list<int> lst3{1, 2};
73
74 EXPECT_TRUE(absl::equal(v1.begin(), v1.end(), lst1.begin(), lst1.end()));
75 EXPECT_FALSE(absl::equal(v1.begin(), v1.end(), lst2.begin(), lst2.end()));
76 EXPECT_FALSE(absl::equal(v1.begin(), v1.end(), lst3.begin(), lst3.end()));
77 }
78
79 TEST(EqualTest, MixedValueTypes) {
80 std::vector<int> v1{1, 2, 3};
81 std::vector<char> v2{1, 2, 3};
82 std::vector<char> v3{1, 2};
83 std::vector<char> v4{1, 2, 4};
84
85 EXPECT_TRUE(absl::equal(v1.begin(), v1.end(), v2.begin(), v2.end()));
86 EXPECT_FALSE(absl::equal(v1.begin(), v1.end(), v3.begin(), v3.end()));
87 EXPECT_FALSE(absl::equal(v1.begin(), v1.end(), v4.begin(), v4.end()));
88 }
89
90 TEST(EqualTest, WeirdIterators) {
91 std::vector<bool> v1{true, false};
92 std::vector<bool> v2 = v1;
93 std::vector<bool> v3{true};
94 std::vector<bool> v4{true, true, true};
95
96 EXPECT_TRUE(absl::equal(v1.begin(), v1.end(), v2.begin(), v2.end()));
97 EXPECT_FALSE(absl::equal(v1.begin(), v1.end(), v3.begin(), v3.end()));
98 EXPECT_FALSE(absl::equal(v1.begin(), v1.end(), v4.begin(), v4.end()));
99 }
100
101 TEST(EqualTest, CustomComparison) {
102 int n[] = {1, 2, 3, 4};
103 std::vector<int*> v1{&n[0], &n[1], &n[2]};
104 std::vector<int*> v2 = v1;
105 std::vector<int*> v3{&n[0], &n[1], &n[3]};
106 std::vector<int*> v4{&n[0], &n[1]};
107
108 auto eq = [](int* a, int* b) { return *a == *b; };
109
110 EXPECT_TRUE(absl::equal(v1.begin(), v1.end(), v2.begin(), v2.end(), eq));
111 EXPECT_FALSE(absl::equal(v1.begin(), v1.end(), v3.begin(), v3.end(), eq));
112 EXPECT_FALSE(absl::equal(v1.begin(), v1.end(), v4.begin(), v4.end(), eq));
113 }
114
115 TEST(EqualTest, MoveOnlyPredicate) {
116 std::vector<int> v1{1, 2, 3};
117 std::vector<int> v2{4, 5, 6};
118
119 // move-only equality predicate
120 struct Eq {
121 Eq() = default;
122 Eq(Eq &&) = default;
123 Eq(const Eq &) = delete;
124 Eq &operator=(const Eq &) = delete;
125 bool operator()(const int a, const int b) const { return a == b; }
126 };
127
128 EXPECT_TRUE(absl::equal(v1.begin(), v1.end(), v1.begin(), v1.end(), Eq()));
129 EXPECT_FALSE(absl::equal(v1.begin(), v1.end(), v2.begin(), v2.end(), Eq()));
130 }
131
132 struct CountingTrivialPred {
133 int* count;
134 bool operator()(int, int) const {
135 ++*count;
136 return true;
137 }
138 };
139
140 TEST(EqualTest, RandomAccessComplexity) {
141 std::vector<int> v1{1, 1, 3};
142 std::vector<int> v2 = v1;
143 std::vector<int> v3{1, 2};
144
145 do {
146 int count = 0;
147 absl::equal(v1.begin(), v1.end(), v2.begin(), v2.end(),
148 CountingTrivialPred{&count});
149 EXPECT_LE(count, 3);
150 } while (std::next_permutation(v2.begin(), v2.end()));
151
152 int count = 0;
153 absl::equal(v1.begin(), v1.end(), v3.begin(), v3.end(),
154 CountingTrivialPred{&count});
155 EXPECT_EQ(count, 0);
156 }
157
158 class LinearSearchTest : public testing::Test {
159 protected:
160 LinearSearchTest() : container_{1, 2, 3} {}
161
162 static bool Is3(int n) { return n == 3; }
163 static bool Is4(int n) { return n == 4; }
164
165 std::vector<int> container_;
166 };
167
168 TEST_F(LinearSearchTest, linear_search) {
169 EXPECT_TRUE(absl::linear_search(container_.begin(), container_.end(), 3));
170 EXPECT_FALSE(absl::linear_search(container_.begin(), container_.end(), 4));
171 }
172
173 TEST_F(LinearSearchTest, linear_searchConst) {
174 const std::vector<int> *const const_container = &container_;
175 EXPECT_TRUE(
176 absl::linear_search(const_container->begin(), const_container->end(), 3));
177 EXPECT_FALSE(
178 absl::linear_search(const_container->begin(), const_container->end(), 4));
179 }
180
181 TEST(RotateTest, Rotate) {
182 std::vector<int> v{0, 1, 2, 3, 4};
183 EXPECT_EQ(*absl::rotate(v.begin(), v.begin() + 2, v.end()), 0);
184 EXPECT_THAT(v, testing::ElementsAreArray({2, 3, 4, 0, 1}));
185
186 std::list<int> l{0, 1, 2, 3, 4};
187 EXPECT_EQ(*absl::rotate(l.begin(), std::next(l.begin(), 3), l.end()), 0);
188 EXPECT_THAT(l, testing::ElementsAreArray({3, 4, 0, 1, 2}));
189 }
190
191 } // namespace