1 // Copyright 2012 The Chromium Authors
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "base/stl_util.h"
6
7 #include <array>
8 #include <deque>
9 #include <forward_list>
10 #include <functional>
11 #include <initializer_list>
12 #include <iterator>
13 #include <list>
14 #include <queue>
15 #include <set>
16 #include <stack>
17 #include <string>
18 #include <type_traits>
19 #include <unordered_set>
20 #include <vector>
21
22 #include "base/containers/cxx20_erase_vector.h"
23 #include "base/containers/queue.h"
24 #include "testing/gmock/include/gmock/gmock.h"
25 #include "testing/gtest/include/gtest/gtest.h"
26 #include "third_party/abseil-cpp/absl/types/optional.h"
27
28 namespace base {
29 namespace {
30
TEST(STLUtilTest,GetUnderlyingContainer)31 TEST(STLUtilTest, GetUnderlyingContainer) {
32 {
33 std::queue<int> queue({1, 2, 3, 4, 5});
34 static_assert(std::is_same_v<decltype(GetUnderlyingContainer(queue)),
35 const std::deque<int>&>,
36 "GetUnderlyingContainer(queue) should be of type deque");
37 EXPECT_THAT(GetUnderlyingContainer(queue),
38 testing::ElementsAre(1, 2, 3, 4, 5));
39 }
40
41 {
42 std::queue<int> queue;
43 EXPECT_THAT(GetUnderlyingContainer(queue), testing::ElementsAre());
44 }
45
46 {
47 base::queue<int> queue({1, 2, 3, 4, 5});
48 static_assert(
49 std::is_same_v<decltype(GetUnderlyingContainer(queue)),
50 const base::circular_deque<int>&>,
51 "GetUnderlyingContainer(queue) should be of type circular_deque");
52 EXPECT_THAT(GetUnderlyingContainer(queue),
53 testing::ElementsAre(1, 2, 3, 4, 5));
54 }
55
56 {
57 std::vector<int> values = {1, 2, 3, 4, 5};
58 std::priority_queue<int> queue(values.begin(), values.end());
59 static_assert(std::is_same_v<decltype(GetUnderlyingContainer(queue)),
60 const std::vector<int>&>,
61 "GetUnderlyingContainer(queue) should be of type vector");
62 EXPECT_THAT(GetUnderlyingContainer(queue),
63 testing::UnorderedElementsAre(1, 2, 3, 4, 5));
64 }
65
66 {
67 std::stack<int> stack({1, 2, 3, 4, 5});
68 static_assert(std::is_same_v<decltype(GetUnderlyingContainer(stack)),
69 const std::deque<int>&>,
70 "GetUnderlyingContainer(stack) should be of type deque");
71 EXPECT_THAT(GetUnderlyingContainer(stack),
72 testing::ElementsAre(1, 2, 3, 4, 5));
73 }
74 }
75
TEST(STLUtilTest,STLSetDifference)76 TEST(STLUtilTest, STLSetDifference) {
77 std::set<int> a1;
78 a1.insert(1);
79 a1.insert(2);
80 a1.insert(3);
81 a1.insert(4);
82
83 std::set<int> a2;
84 a2.insert(3);
85 a2.insert(4);
86 a2.insert(5);
87 a2.insert(6);
88 a2.insert(7);
89
90 {
91 std::set<int> difference;
92 difference.insert(1);
93 difference.insert(2);
94 EXPECT_EQ(difference, STLSetDifference<std::set<int> >(a1, a2));
95 }
96
97 {
98 std::set<int> difference;
99 difference.insert(5);
100 difference.insert(6);
101 difference.insert(7);
102 EXPECT_EQ(difference, STLSetDifference<std::set<int> >(a2, a1));
103 }
104
105 {
106 std::vector<int> difference;
107 difference.push_back(1);
108 difference.push_back(2);
109 EXPECT_EQ(difference, STLSetDifference<std::vector<int> >(a1, a2));
110 }
111
112 {
113 std::vector<int> difference;
114 difference.push_back(5);
115 difference.push_back(6);
116 difference.push_back(7);
117 EXPECT_EQ(difference, STLSetDifference<std::vector<int> >(a2, a1));
118 }
119 }
120
TEST(STLUtilTest,STLSetUnion)121 TEST(STLUtilTest, STLSetUnion) {
122 std::set<int> a1;
123 a1.insert(1);
124 a1.insert(2);
125 a1.insert(3);
126 a1.insert(4);
127
128 std::set<int> a2;
129 a2.insert(3);
130 a2.insert(4);
131 a2.insert(5);
132 a2.insert(6);
133 a2.insert(7);
134
135 {
136 std::set<int> result;
137 result.insert(1);
138 result.insert(2);
139 result.insert(3);
140 result.insert(4);
141 result.insert(5);
142 result.insert(6);
143 result.insert(7);
144 EXPECT_EQ(result, STLSetUnion<std::set<int> >(a1, a2));
145 }
146
147 {
148 std::set<int> result;
149 result.insert(1);
150 result.insert(2);
151 result.insert(3);
152 result.insert(4);
153 result.insert(5);
154 result.insert(6);
155 result.insert(7);
156 EXPECT_EQ(result, STLSetUnion<std::set<int> >(a2, a1));
157 }
158
159 {
160 std::vector<int> result;
161 result.push_back(1);
162 result.push_back(2);
163 result.push_back(3);
164 result.push_back(4);
165 result.push_back(5);
166 result.push_back(6);
167 result.push_back(7);
168 EXPECT_EQ(result, STLSetUnion<std::vector<int> >(a1, a2));
169 }
170
171 {
172 std::vector<int> result;
173 result.push_back(1);
174 result.push_back(2);
175 result.push_back(3);
176 result.push_back(4);
177 result.push_back(5);
178 result.push_back(6);
179 result.push_back(7);
180 EXPECT_EQ(result, STLSetUnion<std::vector<int> >(a2, a1));
181 }
182 }
183
TEST(STLUtilTest,STLSetIntersection)184 TEST(STLUtilTest, STLSetIntersection) {
185 std::set<int> a1;
186 a1.insert(1);
187 a1.insert(2);
188 a1.insert(3);
189 a1.insert(4);
190
191 std::set<int> a2;
192 a2.insert(3);
193 a2.insert(4);
194 a2.insert(5);
195 a2.insert(6);
196 a2.insert(7);
197
198 {
199 std::set<int> result;
200 result.insert(3);
201 result.insert(4);
202 EXPECT_EQ(result, STLSetIntersection<std::set<int> >(a1, a2));
203 }
204
205 {
206 std::set<int> result;
207 result.insert(3);
208 result.insert(4);
209 EXPECT_EQ(result, STLSetIntersection<std::set<int> >(a2, a1));
210 }
211
212 {
213 std::vector<int> result;
214 result.push_back(3);
215 result.push_back(4);
216 EXPECT_EQ(result, STLSetIntersection<std::vector<int> >(a1, a2));
217 }
218
219 {
220 std::vector<int> result;
221 result.push_back(3);
222 result.push_back(4);
223 EXPECT_EQ(result, STLSetIntersection<std::vector<int> >(a2, a1));
224 }
225 }
226
TEST(Erase,IsNotIn)227 TEST(Erase, IsNotIn) {
228 // Should keep both '2' but only one '4', like std::set_intersection.
229 std::vector<int> lhs = {0, 2, 2, 4, 4, 4, 6, 8, 10};
230 std::vector<int> rhs = {1, 2, 2, 4, 5, 6, 7};
231 std::vector<int> expected = {2, 2, 4, 6};
232 EXPECT_EQ(5u, EraseIf(lhs, IsNotIn<std::vector<int>>(rhs)));
233 EXPECT_EQ(expected, lhs);
234 }
235
236 } // namespace
237 } // namespace base
238