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