27200db31f02ccd23a8492eb2c87f92b5ef16810
[WebKit-https.git] / Tools / TestWebKitAPI / Tests / WTF / Vector.cpp
1 /*
2  * Copyright (C) 2011 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
14  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
15  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
17  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
18  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
19  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
20  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
21  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
22  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
23  * THE POSSIBILITY OF SUCH DAMAGE.
24  */
25
26 #include "config.h"
27
28 #include "MoveOnly.h"
29 #include <wtf/Vector.h>
30 #include <wtf/text/CString.h>
31
32 namespace TestWebKitAPI {
33
34 TEST(WTF_Vector, Basic)
35 {
36     Vector<int> intVector;
37     EXPECT_TRUE(intVector.isEmpty());
38     EXPECT_EQ(0U, intVector.size());
39     EXPECT_EQ(0U, intVector.capacity());
40 }
41
42 TEST(WTF_Vector, Iterator)
43 {
44     Vector<int> intVector;
45     intVector.append(10);
46     intVector.append(11);
47     intVector.append(12);
48     intVector.append(13);
49
50     Vector<int>::iterator it = intVector.begin();
51     Vector<int>::iterator end = intVector.end();
52     EXPECT_TRUE(end != it);
53
54     EXPECT_EQ(10, *it);
55     ++it;
56     EXPECT_EQ(11, *it);
57     ++it;
58     EXPECT_EQ(12, *it);
59     ++it;
60     EXPECT_EQ(13, *it);
61     ++it;
62
63     EXPECT_TRUE(end == it);
64 }
65
66 TEST(WTF_Vector, OverloadedOperatorAmpersand)
67 {
68     struct Test {
69     private:
70         Test* operator&() = delete;
71     };
72
73     Vector<Test> vector;
74     vector.append(Test());
75 }
76
77 TEST(WTF_Vector, AppendLast)
78 {
79     Vector<unsigned> vector;
80     vector.append(0);
81
82     // FIXME: This test needs to be run with GuardMalloc to show the bug.
83     for (size_t i = 0; i < 100; ++i)
84         vector.append(const_cast<const unsigned&>(vector.last()));
85 }
86
87 TEST(WTF_Vector, InitializerList)
88 {
89     Vector<int> vector = { 1, 2, 3, 4 };
90     EXPECT_EQ(4U, vector.size());
91
92     EXPECT_EQ(1, vector[0]);
93     EXPECT_EQ(2, vector[1]);
94     EXPECT_EQ(3, vector[2]);
95     EXPECT_EQ(4, vector[3]);
96 }
97
98 TEST(WTF_Vector, InitializeFromOtherInitialCapacity)
99 {
100     Vector<int, 3> vector = { 1, 3, 2, 4 };
101     Vector<int, 5> vectorCopy(vector);
102     EXPECT_EQ(4U, vector.size());
103     EXPECT_EQ(4U, vectorCopy.size());
104     EXPECT_EQ(5U, vectorCopy.capacity());
105
106     EXPECT_EQ(1, vectorCopy[0]);
107     EXPECT_EQ(3, vectorCopy[1]);
108     EXPECT_EQ(2, vectorCopy[2]);
109     EXPECT_EQ(4, vectorCopy[3]);
110 }
111
112 TEST(WTF_Vector, CopyFromOtherInitialCapacity)
113 {
114     Vector<int, 3> vector = { 1, 3, 2, 4 };
115     Vector<int, 5> vectorCopy { 0 };
116     EXPECT_EQ(4U, vector.size());
117     EXPECT_EQ(1U, vectorCopy.size());
118
119     vectorCopy = vector;
120
121     EXPECT_EQ(4U, vector.size());
122     EXPECT_EQ(4U, vectorCopy.size());
123     EXPECT_EQ(5U, vectorCopy.capacity());
124
125     EXPECT_EQ(1, vectorCopy[0]);
126     EXPECT_EQ(3, vectorCopy[1]);
127     EXPECT_EQ(2, vectorCopy[2]);
128     EXPECT_EQ(4, vectorCopy[3]);
129 }
130
131 TEST(WTF_Vector, InitializeFromOtherOverflowBehavior)
132 {
133     Vector<int, 7, WTF::CrashOnOverflow> vector = { 4, 3, 2, 1 };
134     Vector<int, 7, UnsafeVectorOverflow> vectorCopy(vector);
135     EXPECT_EQ(4U, vector.size());
136     EXPECT_EQ(4U, vectorCopy.size());
137
138     EXPECT_EQ(4, vectorCopy[0]);
139     EXPECT_EQ(3, vectorCopy[1]);
140     EXPECT_EQ(2, vectorCopy[2]);
141     EXPECT_EQ(1, vectorCopy[3]);
142 }
143
144 TEST(WTF_Vector, CopyFromOtherOverflowBehavior)
145 {
146     Vector<int, 7, WTF::CrashOnOverflow> vector = { 4, 3, 2, 1 };
147     Vector<int, 7, UnsafeVectorOverflow> vectorCopy = { 0, 0, 0 };
148
149     EXPECT_EQ(4U, vector.size());
150     EXPECT_EQ(3U, vectorCopy.size());
151
152     vectorCopy = vector;
153
154     EXPECT_EQ(4U, vector.size());
155     EXPECT_EQ(4U, vectorCopy.size());
156
157     EXPECT_EQ(4, vectorCopy[0]);
158     EXPECT_EQ(3, vectorCopy[1]);
159     EXPECT_EQ(2, vectorCopy[2]);
160     EXPECT_EQ(1, vectorCopy[3]);
161 }
162
163 TEST(WTF_Vector, InitializeFromOtherMinCapacity)
164 {
165     Vector<int, 7, WTF::CrashOnOverflow, 1> vector = { 3, 4, 2, 1 };
166     Vector<int, 7, WTF::CrashOnOverflow, 50> vectorCopy(vector);
167     EXPECT_EQ(4U, vector.size());
168     EXPECT_EQ(4U, vectorCopy.size());
169
170     EXPECT_EQ(3, vectorCopy[0]);
171     EXPECT_EQ(4, vectorCopy[1]);
172     EXPECT_EQ(2, vectorCopy[2]);
173     EXPECT_EQ(1, vectorCopy[3]);
174 }
175
176 TEST(WTF_Vector, CopyFromOtherMinCapacity)
177 {
178     Vector<int, 7, WTF::CrashOnOverflow, 1> vector = { 3, 4, 2, 1 };
179     Vector<int, 7, WTF::CrashOnOverflow, 50> vectorCopy;
180
181     EXPECT_EQ(4U, vector.size());
182     EXPECT_EQ(0U, vectorCopy.size());
183
184     vectorCopy = vector;
185
186     EXPECT_EQ(4U, vector.size());
187     EXPECT_EQ(4U, vectorCopy.size());
188
189     EXPECT_EQ(3, vectorCopy[0]);
190     EXPECT_EQ(4, vectorCopy[1]);
191     EXPECT_EQ(2, vectorCopy[2]);
192     EXPECT_EQ(1, vectorCopy[3]);
193 }
194
195 TEST(WTF_Vector, Reverse)
196 {
197     Vector<int> intVector;
198     intVector.append(10);
199     intVector.append(11);
200     intVector.append(12);
201     intVector.append(13);
202     intVector.reverse();
203
204     EXPECT_EQ(13, intVector[0]);
205     EXPECT_EQ(12, intVector[1]);
206     EXPECT_EQ(11, intVector[2]);
207     EXPECT_EQ(10, intVector[3]);
208
209     intVector.append(9);
210     intVector.reverse();
211
212     EXPECT_EQ(9, intVector[0]);
213     EXPECT_EQ(10, intVector[1]);
214     EXPECT_EQ(11, intVector[2]);
215     EXPECT_EQ(12, intVector[3]);
216     EXPECT_EQ(13, intVector[4]);
217 }
218
219 TEST(WTF_Vector, ReverseIterator)
220 {
221     Vector<int> intVector;
222     intVector.append(10);
223     intVector.append(11);
224     intVector.append(12);
225     intVector.append(13);
226
227     Vector<int>::reverse_iterator it = intVector.rbegin();
228     Vector<int>::reverse_iterator end = intVector.rend();
229     EXPECT_TRUE(end != it);
230
231     EXPECT_EQ(13, *it);
232     ++it;
233     EXPECT_EQ(12, *it);
234     ++it;
235     EXPECT_EQ(11, *it);
236     ++it;
237     EXPECT_EQ(10, *it);
238     ++it;
239
240     EXPECT_TRUE(end == it);
241 }
242
243 TEST(WTF_Vector, MoveOnly_UncheckedAppend)
244 {
245     Vector<MoveOnly> vector;
246
247     vector.reserveInitialCapacity(100);
248     for (size_t i = 0; i < 100; ++i) {
249         MoveOnly moveOnly(i);
250         vector.uncheckedAppend(WTFMove(moveOnly));
251         EXPECT_EQ(0U, moveOnly.value());
252     }
253
254     for (size_t i = 0; i < 100; ++i)
255         EXPECT_EQ(i, vector[i].value());
256 }
257
258 TEST(WTF_Vector, MoveOnly_Append)
259 {
260     Vector<MoveOnly> vector;
261
262     for (size_t i = 0; i < 100; ++i) {
263         MoveOnly moveOnly(i);
264         vector.append(WTFMove(moveOnly));
265         EXPECT_EQ(0U, moveOnly.value());
266     }
267
268     for (size_t i = 0; i < 100; ++i)
269         EXPECT_EQ(i, vector[i].value());
270
271     for (size_t i = 0; i < 16; ++i) {
272         Vector<MoveOnly> vector;
273
274         vector.append(i);
275
276         for (size_t j = 0; j < i; ++j)
277             vector.append(j);
278         vector.append(WTFMove(vector[0]));
279
280         EXPECT_EQ(0U, vector[0].value());
281
282         for (size_t j = 0; j < i; ++j)
283             EXPECT_EQ(j, vector[j + 1].value());
284         EXPECT_EQ(i, vector.last().value());
285     }
286 }
287
288 TEST(WTF_Vector, MoveOnly_Insert)
289 {
290     Vector<MoveOnly> vector;
291
292     for (size_t i = 0; i < 100; ++i) {
293         MoveOnly moveOnly(i);
294         vector.insert(0, WTFMove(moveOnly));
295         EXPECT_EQ(0U, moveOnly.value());
296     }
297
298     EXPECT_EQ(vector.size(), 100U);
299     for (size_t i = 0; i < 100; ++i)
300         EXPECT_EQ(99 - i, vector[i].value());
301
302     for (size_t i = 0; i < 200; i += 2) {
303         MoveOnly moveOnly(1000 + i);
304         vector.insert(i, WTFMove(moveOnly));
305         EXPECT_EQ(0U, moveOnly.value());
306     }
307
308     EXPECT_EQ(200U, vector.size());
309     for (size_t i = 0; i < 200; ++i) {
310         if (i % 2)
311             EXPECT_EQ(99 - i / 2, vector[i].value());
312         else
313             EXPECT_EQ(1000 + i, vector[i].value());
314     }
315 }
316
317 TEST(WTF_Vector, MoveOnly_TakeLast)
318 {
319     Vector<MoveOnly> vector;
320
321     for (size_t i = 0; i < 100; ++i) {
322         MoveOnly moveOnly(i);
323         vector.append(WTFMove(moveOnly));
324         EXPECT_EQ(0U, moveOnly.value());
325     }
326
327     EXPECT_EQ(100U, vector.size());
328     for (size_t i = 0; i < 100; ++i)
329         EXPECT_EQ(99 - i, vector.takeLast().value());
330
331     EXPECT_EQ(0U, vector.size());
332 }
333
334 TEST(WTF_Vector, VectorOfVectorsOfVectorsInlineCapacitySwap)
335 {
336     Vector<Vector<Vector<int, 1>, 1>, 1> a;
337     Vector<Vector<Vector<int, 1>, 1>, 1> b;
338     Vector<Vector<Vector<int, 1>, 1>, 1> c;
339
340     EXPECT_EQ(0U, a.size());
341     EXPECT_EQ(0U, b.size());
342     EXPECT_EQ(0U, c.size());
343
344     Vector<int, 1> x;
345     x.append(42);
346
347     EXPECT_EQ(1U, x.size());
348     EXPECT_EQ(42, x[0]);
349     
350     Vector<Vector<int, 1>, 1> y;
351     y.append(x);
352     
353     EXPECT_EQ(1U, x.size());
354     EXPECT_EQ(42, x[0]);
355     EXPECT_EQ(1U, y.size());
356     EXPECT_EQ(1U, y[0].size());
357     EXPECT_EQ(42, y[0][0]);
358     
359     a.append(y);
360
361     EXPECT_EQ(1U, x.size());
362     EXPECT_EQ(42, x[0]);
363     EXPECT_EQ(1U, y.size());
364     EXPECT_EQ(1U, y[0].size());
365     EXPECT_EQ(42, y[0][0]);
366     EXPECT_EQ(1U, a.size());
367     EXPECT_EQ(1U, a[0].size());
368     EXPECT_EQ(1U, a[0][0].size());
369     EXPECT_EQ(42, a[0][0][0]);
370     
371     a.swap(b);
372
373     EXPECT_EQ(0U, a.size());
374     EXPECT_EQ(1U, x.size());
375     EXPECT_EQ(42, x[0]);
376     EXPECT_EQ(1U, y.size());
377     EXPECT_EQ(1U, y[0].size());
378     EXPECT_EQ(42, y[0][0]);
379     EXPECT_EQ(1U, b.size());
380     EXPECT_EQ(1U, b[0].size());
381     EXPECT_EQ(1U, b[0][0].size());
382     EXPECT_EQ(42, b[0][0][0]);
383     
384     b.swap(c);
385
386     EXPECT_EQ(0U, a.size());
387     EXPECT_EQ(0U, b.size());
388     EXPECT_EQ(1U, x.size());
389     EXPECT_EQ(42, x[0]);
390     EXPECT_EQ(1U, y.size());
391     EXPECT_EQ(1U, y[0].size());
392     EXPECT_EQ(42, y[0][0]);
393     EXPECT_EQ(1U, c.size());
394     EXPECT_EQ(1U, c[0].size());
395     EXPECT_EQ(1U, c[0][0].size());
396     EXPECT_EQ(42, c[0][0][0]);
397     
398     y[0][0] = 24;
399
400     EXPECT_EQ(1U, x.size());
401     EXPECT_EQ(42, x[0]);
402     EXPECT_EQ(1U, y.size());
403     EXPECT_EQ(1U, y[0].size());
404     EXPECT_EQ(24, y[0][0]);
405     
406     a.append(y);
407
408     EXPECT_EQ(1U, x.size());
409     EXPECT_EQ(42, x[0]);
410     EXPECT_EQ(1U, y.size());
411     EXPECT_EQ(1U, y[0].size());
412     EXPECT_EQ(24, y[0][0]);
413     EXPECT_EQ(1U, a.size());
414     EXPECT_EQ(1U, a[0].size());
415     EXPECT_EQ(1U, a[0][0].size());
416     EXPECT_EQ(24, a[0][0][0]);
417     EXPECT_EQ(1U, c.size());
418     EXPECT_EQ(1U, c[0].size());
419     EXPECT_EQ(1U, c[0][0].size());
420     EXPECT_EQ(42, c[0][0][0]);
421     EXPECT_EQ(0U, b.size());
422 }
423
424 TEST(WTF_Vector, RemoveFirst)
425 {
426     Vector<int> v;
427     EXPECT_TRUE(v.isEmpty());
428     EXPECT_FALSE(v.removeFirst(1));
429     EXPECT_FALSE(v.removeFirst(-1));
430     EXPECT_TRUE(v.isEmpty());
431
432     v.fill(2, 10);
433     EXPECT_EQ(10U, v.size());
434     EXPECT_FALSE(v.removeFirst(1));
435     EXPECT_EQ(10U, v.size());
436     v.clear();
437
438     v.fill(1, 10);
439     EXPECT_EQ(10U, v.size());
440     EXPECT_TRUE(v.removeFirst(1));
441     EXPECT_TRUE(v == Vector<int>({1, 1, 1, 1, 1, 1, 1, 1, 1}));
442     EXPECT_EQ(9U, v.size());
443     EXPECT_FALSE(v.removeFirst(2));
444     EXPECT_EQ(9U, v.size());
445     EXPECT_TRUE(v == Vector<int>({1, 1, 1, 1, 1, 1, 1, 1, 1}));
446
447     unsigned removed = 0;
448     while (v.removeFirst(1))
449         ++removed;
450     EXPECT_EQ(9U, removed);
451     EXPECT_TRUE(v.isEmpty());
452
453     v.resize(1);
454     EXPECT_EQ(1U, v.size());
455     EXPECT_TRUE(v.removeFirst(1));
456     EXPECT_EQ(0U, v.size());
457     EXPECT_TRUE(v.isEmpty());
458 }
459
460 TEST(WTF_Vector, RemoveAll)
461 {
462     // Using a memcpy-able type.
463     static_assert(VectorTraits<int>::canMoveWithMemcpy, "Should use a memcpy-able type");
464     Vector<int> v;
465     EXPECT_TRUE(v.isEmpty());
466     EXPECT_FALSE(v.removeAll(1));
467     EXPECT_FALSE(v.removeAll(-1));
468     EXPECT_TRUE(v.isEmpty());
469
470     v.fill(1, 10);
471     EXPECT_EQ(10U, v.size());
472     EXPECT_EQ(10U, v.removeAll(1));
473     EXPECT_TRUE(v.isEmpty());
474
475     v.fill(2, 10);
476     EXPECT_EQ(10U, v.size());
477     EXPECT_EQ(0U, v.removeAll(1));
478     EXPECT_EQ(10U, v.size());
479
480     v = {1, 2, 1, 2, 1, 2, 2, 1, 1, 1};
481     EXPECT_EQ(10U, v.size());
482     EXPECT_EQ(6U, v.removeAll(1));
483     EXPECT_EQ(4U, v.size());
484     EXPECT_TRUE(v == Vector<int>({2, 2, 2, 2}));
485     EXPECT_TRUE(v.find(1) == notFound);
486     EXPECT_EQ(4U, v.removeAll(2));
487     EXPECT_TRUE(v.isEmpty());
488
489     v = {3, 1, 2, 1, 2, 1, 2, 2, 1, 1, 1, 3};
490     EXPECT_EQ(12U, v.size());
491     EXPECT_EQ(6U, v.removeAll(1));
492     EXPECT_EQ(6U, v.size());
493     EXPECT_TRUE(v.find(1) == notFound);
494     EXPECT_TRUE(v == Vector<int>({3, 2, 2, 2, 2, 3}));
495
496     EXPECT_EQ(4U, v.removeAll(2));
497     EXPECT_EQ(2U, v.size());
498     EXPECT_TRUE(v.find(2) == notFound);
499     EXPECT_TRUE(v == Vector<int>({3, 3}));
500
501     EXPECT_EQ(2U, v.removeAll(3));
502     EXPECT_TRUE(v.isEmpty());
503
504     v = {1, 1, 1, 3, 2, 4, 2, 2, 2, 4, 4, 3};
505     EXPECT_EQ(12U, v.size());
506     EXPECT_EQ(3U, v.removeAll(1));
507     EXPECT_EQ(9U, v.size());
508     EXPECT_TRUE(v.find(1) == notFound);
509     EXPECT_TRUE(v == Vector<int>({3, 2, 4, 2, 2, 2, 4, 4, 3}));
510
511     // Using a non memcpy-able type.
512     static_assert(!VectorTraits<CString>::canMoveWithMemcpy, "Should use a non memcpy-able type");
513     Vector<CString> vExpected;
514     Vector<CString> v2;
515     EXPECT_TRUE(v2.isEmpty());
516     EXPECT_FALSE(v2.removeAll("1"));
517     EXPECT_TRUE(v2.isEmpty());
518
519     v2.fill("1", 10);
520     EXPECT_EQ(10U, v2.size());
521     EXPECT_EQ(10U, v2.removeAll("1"));
522     EXPECT_TRUE(v2.isEmpty());
523
524     v2.fill("2", 10);
525     EXPECT_EQ(10U, v2.size());
526     EXPECT_EQ(0U, v2.removeAll("1"));
527     EXPECT_EQ(10U, v2.size());
528
529     v2 = {"1", "2", "1", "2", "1", "2", "2", "1", "1", "1"};
530     EXPECT_EQ(10U, v2.size());
531     EXPECT_EQ(6U, v2.removeAll("1"));
532     EXPECT_EQ(4U, v2.size());
533     EXPECT_TRUE(v2.find("1") == notFound);
534     EXPECT_EQ(4U, v2.removeAll("2"));
535     EXPECT_TRUE(v2.isEmpty());
536
537     v2 = {"3", "1", "2", "1", "2", "1", "2", "2", "1", "1", "1", "3"};
538     EXPECT_EQ(12U, v2.size());
539     EXPECT_EQ(6U, v2.removeAll("1"));
540     EXPECT_EQ(6U, v2.size());
541     EXPECT_TRUE(v2.find("1") == notFound);
542     vExpected = {"3", "2", "2", "2", "2", "3"};
543     EXPECT_TRUE(v2 == vExpected);
544
545     EXPECT_EQ(4U, v2.removeAll("2"));
546     EXPECT_EQ(2U, v2.size());
547     EXPECT_TRUE(v2.find("2") == notFound);
548     vExpected = {"3", "3"};
549     EXPECT_TRUE(v2 == vExpected);
550
551     EXPECT_EQ(2U, v2.removeAll("3"));
552     EXPECT_TRUE(v2.isEmpty());
553
554     v2 = {"1", "1", "1", "3", "2", "4", "2", "2", "2", "4", "4", "3"};
555     EXPECT_EQ(12U, v2.size());
556     EXPECT_EQ(3U, v2.removeAll("1"));
557     EXPECT_EQ(9U, v2.size());
558     EXPECT_TRUE(v2.find("1") == notFound);
559     vExpected = {"3", "2", "4", "2", "2", "2", "4", "4", "3"};
560     EXPECT_TRUE(v2 == vExpected);
561 }
562
563 TEST(WTF_Vector, FindMatching)
564 {
565     Vector<int> v;
566     EXPECT_TRUE(v.findMatching([](int) { return false; }) == notFound);
567     EXPECT_TRUE(v.findMatching([](int) { return true; }) == notFound);
568
569     v = {3, 1, 2, 1, 2, 1, 2, 2, 1, 1, 1, 3};
570     EXPECT_TRUE(v.findMatching([](int value) { return value > 3; }) == notFound);
571     EXPECT_TRUE(v.findMatching([](int) { return false; }) == notFound);
572     EXPECT_EQ(0U, v.findMatching([](int) { return true; }));
573     EXPECT_EQ(0U, v.findMatching([](int value) { return value <= 3; }));
574     EXPECT_EQ(1U, v.findMatching([](int value) { return value < 3; }));
575     EXPECT_EQ(2U, v.findMatching([](int value) { return value == 2; }));
576 }
577
578 TEST(WTF_Vector, RemoveFirstMatching)
579 {
580     Vector<int> v;
581     EXPECT_TRUE(v.isEmpty());
582     EXPECT_FALSE(v.removeFirstMatching([] (int value) { return value > 0; }));
583     EXPECT_FALSE(v.removeFirstMatching([] (int) { return true; }));
584     EXPECT_FALSE(v.removeFirstMatching([] (int) { return false; }));
585
586     v = {3, 1, 2, 1, 2, 1, 2, 2, 1, 1, 1, 3};
587     EXPECT_EQ(12U, v.size());
588     EXPECT_FALSE(v.removeFirstMatching([] (int) { return false; }));
589     EXPECT_EQ(12U, v.size());
590     EXPECT_FALSE(v.removeFirstMatching([] (int value) { return value < 0; }));
591     EXPECT_EQ(12U, v.size());
592     EXPECT_TRUE(v.removeFirstMatching([] (int value) { return value < 3; }));
593     EXPECT_EQ(11U, v.size());
594     EXPECT_TRUE(v == Vector<int>({3, 2, 1, 2, 1, 2, 2, 1, 1, 1, 3}));
595     EXPECT_TRUE(v.removeFirstMatching([] (int value) { return value > 2; }));
596     EXPECT_EQ(10U, v.size());
597     EXPECT_TRUE(v == Vector<int>({2, 1, 2, 1, 2, 2, 1, 1, 1, 3}));
598     EXPECT_TRUE(v.removeFirstMatching([] (int value) { return value > 2; }));
599     EXPECT_EQ(9U, v.size());
600     EXPECT_TRUE(v == Vector<int>({2, 1, 2, 1, 2, 2, 1, 1, 1}));
601     EXPECT_TRUE(v.removeFirstMatching([] (int value) { return value == 1; }, 1));
602     EXPECT_EQ(8U, v.size());
603     EXPECT_TRUE(v == Vector<int>({2, 2, 1, 2, 2, 1, 1, 1}));
604     EXPECT_TRUE(v.removeFirstMatching([] (int value) { return value == 1; }, 3));
605     EXPECT_EQ(7U, v.size());
606     EXPECT_TRUE(v == Vector<int>({2, 2, 1, 2, 2, 1, 1}));
607     EXPECT_FALSE(v.removeFirstMatching([] (int value) { return value == 1; }, 7));
608     EXPECT_EQ(7U, v.size());
609     EXPECT_FALSE(v.removeFirstMatching([] (int value) { return value == 1; }, 10));
610     EXPECT_EQ(7U, v.size());
611 }
612
613 TEST(WTF_Vector, RemoveAllMatching)
614 {
615     Vector<int> v;
616     EXPECT_TRUE(v.isEmpty());
617     EXPECT_FALSE(v.removeAllMatching([] (int value) { return value > 0; }));
618     EXPECT_FALSE(v.removeAllMatching([] (int) { return true; }));
619     EXPECT_FALSE(v.removeAllMatching([] (int) { return false; }));
620
621     v = {3, 1, 2, 1, 2, 1, 2, 2, 1, 1, 1, 3};
622     EXPECT_EQ(12U, v.size());
623     EXPECT_EQ(0U, v.removeAllMatching([] (int) { return false; }));
624     EXPECT_EQ(12U, v.size());
625     EXPECT_EQ(0U, v.removeAllMatching([] (int value) { return value < 0; }));
626     EXPECT_EQ(12U, v.size());
627     EXPECT_EQ(12U, v.removeAllMatching([] (int value) { return value > 0; }));
628     EXPECT_TRUE(v.isEmpty());
629
630     v = {3, 1, 2, 1, 2, 1, 3, 2, 2, 1, 1, 1, 3};
631     EXPECT_EQ(13U, v.size());
632     EXPECT_EQ(3U, v.removeAllMatching([] (int value) { return value > 2; }));
633     EXPECT_EQ(10U, v.size());
634     EXPECT_TRUE(v == Vector<int>({1, 2, 1, 2, 1, 2, 2, 1, 1, 1}));
635     EXPECT_EQ(6U, v.removeAllMatching([] (int value) { return value != 2; }));
636     EXPECT_EQ(4U, v.size());
637     EXPECT_TRUE(v == Vector<int>({2, 2, 2, 2}));
638     EXPECT_EQ(4U, v.removeAllMatching([] (int value) { return value == 2; }));
639     EXPECT_TRUE(v.isEmpty());
640
641     v = {3, 1, 2, 1, 2, 1, 3, 2, 2, 1, 1, 1, 3};
642     EXPECT_EQ(13U, v.size());
643     EXPECT_EQ(0U, v.removeAllMatching([] (int value) { return value > 0; }, 13));
644     EXPECT_EQ(13U, v.size());
645     EXPECT_EQ(0U, v.removeAllMatching([] (int value) { return value > 0; }, 20));
646     EXPECT_EQ(13U, v.size());
647     EXPECT_EQ(5U, v.removeAllMatching([] (int value) { return value > 1; }, 3));
648     EXPECT_EQ(8U, v.size());
649     EXPECT_TRUE(v == Vector<int>({3, 1, 2, 1, 1, 1, 1, 1}));
650     EXPECT_EQ(8U, v.removeAllMatching([] (int value) { return value > 0; }, 0));
651     EXPECT_EQ(0U, v.size());
652 }
653
654 static int multiplyByTwo(int value)
655 {
656     return 2 * value;
657 }
658
659 TEST(WTF_Vector, MapStaticFunction)
660 {
661     Vector<int> vector { 2, 3, 4 };
662
663     auto mapped = WTF::map(vector, multiplyByTwo);
664
665     EXPECT_EQ(3U, mapped.size());
666     EXPECT_EQ(4, mapped[0]);
667     EXPECT_EQ(6, mapped[1]);
668     EXPECT_EQ(8, mapped[2]);
669 }
670
671 static MoveOnly multiplyByTwoMoveOnly(const MoveOnly& value)
672 {
673     return MoveOnly(2 * value.value());
674 }
675
676 TEST(WTF_Vector, MapStaticFunctionMoveOnly)
677 {
678     Vector<MoveOnly> vector;
679
680     vector.reserveInitialCapacity(3);
681     for (unsigned i = 0; i < 3; ++i)
682         vector.uncheckedAppend(MoveOnly { i });
683
684     auto mapped = WTF::map(vector, multiplyByTwoMoveOnly);
685
686     EXPECT_EQ(3U, mapped.size());
687     EXPECT_EQ(0U, mapped[0].value());
688     EXPECT_EQ(2U, mapped[1].value());
689     EXPECT_EQ(4U, mapped[2].value());
690 }
691
692 TEST(WTF_Vector, MapLambda)
693 {
694     Vector<int> vector { 2, 3, 4 };
695
696     int counter = 0;
697     auto mapped = WTF::map(vector, [&] (int item) {
698         counter += 2;
699         return counter <= item;
700     });
701
702     EXPECT_EQ(3U, mapped.size());
703     EXPECT_TRUE(mapped[0]);
704     EXPECT_FALSE(mapped[1]);
705     EXPECT_FALSE(mapped[2]);
706 }
707
708 TEST(WTF_Vector, MapLambdaMove)
709 {
710     Vector<MoveOnly> vector;
711
712     vector.reserveInitialCapacity(3);
713     for (unsigned i = 0; i < 3; ++i)
714         vector.uncheckedAppend(MoveOnly { i });
715
716
717     unsigned counter = 0;
718     auto mapped = WTF::map(WTFMove(vector), [&] (MoveOnly&& item) {
719         item = item.value() + ++counter;
720         return WTFMove(item);
721     });
722
723     EXPECT_EQ(3U, mapped.size());
724     EXPECT_EQ(1U, mapped[0].value());
725     EXPECT_EQ(3U, mapped[1].value());
726     EXPECT_EQ(5U, mapped[2].value());
727 }
728
729 } // namespace TestWebKitAPI