algorithm_test.cc
Go to the documentation of this file.
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 
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 
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 
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 
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 
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 
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 
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 
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 
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;
125  bool operator()(int, int) const {
126  ++*count;
127  return true;
128  }
129 };
130 
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:
151  LinearSearchTest() : container_{1, 2, 3} {}
152 
153  static bool Is3(int n) { return n == 3; }
154  static bool Is4(int n) { return n == 4; }
155 
156  std::vector<int> container_;
157 };
158 
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 
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 
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
int v
Definition: variant_test.cc:81
AllocList * next[kMaxLevel]
TEST_F(GraphCyclesTest, NoCycle)
static uint64_t Rotate(uint64_t val, int shift)
Definition: city.cc:195
bool linear_search(InputIterator first, InputIterator last, const EqualityComparable &value)
Definition: algorithm.h:124
bool equal(InputIter1 first1, InputIter1 last1, InputIter2 first2, InputIter2 last2, Pred &&pred)
Definition: algorithm.h:99
ForwardIterator rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last)
Definition: algorithm.h:140
TEST(Symbolize, Unimplemented)
uint64_t b
Definition: layout_test.cc:50
hash_default_eq< typename T::first_type > eq


abseil_cpp
Author(s):
autogenerated on Mon Feb 28 2022 21:31:17