1/*
2 * Copyright (C) 2012 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 "wtf/LinkedHashSet.h"
29#include "wtf/ListHashSet.h"
30#include "wtf/PassRefPtr.h"
31#include "wtf/RefCounted.h"
32#include "wtf/RefPtr.h"
33#include <gtest/gtest.h>
34
35namespace {
36
37template<typename Set>
38void removeFirstHelper()
39{
40    Set list;
41    list.add(-1);
42    list.add(0);
43    list.add(1);
44    list.add(2);
45    list.add(3);
46
47    EXPECT_EQ(-1, list.first());
48    EXPECT_EQ(3, list.last());
49
50    list.removeFirst();
51    EXPECT_EQ(0, list.first());
52
53    list.removeLast();
54    EXPECT_EQ(2, list.last());
55
56    list.removeFirst();
57    EXPECT_EQ(1, list.first());
58
59    list.removeFirst();
60    EXPECT_EQ(2, list.first());
61
62    list.removeFirst();
63    EXPECT_TRUE(list.isEmpty());
64}
65
66TEST(ListHashSetTest, RemoveFirst)
67{
68    removeFirstHelper<ListHashSet<int> >();
69    removeFirstHelper<ListHashSet<int, 1> >();
70}
71
72TEST(LinkedHashSetTest, RemoveFirst)
73{
74    removeFirstHelper<LinkedHashSet<int> >();
75}
76
77template<typename Set>
78void appendOrMoveToLastNewItems()
79{
80    Set list;
81    typename Set::AddResult result = list.appendOrMoveToLast(1);
82    EXPECT_TRUE(result.isNewEntry);
83    result = list.add(2);
84    EXPECT_TRUE(result.isNewEntry);
85    result = list.appendOrMoveToLast(3);
86    EXPECT_TRUE(result.isNewEntry);
87
88    EXPECT_EQ(list.size(), 3UL);
89
90    // The list should be in order 1, 2, 3.
91    typename Set::iterator iterator = list.begin();
92    EXPECT_EQ(1, *iterator);
93    ++iterator;
94    EXPECT_EQ(2, *iterator);
95    ++iterator;
96    EXPECT_EQ(3, *iterator);
97    ++iterator;
98}
99
100TEST(ListHashSetTest, AppendOrMoveToLastNewItems)
101{
102    appendOrMoveToLastNewItems<ListHashSet<int> >();
103    appendOrMoveToLastNewItems<ListHashSet<int, 1> >();
104}
105
106TEST(LinkedHashSetTest, AppendOrMoveToLastNewItems)
107{
108    appendOrMoveToLastNewItems<LinkedHashSet<int> >();
109}
110
111template<typename Set>
112void appendOrMoveToLastWithDuplicates()
113{
114    Set list;
115
116    // Add a single element twice.
117    typename Set::AddResult result = list.add(1);
118    EXPECT_TRUE(result.isNewEntry);
119    result = list.appendOrMoveToLast(1);
120    EXPECT_FALSE(result.isNewEntry);
121    EXPECT_EQ(1UL, list.size());
122
123    list.add(2);
124    list.add(3);
125    EXPECT_EQ(3UL, list.size());
126
127    // Appending 2 move it to the end.
128    EXPECT_EQ(3, list.last());
129    result = list.appendOrMoveToLast(2);
130    EXPECT_FALSE(result.isNewEntry);
131    EXPECT_EQ(2, list.last());
132
133    // Inverse the list by moving each element to end end.
134    result = list.appendOrMoveToLast(3);
135    EXPECT_FALSE(result.isNewEntry);
136    result = list.appendOrMoveToLast(2);
137    EXPECT_FALSE(result.isNewEntry);
138    result = list.appendOrMoveToLast(1);
139    EXPECT_FALSE(result.isNewEntry);
140    EXPECT_EQ(3UL, list.size());
141
142    typename Set::iterator iterator = list.begin();
143    EXPECT_EQ(3, *iterator);
144    ++iterator;
145    EXPECT_EQ(2, *iterator);
146    ++iterator;
147    EXPECT_EQ(1, *iterator);
148    ++iterator;
149}
150
151TEST(ListHashSetTest, AppendOrMoveToLastWithDuplicates)
152{
153    appendOrMoveToLastWithDuplicates<ListHashSet<int> >();
154    appendOrMoveToLastWithDuplicates<ListHashSet<int, 1> >();
155}
156
157TEST(LinkedHashSetTest, AppendOrMoveToLastWithDuplicates)
158{
159    appendOrMoveToLastWithDuplicates<LinkedHashSet<int> >();
160}
161
162template<typename Set>
163void prependOrMoveToFirstNewItems()
164{
165    Set list;
166    typename Set::AddResult result = list.prependOrMoveToFirst(1);
167    EXPECT_TRUE(result.isNewEntry);
168    result = list.add(2);
169    EXPECT_TRUE(result.isNewEntry);
170    result = list.prependOrMoveToFirst(3);
171    EXPECT_TRUE(result.isNewEntry);
172
173    EXPECT_EQ(list.size(), 3UL);
174
175    // The list should be in order 3, 1, 2.
176    typename Set::iterator iterator = list.begin();
177    EXPECT_EQ(3, *iterator);
178    ++iterator;
179    EXPECT_EQ(1, *iterator);
180    ++iterator;
181    EXPECT_EQ(2, *iterator);
182    ++iterator;
183}
184
185TEST(ListHashSetTest, PrependOrMoveToFirstNewItems)
186{
187    prependOrMoveToFirstNewItems<ListHashSet<int> >();
188    prependOrMoveToFirstNewItems<ListHashSet<int, 1> >();
189}
190
191TEST(LinkedHashSetTest, PrependOrMoveToFirstNewItems)
192{
193    prependOrMoveToFirstNewItems<LinkedHashSet<int> >();
194}
195
196template<typename Set>
197void prependOrMoveToLastWithDuplicates()
198{
199    Set list;
200
201    // Add a single element twice.
202    typename Set::AddResult result = list.add(1);
203    EXPECT_TRUE(result.isNewEntry);
204    result = list.prependOrMoveToFirst(1);
205    EXPECT_FALSE(result.isNewEntry);
206    EXPECT_EQ(1UL, list.size());
207
208    list.add(2);
209    list.add(3);
210    EXPECT_EQ(3UL, list.size());
211
212    // Prepending 2 move it to the beginning.
213    EXPECT_EQ(1, list.first());
214    result = list.prependOrMoveToFirst(2);
215    EXPECT_FALSE(result.isNewEntry);
216    EXPECT_EQ(2, list.first());
217
218    // Inverse the list by moving each element to the first position.
219    result = list.prependOrMoveToFirst(1);
220    EXPECT_FALSE(result.isNewEntry);
221    result = list.prependOrMoveToFirst(2);
222    EXPECT_FALSE(result.isNewEntry);
223    result = list.prependOrMoveToFirst(3);
224    EXPECT_FALSE(result.isNewEntry);
225    EXPECT_EQ(3UL, list.size());
226
227    typename Set::iterator iterator = list.begin();
228    EXPECT_EQ(3, *iterator);
229    ++iterator;
230    EXPECT_EQ(2, *iterator);
231    ++iterator;
232    EXPECT_EQ(1, *iterator);
233    ++iterator;
234}
235
236TEST(ListHashSetTest, PrependOrMoveToLastWithDuplicates)
237{
238    prependOrMoveToLastWithDuplicates<ListHashSet<int> >();
239    prependOrMoveToLastWithDuplicates<ListHashSet<int, 1> >();
240}
241
242TEST(LinkedHashSetTest, PrependOrMoveToLastWithDuplicates)
243{
244    prependOrMoveToLastWithDuplicates<LinkedHashSet<int> >();
245}
246
247class DummyRefCounted: public WTF::RefCounted<DummyRefCounted> {
248public:
249    DummyRefCounted(bool& isDeleted) : m_isDeleted(isDeleted) { m_isDeleted = false; }
250    ~DummyRefCounted() { m_isDeleted = true; }
251    void ref()
252    {
253        WTF::RefCounted<DummyRefCounted>::ref();
254        ++m_refInvokesCount;
255    }
256
257    static int m_refInvokesCount;
258
259private:
260    bool& m_isDeleted;
261};
262
263int DummyRefCounted::m_refInvokesCount = 0;
264
265template<typename Set>
266void withRefPtr()
267{
268    bool isDeleted = false;
269    DummyRefCounted::m_refInvokesCount = 0;
270    RefPtr<DummyRefCounted> ptr = adoptRef(new DummyRefCounted(isDeleted));
271    EXPECT_EQ(0, DummyRefCounted::m_refInvokesCount);
272
273    Set set;
274    set.add(ptr);
275    // Referenced only once (to store a copy in the container).
276    EXPECT_EQ(1, DummyRefCounted::m_refInvokesCount);
277    EXPECT_EQ(ptr, set.first());
278    EXPECT_EQ(1, DummyRefCounted::m_refInvokesCount);
279
280    DummyRefCounted* rawPtr = ptr.get();
281
282    EXPECT_TRUE(set.contains(ptr));
283    EXPECT_TRUE(set.contains(rawPtr));
284    EXPECT_EQ(1, DummyRefCounted::m_refInvokesCount);
285
286    ptr.clear();
287    EXPECT_FALSE(isDeleted);
288    EXPECT_EQ(1, DummyRefCounted::m_refInvokesCount);
289
290    set.remove(rawPtr);
291    EXPECT_TRUE(isDeleted);
292
293    EXPECT_EQ(1, DummyRefCounted::m_refInvokesCount);
294}
295
296TEST(ListHashSetTest, WithRefPtr)
297{
298    withRefPtr<ListHashSet<RefPtr<DummyRefCounted> > >();
299    withRefPtr<ListHashSet<RefPtr<DummyRefCounted>, 1> >();
300}
301
302TEST(LinkedHashSetTest, WithRefPtr)
303{
304    withRefPtr<LinkedHashSet<RefPtr<DummyRefCounted> > >();
305}
306
307template<typename Set, typename SetRef, typename Iterator>
308void findHelper()
309{
310    Set set;
311    set.add(-1);
312    set.add(0);
313    set.add(1);
314    set.add(2);
315    set.add(3);
316
317    SetRef ref = set;
318    Iterator it = ref.find(2);
319    EXPECT_EQ(2, *it);
320    ++it;
321    EXPECT_EQ(3, *it);
322    --it;
323    --it;
324    EXPECT_EQ(1, *it);
325}
326
327TEST(ListHashSetTest, Find)
328{
329    findHelper<ListHashSet<int>, const ListHashSet<int>&, ListHashSet<int>::const_iterator>();
330    findHelper<ListHashSet<int>, ListHashSet<int>&, ListHashSet<int>::iterator>();
331    findHelper<ListHashSet<int, 1>, const ListHashSet<int, 1>&, ListHashSet<int, 1>::const_iterator>();
332    findHelper<ListHashSet<int, 1>, ListHashSet<int, 1>&, ListHashSet<int, 1>::iterator>();
333}
334
335TEST(LinkedHashSetTest, Find)
336{
337    findHelper<LinkedHashSet<int>, const LinkedHashSet<int>&, LinkedHashSet<int>::const_iterator>();
338    findHelper<LinkedHashSet<int>, LinkedHashSet<int>&, LinkedHashSet<int>::iterator>();
339}
340
341template<typename Set>
342void insertBeforeHelper(bool canModifyWhileIterating)
343{
344    Set set;
345    set.add(-1);
346    set.add(0);
347    set.add(2);
348    set.add(3);
349
350    typename Set::iterator it = set.find(2);
351    EXPECT_EQ(2, *it);
352    set.insertBefore(it, 1);
353    if (!canModifyWhileIterating)
354        it = set.find(2);
355    ++it;
356    EXPECT_EQ(3, *it);
357    EXPECT_EQ(5u, set.size());
358    --it;
359    --it;
360    EXPECT_EQ(1, *it);
361    if (canModifyWhileIterating) {
362        set.remove(-1);
363        set.remove(0);
364        set.remove(2);
365        set.remove(3);
366        EXPECT_EQ(1u, set.size());
367        EXPECT_EQ(1, *it);
368        ++it;
369        EXPECT_EQ(it, set.end());
370        --it;
371        EXPECT_EQ(1, *it);
372        set.insertBefore(it, -1);
373        set.insertBefore(it, 0);
374        set.add(2);
375        set.add(3);
376    }
377    set.insertBefore(2, 42);
378    set.insertBefore(-1, 103);
379    EXPECT_EQ(103, set.first());
380    if (!canModifyWhileIterating)
381        it = set.find(1);
382    ++it;
383    EXPECT_EQ(42, *it);
384    EXPECT_EQ(7u, set.size());
385}
386
387TEST(ListHashSetTest, InsertBefore)
388{
389    insertBeforeHelper<ListHashSet<int> >(true);
390    insertBeforeHelper<ListHashSet<int, 1> >(true);
391}
392
393TEST(LinkedHashSetTest, InsertBefore)
394{
395    insertBeforeHelper<LinkedHashSet<int> >(false);
396}
397
398template<typename Set>
399void addReturnIterator(bool canModifyWhileIterating)
400{
401    Set set;
402    set.add(-1);
403    set.add(0);
404    set.add(1);
405    set.add(2);
406
407    typename Set::iterator it = set.addReturnIterator(3);
408    EXPECT_EQ(3, *it);
409    --it;
410    EXPECT_EQ(2, *it);
411    EXPECT_EQ(5u, set.size());
412    --it;
413    EXPECT_EQ(1, *it);
414    --it;
415    EXPECT_EQ(0, *it);
416    it = set.addReturnIterator(4);
417    if (canModifyWhileIterating) {
418        set.remove(3);
419        set.remove(2);
420        set.remove(1);
421        set.remove(0);
422        set.remove(-1);
423        EXPECT_EQ(1u, set.size());
424    }
425    EXPECT_EQ(4, *it);
426    ++it;
427    EXPECT_EQ(it, set.end());
428    --it;
429    EXPECT_EQ(4, *it);
430    if (canModifyWhileIterating) {
431        set.insertBefore(it, -1);
432        set.insertBefore(it, 0);
433        set.insertBefore(it, 1);
434        set.insertBefore(it, 2);
435        set.insertBefore(it, 3);
436    }
437    EXPECT_EQ(6u, set.size());
438    it = set.addReturnIterator(5);
439    EXPECT_EQ(7u, set.size());
440    set.remove(it);
441    EXPECT_EQ(6u, set.size());
442    EXPECT_EQ(4, set.last());
443}
444
445TEST(ListHashSetTest, AddReturnIterator)
446{
447    addReturnIterator<ListHashSet<int> >(true);
448    addReturnIterator<ListHashSet<int, 1> >(true);
449}
450
451TEST(LinkedHashSetTest, AddReturnIterator)
452{
453    addReturnIterator<LinkedHashSet<int> >(false);
454}
455
456template<typename Set>
457void excerciseValuePeekInType()
458{
459    Set set;
460    bool isDeleted = false;
461    bool isDeleted2 = false;
462
463    RefPtr<DummyRefCounted> ptr = adoptRef(new DummyRefCounted(isDeleted));
464    RefPtr<DummyRefCounted> ptr2 = adoptRef(new DummyRefCounted(isDeleted2));
465
466    typename Set::AddResult addResult = set.add(ptr);
467    EXPECT_TRUE(addResult.isNewEntry);
468    set.find(ptr);
469    const Set& constSet(set);
470    constSet.find(ptr);
471    EXPECT_TRUE(set.contains(ptr));
472    typename Set::iterator it = set.addReturnIterator(ptr);
473    set.appendOrMoveToLast(ptr);
474    set.prependOrMoveToFirst(ptr);
475    set.insertBefore(ptr, ptr);
476    set.insertBefore(it, ptr);
477    EXPECT_EQ(1u, set.size());
478    set.add(ptr2);
479    ptr2.clear();
480    set.remove(ptr);
481
482    EXPECT_FALSE(isDeleted);
483    ptr.clear();
484    EXPECT_TRUE(isDeleted);
485
486    EXPECT_FALSE(isDeleted2);
487    set.removeFirst();
488    EXPECT_TRUE(isDeleted2);
489
490    EXPECT_EQ(0u, set.size());
491}
492
493TEST(ListHashSetTest, ExcerciseValuePeekInType)
494{
495    excerciseValuePeekInType<ListHashSet<RefPtr<DummyRefCounted> > >();
496    excerciseValuePeekInType<ListHashSet<RefPtr<DummyRefCounted>, 1> >();
497}
498
499TEST(LinkedHashSetTest, ExcerciseValuePeekInType)
500{
501    excerciseValuePeekInType<LinkedHashSet<RefPtr<DummyRefCounted> > >();
502}
503
504struct Simple {
505    Simple(int value) : m_value(value) { };
506    int m_value;
507};
508
509struct Complicated {
510    Complicated(int value) : m_simple(value)
511    {
512        s_objectsConstructed++;
513    }
514
515    Complicated(const Complicated& other) : m_simple(other.m_simple)
516    {
517        s_objectsConstructed++;
518    }
519
520    Simple m_simple;
521    static int s_objectsConstructed;
522
523private:
524    Complicated();
525};
526
527int Complicated::s_objectsConstructed = 0;
528
529struct ComplicatedHashFunctions {
530    static unsigned hash(const Complicated& key) { return key.m_simple.m_value; }
531    static bool equal(const Complicated& a, const Complicated& b) { return a.m_simple.m_value == b.m_simple.m_value; }
532};
533struct ComplexityTranslator {
534    static unsigned hash(const Simple& key) { return key.m_value; }
535    static bool equal(const Complicated& a, const Simple& b) { return a.m_simple.m_value == b.m_value; }
536};
537
538template<typename Set>
539void translatorTest()
540{
541    Set set;
542    set.add(Complicated(42));
543    int baseLine = Complicated::s_objectsConstructed;
544
545    typename Set::iterator it = set.template find<ComplexityTranslator>(Simple(42));
546    EXPECT_NE(it, set.end());
547    EXPECT_EQ(baseLine, Complicated::s_objectsConstructed);
548
549    it = set.template find<ComplexityTranslator>(Simple(103));
550    EXPECT_EQ(it, set.end());
551    EXPECT_EQ(baseLine, Complicated::s_objectsConstructed);
552
553    const Set& constSet(set);
554
555    typename Set::const_iterator constIterator = constSet.template find<ComplexityTranslator>(Simple(42));
556    EXPECT_NE(constIterator, constSet.end());
557    EXPECT_EQ(baseLine, Complicated::s_objectsConstructed);
558
559    constIterator = constSet.template find<ComplexityTranslator>(Simple(103));
560    EXPECT_EQ(constIterator, constSet.end());
561    EXPECT_EQ(baseLine, Complicated::s_objectsConstructed);
562}
563
564TEST(ListHashSetTest, ComplexityTranslator)
565{
566    translatorTest<ListHashSet<Complicated, 256, ComplicatedHashFunctions> >();
567    translatorTest<ListHashSet<Complicated, 1, ComplicatedHashFunctions> >();
568}
569
570TEST(LinkedHashSetTest, ComplexityTranslator)
571{
572    translatorTest<LinkedHashSet<Complicated, ComplicatedHashFunctions> >();
573}
574
575struct Dummy {
576    Dummy(bool& deleted) : deleted(deleted) { }
577
578    ~Dummy()
579    {
580        deleted = true;
581    }
582
583    bool& deleted;
584};
585
586TEST(ListHashSetTest, WithOwnPtr)
587{
588    bool deleted1 = false, deleted2 = false;
589
590    typedef ListHashSet<OwnPtr<Dummy> > OwnPtrSet;
591    OwnPtrSet set;
592
593    Dummy* ptr1 = new Dummy(deleted1);
594    {
595        // AddResult in a separate scope to avoid assertion hit,
596        // since we modify the container further.
597        OwnPtrSet::AddResult res1 = set.add(adoptPtr(ptr1));
598        EXPECT_EQ(res1.storedValue->m_value.get(), ptr1);
599    }
600
601    EXPECT_FALSE(deleted1);
602    EXPECT_EQ(1UL, set.size());
603    OwnPtrSet::iterator it1 = set.find(ptr1);
604    EXPECT_NE(set.end(), it1);
605    EXPECT_EQ(ptr1, (*it1));
606
607    Dummy* ptr2 = new Dummy(deleted2);
608    {
609        OwnPtrSet::AddResult res2 = set.add(adoptPtr(ptr2));
610        EXPECT_EQ(res2.storedValue->m_value.get(), ptr2);
611    }
612
613    EXPECT_FALSE(deleted2);
614    EXPECT_EQ(2UL, set.size());
615    OwnPtrSet::iterator it2 = set.find(ptr2);
616    EXPECT_NE(set.end(), it2);
617    EXPECT_EQ(ptr2, (*it2));
618
619    set.remove(ptr1);
620    EXPECT_TRUE(deleted1);
621
622    set.clear();
623    EXPECT_TRUE(deleted2);
624    EXPECT_TRUE(set.isEmpty());
625
626    deleted1 = false;
627    deleted2 = false;
628    {
629        OwnPtrSet set;
630        set.add(adoptPtr(new Dummy(deleted1)));
631        set.add(adoptPtr(new Dummy(deleted2)));
632    }
633    EXPECT_TRUE(deleted1);
634    EXPECT_TRUE(deleted2);
635
636
637    deleted1 = false;
638    deleted2 = false;
639    OwnPtr<Dummy> ownPtr1;
640    OwnPtr<Dummy> ownPtr2;
641    ptr1 = new Dummy(deleted1);
642    ptr2 = new Dummy(deleted2);
643    {
644        OwnPtrSet set;
645        set.add(adoptPtr(ptr1));
646        set.add(adoptPtr(ptr2));
647        ownPtr1 = set.takeFirst();
648        EXPECT_EQ(1UL, set.size());
649        ownPtr2 = set.take(ptr2);
650        EXPECT_TRUE(set.isEmpty());
651    }
652    EXPECT_FALSE(deleted1);
653    EXPECT_FALSE(deleted2);
654
655    EXPECT_EQ(ptr1, ownPtr1);
656    EXPECT_EQ(ptr2, ownPtr2);
657}
658
659template<typename Set>
660void swapTestHelper()
661{
662    int num = 10;
663    Set set0;
664    Set set1;
665    Set set2;
666    for (int i = 0; i < num; ++i) {
667        set1.add(i + 1);
668        set2.add(num - i);
669    }
670
671    typename Set::iterator it1 = set1.begin();
672    typename Set::iterator it2 = set2.begin();
673    for (int i = 0; i < num; ++i, ++it1, ++it2) {
674        EXPECT_EQ(*it1, i + 1);
675        EXPECT_EQ(*it2, num - i);
676    }
677    EXPECT_EQ(set0.begin(), set0.end());
678    EXPECT_EQ(it1, set1.end());
679    EXPECT_EQ(it2, set2.end());
680
681    // Shift sets: 2->1, 1->0, 0->2
682    set1.swap(set2); // Swap with non-empty sets.
683    set0.swap(set2); // Swap with an empty set.
684
685    it1 = set0.begin();
686    it2 = set1.begin();
687    for (int i = 0; i < num; ++i, ++it1, ++it2) {
688        EXPECT_EQ(*it1, i + 1);
689        EXPECT_EQ(*it2, num - i);
690    }
691    EXPECT_EQ(it1, set0.end());
692    EXPECT_EQ(it2, set1.end());
693    EXPECT_EQ(set2.begin(), set2.end());
694
695    int removedIndex = num >> 1;
696    set0.remove(removedIndex + 1);
697    set1.remove(num - removedIndex);
698
699    it1 = set0.begin();
700    it2 = set1.begin();
701    for (int i = 0; i < num; ++i, ++it1, ++it2) {
702        if (i == removedIndex)
703            ++i;
704        EXPECT_EQ(*it1, i + 1);
705        EXPECT_EQ(*it2, num - i);
706    }
707    EXPECT_EQ(it1, set0.end());
708    EXPECT_EQ(it2, set1.end());
709}
710
711TEST(ListHashSetTest, Swap)
712{
713    swapTestHelper<ListHashSet<int> >();
714}
715
716TEST(LinkedHashSetTest, Swap)
717{
718    swapTestHelper<LinkedHashSet<int> >();
719}
720
721} // namespace
722