1/*
2 * Written by Doug Lea with assistance from members of JCP JSR-166
3 * Expert Group and released to the public domain, as explained at
4 * http://creativecommons.org/publicdomain/zero/1.0/
5 * Other contributors include Andrew Wright, Jeffrey Hayes,
6 * Pat Fisher, Mike Judd.
7 */
8
9package jsr166;
10
11import java.util.ArrayList;
12import java.util.Arrays;
13import java.util.Collection;
14import java.util.Collections;
15import java.util.Iterator;
16import java.util.LinkedList;
17import java.util.List;
18import java.util.ListIterator;
19import java.util.NoSuchElementException;
20import java.util.concurrent.CopyOnWriteArrayList;
21
22import junit.framework.Test;
23import junit.framework.TestSuite;
24
25public class CopyOnWriteArrayListTest extends JSR166TestCase {
26
27    // android-note: Removed because the CTS runner does a bad job of
28    // retrying tests that have suite() declarations.
29    //
30    // public static void main(String[] args) {
31    //     main(suite(), args);
32    // }
33    // public static Test suite() {
34    //     return new TestSuite(CopyOnWriteArrayListTest.class);
35    // }
36
37    static CopyOnWriteArrayList<Integer> populatedArray(int n) {
38        CopyOnWriteArrayList<Integer> a = new CopyOnWriteArrayList<Integer>();
39        assertTrue(a.isEmpty());
40        for (int i = 0; i < n; i++)
41            a.add(i);
42        assertFalse(a.isEmpty());
43        assertEquals(n, a.size());
44        return a;
45    }
46
47    static CopyOnWriteArrayList<Integer> populatedArray(Integer[] elements) {
48        CopyOnWriteArrayList<Integer> a = new CopyOnWriteArrayList<Integer>();
49        assertTrue(a.isEmpty());
50        for (int i = 0; i < elements.length; i++)
51            a.add(elements[i]);
52        assertFalse(a.isEmpty());
53        assertEquals(elements.length, a.size());
54        return a;
55    }
56
57    /**
58     * a new list is empty
59     */
60    public void testConstructor() {
61        CopyOnWriteArrayList a = new CopyOnWriteArrayList();
62        assertTrue(a.isEmpty());
63    }
64
65    /**
66     * new list contains all elements of initializing array
67     */
68    public void testConstructor2() {
69        Integer[] ints = new Integer[SIZE];
70        for (int i = 0; i < SIZE - 1; ++i)
71            ints[i] = new Integer(i);
72        CopyOnWriteArrayList a = new CopyOnWriteArrayList(ints);
73        for (int i = 0; i < SIZE; ++i)
74            assertEquals(ints[i], a.get(i));
75    }
76
77    /**
78     * new list contains all elements of initializing collection
79     */
80    public void testConstructor3() {
81        Integer[] ints = new Integer[SIZE];
82        for (int i = 0; i < SIZE - 1; ++i)
83            ints[i] = new Integer(i);
84        CopyOnWriteArrayList a = new CopyOnWriteArrayList(Arrays.asList(ints));
85        for (int i = 0; i < SIZE; ++i)
86            assertEquals(ints[i], a.get(i));
87    }
88
89    /**
90     * addAll adds each element from the given collection, including duplicates
91     */
92    public void testAddAll() {
93        CopyOnWriteArrayList full = populatedArray(3);
94        assertTrue(full.addAll(Arrays.asList(three, four, five)));
95        assertEquals(6, full.size());
96        assertTrue(full.addAll(Arrays.asList(three, four, five)));
97        assertEquals(9, full.size());
98    }
99
100    /**
101     * addAllAbsent adds each element from the given collection that did not
102     * already exist in the List
103     */
104    public void testAddAllAbsent() {
105        CopyOnWriteArrayList full = populatedArray(3);
106        // "one" is duplicate and will not be added
107        assertEquals(2, full.addAllAbsent(Arrays.asList(three, four, one)));
108        assertEquals(5, full.size());
109        assertEquals(0, full.addAllAbsent(Arrays.asList(three, four, one)));
110        assertEquals(5, full.size());
111    }
112
113    /**
114     * addIfAbsent will not add the element if it already exists in the list
115     */
116    public void testAddIfAbsent() {
117        CopyOnWriteArrayList full = populatedArray(SIZE);
118        full.addIfAbsent(one);
119        assertEquals(SIZE, full.size());
120    }
121
122    /**
123     * addIfAbsent adds the element when it does not exist in the list
124     */
125    public void testAddIfAbsent2() {
126        CopyOnWriteArrayList full = populatedArray(SIZE);
127        full.addIfAbsent(three);
128        assertTrue(full.contains(three));
129    }
130
131    /**
132     * clear removes all elements from the list
133     */
134    public void testClear() {
135        CopyOnWriteArrayList full = populatedArray(SIZE);
136        full.clear();
137        assertEquals(0, full.size());
138    }
139
140    /**
141     * Cloned list is equal
142     */
143    public void testClone() {
144        CopyOnWriteArrayList l1 = populatedArray(SIZE);
145        CopyOnWriteArrayList l2 = (CopyOnWriteArrayList)(l1.clone());
146        assertEquals(l1, l2);
147        l1.clear();
148        assertFalse(l1.equals(l2));
149    }
150
151    /**
152     * contains is true for added elements
153     */
154    public void testContains() {
155        CopyOnWriteArrayList full = populatedArray(3);
156        assertTrue(full.contains(one));
157        assertFalse(full.contains(five));
158    }
159
160    /**
161     * adding at an index places it in the indicated index
162     */
163    public void testAddIndex() {
164        CopyOnWriteArrayList full = populatedArray(3);
165        full.add(0, m1);
166        assertEquals(4, full.size());
167        assertEquals(m1, full.get(0));
168        assertEquals(zero, full.get(1));
169
170        full.add(2, m2);
171        assertEquals(5, full.size());
172        assertEquals(m2, full.get(2));
173        assertEquals(two, full.get(4));
174    }
175
176    /**
177     * lists with same elements are equal and have same hashCode
178     */
179    public void testEquals() {
180        CopyOnWriteArrayList a = populatedArray(3);
181        CopyOnWriteArrayList b = populatedArray(3);
182        assertTrue(a.equals(b));
183        assertTrue(b.equals(a));
184        assertTrue(a.containsAll(b));
185        assertTrue(b.containsAll(a));
186        assertEquals(a.hashCode(), b.hashCode());
187        a.add(m1);
188        assertFalse(a.equals(b));
189        assertFalse(b.equals(a));
190        assertTrue(a.containsAll(b));
191        assertFalse(b.containsAll(a));
192        b.add(m1);
193        assertTrue(a.equals(b));
194        assertTrue(b.equals(a));
195        assertTrue(a.containsAll(b));
196        assertTrue(b.containsAll(a));
197        assertEquals(a.hashCode(), b.hashCode());
198
199        assertFalse(a.equals(null));
200    }
201
202    /**
203     * containsAll returns true for collections with subset of elements
204     */
205    public void testContainsAll() {
206        CopyOnWriteArrayList full = populatedArray(3);
207        assertTrue(full.containsAll(Arrays.asList()));
208        assertTrue(full.containsAll(Arrays.asList(one)));
209        assertTrue(full.containsAll(Arrays.asList(one, two)));
210        assertFalse(full.containsAll(Arrays.asList(one, two, six)));
211        assertFalse(full.containsAll(Arrays.asList(six)));
212
213        try {
214            full.containsAll(null);
215            shouldThrow();
216        } catch (NullPointerException success) {}
217    }
218
219    /**
220     * get returns the value at the given index
221     */
222    public void testGet() {
223        CopyOnWriteArrayList full = populatedArray(3);
224        assertEquals(0, full.get(0));
225    }
226
227    /**
228     * indexOf gives the index for the given object
229     */
230    public void testIndexOf() {
231        CopyOnWriteArrayList full = populatedArray(3);
232        assertEquals(1, full.indexOf(one));
233        assertEquals(-1, full.indexOf("puppies"));
234    }
235
236    /**
237     * indexOf gives the index based on the given index
238     * at which to start searching
239     */
240    public void testIndexOf2() {
241        CopyOnWriteArrayList full = populatedArray(3);
242        assertEquals(1, full.indexOf(one, 0));
243        assertEquals(-1, full.indexOf(one, 2));
244    }
245
246    /**
247     * isEmpty returns true when empty, else false
248     */
249    public void testIsEmpty() {
250        CopyOnWriteArrayList empty = new CopyOnWriteArrayList();
251        CopyOnWriteArrayList full = populatedArray(SIZE);
252        assertTrue(empty.isEmpty());
253        assertFalse(full.isEmpty());
254    }
255
256    /**
257     * iterator() returns an iterator containing the elements of the
258     * list in insertion order
259     */
260    public void testIterator() {
261        Collection empty = new CopyOnWriteArrayList();
262        assertFalse(empty.iterator().hasNext());
263        try {
264            empty.iterator().next();
265            shouldThrow();
266        } catch (NoSuchElementException success) {}
267
268        Integer[] elements = new Integer[SIZE];
269        for (int i = 0; i < SIZE; i++)
270            elements[i] = i;
271        Collections.shuffle(Arrays.asList(elements));
272        Collection<Integer> full = populatedArray(elements);
273
274        Iterator it = full.iterator();
275        for (int j = 0; j < SIZE; j++) {
276            assertTrue(it.hasNext());
277            assertEquals(elements[j], it.next());
278        }
279        assertIteratorExhausted(it);
280    }
281
282    /**
283     * iterator of empty collection has no elements
284     */
285    public void testEmptyIterator() {
286        Collection c = new CopyOnWriteArrayList();
287        assertIteratorExhausted(c.iterator());
288    }
289
290    /**
291     * iterator.remove throws UnsupportedOperationException
292     */
293    public void testIteratorRemove() {
294        CopyOnWriteArrayList full = populatedArray(SIZE);
295        Iterator it = full.iterator();
296        it.next();
297        try {
298            it.remove();
299            shouldThrow();
300        } catch (UnsupportedOperationException success) {}
301    }
302
303    /**
304     * toString contains toString of elements
305     */
306    public void testToString() {
307        assertEquals("[]", new CopyOnWriteArrayList().toString());
308        CopyOnWriteArrayList full = populatedArray(3);
309        String s = full.toString();
310        for (int i = 0; i < 3; ++i)
311            assertTrue(s.contains(String.valueOf(i)));
312        assertEquals(new ArrayList(full).toString(),
313                     full.toString());
314    }
315
316    /**
317     * lastIndexOf returns the index for the given object
318     */
319    public void testLastIndexOf1() {
320        CopyOnWriteArrayList full = populatedArray(3);
321        full.add(one);
322        full.add(three);
323        assertEquals(3, full.lastIndexOf(one));
324        assertEquals(-1, full.lastIndexOf(six));
325    }
326
327    /**
328     * lastIndexOf returns the index from the given starting point
329     */
330    public void testLastIndexOf2() {
331        CopyOnWriteArrayList full = populatedArray(3);
332        full.add(one);
333        full.add(three);
334        assertEquals(3, full.lastIndexOf(one, 4));
335        assertEquals(-1, full.lastIndexOf(three, 3));
336    }
337
338    /**
339     * listIterator traverses all elements
340     */
341    public void testListIterator1() {
342        CopyOnWriteArrayList full = populatedArray(SIZE);
343        ListIterator i = full.listIterator();
344        int j;
345        for (j = 0; i.hasNext(); j++)
346            assertEquals(j, i.next());
347        assertEquals(SIZE, j);
348    }
349
350    /**
351     * listIterator only returns those elements after the given index
352     */
353    public void testListIterator2() {
354        CopyOnWriteArrayList full = populatedArray(3);
355        ListIterator i = full.listIterator(1);
356        int j;
357        for (j = 0; i.hasNext(); j++)
358            assertEquals(j + 1, i.next());
359        assertEquals(2, j);
360    }
361
362    /**
363     * remove(int) removes and returns the object at the given index
364     */
365    public void testRemove_int() {
366        int SIZE = 3;
367        for (int i = 0; i < SIZE; i++) {
368            CopyOnWriteArrayList full = populatedArray(SIZE);
369            assertEquals(i, full.remove(i));
370            assertEquals(SIZE - 1, full.size());
371            assertFalse(full.contains(new Integer(i)));
372        }
373    }
374
375    /**
376     * remove(Object) removes the object if found and returns true
377     */
378    public void testRemove_Object() {
379        int SIZE = 3;
380        for (int i = 0; i < SIZE; i++) {
381            CopyOnWriteArrayList full = populatedArray(SIZE);
382            assertFalse(full.remove(new Integer(-42)));
383            assertTrue(full.remove(new Integer(i)));
384            assertEquals(SIZE - 1, full.size());
385            assertFalse(full.contains(new Integer(i)));
386        }
387        CopyOnWriteArrayList x = new CopyOnWriteArrayList(Arrays.asList(4, 5, 6));
388        assertTrue(x.remove(new Integer(6)));
389        assertEquals(x, Arrays.asList(4, 5));
390        assertTrue(x.remove(new Integer(4)));
391        assertEquals(x, Arrays.asList(5));
392        assertTrue(x.remove(new Integer(5)));
393        assertEquals(x, Arrays.asList());
394        assertFalse(x.remove(new Integer(5)));
395    }
396
397    /**
398     * removeAll removes all elements from the given collection
399     */
400    public void testRemoveAll() {
401        CopyOnWriteArrayList full = populatedArray(3);
402        assertTrue(full.removeAll(Arrays.asList(one, two)));
403        assertEquals(1, full.size());
404        assertFalse(full.removeAll(Arrays.asList(one, two)));
405        assertEquals(1, full.size());
406    }
407
408    /**
409     * set changes the element at the given index
410     */
411    public void testSet() {
412        CopyOnWriteArrayList full = populatedArray(3);
413        assertEquals(2, full.set(2, four));
414        assertEquals(4, full.get(2));
415    }
416
417    /**
418     * size returns the number of elements
419     */
420    public void testSize() {
421        CopyOnWriteArrayList empty = new CopyOnWriteArrayList();
422        CopyOnWriteArrayList full = populatedArray(SIZE);
423        assertEquals(SIZE, full.size());
424        assertEquals(0, empty.size());
425    }
426
427    /**
428     * toArray() returns an Object array containing all elements from
429     * the list in insertion order
430     */
431    public void testToArray() {
432        Object[] a = new CopyOnWriteArrayList().toArray();
433        assertTrue(Arrays.equals(new Object[0], a));
434        assertSame(Object[].class, a.getClass());
435
436        Integer[] elements = new Integer[SIZE];
437        for (int i = 0; i < SIZE; i++)
438            elements[i] = i;
439        Collections.shuffle(Arrays.asList(elements));
440        Collection<Integer> full = populatedArray(elements);
441
442        assertTrue(Arrays.equals(elements, full.toArray()));
443        assertSame(Object[].class, full.toArray().getClass());
444    }
445
446    /**
447     * toArray(Integer array) returns an Integer array containing all
448     * elements from the list in insertion order
449     */
450    public void testToArray2() {
451        Collection empty = new CopyOnWriteArrayList();
452        Integer[] a;
453
454        a = new Integer[0];
455        assertSame(a, empty.toArray(a));
456
457        a = new Integer[SIZE / 2];
458        Arrays.fill(a, 42);
459        assertSame(a, empty.toArray(a));
460        assertNull(a[0]);
461        for (int i = 1; i < a.length; i++)
462            assertEquals(42, (int) a[i]);
463
464        Integer[] elements = new Integer[SIZE];
465        for (int i = 0; i < SIZE; i++)
466            elements[i] = i;
467        Collections.shuffle(Arrays.asList(elements));
468        Collection<Integer> full = populatedArray(elements);
469
470        Arrays.fill(a, 42);
471        assertTrue(Arrays.equals(elements, full.toArray(a)));
472        for (int i = 0; i < a.length; i++)
473            assertEquals(42, (int) a[i]);
474        assertSame(Integer[].class, full.toArray(a).getClass());
475
476        a = new Integer[SIZE];
477        Arrays.fill(a, 42);
478        assertSame(a, full.toArray(a));
479        assertTrue(Arrays.equals(elements, a));
480
481        a = new Integer[2 * SIZE];
482        Arrays.fill(a, 42);
483        assertSame(a, full.toArray(a));
484        assertTrue(Arrays.equals(elements, Arrays.copyOf(a, SIZE)));
485        assertNull(a[SIZE]);
486        for (int i = SIZE + 1; i < a.length; i++)
487            assertEquals(42, (int) a[i]);
488    }
489
490    /**
491     * sublists contains elements at indexes offset from their base
492     */
493    public void testSubList() {
494        CopyOnWriteArrayList a = populatedArray(10);
495        assertTrue(a.subList(1,1).isEmpty());
496        for (int j = 0; j < 9; ++j) {
497            for (int i = j ; i < 10; ++i) {
498                List b = a.subList(j,i);
499                for (int k = j; k < i; ++k) {
500                    assertEquals(new Integer(k), b.get(k-j));
501                }
502            }
503        }
504
505        List s = a.subList(2, 5);
506        assertEquals(3, s.size());
507        s.set(2, m1);
508        assertEquals(a.get(4), m1);
509        s.clear();
510        assertEquals(7, a.size());
511    }
512
513    // Exception tests
514
515    /**
516     * toArray throws an ArrayStoreException when the given array
517     * can not store the objects inside the list
518     */
519    public void testToArray_ArrayStoreException() {
520        CopyOnWriteArrayList c = new CopyOnWriteArrayList();
521        c.add("zfasdfsdf");
522        c.add("asdadasd");
523        try {
524            c.toArray(new Long[5]);
525            shouldThrow();
526        } catch (ArrayStoreException success) {}
527    }
528
529    /**
530     * get throws an IndexOutOfBoundsException on a negative index
531     */
532    public void testGet1_IndexOutOfBoundsException() {
533        CopyOnWriteArrayList c = populatedArray(5);
534        List[] lists = { c, c.subList(1, c.size() - 1) };
535        for (List list : lists) {
536            try {
537                list.get(-1);
538                shouldThrow();
539            } catch (IndexOutOfBoundsException success) {}
540        }
541    }
542
543    /**
544     * get throws an IndexOutOfBoundsException on a too high index
545     */
546    public void testGet2_IndexOutOfBoundsException() {
547        CopyOnWriteArrayList c = populatedArray(5);
548        List[] lists = { c, c.subList(1, c.size() - 1) };
549        for (List list : lists) {
550            try {
551                list.get(list.size());
552                shouldThrow();
553            } catch (IndexOutOfBoundsException success) {}
554        }
555    }
556
557    /**
558     * set throws an IndexOutOfBoundsException on a negative index
559     */
560    public void testSet1_IndexOutOfBoundsException() {
561        CopyOnWriteArrayList c = populatedArray(5);
562        List[] lists = { c, c.subList(1, c.size() - 1) };
563        for (List list : lists) {
564            try {
565                list.set(-1, "qwerty");
566                shouldThrow();
567            } catch (IndexOutOfBoundsException success) {}
568        }
569    }
570
571    /**
572     * set throws an IndexOutOfBoundsException on a too high index
573     */
574    public void testSet2() {
575        CopyOnWriteArrayList c = populatedArray(5);
576        List[] lists = { c, c.subList(1, c.size() - 1) };
577        for (List list : lists) {
578            try {
579                list.set(list.size(), "qwerty");
580                shouldThrow();
581            } catch (IndexOutOfBoundsException success) {}
582        }
583    }
584
585    /**
586     * add throws an IndexOutOfBoundsException on a negative index
587     */
588    public void testAdd1_IndexOutOfBoundsException() {
589        CopyOnWriteArrayList c = populatedArray(5);
590        List[] lists = { c, c.subList(1, c.size() - 1) };
591        for (List list : lists) {
592            try {
593                list.add(-1, "qwerty");
594                shouldThrow();
595            } catch (IndexOutOfBoundsException success) {}
596        }
597    }
598
599    /**
600     * add throws an IndexOutOfBoundsException on a too high index
601     */
602    public void testAdd2_IndexOutOfBoundsException() {
603        CopyOnWriteArrayList c = populatedArray(5);
604        List[] lists = { c, c.subList(1, c.size() - 1) };
605        for (List list : lists) {
606            try {
607                list.add(list.size() + 1, "qwerty");
608                shouldThrow();
609            } catch (IndexOutOfBoundsException success) {}
610        }
611    }
612
613    /**
614     * remove throws an IndexOutOfBoundsException on a negative index
615     */
616    public void testRemove1_IndexOutOfBounds() {
617        CopyOnWriteArrayList c = populatedArray(5);
618        List[] lists = { c, c.subList(1, c.size() - 1) };
619        for (List list : lists) {
620            try {
621                list.remove(-1);
622                shouldThrow();
623            } catch (IndexOutOfBoundsException success) {}
624        }
625    }
626
627    /**
628     * remove throws an IndexOutOfBoundsException on a too high index
629     */
630    public void testRemove2_IndexOutOfBounds() {
631        CopyOnWriteArrayList c = populatedArray(5);
632        List[] lists = { c, c.subList(1, c.size() - 1) };
633        for (List list : lists) {
634            try {
635                list.remove(list.size());
636                shouldThrow();
637            } catch (IndexOutOfBoundsException success) {}
638        }
639    }
640
641    /**
642     * addAll throws an IndexOutOfBoundsException on a negative index
643     */
644    public void testAddAll1_IndexOutOfBoundsException() {
645        CopyOnWriteArrayList c = populatedArray(5);
646        List[] lists = { c, c.subList(1, c.size() - 1) };
647        for (List list : lists) {
648            try {
649                list.addAll(-1, new LinkedList());
650                shouldThrow();
651            } catch (IndexOutOfBoundsException success) {}
652        }
653    }
654
655    /**
656     * addAll throws an IndexOutOfBoundsException on a too high index
657     */
658    public void testAddAll2_IndexOutOfBoundsException() {
659        CopyOnWriteArrayList c = populatedArray(5);
660        List[] lists = { c, c.subList(1, c.size() - 1) };
661        for (List list : lists) {
662            try {
663                list.addAll(list.size() + 1, new LinkedList());
664                shouldThrow();
665            } catch (IndexOutOfBoundsException success) {}
666        }
667    }
668
669    /**
670     * listIterator throws an IndexOutOfBoundsException on a negative index
671     */
672    public void testListIterator1_IndexOutOfBoundsException() {
673        CopyOnWriteArrayList c = populatedArray(5);
674        List[] lists = { c, c.subList(1, c.size() - 1) };
675        for (List list : lists) {
676            try {
677                list.listIterator(-1);
678                shouldThrow();
679            } catch (IndexOutOfBoundsException success) {}
680        }
681    }
682
683    /**
684     * listIterator throws an IndexOutOfBoundsException on a too high index
685     */
686    public void testListIterator2_IndexOutOfBoundsException() {
687        CopyOnWriteArrayList c = populatedArray(5);
688        List[] lists = { c, c.subList(1, c.size() - 1) };
689        for (List list : lists) {
690            try {
691                list.listIterator(list.size() + 1);
692                shouldThrow();
693            } catch (IndexOutOfBoundsException success) {}
694        }
695    }
696
697    /**
698     * subList throws an IndexOutOfBoundsException on a negative index
699     */
700    public void testSubList1_IndexOutOfBoundsException() {
701        CopyOnWriteArrayList c = populatedArray(5);
702        List[] lists = { c, c.subList(1, c.size() - 1) };
703        for (List list : lists) {
704            try {
705                list.subList(-1, list.size());
706                shouldThrow();
707            } catch (IndexOutOfBoundsException success) {}
708        }
709    }
710
711    /**
712     * subList throws an IndexOutOfBoundsException on a too high index
713     */
714    public void testSubList2_IndexOutOfBoundsException() {
715        CopyOnWriteArrayList c = populatedArray(5);
716        List[] lists = { c, c.subList(1, c.size() - 1) };
717        for (List list : lists) {
718            try {
719                list.subList(0, list.size() + 1);
720                shouldThrow();
721            } catch (IndexOutOfBoundsException success) {}
722        }
723    }
724
725    /**
726     * subList throws IndexOutOfBoundsException when the second index
727     * is lower then the first
728     */
729    public void testSubList3_IndexOutOfBoundsException() {
730        CopyOnWriteArrayList c = populatedArray(5);
731        List[] lists = { c, c.subList(1, c.size() - 1) };
732        for (List list : lists) {
733            try {
734                list.subList(list.size() - 1, 1);
735                shouldThrow();
736            } catch (IndexOutOfBoundsException success) {}
737        }
738    }
739
740    /**
741     * a deserialized serialized list is equal
742     */
743    public void testSerialization() throws Exception {
744        List x = populatedArray(SIZE);
745        List y = serialClone(x);
746
747        assertNotSame(x, y);
748        assertEquals(x.size(), y.size());
749        assertEquals(x.toString(), y.toString());
750        assertTrue(Arrays.equals(x.toArray(), y.toArray()));
751        assertEquals(x, y);
752        assertEquals(y, x);
753        while (!x.isEmpty()) {
754            assertFalse(y.isEmpty());
755            assertEquals(x.remove(0), y.remove(0));
756        }
757        assertTrue(y.isEmpty());
758    }
759
760}
761