1//===- unittest/ADT/MapVectorTest.cpp - MapVector unit tests ----*- C++ -*-===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9
10#include "gtest/gtest.h"
11#include "llvm/ADT/MapVector.h"
12#include "llvm/ADT/iterator_range.h"
13#include <utility>
14
15using namespace llvm;
16
17TEST(MapVectorTest, swap) {
18  MapVector<int, int> MV1, MV2;
19  std::pair<MapVector<int, int>::iterator, bool> R;
20
21  R = MV1.insert(std::make_pair(1, 2));
22  ASSERT_EQ(R.first, MV1.begin());
23  EXPECT_EQ(R.first->first, 1);
24  EXPECT_EQ(R.first->second, 2);
25  EXPECT_TRUE(R.second);
26
27  EXPECT_FALSE(MV1.empty());
28  EXPECT_TRUE(MV2.empty());
29  MV2.swap(MV1);
30  EXPECT_TRUE(MV1.empty());
31  EXPECT_FALSE(MV2.empty());
32
33  auto I = MV1.find(1);
34  ASSERT_EQ(MV1.end(), I);
35
36  I = MV2.find(1);
37  ASSERT_EQ(I, MV2.begin());
38  EXPECT_EQ(I->first, 1);
39  EXPECT_EQ(I->second, 2);
40}
41
42TEST(MapVectorTest, insert_pop) {
43  MapVector<int, int> MV;
44  std::pair<MapVector<int, int>::iterator, bool> R;
45
46  R = MV.insert(std::make_pair(1, 2));
47  ASSERT_EQ(R.first, MV.begin());
48  EXPECT_EQ(R.first->first, 1);
49  EXPECT_EQ(R.first->second, 2);
50  EXPECT_TRUE(R.second);
51
52  R = MV.insert(std::make_pair(1, 3));
53  ASSERT_EQ(R.first, MV.begin());
54  EXPECT_EQ(R.first->first, 1);
55  EXPECT_EQ(R.first->second, 2);
56  EXPECT_FALSE(R.second);
57
58  R = MV.insert(std::make_pair(4, 5));
59  ASSERT_NE(R.first, MV.end());
60  EXPECT_EQ(R.first->first, 4);
61  EXPECT_EQ(R.first->second, 5);
62  EXPECT_TRUE(R.second);
63
64  EXPECT_EQ(MV.size(), 2u);
65  EXPECT_EQ(MV[1], 2);
66  EXPECT_EQ(MV[4], 5);
67
68  MV.pop_back();
69  EXPECT_EQ(MV.size(), 1u);
70  EXPECT_EQ(MV[1], 2);
71
72  R = MV.insert(std::make_pair(4, 7));
73  ASSERT_NE(R.first, MV.end());
74  EXPECT_EQ(R.first->first, 4);
75  EXPECT_EQ(R.first->second, 7);
76  EXPECT_TRUE(R.second);
77
78  EXPECT_EQ(MV.size(), 2u);
79  EXPECT_EQ(MV[1], 2);
80  EXPECT_EQ(MV[4], 7);
81}
82
83TEST(MapVectorTest, erase) {
84  MapVector<int, int> MV;
85
86  MV.insert(std::make_pair(1, 2));
87  MV.insert(std::make_pair(3, 4));
88  MV.insert(std::make_pair(5, 6));
89  ASSERT_EQ(MV.size(), 3u);
90
91  MV.erase(MV.find(1));
92  ASSERT_EQ(MV.size(), 2u);
93  ASSERT_EQ(MV.find(1), MV.end());
94  ASSERT_EQ(MV[3], 4);
95  ASSERT_EQ(MV[5], 6);
96
97  ASSERT_EQ(MV.erase(3), 1u);
98  ASSERT_EQ(MV.size(), 1u);
99  ASSERT_EQ(MV.find(3), MV.end());
100  ASSERT_EQ(MV[5], 6);
101
102  ASSERT_EQ(MV.erase(79), 0u);
103  ASSERT_EQ(MV.size(), 1u);
104}
105
106TEST(MapVectorTest, remove_if) {
107  MapVector<int, int> MV;
108
109  MV.insert(std::make_pair(1, 11));
110  MV.insert(std::make_pair(2, 12));
111  MV.insert(std::make_pair(3, 13));
112  MV.insert(std::make_pair(4, 14));
113  MV.insert(std::make_pair(5, 15));
114  MV.insert(std::make_pair(6, 16));
115  ASSERT_EQ(MV.size(), 6u);
116
117  MV.remove_if([](const std::pair<int, int> &Val) { return Val.second % 2; });
118  ASSERT_EQ(MV.size(), 3u);
119  ASSERT_EQ(MV.find(1), MV.end());
120  ASSERT_EQ(MV.find(3), MV.end());
121  ASSERT_EQ(MV.find(5), MV.end());
122  ASSERT_EQ(MV[2], 12);
123  ASSERT_EQ(MV[4], 14);
124  ASSERT_EQ(MV[6], 16);
125}
126
127TEST(MapVectorTest, iteration_test) {
128  MapVector<int, int> MV;
129
130  MV.insert(std::make_pair(1, 11));
131  MV.insert(std::make_pair(2, 12));
132  MV.insert(std::make_pair(3, 13));
133  MV.insert(std::make_pair(4, 14));
134  MV.insert(std::make_pair(5, 15));
135  MV.insert(std::make_pair(6, 16));
136  ASSERT_EQ(MV.size(), 6u);
137
138  int count = 1;
139  for (auto P : make_range(MV.begin(), MV.end())) {
140    ASSERT_EQ(P.first, count);
141    count++;
142  }
143
144  count = 6;
145  for (auto P : make_range(MV.rbegin(), MV.rend())) {
146    ASSERT_EQ(P.first, count);
147    count--;
148  }
149}
150
151TEST(SmallMapVectorSmallTest, insert_pop) {
152  SmallMapVector<int, int, 32> MV;
153  std::pair<SmallMapVector<int, int, 32>::iterator, bool> R;
154
155  R = MV.insert(std::make_pair(1, 2));
156  ASSERT_EQ(R.first, MV.begin());
157  EXPECT_EQ(R.first->first, 1);
158  EXPECT_EQ(R.first->second, 2);
159  EXPECT_TRUE(R.second);
160
161  R = MV.insert(std::make_pair(1, 3));
162  ASSERT_EQ(R.first, MV.begin());
163  EXPECT_EQ(R.first->first, 1);
164  EXPECT_EQ(R.first->second, 2);
165  EXPECT_FALSE(R.second);
166
167  R = MV.insert(std::make_pair(4, 5));
168  ASSERT_NE(R.first, MV.end());
169  EXPECT_EQ(R.first->first, 4);
170  EXPECT_EQ(R.first->second, 5);
171  EXPECT_TRUE(R.second);
172
173  EXPECT_EQ(MV.size(), 2u);
174  EXPECT_EQ(MV[1], 2);
175  EXPECT_EQ(MV[4], 5);
176
177  MV.pop_back();
178  EXPECT_EQ(MV.size(), 1u);
179  EXPECT_EQ(MV[1], 2);
180
181  R = MV.insert(std::make_pair(4, 7));
182  ASSERT_NE(R.first, MV.end());
183  EXPECT_EQ(R.first->first, 4);
184  EXPECT_EQ(R.first->second, 7);
185  EXPECT_TRUE(R.second);
186
187  EXPECT_EQ(MV.size(), 2u);
188  EXPECT_EQ(MV[1], 2);
189  EXPECT_EQ(MV[4], 7);
190}
191
192TEST(SmallMapVectorSmallTest, erase) {
193  SmallMapVector<int, int, 32> MV;
194
195  MV.insert(std::make_pair(1, 2));
196  MV.insert(std::make_pair(3, 4));
197  MV.insert(std::make_pair(5, 6));
198  ASSERT_EQ(MV.size(), 3u);
199
200  MV.erase(MV.find(1));
201  ASSERT_EQ(MV.size(), 2u);
202  ASSERT_EQ(MV.find(1), MV.end());
203  ASSERT_EQ(MV[3], 4);
204  ASSERT_EQ(MV[5], 6);
205
206  ASSERT_EQ(MV.erase(3), 1u);
207  ASSERT_EQ(MV.size(), 1u);
208  ASSERT_EQ(MV.find(3), MV.end());
209  ASSERT_EQ(MV[5], 6);
210
211  ASSERT_EQ(MV.erase(79), 0u);
212  ASSERT_EQ(MV.size(), 1u);
213}
214
215TEST(SmallMapVectorSmallTest, remove_if) {
216  SmallMapVector<int, int, 32> MV;
217
218  MV.insert(std::make_pair(1, 11));
219  MV.insert(std::make_pair(2, 12));
220  MV.insert(std::make_pair(3, 13));
221  MV.insert(std::make_pair(4, 14));
222  MV.insert(std::make_pair(5, 15));
223  MV.insert(std::make_pair(6, 16));
224  ASSERT_EQ(MV.size(), 6u);
225
226  MV.remove_if([](const std::pair<int, int> &Val) { return Val.second % 2; });
227  ASSERT_EQ(MV.size(), 3u);
228  ASSERT_EQ(MV.find(1), MV.end());
229  ASSERT_EQ(MV.find(3), MV.end());
230  ASSERT_EQ(MV.find(5), MV.end());
231  ASSERT_EQ(MV[2], 12);
232  ASSERT_EQ(MV[4], 14);
233  ASSERT_EQ(MV[6], 16);
234}
235
236TEST(SmallMapVectorSmallTest, iteration_test) {
237  SmallMapVector<int, int, 32> MV;
238
239  MV.insert(std::make_pair(1, 11));
240  MV.insert(std::make_pair(2, 12));
241  MV.insert(std::make_pair(3, 13));
242  MV.insert(std::make_pair(4, 14));
243  MV.insert(std::make_pair(5, 15));
244  MV.insert(std::make_pair(6, 16));
245  ASSERT_EQ(MV.size(), 6u);
246
247  int count = 1;
248  for (auto P : make_range(MV.begin(), MV.end())) {
249    ASSERT_EQ(P.first, count);
250    count++;
251  }
252
253  count = 6;
254  for (auto P : make_range(MV.rbegin(), MV.rend())) {
255    ASSERT_EQ(P.first, count);
256    count--;
257  }
258}
259
260TEST(SmallMapVectorLargeTest, insert_pop) {
261  SmallMapVector<int, int, 1> MV;
262  std::pair<SmallMapVector<int, int, 1>::iterator, bool> R;
263
264  R = MV.insert(std::make_pair(1, 2));
265  ASSERT_EQ(R.first, MV.begin());
266  EXPECT_EQ(R.first->first, 1);
267  EXPECT_EQ(R.first->second, 2);
268  EXPECT_TRUE(R.second);
269
270  R = MV.insert(std::make_pair(1, 3));
271  ASSERT_EQ(R.first, MV.begin());
272  EXPECT_EQ(R.first->first, 1);
273  EXPECT_EQ(R.first->second, 2);
274  EXPECT_FALSE(R.second);
275
276  R = MV.insert(std::make_pair(4, 5));
277  ASSERT_NE(R.first, MV.end());
278  EXPECT_EQ(R.first->first, 4);
279  EXPECT_EQ(R.first->second, 5);
280  EXPECT_TRUE(R.second);
281
282  EXPECT_EQ(MV.size(), 2u);
283  EXPECT_EQ(MV[1], 2);
284  EXPECT_EQ(MV[4], 5);
285
286  MV.pop_back();
287  EXPECT_EQ(MV.size(), 1u);
288  EXPECT_EQ(MV[1], 2);
289
290  R = MV.insert(std::make_pair(4, 7));
291  ASSERT_NE(R.first, MV.end());
292  EXPECT_EQ(R.first->first, 4);
293  EXPECT_EQ(R.first->second, 7);
294  EXPECT_TRUE(R.second);
295
296  EXPECT_EQ(MV.size(), 2u);
297  EXPECT_EQ(MV[1], 2);
298  EXPECT_EQ(MV[4], 7);
299}
300
301TEST(SmallMapVectorLargeTest, erase) {
302  SmallMapVector<int, int, 1> MV;
303
304  MV.insert(std::make_pair(1, 2));
305  MV.insert(std::make_pair(3, 4));
306  MV.insert(std::make_pair(5, 6));
307  ASSERT_EQ(MV.size(), 3u);
308
309  MV.erase(MV.find(1));
310  ASSERT_EQ(MV.size(), 2u);
311  ASSERT_EQ(MV.find(1), MV.end());
312  ASSERT_EQ(MV[3], 4);
313  ASSERT_EQ(MV[5], 6);
314
315  ASSERT_EQ(MV.erase(3), 1u);
316  ASSERT_EQ(MV.size(), 1u);
317  ASSERT_EQ(MV.find(3), MV.end());
318  ASSERT_EQ(MV[5], 6);
319
320  ASSERT_EQ(MV.erase(79), 0u);
321  ASSERT_EQ(MV.size(), 1u);
322}
323
324TEST(SmallMapVectorLargeTest, remove_if) {
325  SmallMapVector<int, int, 1> MV;
326
327  MV.insert(std::make_pair(1, 11));
328  MV.insert(std::make_pair(2, 12));
329  MV.insert(std::make_pair(3, 13));
330  MV.insert(std::make_pair(4, 14));
331  MV.insert(std::make_pair(5, 15));
332  MV.insert(std::make_pair(6, 16));
333  ASSERT_EQ(MV.size(), 6u);
334
335  MV.remove_if([](const std::pair<int, int> &Val) { return Val.second % 2; });
336  ASSERT_EQ(MV.size(), 3u);
337  ASSERT_EQ(MV.find(1), MV.end());
338  ASSERT_EQ(MV.find(3), MV.end());
339  ASSERT_EQ(MV.find(5), MV.end());
340  ASSERT_EQ(MV[2], 12);
341  ASSERT_EQ(MV[4], 14);
342  ASSERT_EQ(MV[6], 16);
343}
344
345TEST(SmallMapVectorLargeTest, iteration_test) {
346  SmallMapVector<int, int, 1> MV;
347
348  MV.insert(std::make_pair(1, 11));
349  MV.insert(std::make_pair(2, 12));
350  MV.insert(std::make_pair(3, 13));
351  MV.insert(std::make_pair(4, 14));
352  MV.insert(std::make_pair(5, 15));
353  MV.insert(std::make_pair(6, 16));
354  ASSERT_EQ(MV.size(), 6u);
355
356  int count = 1;
357  for (auto P : make_range(MV.begin(), MV.end())) {
358    ASSERT_EQ(P.first, count);
359    count++;
360  }
361
362  count = 6;
363  for (auto P : make_range(MV.rbegin(), MV.rend())) {
364    ASSERT_EQ(P.first, count);
365    count--;
366  }
367}
368