1/*
2 *  Licensed to the Apache Software Foundation (ASF) under one or more
3 *  contributor license agreements.  See the NOTICE file distributed with
4 *  this work for additional information regarding copyright ownership.
5 *  The ASF licenses this file to You under the Apache License, Version 2.0
6 *  (the "License"); you may not use this file except in compliance with
7 *  the License.  You may obtain a copy of the License at
8 *
9 *     http://www.apache.org/licenses/LICENSE-2.0
10 *
11 *  Unless required by applicable law or agreed to in writing, software
12 *  distributed under the License is distributed on an "AS IS" BASIS,
13 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 *  See the License for the specific language governing permissions and
15 *  limitations under the License.
16 */
17package org.apache.harmony.tests.java.util;
18
19import java.util.ArrayDeque;
20import java.util.ArrayList;
21import java.util.Arrays;
22import java.util.Collection;
23import java.util.ConcurrentModificationException;
24import java.util.HashSet;
25import java.util.Iterator;
26import java.util.List;
27import java.util.Set;
28import java.util.Spliterator;
29import java.util.Vector;
30
31import libcore.java.util.SpliteratorTester;
32import tests.support.Support_ListTest;
33import libcore.java.util.ForEachRemainingTester;
34
35import static libcore.java.util.RemoveIfTester.*;
36
37public class ArrayListTest extends junit.framework.TestCase {
38
39    List alist;
40
41    Object[] objArray;
42
43    /**
44     * java.util.ArrayList#ArrayList()
45     */
46    public void test_Constructor() {
47        // Test for method java.util.ArrayList()
48        new Support_ListTest("", alist).runTest();
49
50        ArrayList subList = new ArrayList();
51        for (int i = -50; i < 150; i++)
52            subList.add(new Integer(i));
53        new Support_ListTest("", subList.subList(50, 150)).runTest();
54    }
55
56    /**
57     * java.util.ArrayList#ArrayList(int)
58     */
59    public void test_ConstructorI() {
60        // Test for method java.util.ArrayList(int)
61        ArrayList al = new ArrayList(5);
62        assertEquals("Incorrect arrayList created", 0, al.size());
63
64        al = new ArrayList(0);
65        assertEquals("Incorrect arrayList created", 0, al.size());
66
67        try {
68            new ArrayList(-1);
69            fail("IllegalArgumentException expected");
70        } catch (IllegalArgumentException expected) {
71        }
72    }
73
74    /**
75     * java.util.ArrayList#ArrayList(java.util.Collection)
76     */
77    public void test_ConstructorLjava_util_Collection() {
78        // Test for method java.util.ArrayList(java.util.Collection)
79        ArrayList al = new ArrayList(Arrays.asList(objArray));
80        assertTrue("arrayList created from collection has incorrect size", al
81                .size() == objArray.length);
82        for (int counter = 0; counter < objArray.length; counter++)
83            assertTrue(
84                    "arrayList created from collection has incorrect elements",
85                    al.get(counter) == objArray[counter]);
86        try {
87            new ArrayList(null);
88            fail("NullPointerException expected");
89        } catch (NullPointerException e) {
90            //expected
91        }
92
93    }
94
95    public void testConstructorWithConcurrentCollection() {
96        Collection<String> collection = shrinksOnSize("A", "B", "C", "D");
97        ArrayList<String> list = new ArrayList<String>(collection);
98        assertFalse(list.contains(null));
99    }
100
101    /**
102     * java.util.ArrayList#add(int, java.lang.Object)
103     */
104    public void test_addILjava_lang_Object() {
105        // Test for method void java.util.ArrayList.add(int, java.lang.Object)
106        Object o;
107        alist.add(50, o = new Object());
108        assertTrue("Failed to add Object", alist.get(50) == o);
109        assertTrue("Failed to fix up list after insert",
110                alist.get(51) == objArray[50]
111                        && (alist.get(52) == objArray[51]));
112        Object oldItem = alist.get(25);
113        alist.add(25, null);
114        assertNull("Should have returned null", alist.get(25));
115        assertTrue("Should have returned the old item from slot 25", alist
116                .get(26) == oldItem);
117
118        alist.add(0, o = new Object());
119        assertEquals("Failed to add Object", alist.get(0), o);
120        assertEquals(alist.get(1), objArray[0]);
121        assertEquals(alist.get(2), objArray[1]);
122
123        oldItem = alist.get(0);
124        alist.add(0, null);
125        assertNull("Should have returned null", alist.get(0));
126        assertEquals("Should have returned the old item from slot 0", alist
127                .get(1), oldItem);
128
129        try {
130            alist.add(-1, new Object());
131            fail("Should throw IndexOutOfBoundsException");
132        } catch (IndexOutOfBoundsException e) {
133            // Expected
134            assertNotNull(e.getMessage());
135        }
136
137        try {
138            alist.add(-1, null);
139            fail("Should throw IndexOutOfBoundsException");
140        } catch (IndexOutOfBoundsException e) {
141            // Expected
142            assertNotNull(e.getMessage());
143        }
144
145        try {
146            alist.add(alist.size() + 1, new Object());
147            fail("Should throw IndexOutOfBoundsException");
148        } catch (IndexOutOfBoundsException e) {
149            // Expected
150            assertNotNull(e.getMessage());
151        }
152
153        try {
154            alist.add(alist.size() + 1, null);
155            fail("Should throw IndexOutOfBoundsException");
156        } catch (IndexOutOfBoundsException e) {
157            // Expected
158            assertNotNull(e.getMessage());
159        }
160    }
161
162    /**
163     * java.util.ArrayList#add(int, java.lang.Object)
164     */
165    public void test_addILjava_lang_Object_2() {
166        Object o = new Object();
167        int size = alist.size();
168        alist.add(size, o);
169        assertEquals("Failed to add Object", alist.get(size), o);
170        assertEquals(alist.get(size - 2), objArray[size - 2]);
171        assertEquals(alist.get(size - 1), objArray[size - 1]);
172
173        alist.remove(size);
174
175        size = alist.size();
176        alist.add(size, null);
177        assertNull("Should have returned null", alist.get(size));
178        assertEquals(alist.get(size - 2), objArray[size - 2]);
179        assertEquals(alist.get(size - 1), objArray[size - 1]);
180    }
181
182    /**
183     * java.util.ArrayList#add(java.lang.Object)
184     */
185    public void test_addLjava_lang_Object() {
186        // Test for method boolean java.util.ArrayList.add(java.lang.Object)
187        Object o = new Object();
188        alist.add(o);
189        assertTrue("Failed to add Object", alist.get(alist.size() - 1) == o);
190        alist.add(null);
191        assertNull("Failed to add null", alist.get(alist.size() - 1));
192    }
193
194    /**
195     * java.util.ArrayList#addAll(int, java.util.Collection)
196     */
197    public void test_addAllILjava_util_Collection() {
198        // Test for method boolean java.util.ArrayList.addAll(int,
199        // java.util.Collection)
200        alist.addAll(50, alist);
201        assertEquals("Returned incorrect size after adding to existing list",
202                200, alist.size());
203        for (int i = 0; i < 50; i++)
204            assertTrue("Manipulated elements < index",
205                    alist.get(i) == objArray[i]);
206        for (int i = 0; i >= 50 && (i < 150); i++)
207            assertTrue("Failed to ad elements properly",
208                    alist.get(i) == objArray[i - 50]);
209        for (int i = 0; i >= 150 && (i < 200); i++)
210            assertTrue("Failed to ad elements properly",
211                    alist.get(i) == objArray[i - 100]);
212        ArrayList listWithNulls = new ArrayList();
213        listWithNulls.add(null);
214        listWithNulls.add(null);
215        listWithNulls.add("yoink");
216        listWithNulls.add("kazoo");
217        listWithNulls.add(null);
218        alist.addAll(100, listWithNulls);
219        assertTrue("Incorrect size: " + alist.size(), alist.size() == 205);
220        assertNull("Item at slot 100 should be null", alist.get(100));
221        assertNull("Item at slot 101 should be null", alist.get(101));
222        assertEquals("Item at slot 102 should be 'yoink'", "yoink", alist
223                .get(102));
224        assertEquals("Item at slot 103 should be 'kazoo'", "kazoo", alist
225                .get(103));
226        assertNull("Item at slot 104 should be null", alist.get(104));
227        alist.addAll(205, listWithNulls);
228        assertTrue("Incorrect size2: " + alist.size(), alist.size() == 210);
229    }
230
231    /**
232     * java.util.ArrayList#addAll(int, java.util.Collection)
233     */
234    @SuppressWarnings("unchecked")
235    public void test_addAllILjava_util_Collection_2() {
236        // Regression for HARMONY-467
237        ArrayList obj = new ArrayList();
238        try {
239            obj.addAll((int) -1, (Collection) null);
240            fail("IndexOutOfBoundsException expected");
241        } catch (IndexOutOfBoundsException e) {
242            // Expected
243            assertNotNull(e.getMessage());
244        }
245
246        // Regression for HARMONY-5705
247        String[] data = new String[] { "1", "2", "3", "4", "5", "6", "7", "8" };
248        ArrayList list1 = new ArrayList();
249        ArrayList list2 = new ArrayList();
250        for (String d : data) {
251            list1.add(d);
252            list2.add(d);
253            list2.add(d);
254        }
255        while (list1.size() > 0)
256            list1.remove(0);
257        list1.addAll(list2);
258        assertTrue("The object list is not the same as original list", list1
259                .containsAll(list2)
260                && list2.containsAll(list1));
261
262        obj = new ArrayList();
263        for (int i = 0; i < 100; i++) {
264            if (list1.size() > 0) {
265                obj.removeAll(list1);
266                obj.addAll(list1);
267            }
268        }
269        assertTrue("The object list is not the same as original list", obj
270                .containsAll(list1)
271                && list1.containsAll(obj));
272
273        // Regression for Harmony-5799
274        list1 = new ArrayList();
275        list2 = new ArrayList();
276        int location = 2;
277
278        String[] strings = { "0", "1", "2", "3", "4", "5", "6" };
279        int[] integers = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
280        for (int i = 0; i < 7; i++) {
281            list1.add(strings[i]);
282        }
283        for (int i = 0; i < 10; i++) {
284            list2.add(integers[i]);
285        }
286        list1.remove(location);
287        list1.addAll(location, list2);
288
289        // Inserted elements should be equal to integers array
290        for (int i = 0; i < integers.length; i++) {
291            assertEquals(integers[i], list1.get(location + i));
292        }
293        // Elements after inserted location should
294        // be equals to related elements in strings array
295        for (int i = location + 1; i < strings.length; i++) {
296            assertEquals(strings[i], list1.get(i + integers.length - 1));
297        }
298    }
299
300    /**
301     * java.util.ArrayList#addAll(int, java.util.Collection)
302     */
303    public void test_addAllILjava_util_Collection_3() {
304        ArrayList obj = new ArrayList();
305        obj.addAll(0, obj);
306        obj.addAll(obj.size(), obj);
307        try {
308            obj.addAll(-1, obj);
309            fail("Should throw IndexOutOfBoundsException");
310        } catch (IndexOutOfBoundsException e) {
311            // Expected
312            assertNotNull(e.getMessage());
313        }
314
315        try {
316            obj.addAll(obj.size() + 1, obj);
317            fail("Should throw IndexOutOfBoundsException");
318        } catch (IndexOutOfBoundsException e) {
319            // Expected
320            assertNotNull(e.getMessage());
321        }
322
323        try {
324            obj.addAll(0, null);
325            fail("Should throw NullPointerException");
326        } catch (NullPointerException e) {
327            // Excepted
328        }
329
330        try {
331            obj.addAll(obj.size() + 1, null);
332            fail("Should throw IndexOutOfBoundsException");
333        } catch (IndexOutOfBoundsException e) {
334            // Expected
335            assertNotNull(e.getMessage());
336        }
337
338        try {
339            obj.addAll((int) -1, (Collection) null);
340            fail("IndexOutOfBoundsException expected");
341        } catch (IndexOutOfBoundsException e) {
342            // Expected
343            assertNotNull(e.getMessage());
344        }
345    }
346
347// BEGIN Android-removed
348// The spec does not mandate that IndexOutOfBoundsException be thrown in
349// preference to NullPointerException when the caller desserves both.
350//
351//    /**
352//     * java.util.ArrayList#addAll(int, java.util.Collection)
353//     */
354//    public void test_addAllILjava_util_Collection_2() {
355//        // Regression for HARMONY-467
356//        ArrayList obj = new ArrayList();
357//        try {
358//            obj.addAll((int) -1, (Collection) null);
359//            fail("IndexOutOfBoundsException expected");
360//        } catch (IndexOutOfBoundsException e) {
361//        }
362//    }
363// END Android-removed
364
365    /**
366     * java.util.ArrayList#addAll(java.util.Collection)
367     */
368    public void test_addAllLjava_util_Collection() {
369        // Test for method boolean
370        // java.util.ArrayList.addAll(java.util.Collection)
371        List l = new ArrayList();
372        l.addAll(alist);
373        for (int i = 0; i < alist.size(); i++)
374            assertTrue("Failed to add elements properly", l.get(i).equals(
375                    alist.get(i)));
376        alist.addAll(alist);
377        assertEquals("Returned incorrect size after adding to existing list",
378                200, alist.size());
379        for (int i = 0; i < 100; i++) {
380            assertTrue("Added to list in incorrect order", alist.get(i).equals(
381                    l.get(i)));
382            assertTrue("Failed to add to existing list", alist.get(i + 100)
383                    .equals(l.get(i)));
384        }
385        Set setWithNulls = new HashSet();
386        setWithNulls.add(null);
387        setWithNulls.add(null);
388        setWithNulls.add("yoink");
389        setWithNulls.add("kazoo");
390        setWithNulls.add(null);
391        alist.addAll(100, setWithNulls);
392        Iterator i = setWithNulls.iterator();
393        assertTrue("Item at slot 100 is wrong: " + alist.get(100), alist
394                .get(100) == i.next());
395        assertTrue("Item at slot 101 is wrong: " + alist.get(101), alist
396                .get(101) == i.next());
397        assertTrue("Item at slot 103 is wrong: " + alist.get(102), alist
398                .get(102) == i.next());
399
400        try {
401            alist.addAll(null);
402            fail("Should throw NullPointerException");
403        } catch (NullPointerException e) {
404            // Excepted
405        }
406
407        // Regression test for Harmony-3481
408        ArrayList<Integer> originalList = new ArrayList<Integer>(12);
409        for (int j = 0; j < 12; j++) {
410            originalList.add(j);
411        }
412
413        originalList.remove(0);
414        originalList.remove(0);
415
416        ArrayList<Integer> additionalList = new ArrayList<Integer>(11);
417        for (int j = 0; j < 11; j++) {
418            additionalList.add(j);
419        }
420        assertTrue(originalList.addAll(additionalList));
421        assertEquals(21, originalList.size());
422
423    }
424
425    public void test_ArrayList_addAll_scenario1() {
426        ArrayList arrayListA = new ArrayList();
427        arrayListA.add(1);
428        ArrayList arrayListB = new ArrayList();
429        arrayListB.add(1);
430        arrayListA.addAll(1, arrayListB);
431        int size = arrayListA.size();
432        assertEquals(2, size);
433        for (int index = 0; index < size; index++) {
434            assertEquals(1, arrayListA.get(index));
435        }
436    }
437
438    public void test_ArrayList_addAll_scenario2() {
439        ArrayList arrayList = new ArrayList();
440        arrayList.add(1);
441        arrayList.addAll(1, arrayList);
442        int size = arrayList.size();
443        assertEquals(2, size);
444        for (int index = 0; index < size; index++) {
445            assertEquals(1, arrayList.get(index));
446        }
447    }
448
449    // Regression test for HARMONY-5839
450    public void testaddAllHarmony5839() {
451        Collection coll = Arrays.asList(new String[] { "1", "2" });
452        List list = new ArrayList();
453        list.add("a");
454        list.add(0, "b");
455        list.add(0, "c");
456        list.add(0, "d");
457        list.add(0, "e");
458        list.add(0, "f");
459        list.add(0, "g");
460        list.add(0, "h");
461        list.add(0, "i");
462
463        list.addAll(6, coll);
464
465        assertEquals(11, list.size());
466        assertFalse(list.contains(null));
467    }
468
469    /**
470     * java.util.ArrayList#clear()
471     */
472    public void test_clear() {
473        // Test for method void java.util.ArrayList.clear()
474        alist.clear();
475        assertEquals("List did not clear", 0, alist.size());
476        alist.add(null);
477        alist.add(null);
478        alist.add(null);
479        alist.add("bam");
480        alist.clear();
481        assertEquals("List with nulls did not clear", 0, alist.size());
482        /*
483         * for (int i = 0; i < alist.size(); i++) assertNull("Failed to clear
484         * list", alist.get(i));
485         */
486
487    }
488
489    /**
490     * java.util.ArrayList#clone()
491     */
492    public void test_clone() {
493        // Test for method java.lang.Object java.util.ArrayList.clone()
494        ArrayList x = (ArrayList) (((ArrayList) (alist)).clone());
495        assertTrue("Cloned list was inequal to original", x.equals(alist));
496        for (int i = 0; i < alist.size(); i++)
497            assertTrue("Cloned list contains incorrect elements",
498                    alist.get(i) == x.get(i));
499
500        alist.add(null);
501        alist.add(25, null);
502        x = (ArrayList) (((ArrayList) (alist)).clone());
503        assertTrue("nulls test - Cloned list was inequal to original", x
504                .equals(alist));
505        for (int i = 0; i < alist.size(); i++)
506            assertTrue("nulls test - Cloned list contains incorrect elements",
507                    alist.get(i) == x.get(i));
508
509    }
510
511    /**
512     * java.util.ArrayList#contains(java.lang.Object)
513     */
514    public void test_containsLjava_lang_Object() {
515        // Test for method boolean
516        // java.util.ArrayList.contains(java.lang.Object)
517        assertTrue("Returned false for valid element", alist
518                .contains(objArray[99]));
519        assertTrue("Returned false for equal element", alist
520                .contains(new Integer(8)));
521        assertTrue("Returned true for invalid element", !alist
522                .contains(new Object()));
523        assertTrue("Returned true for null but should have returned false",
524                !alist.contains(null));
525        alist.add(null);
526        assertTrue("Returned false for null but should have returned true",
527                alist.contains(null));
528    }
529
530    /**
531     * java.util.ArrayList#ensureCapacity(int)
532     */
533    public void test_ensureCapacityI() throws Exception {
534        // Test for method void java.util.ArrayList.ensureCapacity(int)
535        // TODO : There is no good way to test this as it only really impacts on
536        // the private implementation.
537
538        Object testObject = new Object();
539        int capacity = 20;
540        ArrayList al = new ArrayList(capacity);
541        int i;
542        for (i = 0; i < capacity / 2; i++) {
543            al.add(i, new Object());
544        }
545        al.add(i, testObject);
546        int location = al.indexOf(testObject);
547        al.ensureCapacity(capacity);
548        assertTrue("EnsureCapacity moved objects around in array1.",
549                location == al.indexOf(testObject));
550        al.remove(0);
551        al.ensureCapacity(capacity);
552        assertTrue("EnsureCapacity moved objects around in array2.",
553                --location == al.indexOf(testObject));
554        al.ensureCapacity(capacity + 2);
555        assertTrue("EnsureCapacity did not change location.", location == al
556                .indexOf(testObject));
557
558        ArrayList<String> list = new ArrayList<String>(1);
559        list.add("hello");
560        list.ensureCapacity(Integer.MIN_VALUE);
561    }
562
563    /**
564     * java.util.ArrayList#get(int)
565     */
566    public void test_getI() {
567        // Test for method java.lang.Object java.util.ArrayList.get(int)
568        assertTrue("Returned incorrect element", alist.get(22) == objArray[22]);
569        try {
570            alist.get(8765);
571            fail("Failed to throw expected exception for index > size");
572        } catch (IndexOutOfBoundsException e) {
573            // Expected
574            assertNotNull(e.getMessage());
575        }
576    }
577
578    /**
579     * java.util.ArrayList#indexOf(java.lang.Object)
580     */
581    public void test_indexOfLjava_lang_Object() {
582        // Test for method int java.util.ArrayList.indexOf(java.lang.Object)
583        assertEquals("Returned incorrect index", 87, alist
584                .indexOf(objArray[87]));
585        assertEquals("Returned index for invalid Object", -1, alist
586                .indexOf(new Object()));
587        alist.add(25, null);
588        alist.add(50, null);
589        assertTrue("Wrong indexOf for null.  Wanted 25 got: "
590                + alist.indexOf(null), alist.indexOf(null) == 25);
591    }
592
593    /**
594     * java.util.ArrayList#isEmpty()
595     */
596    public void test_isEmpty() {
597        // Test for method boolean java.util.ArrayList.isEmpty()
598        assertTrue("isEmpty returned false for new list", new ArrayList()
599                .isEmpty());
600        assertTrue("Returned true for existing list with elements", !alist
601                .isEmpty());
602    }
603
604    /**
605     * java.util.ArrayList#lastIndexOf(java.lang.Object)
606     */
607    public void test_lastIndexOfLjava_lang_Object() {
608        // Test for method int java.util.ArrayList.lastIndexOf(java.lang.Object)
609        alist.add(new Integer(99));
610        assertEquals("Returned incorrect index", 100, alist
611                .lastIndexOf(objArray[99]));
612        assertEquals("Returned index for invalid Object", -1, alist
613                .lastIndexOf(new Object()));
614        alist.add(25, null);
615        alist.add(50, null);
616        assertTrue("Wrong lastIndexOf for null.  Wanted 50 got: "
617                + alist.lastIndexOf(null), alist.lastIndexOf(null) == 50);
618    }
619
620    /**
621     * {@link java.util.ArrayList#removeRange(int, int)}
622     */
623    public void test_removeRange() {
624        MockArrayList mylist = new MockArrayList();
625        mylist.removeRange(0, 0);
626
627        try {
628            mylist.removeRange(0, 1);
629            fail("Should throw IndexOutOfBoundsException");
630        } catch (IndexOutOfBoundsException e) {
631            // Expected
632            assertNotNull(e.getMessage());
633        }
634
635        int[] data = { 1, 2, 3 };
636        for (int i = 0; i < data.length; i++) {
637            mylist.add(i, data[i]);
638        }
639
640        mylist.removeRange(0, 1);
641        assertEquals(data[1], mylist.get(0));
642        assertEquals(data[2], mylist.get(1));
643
644        try {
645            mylist.removeRange(-1, 1);
646            fail("Should throw IndexOutOfBoundsException");
647        } catch (IndexOutOfBoundsException e) {
648            // Expected
649            assertNotNull(e.getMessage());
650        }
651
652        try {
653            mylist.removeRange(0, -1);
654            fail("Should throw IndexOutOfBoundsException");
655        } catch (IndexOutOfBoundsException e) {
656            // Expected
657            assertNotNull(e.getMessage());
658        }
659
660        try {
661            mylist.removeRange(1, 0);
662            fail("Should throw IndexOutOfBoundsException");
663        } catch (IndexOutOfBoundsException e) {
664            // Expected
665            assertNotNull(e.getMessage());
666        }
667
668        try {
669            mylist.removeRange(2, 1);
670            fail("Should throw IndexOutOfBoundsException");
671        } catch (IndexOutOfBoundsException e) {
672            // Expected
673            assertNotNull(e.getMessage());
674        }
675    }
676
677    /**
678     * java.util.ArrayList#remove(int)
679     */
680    public void test_removeI() {
681        // Test for method java.lang.Object java.util.ArrayList.remove(int)
682        alist.remove(10);
683        assertEquals("Failed to remove element", -1, alist
684                .indexOf(objArray[10]));
685        try {
686            alist.remove(999);
687            fail("Failed to throw exception when index out of range");
688        } catch (IndexOutOfBoundsException e) {
689            // Expected
690            assertNotNull(e.getMessage());
691        }
692
693        ArrayList myList = (ArrayList) (((ArrayList) (alist)).clone());
694        alist.add(25, null);
695        alist.add(50, null);
696        alist.remove(50);
697        alist.remove(25);
698        assertTrue("Removing nulls did not work", alist.equals(myList));
699
700        List list = new ArrayList(Arrays.asList(new String[] { "a", "b", "c",
701                "d", "e", "f", "g" }));
702        assertTrue("Removed wrong element 1", list.remove(0) == "a");
703        assertTrue("Removed wrong element 2", list.remove(4) == "f");
704        String[] result = new String[5];
705        list.toArray(result);
706        assertTrue("Removed wrong element 3", Arrays.equals(result,
707                new String[] { "b", "c", "d", "e", "g" }));
708
709        List l = new ArrayList(0);
710        l.add(new Object());
711        l.add(new Object());
712        l.remove(0);
713        l.remove(0);
714        try {
715            l.remove(-1);
716            fail("-1 should cause exception");
717        } catch (IndexOutOfBoundsException e) {
718            // Expected
719            assertNotNull(e.getMessage());
720        }
721        try {
722            l.remove(0);
723            fail("0 should case exception");
724        } catch (IndexOutOfBoundsException e) {
725            // Expected
726            assertNotNull(e.getMessage());
727        }
728    }
729
730    /**
731     * java.util.ArrayList#set(int, java.lang.Object)
732     */
733    public void test_setILjava_lang_Object() {
734        // Test for method java.lang.Object java.util.ArrayList.set(int,
735        // java.lang.Object)
736        Object obj;
737        alist.set(65, obj = new Object());
738        assertTrue("Failed to set object", alist.get(65) == obj);
739        alist.set(50, null);
740        assertNull("Setting to null did not work", alist.get(50));
741        assertTrue("Setting increased the list's size to: " + alist.size(),
742                alist.size() == 100);
743
744        obj = new Object();
745        alist.set(0, obj);
746        assertTrue("Failed to set object", alist.get(0) == obj);
747
748        try {
749            alist.set(-1, obj);
750            fail("Should throw IndexOutOfBoundsException");
751        } catch (IndexOutOfBoundsException e) {
752            // Expected
753            assertNotNull(e.getMessage());
754        }
755
756        try {
757            alist.set(alist.size(), obj);
758            fail("Should throw IndexOutOfBoundsException");
759        } catch (IndexOutOfBoundsException e) {
760            // Expected
761            assertNotNull(e.getMessage());
762        }
763
764        try {
765            alist.set(-1, null);
766            fail("Should throw IndexOutOfBoundsException");
767        } catch (IndexOutOfBoundsException e) {
768            // Expected
769            assertNotNull(e.getMessage());
770        }
771
772        try {
773            alist.set(alist.size(), null);
774            fail("Should throw IndexOutOfBoundsException");
775        } catch (IndexOutOfBoundsException e) {
776            // Expected
777            assertNotNull(e.getMessage());
778        }
779    }
780
781    /**
782     * java.util.ArrayList#size()
783     */
784    public void test_size() {
785        // Test for method int java.util.ArrayList.size()
786        assertEquals("Returned incorrect size for exiting list", 100, alist
787                .size());
788        assertEquals("Returned incorrect size for new list", 0, new ArrayList()
789                .size());
790    }
791
792    /**
793     * java.util.AbstractCollection#toString()
794     */
795    public void test_toString() {
796        ArrayList l = new ArrayList(1);
797        l.add(l);
798        String result = l.toString();
799        assertTrue("should contain self ref", result.indexOf("(this") > -1);
800    }
801
802    /**
803     * java.util.ArrayList#toArray()
804     */
805    public void test_toArray() {
806        // Test for method java.lang.Object [] java.util.ArrayList.toArray()
807        alist.set(25, null);
808        alist.set(75, null);
809        Object[] obj = alist.toArray();
810        assertEquals("Returned array of incorrect size", objArray.length,
811                obj.length);
812
813        for (int i = 0; i < obj.length; i++) {
814            if ((i == 25) || (i == 75))
815                assertNull("Should be null at: " + i + " but instead got: "
816                        + obj[i], obj[i]);
817            else
818                assertTrue("Returned incorrect array: " + i,
819                        obj[i] == objArray[i]);
820        }
821
822    }
823
824    /**
825     * java.util.ArrayList#toArray(java.lang.Object[])
826     */
827    public void test_toArray$Ljava_lang_Object() {
828        // Test for method java.lang.Object []
829        // java.util.ArrayList.toArray(java.lang.Object [])
830        alist.set(25, null);
831        alist.set(75, null);
832        Integer[] argArray = new Integer[100];
833        Object[] retArray;
834        retArray = alist.toArray(argArray);
835        assertTrue("Returned different array than passed", retArray == argArray);
836        argArray = new Integer[1000];
837        retArray = alist.toArray(argArray);
838        assertNull("Failed to set first extra element to null", argArray[alist
839                .size()]);
840        for (int i = 0; i < 100; i++) {
841            if ((i == 25) || (i == 75))
842                assertNull("Should be null: " + i, retArray[i]);
843            else
844                assertTrue("Returned incorrect array: " + i,
845                        retArray[i] == objArray[i]);
846        }
847
848        String[] strArray = new String[100];
849        try {
850            alist.toArray(strArray);
851            fail("ArrayStoreException expected");
852        } catch (ArrayStoreException e) {
853            //expected
854        }
855    }
856
857    /**
858     * java.util.ArrayList#trimToSize()
859     */
860    public void test_trimToSize() {
861        // Test for method void java.util.ArrayList.trimToSize()
862        for (int i = 99; i > 24; i--)
863            alist.remove(i);
864        ((ArrayList) alist).trimToSize();
865        assertEquals("Returned incorrect size after trim", 25, alist.size());
866        for (int i = 0; i < alist.size(); i++)
867            assertTrue("Trimmed list contained incorrect elements", alist
868                    .get(i) == objArray[i]);
869        Vector v = new Vector();
870        v.add("a");
871        ArrayList al = new ArrayList(v);
872        al.add("b");
873        Iterator it = al.iterator();
874        al.trimToSize();
875        try {
876            it.next();
877            fail("should throw a ConcurrentModificationException");
878        } catch (ConcurrentModificationException ioobe) {
879            // expected
880        }
881    }
882
883    public void test_trimToSize_02() {
884        ArrayList list = new ArrayList(Arrays.asList(new String[] { "a", "b", "c",
885                "d", "e", "f", "g" }));
886        list.remove("a");
887        list.remove("f");
888        list.trimToSize();
889    }
890
891    public void test_addAll() {
892        ArrayList list = new ArrayList();
893        list.add("one");
894        list.add("two");
895        assertEquals(2, list.size());
896
897        list.remove(0);
898        assertEquals(1, list.size());
899
900        ArrayList collection = new ArrayList();
901        collection.add("1");
902        collection.add("2");
903        collection.add("3");
904        assertEquals(3, collection.size());
905
906        list.addAll(0, collection);
907        assertEquals(4, list.size());
908
909        list.remove(0);
910        list.remove(0);
911        assertEquals(2, list.size());
912
913        collection.add("4");
914        collection.add("5");
915        collection.add("6");
916        collection.add("7");
917        collection.add("8");
918        collection.add("9");
919        collection.add("10");
920        collection.add("11");
921        collection.add("12");
922
923        assertEquals(12, collection.size());
924
925        list.addAll(0, collection);
926        assertEquals(14, list.size());
927    }
928
929    public void test_removeLjava_lang_Object() {
930        List list = new ArrayList(Arrays.asList(new String[] { "a", "b", "c",
931                "d", "e", "f", "g" }));
932        assertTrue("Removed wrong element 1", list.remove("a"));
933        assertTrue("Removed wrong element 2", list.remove("f"));
934        String[] result = new String[5];
935        list.toArray(result);
936        assertTrue("Removed wrong element 3", Arrays.equals(result,
937                new String[] { "b", "c", "d", "e", "g" }));
938    }
939
940    public void testAddAllWithConcurrentCollection() {
941        ArrayList<String> list = new ArrayList<String>();
942        list.addAll(shrinksOnSize("A", "B", "C", "D"));
943        assertFalse(list.contains(null));
944    }
945
946    public void testAddAllAtPositionWithConcurrentCollection() {
947        ArrayList<String> list = new ArrayList<String>(
948                Arrays.asList("A", "B", "C", "D"));
949
950        list.addAll(3, shrinksOnSize("E", "F", "G", "H"));
951        assertFalse(list.contains(null));
952    }
953
954    public void test_override_size() throws Exception {
955        ArrayList testlist = new MockArrayList();
956        // though size is overriden, it should passed without exception
957        testlist.add("test_0");
958        testlist.add("test_1");
959        testlist.add("test_2");
960        testlist.add(1, "test_3");
961        testlist.get(1);
962        testlist.remove(2);
963        testlist.set(1, "test_4");
964    }
965
966    public class MockArrayList extends ArrayList {
967        public int size() {
968            return 0;
969        }
970
971        public void removeRange(int begin, int end) {
972            super.removeRange(begin, end);
973        }
974    }
975
976    public void test_removeRangeII() {
977        MockArrayList mal = new MockArrayList();
978        mal.add("a");
979        mal.add("b");
980        mal.add("c");
981        mal.add("d");
982        mal.add("e");
983        mal.add("f");
984        mal.add("g");
985        mal.add("h");
986
987        mal.removeRange(2, 4);
988
989        String[] result = new String[6];
990        mal.toArray(result);
991        assertTrue("Removed wrong element 3", Arrays.equals(result,
992                new String[] { "a", "b", "e", "f", "g", "h"}));
993    }
994
995    public static class ArrayListExtend extends ArrayList {
996
997        private int size = 0;
998
999        public ArrayListExtend() {
1000            super(10);
1001        }
1002
1003        public boolean add(Object o) {
1004            size++;
1005            return super.add(o);
1006        }
1007
1008        public int size() {
1009            return size;
1010        }
1011    }
1012
1013    public void test_subclassing() {
1014        ArrayListExtend a = new ArrayListExtend();
1015        /*
1016         * Regression test for subclasses that override size() (which used to
1017         * cause an exception when growing 'a').
1018         */
1019        for (int i = 0; i < 100; i++) {
1020            a.add(new Object());
1021        }
1022    }
1023
1024    // http://b/25867131 et al.
1025    public void testIteratorAddAfterCompleteIteration() {
1026        ArrayList<String> strings = new ArrayList<>();
1027        strings.add("string1");
1028        Iterator<String> it = strings.iterator();
1029        assertTrue(it.hasNext());
1030        assertEquals("string1", it.next());
1031        assertFalse(it.hasNext());
1032        strings.add("string2");
1033        // The value of hasNext() must not flap between true and false. If we returned "true"
1034        // here, we'd fail with a CME on the next call to next() anyway.
1035        assertFalse(it.hasNext());
1036    }
1037
1038    public void testHasNextAfterRemoval() {
1039        ArrayList<String> strings = new ArrayList<>();
1040        strings.add("string1");
1041        Iterator<String> it = strings.iterator();
1042        it.next();
1043        it.remove();
1044        assertFalse(it.hasNext());
1045
1046        strings = new ArrayList<>();
1047        strings.add("string1");
1048        strings.add("string2");
1049        it = strings.iterator();
1050        it.next();
1051        it.remove();
1052        assertTrue(it.hasNext());
1053        assertEquals("string2", it.next());
1054    }
1055
1056    // http://b/27430229
1057    public void testRemoveAllDuringIteration() {
1058        ArrayList<String> list = new ArrayList<>();
1059        list.add("food");
1060        Iterator<String> iterator = list.iterator();
1061        iterator.next();
1062        list.clear();
1063        assertFalse(iterator.hasNext());
1064    }
1065
1066    public void test_forEach() throws Exception {
1067        ArrayList<Integer> list = new ArrayList<>();
1068        list.add(0);
1069        list.add(1);
1070        list.add(2);
1071
1072        ArrayList<Integer> output = new ArrayList<>();
1073        list.forEach(k -> output.add(k));
1074
1075        assertEquals(list, output);
1076    }
1077
1078    public void test_forEach_NPE() throws Exception {
1079        ArrayList<Integer> list = new ArrayList<>();
1080        try {
1081            list.forEach(null);
1082            fail();
1083        } catch(NullPointerException expected) {}
1084    }
1085
1086    public void test_forEach_CME() throws Exception {
1087        ArrayList<Integer> list = new ArrayList<>();
1088        list.add(1);
1089        list.add(2);
1090        ArrayList<Integer> processed = new ArrayList<>();
1091        try {
1092            list.forEach(t -> { processed.add(t); list.add(t); });
1093            fail();
1094        } catch(ConcurrentModificationException expected) {}
1095        assertEquals(1, processed.size());
1096    }
1097
1098    public void test_forEach_CME_onLastElement() throws Exception {
1099        ArrayList<Integer> list = new ArrayList<>();
1100        list.add(1);
1101        list.add(2);
1102        list.add(3);
1103        try {
1104            list.forEach(t -> {
1105                if (t == 3) list.add(t);
1106            });
1107            fail();
1108        } catch(ConcurrentModificationException expected) {}
1109    }
1110
1111    public void test_forEachRemaining_iterator() throws Exception {
1112        ForEachRemainingTester.runTests(ArrayList.class, new String[] { "foo", "bar", "baz"});
1113        ForEachRemainingTester.runTests(ArrayList.class, new String[] { "foo" });
1114    }
1115
1116    public void test_spliterator() throws Exception {
1117        ArrayList<Integer> testElements = new ArrayList<>(
1118                Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16));
1119        ArrayList<Integer> list = new ArrayList<>();
1120        list.addAll(testElements);
1121
1122        SpliteratorTester.runBasicIterationTests(list.spliterator(), testElements);
1123        SpliteratorTester.runBasicSplitTests(list, testElements);
1124        SpliteratorTester.testSpliteratorNPE(list.spliterator());
1125
1126        assertTrue(list.spliterator().hasCharacteristics(
1127                Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED));
1128
1129        SpliteratorTester.runOrderedTests(list);
1130        SpliteratorTester.runSizedTests(list, 16 /* expected size */);
1131        SpliteratorTester.runSubSizedTests(list, 16 /* expected size */);
1132        SpliteratorTester.assertSupportsTrySplit(list);
1133    }
1134
1135    public void test_spliterator_CME() throws Exception {
1136        ArrayList<Integer> list = new ArrayList<>();
1137        list.add(52);
1138
1139        Spliterator<Integer> sp = list.spliterator();
1140        try {
1141            sp.tryAdvance(value -> list.add(value));
1142            fail();
1143        } catch (ConcurrentModificationException expected) {
1144        }
1145
1146        ArrayList<Integer> list2 = new ArrayList<>();
1147        list2.add(52);
1148        try {
1149            sp.forEachRemaining(value -> list2.add(value));
1150            fail();
1151        } catch (ConcurrentModificationException expected) {
1152        }
1153    }
1154
1155    public void test_removeIf() {
1156        runBasicRemoveIfTests(ArrayList<Integer>::new);
1157        runBasicRemoveIfTestsUnordered(ArrayList<Integer>::new);
1158        runRemoveIfOnEmpty(ArrayList<Integer>::new);
1159        testRemoveIfNPE(ArrayList<Integer>::new);
1160        testRemoveIfCME(ArrayList<Integer>::new);
1161    }
1162
1163    public void test_sublist_spliterator() {
1164        ArrayList<Integer> testElements = new ArrayList<>(
1165                Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16));
1166        List<Integer> list = new ArrayList<>();
1167        list.addAll(testElements);
1168
1169        testElements = new ArrayList<Integer>(list.subList(8, 16));
1170        list = list.subList(8, 16);
1171
1172        SpliteratorTester.runBasicIterationTests(list.spliterator(), testElements);
1173        SpliteratorTester.runBasicSplitTests(list, testElements);
1174        SpliteratorTester.testSpliteratorNPE(list.spliterator());
1175
1176        assertTrue(list.spliterator().hasCharacteristics(
1177                Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED));
1178
1179        SpliteratorTester.runOrderedTests(list);
1180        SpliteratorTester.runSizedTests(list, 8 /* expected size */);
1181        SpliteratorTester.runSubSizedTests(list, 8 /* expected size */);
1182        SpliteratorTester.assertSupportsTrySplit(list);
1183    }
1184
1185    /**
1186     * Sets up the fixture, for example, open a network connection. This method
1187     * is called before a test is executed.
1188     */
1189    protected void setUp() throws Exception {
1190        super.setUp();
1191
1192        objArray = new Object[100];
1193        for (int i = 0; i < objArray.length; i++) {
1194            objArray[i] = new Integer(i);
1195        }
1196
1197        alist = new ArrayList();
1198        for (int i = 0; i < objArray.length; i++) {
1199            alist.add(objArray[i]);
1200        }
1201    }
1202
1203    @Override
1204    protected void tearDown() throws Exception {
1205        objArray = null;
1206        alist = null;
1207
1208        super.tearDown();
1209    }
1210
1211    /**
1212     * Returns a collection that emulates another thread calling remove() each
1213     * time the current thread calls size().
1214     */
1215    private <T> Collection<T> shrinksOnSize(T... elements) {
1216        return new HashSet<T>(Arrays.asList(elements)) {
1217            boolean shrink = true;
1218
1219            @Override
1220            public int size() {
1221                int result = super.size();
1222                if (shrink) {
1223                    Iterator<T> i = iterator();
1224                    i.next();
1225                    i.remove();
1226                }
1227                return result;
1228            }
1229
1230            @Override
1231            public Object[] toArray() {
1232                shrink = false;
1233                return super.toArray();
1234            }
1235        };
1236    }
1237}
1238