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 */
17
18package org.apache.harmony.tests.java.util;
19
20import org.apache.harmony.testframework.serialization.SerializationTest;
21import org.apache.harmony.testframework.serialization.SerializationTest.SerializableAssert;
22import tests.support.Support_CollectionTest;
23import tests.support.Support_ListTest;
24import tests.support.Support_SetTest;
25import tests.support.Support_UnmodifiableCollectionTest;
26
27import java.io.Serializable;
28import java.lang.reflect.Array;
29import java.lang.reflect.InvocationTargetException;
30import java.lang.reflect.Method;
31import java.util.AbstractList;
32import java.util.ArrayDeque;
33import java.util.ArrayList;
34import java.util.Arrays;
35import java.util.Collection;
36import java.util.Collections;
37import java.util.Comparator;
38import java.util.Deque;
39import java.util.Enumeration;
40import java.util.HashMap;
41import java.util.HashSet;
42import java.util.Iterator;
43import java.util.LinkedHashMap;
44import java.util.LinkedList;
45import java.util.List;
46import java.util.ListIterator;
47import java.util.Map;
48import java.util.NoSuchElementException;
49import java.util.Queue;
50import java.util.Random;
51import java.util.RandomAccess;
52import java.util.Set;
53import java.util.SortedSet;
54import java.util.TreeMap;
55import java.util.TreeSet;
56
57public class CollectionsTest extends junit.framework.TestCase {
58
59    private LinkedList ll;
60
61    private LinkedList myll;
62
63    private LinkedList reversedLinkedList;
64
65    private LinkedList myReversedLinkedList;
66
67    private Set s;
68
69    private Set mys;
70
71    private HashMap hm;
72
73    private Integer[] objArray;
74
75    private Object[] myobjArray;
76
77    public static class ReversedMyIntComparator implements Comparator {
78        public int compare(Object o1, Object o2) {
79            return -((MyInt) o1).compareTo((MyInt) o2);
80        }
81
82        public int equals(Object o1, Object o2) {
83            return ((MyInt) o1).compareTo((MyInt) o2);
84        }
85    }
86
87    public static class SynchCollectionChecker implements Runnable {
88        Collection col;
89
90        int colSize;
91
92        int totalToRun;
93
94        boolean offset;
95
96        volatile int numberOfChecks = 0;
97
98        boolean result = true;
99
100        ArrayList normalCountingList;
101
102        ArrayList offsetCountingList;
103
104        public void run() {
105            // ensure the list either contains the numbers from 0 to size-1 or
106            // the numbers from size to 2*size -1
107            while (numberOfChecks < totalToRun) {
108                synchronized (col) {
109                    if (!(col.isEmpty() || col.containsAll(normalCountingList) || col
110                            .containsAll(offsetCountingList)))
111                        result = false;
112                    col.clear();
113                }
114                if (offset)
115                    col.addAll(offsetCountingList);
116                else
117                    col.addAll(normalCountingList);
118                numberOfChecks++;
119            }
120        }
121
122        public SynchCollectionChecker(Collection c, boolean offset,
123                int totalChecks) {
124            // The collection to test, whether to offset the filler values by
125            // size or not, and the min number of iterations to run
126            totalToRun = totalChecks;
127            col = c;
128            colSize = c.size();
129            normalCountingList = new ArrayList(colSize);
130            offsetCountingList = new ArrayList(colSize);
131            for (int i = 0; i < colSize; i++)
132                normalCountingList.add(new Integer(i));
133            for (int i = 0; i < colSize; i++)
134                offsetCountingList.add(new Integer(i + colSize));
135            col.clear();
136            if (offset)
137                col.addAll(offsetCountingList);
138            else
139                col.addAll(normalCountingList);
140        }
141
142        public boolean offset() {
143            // answer true iff the list is filled with a counting sequence
144            // starting at the value size to 2*size - 1
145            // else the list with be filled starting at 0 to size - 1
146            return offset;
147        }
148
149        public boolean getResult() {
150            // answer true iff no corruption has been found in the collection
151            return result;
152        }
153
154        public int getNumberOfChecks() {
155            // answer the number of checks that have been performed on the list
156            return numberOfChecks;
157        }
158    }
159
160    public static class SynchMapChecker implements Runnable {
161        Map map;
162
163        int mapSize;
164
165        int totalToRun;
166
167        boolean offset;
168
169        volatile int numberOfChecks = 0;
170
171        boolean result = true;
172
173        Map normalCountingMap;
174
175        Map offsetCountingMap;
176
177        public void run() {
178            Object firstNormalValue = normalCountingMap.get(new Integer(0));
179            Object lastNormalValue = normalCountingMap.get(new Integer(
180                    mapSize - 1));
181            Object firstOffsetValue = offsetCountingMap
182                    .get(new Integer(mapSize));
183            Object lastOffsetValue = offsetCountingMap.get(new Integer(
184                    2 * mapSize - 1));
185            // ensure the list either contains the numbers from 0 to size-1 or
186            // the numbers from size to 2*size -1
187            while (numberOfChecks < totalToRun) {
188                synchronized (map) {
189                    if (!(map.isEmpty()
190                            || (map.containsValue(firstNormalValue) && map
191                            .containsValue(lastNormalValue)) || (map
192                            .containsValue(firstOffsetValue) && map
193                            .containsValue(lastOffsetValue))))
194                        result = false;
195                    map.clear();
196                }
197                if (offset)
198                    map.putAll(offsetCountingMap);
199                else
200                    map.putAll(normalCountingMap);
201                numberOfChecks++;
202            }
203        }
204
205        public SynchMapChecker(Map m, boolean offset, int totalChecks) {
206            // The collection to test, whether to offset the filler values by
207            // size or not, and the min number of iterations to run
208            Integer myInt;
209            totalToRun = totalChecks;
210            map = m;
211            mapSize = m.size();
212            normalCountingMap = new HashMap(mapSize);
213            offsetCountingMap = new HashMap(mapSize);
214            for (int i = 0; i < mapSize; i++) {
215                myInt = new Integer(i);
216                normalCountingMap.put(myInt, myInt);
217            }
218            for (int i = 0; i < mapSize; i++) {
219                myInt = new Integer(i + mapSize);
220                offsetCountingMap.put(myInt, myInt);
221            }
222            map.clear();
223            if (offset)
224                map.putAll(offsetCountingMap);
225            else
226                map.putAll(normalCountingMap);
227        }
228
229        public boolean offset() {
230            // answer true iff the list is filled with a counting sequence
231            // starting at the value size to 2*size - 1
232            // else the list with be filled starting at 0 to size - 1
233            return offset;
234        }
235
236        public boolean getResult() {
237            // answer true iff no corruption has been found in the collection
238            return result;
239        }
240
241        public int getNumberOfChecks() {
242            // answer the number of checks that have been performed on the list
243            return numberOfChecks;
244        }
245    }
246
247    static class MyInt {
248        int data;
249
250        public MyInt(int value) {
251            data = value;
252        }
253
254        public int compareTo(MyInt object) {
255            return data > object.data ? 1 : (data < object.data ? -1 : 0);
256        }
257    }
258
259    public void test_binarySearchLjava_util_ListLjava_lang_Object() {
260        // Test for method int
261        // java.util.Collections.binarySearch(java.util.List, java.lang.Object)
262        // assumes ll is sorted and has no duplicate keys
263        final int llSize = ll.size();
264        // Ensure a NPE is thrown if the list is NULL
265        try {
266            Collections.binarySearch(null, new Object());
267            fail("Expected NullPointerException for null list parameter");
268        } catch (NullPointerException e) {
269            //Expected
270        }
271        for (int i = 0; i < llSize; i++) {
272            assertEquals("Returned incorrect binary search item position", ll
273                    .get(i), ll.get(Collections.binarySearch(ll, ll
274                    .get(i))));
275        }
276    }
277
278    public void test_binarySearchLjava_util_ListLjava_lang_ObjectLjava_util_Comparator() {
279        // Test for method int
280        // java.util.Collections.binarySearch(java.util.List, java.lang.Object,
281        // java.util.Comparator)
282        // assumes reversedLinkedList is sorted in reversed order and has no
283        // duplicate keys
284        final int rSize = myReversedLinkedList.size();
285        ReversedMyIntComparator comp = new ReversedMyIntComparator();
286        // Ensure a NPE is thrown if the list is NULL
287        try {
288            Collections.binarySearch(null, new Object(), comp);
289            fail("Expected NullPointerException for null list parameter");
290        } catch (NullPointerException e) {
291            //Expected
292        }
293        for (int i = 0; i < rSize; i++) {
294            assertEquals(
295                    "Returned incorrect binary search item position using custom comparator",
296                    myReversedLinkedList.get(i), myReversedLinkedList
297                    .get(Collections.binarySearch(myReversedLinkedList,
298                            myReversedLinkedList.get(i), comp)));
299        }
300    }
301
302    class Mock_ArrayList extends ArrayList {
303        @Override
304        public
305        Object set (int index, Object o){
306            throw new UnsupportedOperationException();
307        }
308    }
309
310    public void test_copyLjava_util_ListLjava_util_List() {
311        // Test for method void java.util.Collections.copy(java.util.List,
312        // java.util.List)
313        // Ensure a NPE is thrown if the list is NULL
314        try {
315            Collections.copy(null, ll);
316            fail("Expected NullPointerException for null list first parameter");
317        } catch (NullPointerException e) {
318            //Expected
319        }
320        try {
321            Collections.copy(ll, null);
322            fail("Expected NullPointerException for null list second parameter");
323        } catch (NullPointerException e) {
324            //Expected
325        }
326        final int llSize = ll.size();
327        ll.set(25, null);
328        ArrayList al = new ArrayList();
329        Integer extraElement = new Integer(1);
330        Integer extraElement2 = new Integer(2);
331        al.addAll(myReversedLinkedList);
332        al.add(extraElement);
333        al.add(extraElement2);
334        Collections.copy(al, ll);
335        for (int i = 0; i < llSize; i++) {
336            assertEquals("Elements do not match after copying collection", ll
337                    .get(i), al.get(i));
338        }
339        assertTrue("Elements after copied elements affected by copy",
340                extraElement == al.get(llSize)
341                        && extraElement2 == al.get(llSize + 1));
342
343        ArrayList ar1 = new ArrayList();
344        ArrayList ar2 = new ArrayList();
345
346        int i;
347
348        for(i = 0; i < 5; i ++) {
349            ar2.add(new Integer(i));
350        }
351
352        for(i = 0; i < 10; i ++) {
353            ar1.add(new Integer(i));
354        }
355
356        try {
357            Collections.copy(ar2, ar1);
358            fail("IndexOutOfBoundsException expected");
359        } catch (IndexOutOfBoundsException e) {
360            //expected
361        }
362
363        Mock_ArrayList mal1 = new Mock_ArrayList();
364        Mock_ArrayList mal2 = new Mock_ArrayList();
365
366        for(i = 0; i < 10; i ++) {
367            mal1.add(new Integer(i));
368            mal2.add(new Integer(10 - i));
369        }
370
371        try {
372            Collections.copy(mal1, mal2);
373            fail("UnsupportedOperationException expected");
374        } catch (UnsupportedOperationException e) {
375            //expected
376        }
377    }
378
379    public void test_copy_check_index() {
380        ArrayList a1 = new ArrayList();
381        a1.add("one");
382        a1.add("two");
383
384        ArrayList a2 = new ArrayList();
385        a2.add("aa");
386
387        try {
388            Collections.copy(a2, a1);
389            fail("Expected IndexOutOfBoundsException");
390        } catch (IndexOutOfBoundsException e) {
391            //Expected
392        }
393
394        assertEquals("aa", a2.get(0));
395    }
396
397    public void test_enumerationLjava_util_Collection() {
398        // Test for method java.util.Enumeration
399        // java.util.Collections.enumeration(java.util.Collection)
400        TreeSet ts = new TreeSet();
401        ts.addAll(s);
402        Enumeration e = Collections.enumeration(ts);
403        int count = 0;
404        while (e.hasMoreElements()) {
405            assertEquals("Returned incorrect enumeration", e.nextElement(),
406                    objArray[count++]);
407        }
408        assertEquals("Enumeration missing elements: " + count, objArray.length,
409                count);
410    }
411
412    public void test_fillLjava_util_ListLjava_lang_Object() {
413        // Test for method void java.util.Collections.fill(java.util.List,
414        // java.lang.Object)
415        try {
416            Collections.fill(null, new Object());
417            fail("Expected NullPointerException for null list parameter");
418        } catch (NullPointerException e) {
419            //Expected
420        }
421        final int size = ll.size();
422        Collections.fill(ll, "k");
423        assertEquals("Fill modified list size", size, ll.size());
424        Iterator i = ll.iterator();
425        while (i.hasNext())
426            assertEquals("Failed to fill elements", "k", i.next());
427
428        Collections.fill(ll, null);
429        assertEquals("Fill with nulls modified list size", size, ll.size());
430        i = ll.iterator();
431        while (i.hasNext())
432            assertNull("Failed to fill with nulls", i.next());
433
434        Mock_ArrayList mal = new Mock_ArrayList();
435
436        mal.add("one");
437        mal.add("two");
438
439        try {
440            Collections.fill(mal, "value");
441            fail("UnsupportedOperationException ecpected");
442        } catch (UnsupportedOperationException e) {
443            //expected
444        }
445    }
446
447    public void test_maxLjava_util_Collection() {
448        // Test for method java.lang.Object
449        // java.util.Collections.max(java.util.Collection)
450        // assumes s, objArray are sorted
451        assertEquals("Returned incorrect max element", Collections.max(s),
452                objArray[objArray.length - 1]);
453
454        ArrayList al = new ArrayList();
455
456        try {
457            Collections.max(al);
458            fail("NoSuchElementException expected");
459        } catch (NoSuchElementException e) {
460            //expected
461        }
462
463        al.add("String");
464        al.add(new Integer(1));
465        al.add(new Double(3.14));
466
467        try {
468            Collections.max(al);
469            fail("ClassCastException expected");
470        } catch (ClassCastException e) {
471            //expected
472        }
473    }
474
475    public void test_maxLjava_util_CollectionLjava_util_Comparator() {
476        // Test for method java.lang.Object
477        // java.util.Collections.max(java.util.Collection, java.util.Comparator)
478        // assumes s, objArray are sorted
479
480        // With this custom (backwards) comparator the 'max' element should be
481        // the smallest in the list
482        assertEquals("Returned incorrect max element using custom comparator",
483                Collections.max(mys, new ReversedMyIntComparator()),
484                myobjArray[0]);
485    }
486
487    public void test_minLjava_util_Collection() {
488        // Test for method java.lang.Object
489        // java.util.Collections.min(java.util.Collection)
490        // assumes s, objArray are sorted
491        assertEquals("Returned incorrect min element", Collections.min(s),
492                objArray[0]);
493    }
494
495    public void test_minLjava_util_CollectionLjava_util_Comparator() {
496        // Test for method java.lang.Object
497        // java.util.Collections.min(java.util.Collection, java.util.Comparator)
498        // assumes s, objArray are sorted
499
500        // With this custom (backwards) comparator the 'min' element should be
501        // the largest in the list
502        assertEquals("Returned incorrect min element using custom comparator",
503                Collections.min(mys, new ReversedMyIntComparator()),
504                myobjArray[objArray.length - 1]);
505    }
506
507    public void test_nCopiesILjava_lang_Object() {
508        // Test for method java.util.List java.util.Collections.nCopies(int,
509        // java.lang.Object)
510        Object o = new Object();
511        List l = Collections.nCopies(100, o);
512        Iterator iterator = l.iterator();
513        Object first = iterator.next();
514        assertEquals("Returned list consists of copies not refs", first, o);
515        assertEquals("Returned list of incorrect size", 100, l.size());
516        assertTrue("Contains", l.contains(o));
517        assertFalse("Contains null", l.contains(null));
518        assertFalse("null nCopies contains", Collections.nCopies(2, null)
519                .contains(o));
520        assertTrue("null nCopies contains null", Collections.nCopies(2, null)
521                .contains(null));
522        l = Collections.nCopies(20, null);
523        iterator = l.iterator();
524        for (int i = 0; iterator.hasNext(); i++) {
525            assertTrue("List is too large", i < 20);
526            assertNull("Element should be null: " + i, iterator.next());
527        }
528        try {
529            l.add(o);
530            fail("Returned list is not immutable");
531        } catch (UnsupportedOperationException e) {
532            // Expected
533        }
534        try {
535            Collections.nCopies(-2, new HashSet());
536            fail("nCopies with negative arg didn't throw IAE");
537        } catch (IllegalArgumentException e) {
538            // Expected
539        }
540    }
541
542    public void test_reverseLjava_util_List() {
543        // Test for method void java.util.Collections.reverse(java.util.List)
544        try {
545            Collections.reverse(null);
546            fail("Expected NullPointerException for null list parameter");
547        } catch (NullPointerException e) {
548            //Expected
549        }
550        Collections.reverse(ll);
551        Iterator i = ll.iterator();
552        int count = objArray.length - 1;
553        while (i.hasNext()) {
554            assertEquals("Failed to reverse collection", objArray[count], i
555                    .next());
556            --count;
557        }
558        ArrayList myList = new ArrayList();
559        myList.add(null);
560        myList.add(new Integer(20));
561        Collections.reverse(myList);
562        assertEquals("Did not reverse correctly--first element is: "
563                + myList.get(0), new Integer(20), myList.get(0));
564        assertNull("Did not reverse correctly--second element is: "
565                + myList.get(1), myList.get(1));
566    }
567
568    public void test_reverseOrder() {
569        // Test for method java.util.Comparator
570        // java.util.Collections.reverseOrder()
571        // assumes no duplicates in ll
572        Comparator comp = Collections.reverseOrder();
573        LinkedList list2 = new LinkedList(ll);
574        Collections.sort(list2, comp);
575        final int llSize = ll.size();
576        for (int i = 0; i < llSize; i++)
577            assertEquals("New comparator does not reverse sorting order", list2
578                    .get(llSize - i - 1), ll.get(i));
579    }
580
581    public void test_shuffleLjava_util_List() {
582        // Test for method void java.util.Collections.shuffle(java.util.List)
583        // Assumes ll is sorted and has no duplicate keys and is large ( > 20
584        // elements)
585
586        // test shuffling a Sequential Access List
587        try {
588            Collections.shuffle(null);
589            fail("Expected NullPointerException for null list parameter");
590        } catch (NullPointerException e) {
591            //Expected
592        }
593        ArrayList al = new ArrayList();
594        al.addAll(ll);
595        testShuffle(al, "Sequential Access", false);
596
597        // test shuffling a Random Access List
598        LinkedList ll2 = new LinkedList();
599        ll2.addAll(ll);
600        testShuffle(ll2, "Random Access", false);
601    }
602
603    public void testShuffleRandomAccessWithSeededRandom() {
604        List<String> list = Arrays.asList("A", "B", "C", "D", "E", "F", "G");
605        Collections.shuffle(list, new Random(0));
606        assertEquals(Arrays.asList("B", "A", "D", "C", "G", "E", "F"), list);
607    }
608
609    public void testShuffleWithSeededRandom() {
610        List<String> list = new LinkedList<String>(Arrays.asList(
611                "A", "B", "C", "D", "E", "F", "G"));
612        Collections.shuffle(list, new Random(0));
613        assertEquals(Arrays.asList("B", "A", "D", "C", "G", "E", "F"), list);
614    }
615
616    private void testShuffle(List list, String type, boolean random) {
617        boolean sorted = true;
618        boolean allMatch = true;
619        int index = 0;
620        final int size = list.size();
621
622        if (random)
623            Collections.shuffle(list);
624        else
625            Collections.shuffle(list, new Random(200));
626
627        for (int i = 0; i < size - 1; i++) {
628            if (((Integer) list.get(i)).compareTo((Integer) list.get(i + 1)) > 0) {
629                sorted = false;
630            }
631        }
632        assertFalse("Shuffling sorted " + type
633                + " list resulted in sorted list (should be unlikely)", sorted);
634        for (int i = 0; i < 20; i++) {
635            index = 30031 * i % (size + 1); // 30031 is a large prime
636            if (list.get(index) != ll.get(index))
637                allMatch = false;
638        }
639        assertFalse("Too many element positions match in shuffled " + type
640                + " list", allMatch);
641    }
642
643    public void test_shuffleLjava_util_ListLjava_util_Random() {
644        // Test for method void java.util.Collections.shuffle(java.util.List,
645        // java.util.Random)
646        // Assumes ll is sorted and has no duplicate keys and is large ( > 20
647        // elements)
648
649        // test shuffling a Sequential Access List
650        try {
651            Collections.shuffle(null, new Random(200));
652            fail("Expected NullPointerException for null list parameter");
653        } catch (NullPointerException e) {
654            //Excepted
655        }
656        ArrayList al = new ArrayList();
657        al.addAll(ll);
658        testShuffle(al, "Sequential Access", true);
659
660        // test shuffling a Random Access List
661        LinkedList ll2 = new LinkedList();
662        ll2.addAll(ll);
663        testShuffle(ll2, "Random Access", true);
664
665        List l = new ArrayList();
666        l.add('a');
667        l.add('b');
668        l.add('c');
669        Collections.shuffle(l, new Random(12345678921L));
670        assertEquals("acb", l.get(0).toString() + l.get(1) + l.get(2));
671    }
672
673    public void test_singletonLjava_lang_Object() {
674        // Test for method java.util.Set
675        // java.util.Collections.singleton(java.lang.Object)
676        Object o = new Object();
677        Set single = Collections.singleton(o);
678        assertEquals("Wrong size", 1, single.size());
679        assertTrue("Contains", single.contains(o));
680        assertFalse("Contains null", single.contains(null));
681        assertFalse("null nCopies contains", Collections.singleton(null)
682                .contains(o));
683        assertTrue("null nCopies contains null", Collections.singleton(null)
684                .contains(null));
685        try {
686            single.add("l");
687            fail("Allowed modification of singleton");
688        } catch (UnsupportedOperationException e) {
689            // Excepted
690        }
691    }
692
693    public void test_sortLjava_util_List() {
694        // Test for method void java.util.Collections.sort(java.util.List)
695        // assumes no duplicate keys in ll
696        final int llSize = ll.size();
697        final int rllSize = reversedLinkedList.size();
698        try {
699            Collections.sort((List) null);
700            fail("Expected NullPointerException for null list parameter");
701        } catch (NullPointerException e) {
702            //Expected
703        }
704        Collections.shuffle(ll);
705        Collections.sort(ll);
706        Collections.sort(reversedLinkedList);
707        for (int i = 0; i < llSize - 1; i++) {
708            assertTrue(
709                    "Sorting shuffled list resulted in unsorted list",
710                    ((Integer) ll.get(i)).compareTo((Integer) ll.get(i + 1)) < 0);
711        }
712
713        for (int i = 0; i < rllSize - 1; i++) {
714            assertTrue("Sorting reversed list resulted in unsorted list",
715                    ((Integer) reversedLinkedList.get(i))
716                            .compareTo((Integer) reversedLinkedList.get(i + 1)) < 0);
717        }
718    }
719
720    public void test_sortLjava_util_ListLjava_util_Comparator() {
721        // Test for method void java.util.Collections.sort(java.util.List,
722        // java.util.Comparator)
723        Comparator comp = new ReversedMyIntComparator();
724        try {
725            Collections.sort(null, comp);
726            fail("Expected NullPointerException for null list parameter");
727        } catch (NullPointerException e) {
728            //Expected
729        }
730        Collections.shuffle(myll);
731        Collections.sort(myll, comp);
732        final int llSize = myll.size();
733
734        for (int i = 0; i < llSize - 1; i++) {
735            assertTrue(
736                    "Sorting shuffled list with custom comparator resulted in unsorted list",
737                    ((MyInt) myll.get(i)).compareTo((MyInt) myll
738                            .get(i + 1)) >= 0);
739        }
740
741        ArrayList al = new ArrayList();
742
743        al.add("String");
744        al.add(new Integer(1));
745        al.add(new Double(3.14));
746
747        try {
748            Collections.sort(al, comp);
749            fail("ClassCastException expected");
750        } catch (ClassCastException e) {
751            //expected
752        }
753
754        List mal = new AbstractList() {
755            private final List delegate = Arrays.asList(new MyInt(1), new MyInt(2));
756            @Override public Object get(int index) { return delegate.get(index); }
757            @Override public int size() { return delegate.size(); }
758        };
759
760        try {
761            Collections.sort(mal, comp);
762            fail("UnsupportedOperationException expected");
763        } catch (UnsupportedOperationException e) {
764            //expected
765        }
766    }
767
768    public void test_swapLjava_util_ListII() {
769        // Test for method swap(java.util.List, int, int)
770
771        LinkedList smallList = new LinkedList();
772        for (int i = 0; i < 10; i++) {
773            smallList.add(objArray[i]);
774        }
775
776        // test exception cases
777        try {
778            Collections.swap(smallList, -1, 6);
779            fail("Expected IndexOutOfBoundsException for -1");
780        } catch (IndexOutOfBoundsException e) {
781            //Expected
782        }
783
784        try {
785            Collections.swap(smallList, 6, -1);
786            fail("Expected IndexOutOfBoundsException for -1");
787        } catch (IndexOutOfBoundsException e) {
788            //Expected
789        }
790
791        try {
792            Collections.swap(smallList, 6, 11);
793            fail("Expected IndexOutOfBoundsException for 11");
794        } catch (IndexOutOfBoundsException e) {
795            //Expected
796        }
797
798        try {
799            Collections.swap(smallList, 11, 6);
800            fail("Expected IndexOutOfBoundsException for 11");
801        } catch (IndexOutOfBoundsException e) {
802            //Expected
803        }
804
805        // Ensure a NPE is thrown if the list is NULL
806        try {
807            Collections.swap(null, 1, 1);
808            fail("Expected NullPointerException for null list parameter");
809        } catch (NullPointerException e) {
810            //Expected
811        }
812
813        // test with valid parameters
814        Collections.swap(smallList, 4, 7);
815        assertEquals("Didn't Swap the element at position 4 ", new Integer(7),
816                smallList.get(4));
817        assertEquals("Didn't Swap the element at position 7 ", new Integer(4),
818                smallList.get(7));
819
820        // make sure other elements didn't get swapped by mistake
821        for (int i = 0; i < 10; i++) {
822            if (i != 4 && i != 7)
823                assertEquals("shouldn't have swapped the element at position "
824                        + i, new Integer(i), smallList.get(i));
825        }
826    }
827
828    public void test_replaceAllLjava_util_ListLjava_lang_ObjectLjava_lang_Object() {
829        // Test for method replaceAll(java.util.List, java.lang.Object,
830        // java.lang.Object)
831
832        String string1 = "A-B-C-D-E-S-JF-SUB-G-H-I-J-SUBL-K-L-LIST-M-N--S-S-O-SUBLIS-P-Q-R-SUBLIST-S-T-U-V-W-X-Y-Z";
833        char[] chars = string1.toCharArray();
834        List list = new ArrayList();
835        for (int i = 0; i < chars.length; i++) {
836            list.add(new Character(chars[i]));
837        }
838
839        try {
840            Collections.replaceAll(null, new Object(), new Object());
841            fail("Expected NullPointerException for null list parameter");
842        } catch (NullPointerException e) {
843            //Expected
844        }
845
846        // test replace for an element that is not in the list
847        boolean result = Collections.replaceAll(list, new Character('1'),
848                new Character('Z'));
849        assertFalse("Test1: Collections.replaceAll() returned wrong result",
850                result);
851        assertEquals("Test2 : ReplaceAll modified the list incorrectly",
852                string1, getString(list));
853
854        // test replace for an element that is in the list
855        result = Collections.replaceAll(list, new Character('S'),
856                new Character('K'));
857        assertTrue("Test3: Collections.replaceAll() returned wrong result",
858                result);
859        assertEquals("Test4: ReplaceAll modified the list incorrectly",
860                (string1 = string1.replace('S', 'K')), getString(list));
861
862        // test replace for the last element in the list
863        result = Collections.replaceAll(list, new Character('Z'),
864                new Character('N'));
865        assertTrue("Test5: Collections.replaceAll() returned wrong result",
866                result);
867        assertEquals("Test6: ReplaceAll modified the list incorrectly",
868                (string1 = string1.replace('Z', 'N')), getString(list));
869
870        // test replace for the first element in the list
871        result = Collections.replaceAll(list, new Character('A'),
872                new Character('B'));
873        assertTrue("Test7: Collections.replaceAll() returned wrong result",
874                result);
875        assertEquals("Test8: ReplaceAll modified the list incorrectly",
876                (string1 = string1.replace('A', 'B')), getString(list));
877
878        // test replacing elements with null
879        LinkedList smallList = new LinkedList();
880        for (int i = 0; i < 10; i++) {
881            smallList.add(objArray[i]);
882        }
883        smallList.set(4, new Integer(5));
884        result = Collections.replaceAll(smallList, new Integer(5), null);
885        assertTrue("Test9: Collections.replaceAll() returned wrong result",
886                result);
887        for (int i = 0; i < smallList.size(); i++) {
888            if (i == 4 || i == 5)
889                assertSame("Test9: ReplaceAll didn't replace element at " + i,
890                        null, smallList.get(i));
891            else
892                assertEquals(
893                        "Test9: ReplaceAll shouldn't have replaced element at "
894                                + i, new Integer(i), smallList.get(i));
895        }
896
897        // test replacing null elements with another value
898        result = Collections.replaceAll(smallList, null, new Integer(99));
899        assertTrue("Test10: Collections.replaceAll() returned wrong result",
900                result);
901
902        for (int i = 0; i < smallList.size(); i++) {
903            if (i == 4 || i == 5)
904                assertEquals("Test10: ReplaceAll didn't replace element at "
905                        + i, new Integer(99), smallList.get(i));
906            else
907                assertEquals(
908                        "Test10: ReplaceAll shouldn't have replaced element at "
909                                + i, new Integer(i), smallList.get(i));
910        }
911
912        Mock_ArrayList mal = new Mock_ArrayList();
913
914        mal.add("First");
915        mal.add("Second");
916
917        try {
918            Collections.replaceAll(mal, "Second", null);
919            fail("UnsupportedOperationException expected");
920        } catch (UnsupportedOperationException e) {
921            //expected
922        }
923    }
924
925    public void test_rotateLjava_util_ListI() {
926        // Test for method rotate(java.util.List, int)
927
928        try {
929            Collections.rotate(null, 0);
930            fail("Expected NullPointerException for null list parameter");
931        } catch (NullPointerException e) {
932            //Expected
933        }
934
935        // Test rotating a Sequential Access List
936        LinkedList list1 = new LinkedList();
937        for (int i = 0; i < 10; i++) {
938            list1.add(objArray[i]);
939        }
940        testRotate(list1, "Sequential Access");
941
942        // Test rotating a Random Access List
943        ArrayList list2 = new ArrayList();
944        for (int i = 0; i < 10; i++) {
945            list2.add(objArray[i]);
946        }
947        testRotate(list2, "Random Access");
948    }
949
950    private void testRotate(List list, String type) {
951        // rotate with positive distance
952        Collections.rotate(list, 7);
953        assertEquals("Test1: rotate modified the " + type
954                + " list incorrectly,", "3456789012", getString(list));
955
956        // rotate with negative distance
957        Collections.rotate(list, -2);
958        assertEquals("Test2: rotate modified the " + type
959                + " list incorrectly,", "5678901234", getString(list));
960
961        // rotate sublist with negative distance
962        List subList = list.subList(1, 5);
963        Collections.rotate(subList, -1);
964        assertEquals("Test3: rotate modified the " + type
965                + " list incorrectly,", "5789601234", getString(list));
966
967        // rotate sublist with positive distance
968        Collections.rotate(subList, 2);
969        assertEquals("Test4: rotate modified the " + type
970                + " list incorrectly,", "5967801234", getString(list));
971
972        // rotate with positive distance that is larger than list size
973        Collections.rotate(list, 23);
974        assertEquals("Test5: rotate modified the " + type
975                + " list incorrectly,", "2345967801", getString(list));
976
977        // rotate with negative distance that is larger than list size
978        Collections.rotate(list, -23);
979        assertEquals("Test6: rotate modified the " + type
980                + " list incorrectly,", "5967801234", getString(list));
981
982        // rotate with 0 and equivalent distances, this should make no
983        // modifications to the list
984        Collections.rotate(list, 0);
985        assertEquals("Test7: rotate modified the " + type
986                + " list incorrectly,", "5967801234", getString(list));
987
988        Collections.rotate(list, -30);
989        assertEquals("Test8: rotate modified the " + type
990                + " list incorrectly,", "5967801234", getString(list));
991
992        Collections.rotate(list, 30);
993        assertEquals("Test9: rotate modified the " + type
994                + " list incorrectly,", "5967801234", getString(list));
995    }
996
997    private String getString(List list) {
998        StringBuffer buffer = new StringBuffer();
999        for (int i = 0; i < list.size(); i++) {
1000            buffer.append(list.get(i));
1001        }
1002        return buffer.toString();
1003    }
1004
1005    public void test_rotate2() {
1006        List list = new ArrayList();
1007        try {
1008            Collections.rotate(list, 5);
1009        } catch (UnsupportedOperationException e) {
1010            fail("Unexpected UnsupportedOperationException for empty list, "
1011                    + e);
1012        }
1013
1014        list.add(0, "zero");
1015        list.add(1, "one");
1016        list.add(2, "two");
1017        list.add(3, "three");
1018        list.add(4, "four");
1019
1020        Collections.rotate(list, Integer.MIN_VALUE);
1021        assertEquals("Rotated incorrectly at position 0, ", "three",
1022                (String) list.get(0));
1023        assertEquals("Rotated incorrectly at position 1, ", "four",
1024                (String) list.get(1));
1025        assertEquals("Rotated incorrectly at position 2, ", "zero",
1026                (String) list.get(2));
1027        assertEquals("Rotated incorrectly at position 3, ", "one",
1028                (String) list.get(3));
1029        assertEquals("Rotated incorrectly at position 4, ", "two",
1030                (String) list.get(4));
1031    }
1032
1033    public void test_indexOfSubListLjava_util_ListLjava_util_List() {
1034        // Test for method int indexOfSubList(java.util.List, java.util.List)
1035        List list = new ArrayList();
1036        try {
1037            Collections.indexOfSubList(null, list);
1038            fail("Expected NullPointerException for null list first parameter");
1039        } catch (NullPointerException e) {
1040            //Expected
1041        }
1042        try {
1043            Collections.indexOfSubList(list, null);
1044            fail("Expected NullPointerException for null list second parameter");
1045        } catch (NullPointerException e) {
1046            //Expected
1047        }
1048
1049        String string1 = "A-B-C-D-E-S-JF-SUB-G-H-I-J-SUBL-K-L-LIST-M-N--S-S-O-SUBLIS-P-Q-R-SUBLIST-S-T-U-V-W-X-Y-Z";
1050
1051        testwithCharList(1, string1, "B", true);
1052        testwithCharList(2, string1, "LIST", true);
1053        testwithCharList(3, string1, "SUBLIST", true);
1054        testwithCharList(4, string1, "NONE", true);
1055        testwithCharList(5, string1, "END", true);
1056
1057        // test boundary conditions:
1058        testwithCharList(6, "", "", true);
1059        testwithCharList(7, "LIST", "", true);
1060        testwithCharList(8, "", "SUBLIST", true);
1061    }
1062
1063    public void test_indexOfSubList2() {
1064        ArrayList sub = new ArrayList();
1065        sub.add(new Integer(1));
1066        sub.add(new Integer(2));
1067        sub.add(new Integer(3));
1068
1069        ArrayList sub2 = new ArrayList();
1070        sub2.add(new Integer(7));
1071        sub2.add(new Integer(8));
1072
1073        ArrayList src = new ArrayList();
1074        src.addAll(sub);
1075        src.addAll(sub);
1076        src.addAll(sub);
1077        src.add(new Integer(5));
1078        src.add(new Integer(6));
1079
1080        // so src becomes a list like this:
1081        // [1, 2, 3, 1, 2, 3, 1, 2, 3, 5, 6]
1082
1083        sub = new ArrayList(src.subList(3, 11));
1084        // [1, 2, 3, 1, 2, 3, 5, 6]
1085        assertEquals("TestA : Returned wrong indexOfSubList, ", 3, Collections
1086                .indexOfSubList(src, sub));
1087
1088        sub = new ArrayList(src.subList(6, 11));
1089        // [1, 2, 3, 5, 6]
1090        assertEquals("TestB : Returned wrong indexOfSubList, ", 6, Collections
1091                .indexOfSubList(src, sub));
1092
1093        sub = new ArrayList(src.subList(0, 3));
1094        // [1, 2, 3]
1095        assertEquals("TestCC : Returned wrong indexOfSubList, ", 0, Collections
1096                .indexOfSubList(src, sub));
1097
1098        sub = new ArrayList(src.subList(9, 11));
1099        // [5, 6]
1100        assertEquals("TestD : Returned wrong indexOfSubList, ", 9, Collections
1101                .indexOfSubList(src, sub));
1102
1103        sub = new ArrayList(src.subList(10, 11));
1104        // [6]
1105        assertEquals("TestE : Returned wrong indexOfSubList, ", 10, Collections
1106                .indexOfSubList(src, sub));
1107
1108        sub = new ArrayList(src.subList(0, 11));
1109        // the whole list
1110        assertEquals("TestH : Returned wrong indexIndexOfSubList, ", 0,
1111                Collections.indexOfSubList(src, sub));
1112
1113        // a non-matching list
1114        assertEquals("TestI : Returned wrong indexOfSubList, ", -1, Collections
1115                .indexOfSubList(src, sub2));
1116    }
1117
1118    private void testwithCharList(int count, String string1, String string2,
1119            boolean first) {
1120        char[] chars = string1.toCharArray();
1121        List list = new ArrayList();
1122        for (int i = 0; i < chars.length; i++) {
1123            list.add(new Character(chars[i]));
1124        }
1125        chars = string2.toCharArray();
1126        List sublist = new ArrayList();
1127        for (int i = 0; i < chars.length; i++) {
1128            sublist.add(new Character(chars[i]));
1129        }
1130
1131        if (first)
1132            assertEquals("Test " + count + ": Returned wrong index:", string1
1133                    .indexOf(string2), Collections
1134                    .indexOfSubList(list, sublist));
1135        else
1136            assertEquals("Test " + count + ": Returned wrong index:", string1
1137                    .lastIndexOf(string2), Collections.lastIndexOfSubList(list,
1138                    sublist));
1139    }
1140
1141    public void test_lastIndexOfSubListLjava_util_ListLjava_util_List() {
1142        // Test for method int lastIndexOfSubList(java.util.List,
1143        // java.util.List)
1144        String string1 = "A-B-C-D-E-S-JF-SUB-G-H-I-J-SUBL-K-L-LIST-M-N--S-S-O-SUBLIS-P-Q-R-SUBLIST-S-T-U-V-W-X-Y-Z-END";
1145
1146        List list = new ArrayList();
1147        try {
1148            Collections.lastIndexOfSubList(null, list);
1149            fail("Expected NullPointerException for null list first parameter");
1150        } catch (NullPointerException e) {
1151            //Expected
1152        }
1153        try {
1154            Collections.lastIndexOfSubList(list, null);
1155            fail("Expected NullPointerException for null list second parameter");
1156        } catch (NullPointerException e) {
1157            //Expected
1158        }
1159
1160        testwithCharList(1, string1, "B", false);
1161        testwithCharList(2, string1, "LIST", false);
1162        testwithCharList(3, string1, "SUBLIST", false);
1163        testwithCharList(4, string1, "END", false);
1164        testwithCharList(5, string1, "NONE", false);
1165
1166        // test boundary conditions
1167        testwithCharList(6, "", "", false);
1168        testwithCharList(7, "LIST", "", false);
1169        testwithCharList(8, "", "SUBLIST", false);
1170    }
1171
1172    public void test_lastIndexOfSubList2() {
1173        ArrayList sub = new ArrayList();
1174        sub.add(new Integer(1));
1175        sub.add(new Integer(2));
1176        sub.add(new Integer(3));
1177
1178        ArrayList sub2 = new ArrayList();
1179        sub2.add(new Integer(7));
1180        sub2.add(new Integer(8));
1181
1182        ArrayList src = new ArrayList();
1183        src.addAll(sub);
1184        src.addAll(sub);
1185        src.addAll(sub);
1186        src.add(new Integer(5));
1187        src.add(new Integer(6));
1188
1189        // so src is a list like this:
1190        // [1, 2, 3, 1, 2, 3, 1, 2, 3, 5, 6]
1191
1192        Collections.reverse(src);
1193        // it becomes like this :
1194        // [6, 5, 3, 2, 1, 3, 2, 1, 3, 2, 1]
1195
1196        sub = new ArrayList(src.subList(0, 8));
1197        // [6, 5, 3, 2, 1, 3, 2, 1]
1198        assertEquals("TestA : Returned wrong lastIndexOfSubList, ", 0,
1199                Collections.lastIndexOfSubList(src, sub));
1200
1201        sub = new ArrayList(src.subList(0, 5));
1202        // [6, 5, 3, 2, 1]
1203        assertEquals("TestB : Returned wrong lastIndexOfSubList, ", 0,
1204                Collections.lastIndexOfSubList(src, sub));
1205
1206        sub = new ArrayList(src.subList(2, 5));
1207        // [3, 2, 1]
1208        assertEquals("TestC : Returned wrong lastIndexOfSubList, ", 8,
1209                Collections.lastIndexOfSubList(src, sub));
1210
1211        sub = new ArrayList(src.subList(9, 11));
1212        // [2, 1]
1213        assertEquals("TestD : Returned wrong lastIndexOfSubList, ", 9,
1214                Collections.lastIndexOfSubList(src, sub));
1215
1216        sub = new ArrayList(src.subList(10, 11));
1217        // [1]
1218        assertEquals("TestE : Returned wrong lastIndexOfSubList, ", 10,
1219                Collections.lastIndexOfSubList(src, sub));
1220
1221        sub = new ArrayList(src.subList(0, 2));
1222        // [6, 5]
1223        assertEquals("TestF : Returned wrong lastIndexOfSubList, ", 0,
1224                Collections.lastIndexOfSubList(src, sub));
1225
1226        sub = new ArrayList(src.subList(0, 1));
1227        // [6]
1228        assertEquals("TestG : Returned wrong lastIndexOfSubList, ", 0,
1229                Collections.lastIndexOfSubList(src, sub));
1230
1231        sub = new ArrayList(src.subList(0, 11));
1232        // the whole list
1233        assertEquals("TestH : Returned wrong lastIndexOfSubList, ", 0,
1234                Collections.lastIndexOfSubList(src, sub));
1235
1236        // a non-matching list
1237        assertEquals("TestI : Returned wrong lastIndexOfSubList, ", -1,
1238                Collections.lastIndexOfSubList(src, sub2));
1239    }
1240
1241    public void test_listLjava_util_Enumeration() {
1242        // Test for method java.util.ArrayList list(java.util.Enumeration)
1243
1244        Enumeration e = Collections.enumeration(ll);
1245        ArrayList al = Collections.list(e);
1246
1247        int size = al.size();
1248        assertEquals("Wrong size", ll.size(), size);
1249
1250        for (int i = 0; i < size; i++) {
1251            assertEquals("wrong element at position " + i + ",", ll.get(i), al
1252                    .get(i));
1253        }
1254    }
1255
1256    public void test_synchronizedCollectionLjava_util_Collection() {
1257        // Test for method java.util.Collection
1258        // java.util.Collections.synchronizedCollection(java.util.Collection)
1259
1260        LinkedList smallList = new LinkedList();
1261        for (int i = 0; i < 50; i++) {
1262            smallList.add(objArray[i]);
1263        }
1264
1265        final int numberOfLoops = 200;
1266        Collection synchCol = Collections.synchronizedCollection(smallList);
1267        // Replacing the previous line with the line below *should* cause the
1268        // test to fail--the collecion below isn't synchronized
1269        // Collection synchCol = smallList;
1270
1271        SynchCollectionChecker normalSynchChecker = new SynchCollectionChecker(
1272                synchCol, false, numberOfLoops);
1273        SynchCollectionChecker offsetSynchChecker = new SynchCollectionChecker(
1274                synchCol, true, numberOfLoops);
1275        Thread normalThread = new Thread(normalSynchChecker);
1276        Thread offsetThread = new Thread(offsetSynchChecker);
1277        normalThread.start();
1278        offsetThread.start();
1279        while ((normalSynchChecker.getNumberOfChecks() < numberOfLoops)
1280                || (offsetSynchChecker.getNumberOfChecks() < numberOfLoops)) {
1281            try {
1282                Thread.sleep(10);
1283            } catch (InterruptedException e) {
1284            }
1285        }
1286        assertTrue("Returned collection corrupted by multiple thread access",
1287                normalSynchChecker.getResult()
1288                        && offsetSynchChecker.getResult());
1289        try {
1290            normalThread.join(5000);
1291            offsetThread.join(5000);
1292        } catch (InterruptedException e) {
1293            fail("join() interrupted");
1294        }
1295
1296        synchCol.add(null);
1297        assertTrue("Trying to use nulls in collection failed", synchCol
1298                .contains(null));
1299
1300        smallList = new LinkedList();
1301        for (int i = 0; i < 100; i++) {
1302            smallList.add(objArray[i]);
1303        }
1304        new Support_CollectionTest("", Collections
1305                .synchronizedCollection(smallList)).runTest();
1306
1307        //Test self reference
1308        synchCol = Collections.synchronizedCollection(smallList);
1309        synchCol.add(smallList);
1310        assertTrue("should contain self ref", synchCol.toString().indexOf("(this") > -1);
1311    }
1312
1313    public void test_synchronizedListLjava_util_List() {
1314        try {
1315            Collections.synchronizedList(null);
1316            fail("Expected NullPointerException for null list parameter");
1317        } catch (NullPointerException e) {
1318            //Expected
1319        }
1320
1321        // test with a Sequential Access List
1322        List smallList = new LinkedList();
1323        testSynchronizedList(smallList, "Sequential Access");
1324
1325        smallList = new LinkedList();
1326        List myList;
1327        for (int i = 0; i < 100; i++) {
1328            smallList.add(objArray[i]);
1329        }
1330        myList = Collections.synchronizedList(smallList);
1331        new Support_ListTest("", myList).runTest();
1332
1333        // test with a Random Access List
1334        smallList = new ArrayList();
1335        testSynchronizedList(smallList, "Random Access");
1336
1337        smallList = new ArrayList();
1338        for (int i = 0; i < 100; i++) {
1339            smallList.add(objArray[i]);
1340        }
1341        myList = Collections.synchronizedList(smallList);
1342        new Support_ListTest("", myList).runTest();
1343
1344        //Test self reference
1345        myList = Collections.synchronizedList(smallList);
1346        myList.add(smallList);
1347        assertTrue("should contain self ref", myList.toString().indexOf("(this") > -1);
1348    }
1349
1350    private void testSynchronizedList(List smallList, String type) {
1351        for (int i = 0; i < 50; i++) {
1352            smallList.add(objArray[i]);
1353        }
1354        final int numberOfLoops = 200;
1355        List synchList = Collections.synchronizedList(smallList);
1356        if (type.equals("Random Access"))
1357            assertTrue(
1358                    "Returned synchronized list should implement the Random Access interface",
1359                    synchList instanceof RandomAccess);
1360        else
1361            assertTrue(
1362                    "Returned synchronized list should not implement the Random Access interface",
1363                    !(synchList instanceof RandomAccess));
1364
1365        // Replacing the previous line with the line below *should* cause the
1366        // test to fail--the list below isn't synchronized
1367        // List synchList = smallList;
1368        SynchCollectionChecker normalSynchChecker = new SynchCollectionChecker(
1369                synchList, false, numberOfLoops);
1370        SynchCollectionChecker offsetSynchChecker = new SynchCollectionChecker(
1371                synchList, true, numberOfLoops);
1372        Thread normalThread = new Thread(normalSynchChecker);
1373        Thread offsetThread = new Thread(offsetSynchChecker);
1374        normalThread.start();
1375        offsetThread.start();
1376        while ((normalSynchChecker.getNumberOfChecks() < numberOfLoops)
1377                || (offsetSynchChecker.getNumberOfChecks() < numberOfLoops)) {
1378            try {
1379                Thread.sleep(10);
1380            } catch (InterruptedException e) {
1381                //Expected
1382            }
1383        }
1384        assertTrue(
1385                type
1386                        + " list tests: Returned list corrupted by multiple thread access",
1387                normalSynchChecker.getResult()
1388                        && offsetSynchChecker.getResult());
1389        try {
1390            normalThread.join(5000);
1391            offsetThread.join(5000);
1392        } catch (InterruptedException e) {
1393            fail(type + " list tests: join() interrupted");
1394        }
1395        synchList.set(25, null);
1396        assertNull(type + " list tests: Trying to use nulls in list failed",
1397                synchList.get(25));
1398    }
1399
1400    public void test_synchronizedMapLjava_util_Map() {
1401        // Test for method java.util.Map
1402        // java.util.Collections.synchronizedMap(java.util.Map)
1403        HashMap smallMap = new HashMap();
1404        for (int i = 0; i < 50; i++) {
1405            smallMap.put(objArray[i], objArray[i]);
1406        }
1407
1408        final int numberOfLoops = 200;
1409        Map synchMap = Collections.synchronizedMap(smallMap);
1410        // Replacing the previous line with the line below should cause the test
1411        // to fail--the list below isn't synchronized
1412        // Map synchMap = smallMap;
1413
1414        SynchMapChecker normalSynchChecker = new SynchMapChecker(synchMap,
1415                false, numberOfLoops);
1416        SynchMapChecker offsetSynchChecker = new SynchMapChecker(synchMap,
1417                true, numberOfLoops);
1418        Thread normalThread = new Thread(normalSynchChecker);
1419        Thread offsetThread = new Thread(offsetSynchChecker);
1420        normalThread.start();
1421        offsetThread.start();
1422        while ((normalSynchChecker.getNumberOfChecks() < numberOfLoops)
1423                || (offsetSynchChecker.getNumberOfChecks() < numberOfLoops)) {
1424            try {
1425                Thread.sleep(10);
1426            } catch (InterruptedException e) {
1427                //Expected
1428            }
1429        }
1430        assertTrue("Returned map corrupted by multiple thread access",
1431                normalSynchChecker.getResult()
1432                        && offsetSynchChecker.getResult());
1433        try {
1434            normalThread.join(5000);
1435            offsetThread.join(5000);
1436        } catch (InterruptedException e) {
1437            fail("join() interrupted");
1438        }
1439
1440        // synchronized map does not have to permit null keys or values
1441        synchMap.put(new Long(25), null);
1442        synchMap.put(null, new Long(30));
1443        assertNull("Trying to use a null value in map failed", synchMap
1444                .get(new Long(25)));
1445        assertTrue("Trying to use a null key in map failed", synchMap.get(null)
1446                .equals(new Long(30)));
1447
1448        smallMap = new HashMap();
1449        for (int i = 0; i < 100; i++) {
1450            smallMap.put(objArray[i].toString(), objArray[i]);
1451        }
1452        synchMap = Collections.synchronizedMap(smallMap);
1453        new MapTestSupport(synchMap).runTest();
1454        synchMap.keySet().remove(objArray[50].toString());
1455        assertNull(
1456                "Removing a key from the keySet of the synchronized map did not remove it from the synchronized map: ",
1457                synchMap.get(objArray[50].toString()));
1458        assertNull(
1459                "Removing a key from the keySet of the synchronized map did not remove it from the original map",
1460                smallMap.get(objArray[50].toString()));
1461    }
1462
1463    public void test_unmodifiableMap_LinkedHashMap() {
1464        // LinkedHashMap has a well defined iteration order and shows ordering issues with
1465        // entrySet() / keySet() methods: iterator(), toArray(T[]) and toArray(). See bug 72073.
1466        LinkedHashMap<String, Integer> smallMap = new LinkedHashMap<String, Integer>();
1467        for (int i = 0; i < 100; i++) {
1468            Integer object = objArray[i];
1469            smallMap.put(object.toString(), object);
1470        }
1471        new MapTestSupport(smallMap).runTest();
1472    }
1473
1474    public void test_synchronizedSetLjava_util_Set() {
1475        // Test for method java.util.Set
1476        // java.util.Collections.synchronizedSet(java.util.Set)
1477        HashSet smallSet = new HashSet();
1478        for (int i = 0; i < 50; i++) {
1479            smallSet.add(objArray[i]);
1480        }
1481
1482        final int numberOfLoops = 200;
1483        Set synchSet = Collections.synchronizedSet(smallSet);
1484        // Replacing the previous line with the line below should cause the test
1485        // to fail--the set below isn't synchronized
1486        // Set synchSet = smallSet;
1487
1488        SynchCollectionChecker normalSynchChecker = new SynchCollectionChecker(
1489                synchSet, false, numberOfLoops);
1490        SynchCollectionChecker offsetSynchChecker = new SynchCollectionChecker(
1491                synchSet, true, numberOfLoops);
1492        Thread normalThread = new Thread(normalSynchChecker);
1493        Thread offsetThread = new Thread(offsetSynchChecker);
1494        normalThread.start();
1495        offsetThread.start();
1496        while ((normalSynchChecker.getNumberOfChecks() < numberOfLoops)
1497                || (offsetSynchChecker.getNumberOfChecks() < numberOfLoops)) {
1498            try {
1499                Thread.sleep(10);
1500            } catch (InterruptedException e) {
1501                //Expected
1502            }
1503        }
1504        assertTrue("Returned set corrupted by multiple thread access",
1505                normalSynchChecker.getResult()
1506                        && offsetSynchChecker.getResult());
1507        try {
1508            normalThread.join(5000);
1509            offsetThread.join(5000);
1510        } catch (InterruptedException e) {
1511            fail("join() interrupted");
1512        }
1513
1514        Set mySet = Collections.synchronizedSet(smallSet);
1515        mySet.add(null);
1516        assertTrue("Trying to use nulls in list failed", mySet.contains(null));
1517
1518        smallSet = new HashSet();
1519        for (int i = 0; i < 100; i++) {
1520            smallSet.add(objArray[i]);
1521        }
1522        new Support_SetTest("", Collections.synchronizedSet(smallSet))
1523                .runTest();
1524
1525        //Test self reference
1526        mySet = Collections.synchronizedSet(smallSet);
1527        mySet.add(smallSet);
1528        assertTrue("should contain self ref", mySet.toString().indexOf("(this") > -1);
1529    }
1530
1531    public void test_synchronizedSortedMapLjava_util_SortedMap() {
1532        // Test for method java.util.SortedMap
1533        // java.util.Collections.synchronizedSortedMap(java.util.SortedMap)
1534        TreeMap smallMap = new TreeMap();
1535        for (int i = 0; i < 50; i++) {
1536            smallMap.put(objArray[i], objArray[i]);
1537        }
1538
1539        final int numberOfLoops = 200;
1540        Map synchMap = Collections.synchronizedMap(smallMap);
1541        // Replacing the previous line with the line below should cause the test
1542        // to fail--the list below isn't synchronized
1543        // Map synchMap = smallMap;
1544
1545        SynchMapChecker normalSynchChecker = new SynchMapChecker(synchMap,
1546                false, numberOfLoops);
1547        SynchMapChecker offsetSynchChecker = new SynchMapChecker(synchMap,
1548                true, numberOfLoops);
1549        Thread normalThread = new Thread(normalSynchChecker);
1550        Thread offsetThread = new Thread(offsetSynchChecker);
1551        normalThread.start();
1552        offsetThread.start();
1553        while ((normalSynchChecker.getNumberOfChecks() < numberOfLoops)
1554                || (offsetSynchChecker.getNumberOfChecks() < numberOfLoops)) {
1555            try {
1556                Thread.sleep(10);
1557            } catch (InterruptedException e) {
1558                //Expected
1559            }
1560        }
1561        assertTrue("Returned map corrupted by multiple thread access",
1562                normalSynchChecker.getResult()
1563                        && offsetSynchChecker.getResult());
1564        try {
1565            normalThread.join(5000);
1566            offsetThread.join(5000);
1567        } catch (InterruptedException e) {
1568            fail("join() interrupted");
1569        }
1570
1571        smallMap = new TreeMap();
1572        for (int i = 0; i < 100; i++) {
1573            smallMap.put(objArray[i].toString(), objArray[i]);
1574        }
1575        synchMap = Collections.synchronizedSortedMap(smallMap);
1576        new MapTestSupport(synchMap).runTest();
1577        synchMap.keySet().remove(objArray[50].toString());
1578        assertNull(
1579                "Removing a key from the keySet of the synchronized map did not remove it from the synchronized map",
1580                synchMap.get(objArray[50].toString()));
1581        assertNull(
1582                "Removing a key from the keySet of the synchronized map did not remove it from the original map",
1583                smallMap.get(objArray[50].toString()));
1584    }
1585
1586    public void test_synchronizedSortedSetLjava_util_SortedSet() {
1587        // Test for method java.util.SortedSet
1588        // java.util.Collections.synchronizedSortedSet(java.util.SortedSet)
1589        TreeSet smallSet = new TreeSet();
1590        for (int i = 0; i < 50; i++) {
1591            smallSet.add(objArray[i]);
1592        }
1593
1594        final int numberOfLoops = 200;
1595        Set synchSet = Collections.synchronizedSet(smallSet);
1596        // Replacing the previous line with the line below should cause the test
1597        // to fail--the list below isn't synchronized
1598        // Set synchSet = smallSet;
1599
1600        SynchCollectionChecker normalSynchChecker = new SynchCollectionChecker(
1601                synchSet, false, numberOfLoops);
1602        SynchCollectionChecker offsetSynchChecker = new SynchCollectionChecker(
1603                synchSet, true, numberOfLoops);
1604        Thread normalThread = new Thread(normalSynchChecker);
1605        Thread offsetThread = new Thread(offsetSynchChecker);
1606        normalThread.start();
1607        offsetThread.start();
1608        while ((normalSynchChecker.getNumberOfChecks() < numberOfLoops)
1609                || (offsetSynchChecker.getNumberOfChecks() < numberOfLoops)) {
1610            try {
1611                Thread.sleep(10);
1612            } catch (InterruptedException e) {
1613                //Expected
1614            }
1615        }
1616        assertTrue("Returned set corrupted by multiple thread access",
1617                normalSynchChecker.getResult()
1618                        && offsetSynchChecker.getResult());
1619        try {
1620            normalThread.join(5000);
1621            offsetThread.join(5000);
1622        } catch (InterruptedException e) {
1623            fail("join() interrupted");
1624        }
1625    }
1626
1627    public void test_unmodifiableCollectionLjava_util_Collection() {
1628        // Test for method java.util.Collection
1629        // java.util.Collections.unmodifiableCollection(java.util.Collection)
1630        boolean exception = false;
1631        Collection c = Collections.unmodifiableCollection(ll);
1632        assertTrue("Returned collection is of incorrect size", c.size() == ll
1633                .size());
1634        Iterator iterator = ll.iterator();
1635        while (iterator.hasNext())
1636            assertTrue("Returned list missing elements", c.contains(iterator.next()));
1637        try {
1638            c.add(new Object());
1639        } catch (UnsupportedOperationException e) {
1640            exception = true;
1641            // Correct
1642        }
1643        if (!exception) {
1644            fail("Allowed modification of collection");
1645        }
1646
1647        try {
1648            c.remove(new Object());
1649            fail("Allowed modification of collection");
1650        } catch (UnsupportedOperationException e) {
1651            // Correct
1652        }
1653
1654        try {
1655            c.removeIf(x -> true);
1656            fail("Allowed modification of collection");
1657        } catch (UnsupportedOperationException e) {
1658            // Correct
1659        }
1660
1661        Collection myCollection = new ArrayList();
1662        myCollection.add(new Integer(20));
1663        myCollection.add(null);
1664        c = Collections.unmodifiableCollection(myCollection);
1665        assertTrue("Collection should contain null", c.contains(null));
1666        assertTrue("Collection should contain Integer(20)", c
1667                .contains(new Integer(20)));
1668
1669        myCollection = new ArrayList();
1670        for (int i = 0; i < 100; i++) {
1671            myCollection.add(objArray[i]);
1672        }
1673        new Support_UnmodifiableCollectionTest("", Collections
1674                .unmodifiableCollection(myCollection)).runTest();
1675    }
1676
1677    public void test_unmodifiableListLjava_util_List() {
1678        // Test for method java.util.List
1679        // java.util.Collections.unmodifiableList(java.util.List)
1680
1681        // test with a Sequential Access List
1682        boolean exception = false;
1683        List c = Collections.unmodifiableList(ll);
1684        // Ensure a NPE is thrown if the list is NULL
1685        try {
1686            Collections.unmodifiableList(null);
1687            fail("Expected NullPointerException for null list parameter");
1688        } catch (NullPointerException e) {
1689        }
1690
1691        assertTrue("Returned list is of incorrect size", c.size() == ll.size());
1692        assertTrue(
1693                "Returned List should not implement Random Access interface",
1694                !(c instanceof RandomAccess));
1695
1696        Iterator iterator = ll.iterator();
1697        while (iterator.hasNext())
1698            assertTrue("Returned list missing elements", c.contains(iterator.next()));
1699        try {
1700            c.add(new Object());
1701        } catch (UnsupportedOperationException e) {
1702            exception = true;
1703            // Correct
1704        }
1705        if (!exception) {
1706            fail("Allowed modification of list");
1707        }
1708
1709        try {
1710            c.remove(new Object());
1711            fail("Allowed modification of list");
1712        } catch (UnsupportedOperationException e) {
1713            // Correct
1714        }
1715
1716        try {
1717            c.removeIf(x -> true);
1718            fail("Allowed modification of list");
1719        } catch (UnsupportedOperationException e) {
1720            // Correct
1721        }
1722
1723        // test with a Random Access List
1724        List smallList = new ArrayList();
1725        smallList.add(null);
1726        smallList.add("yoink");
1727        c = Collections.unmodifiableList(smallList);
1728        assertNull("First element should be null", c.get(0));
1729        assertTrue("List should contain null", c.contains(null));
1730        assertTrue(
1731                "T1. Returned List should implement Random Access interface",
1732                c instanceof RandomAccess);
1733
1734        smallList = new ArrayList();
1735        for (int i = 0; i < 100; i++) {
1736            smallList.add(objArray[i]);
1737        }
1738        List myList = Collections.unmodifiableList(smallList);
1739        assertTrue("List should not contain null", !myList.contains(null));
1740        assertTrue(
1741                "T2. Returned List should implement Random Access interface",
1742                myList instanceof RandomAccess);
1743
1744        assertTrue("get failed on unmodifiable list", myList.get(50).equals(
1745                new Integer(50)));
1746        ListIterator listIterator = myList.listIterator();
1747        for (int i = 0; listIterator.hasNext(); i++) {
1748            assertTrue("List has wrong elements", ((Integer) listIterator
1749                    .next()).intValue() == i);
1750        }
1751        new Support_UnmodifiableCollectionTest("", smallList).runTest();
1752    }
1753
1754    public void test_unmodifiableMapLjava_util_Map() {
1755        // Test for method java.util.Map
1756        // java.util.Collections.unmodifiableMap(java.util.Map)
1757        boolean exception = false;
1758        Map c = Collections.unmodifiableMap(hm);
1759        assertTrue("Returned map is of incorrect size", c.size() == hm.size());
1760        Iterator iterator = hm.keySet().iterator();
1761        while (iterator.hasNext()) {
1762            Object x = iterator.next();
1763            assertTrue("Returned map missing elements", c.get(x).equals(
1764                    hm.get(x)));
1765        }
1766        try {
1767            c.put(new Object(), "");
1768        } catch (UnsupportedOperationException e) {
1769            exception = true;
1770            // Correct
1771        }
1772        assertTrue("Allowed modification of map", exception);
1773
1774        exception = false;
1775        try {
1776            c.remove(new Object());
1777        } catch (UnsupportedOperationException e) {
1778            // Correct
1779            exception = true;
1780        }
1781        assertTrue("Allowed modification of map", exception);
1782
1783        exception = false;
1784        Iterator entrySetIterator = c.entrySet().iterator();
1785        Map.Entry entry = (Map.Entry) entrySetIterator.next();
1786        try {
1787            entry.setValue("modified");
1788        } catch (UnsupportedOperationException e) {
1789            // Correct
1790            exception = true;
1791        }
1792        assertTrue("Allowed modification of entry", exception);
1793
1794        exception = false;
1795        Object[] array = c.entrySet().toArray();
1796        try {
1797            ((Map.Entry) array[0]).setValue("modified");
1798        } catch (UnsupportedOperationException e) {
1799            // Correct
1800            exception = true;
1801        }
1802        assertTrue("Allowed modification of array entry", exception);
1803
1804        exception = false;
1805        Map.Entry[] array2 = (Map.Entry[]) c.entrySet().toArray(
1806                new Map.Entry[0]);
1807        try {
1808            array2[0].setValue("modified");
1809        } catch (UnsupportedOperationException e) {
1810            // Correct
1811            exception = true;
1812        }
1813        assertTrue("Allowed modification of array entry2", exception);
1814
1815        HashMap smallMap = new HashMap();
1816        smallMap.put(null, new Long(30));
1817        smallMap.put(new Long(25), null);
1818        Map unmodMap = Collections.unmodifiableMap(smallMap);
1819
1820        assertNull("Trying to use a null value in map failed", unmodMap
1821                .get(new Long(25)));
1822        assertTrue("Trying to use a null key in map failed", unmodMap.get(null)
1823                .equals(new Long(30)));
1824
1825        smallMap = new HashMap();
1826        for (int i = 0; i < 100; i++) {
1827            smallMap.put(objArray[i].toString(), objArray[i]);
1828        }
1829        new MapTestSupport(smallMap).runTest();
1830    }
1831
1832    public void test_unmodifiableSetLjava_util_Set() {
1833        // Test for method java.util.Set
1834        // java.util.Collections.unmodifiableSet(java.util.Set)
1835        boolean exception = false;
1836        Set c = Collections.unmodifiableSet(s);
1837        assertTrue("Returned set is of incorrect size", c.size() == s.size());
1838        Iterator iterator = ll.iterator();
1839        while (iterator.hasNext())
1840            assertTrue("Returned set missing elements", c.contains(iterator.next()));
1841        try {
1842            c.add(new Object());
1843        } catch (UnsupportedOperationException e) {
1844            exception = true;
1845            // Correct
1846        }
1847        if (!exception) {
1848            fail("Allowed modification of set");
1849        }
1850        try {
1851            c.remove(new Object());
1852            fail("Allowed modification of set");
1853        } catch (UnsupportedOperationException e) {
1854            // Correct
1855        }
1856        try {
1857            c.removeIf(x -> true);
1858            fail("Allowed modification of set");
1859        } catch (UnsupportedOperationException e) {
1860            // Correct
1861        }
1862
1863        Set mySet = Collections.unmodifiableSet(new HashSet());
1864        assertTrue("Should not contain null", !mySet.contains(null));
1865        mySet = Collections.unmodifiableSet(Collections.singleton(null));
1866        assertTrue("Should contain null", mySet.contains(null));
1867
1868        mySet = new TreeSet();
1869        for (int i = 0; i < 100; i++) {
1870            mySet.add(objArray[i]);
1871        }
1872        new Support_UnmodifiableCollectionTest("", Collections
1873                .unmodifiableSet(mySet)).runTest();
1874    }
1875
1876    public void test_unmodifiableSortedMapLjava_util_SortedMap() {
1877        // Test for method java.util.SortedMap
1878        // java.util.Collections.unmodifiableSortedMap(java.util.SortedMap)
1879        boolean exception = false;
1880        TreeMap tm = new TreeMap();
1881        tm.putAll(hm);
1882        Map c = Collections.unmodifiableSortedMap(tm);
1883        assertTrue("Returned map is of incorrect size", c.size() == tm.size());
1884        Iterator i = hm.keySet().iterator();
1885        while (i.hasNext()) {
1886            Object x = i.next();
1887            assertTrue("Returned map missing elements", c.get(x).equals(
1888                    tm.get(x)));
1889        }
1890        try {
1891            c.put(new Object(), "");
1892        } catch (UnsupportedOperationException e) {
1893            exception = true;
1894            // Correct
1895        }
1896
1897        if (!exception) {
1898            fail("Allowed modification of map");
1899        }
1900        try {
1901            c.remove(new Object());
1902        } catch (UnsupportedOperationException e) {
1903            // Correct
1904            return;
1905        }
1906        fail("Allowed modification of map");
1907    }
1908
1909    public void test_unmodifiableSortedSetLjava_util_SortedSet() {
1910        // Test for method java.util.SortedSet
1911        // java.util.Collections.unmodifiableSortedSet(java.util.SortedSet)
1912        boolean exception = false;
1913        SortedSet ss = new TreeSet();
1914        ss.addAll(s);
1915        SortedSet c = Collections.unmodifiableSortedSet(ss);
1916        assertTrue("Returned set is of incorrect size", c.size() == ss.size());
1917        Iterator i = ll.iterator();
1918        while (i.hasNext())
1919            assertTrue("Returned set missing elements", c.contains(i.next()));
1920        try {
1921            c.add(new Object());
1922            fail("Allowed modification of set");
1923        } catch (UnsupportedOperationException e) {}
1924
1925        try {
1926            c.remove(new Object());
1927            fail("Allowed modification of set");
1928        } catch (UnsupportedOperationException expected) {}
1929
1930        try {
1931            c.removeIf(x -> true);
1932            fail("Allowed modification of set");
1933        } catch (UnsupportedOperationException expected) {}
1934    }
1935
1936    /**
1937     * Test unmodifiable objects toString methods
1938     */
1939    public void test_unmodifiable_toString_methods() {
1940        // Regression for HARMONY-552
1941        ArrayList al = new ArrayList();
1942        al.add("a");
1943        al.add("b");
1944        Collection uc = Collections.unmodifiableCollection(al);
1945        assertEquals("[a, b]", uc.toString());
1946        HashMap m = new HashMap();
1947        m.put("one", "1");
1948        m.put("two", "2");
1949        Map um = Collections.unmodifiableMap(m);
1950        assertTrue("{one=1, two=2}".equals(um.toString()) ||
1951                   "{two=2, one=1}".equals(um.toString()));
1952    }
1953
1954
1955    public void test_singletonListLjava_lang_Object() {
1956        // Test for method java.util.Set
1957        // java.util.Collections.singleton(java.lang.Object)
1958        String str = "Singleton";
1959
1960        List single = Collections.singletonList(str);
1961        assertEquals(1, single.size());
1962        assertTrue(single.contains(str));
1963        assertFalse(single.contains(null));
1964        assertFalse(Collections.singletonList(null).contains(str));
1965        assertTrue(Collections.singletonList(null).contains(null));
1966
1967        try {
1968            single.add("New element");
1969            fail("UnsupportedOperationException expected");
1970        } catch (UnsupportedOperationException e) {
1971            //expected
1972        }
1973    }
1974
1975    public void test_singletonMapLjava_lang_Object() {
1976        // Test for method java.util.Set
1977        // java.util.Collections.singleton(java.lang.Object)
1978        Double key = new Double (3.14);
1979        String value = "Fundamental constant";
1980
1981        Map single = Collections.singletonMap(key, value);
1982        assertEquals(1, single.size());
1983        assertTrue(single.containsKey(key));
1984        assertTrue(single.containsValue(value));
1985        assertFalse(single.containsKey(null));
1986        assertFalse(single.containsValue(null));
1987        assertFalse(Collections.singletonMap(null, null).containsKey(key));
1988        assertFalse(Collections.singletonMap(null, null).containsValue(value));
1989        assertTrue(Collections.singletonMap(null, null).containsKey(null));
1990        assertTrue(Collections.singletonMap(null, null).containsValue(null));
1991
1992        try {
1993            single.clear();
1994            fail("UnsupportedOperationException expected");
1995        } catch (UnsupportedOperationException e) {
1996            //expected
1997        }
1998
1999        try {
2000            single.put(new Double(1), "one wrong value");
2001            fail("UnsupportedOperationException expected");
2002        } catch (UnsupportedOperationException e) {
2003            //expected
2004        }
2005    }
2006
2007    // Test on a non-public method that isn't guaranteed to exist.
2008    //
2009    // public void test_checkType_Ljava_lang_Object_Ljava_lang_Class() throws Exception {
2010    //     Method m = Collections.class.getDeclaredMethod("checkType", Object.class, Class.class);
2011    //    m.setAccessible(true);
2012    //     m.invoke(null, new Object(), Object.class);
2013    //
2014    //     try {
2015    //         m.invoke(null, new Object(), int.class);
2016    //         fail();
2017    //     } catch (InvocationTargetException expected) {
2018    //     }
2019    // }
2020
2021    public void test_binarySearch_asymmetry_with_comparator() throws Exception {
2022        List list = new ArrayList();
2023        String s1 = new String("a");
2024        String s2 = new String("aa");
2025        String s3 = new String("aaa");
2026        list.add(s1);
2027        list.add(s2);
2028        list.add(s3);
2029        Collections.sort(list);
2030        Object o = Collections.binarySearch(list, 1, new StringComparator());
2031        assertSame(0, o);
2032    }
2033
2034    public void test_binarySearch_asymmetry() throws Exception {
2035        List list = new LinkedList();
2036        String s1 = new String("a");
2037        String s2 = new String("aa");
2038        String s3 = new String("aaa");
2039        list.add(new MyComparable(s1));
2040        list.add(new MyComparable(s2));
2041        list.add(new MyComparable(s3));
2042        Collections.sort(list);
2043        Object o = Collections.binarySearch(list, 1);
2044        assertSame(0, o);
2045    }
2046
2047
2048    private class MyComparable implements Comparable {
2049
2050        public String s;
2051
2052        public MyComparable(String s) {
2053            this.s = s;
2054
2055        }
2056
2057        public int compareTo(Object another) {
2058            int length = 0;
2059            if (another instanceof MyComparable) {
2060                length = (((MyComparable) another).s).length();
2061            } else {
2062                length = (Integer) another;
2063            }
2064            return s.length() - length;
2065        }
2066
2067    }
2068
2069    private class StringComparator implements Comparator {
2070
2071        public int compare(Object object1, Object object2) {
2072            String s = (String) object1;
2073            int length;
2074            if (object2 instanceof String) {
2075                length = ((String) object2).length();
2076            } else {
2077                length = (Integer) object2;
2078            }
2079            return s.length() - length;
2080        }
2081    }
2082
2083
2084    public void test_newSetFromMap_LMap() throws Exception {
2085        Integer testInt[] = new Integer[100];
2086        for (int i = 0; i < testInt.length; i++) {
2087            testInt[i] = new Integer(i);
2088        }
2089        Map<Integer, Boolean> map = new HashMap<Integer, Boolean>();
2090        Set<Integer> set = Collections.newSetFromMap(map);
2091        for (int i = 0; i < testInt.length; i++) {
2092            map.put(testInt[i], true);
2093        }
2094        // operater on map successed
2095        map.put(testInt[1], false);
2096        assertTrue(map.containsKey(testInt[1]));
2097        assertEquals(100, map.size());
2098        assertFalse(map.get(testInt[1]));
2099        assertEquals(100, set.size());
2100        assertTrue(set.contains(testInt[16]));
2101        Iterator setIter = set.iterator();
2102        Iterator mapIter = map.keySet().iterator();
2103        int i = 0;
2104        // in the same order
2105        while (setIter.hasNext()) {
2106            assertEquals(mapIter.next(), setIter.next());
2107        }
2108
2109        // operator on set successed
2110        Integer testInt101 = new Integer(101);
2111        Integer testInt102 = new Integer(102);
2112        set.add(testInt101);
2113        assertTrue(set.contains(testInt101));
2114        assertTrue(map.get(testInt101));
2115
2116        // operator on map still passes
2117        map.put(testInt102, false);
2118        assertTrue(set.contains(testInt102));
2119        assertFalse(map.get(testInt102));
2120
2121        // exception thrown
2122        try {
2123            Collections.newSetFromMap(map);
2124            fail("should throw IllegalArgumentException");
2125        } catch (IllegalArgumentException e) {
2126            // expected
2127        }
2128    }
2129
2130    /**
2131     * serialization/deserialization.
2132     */
2133    @SuppressWarnings({ "unchecked", "boxing" })
2134    public void testSerializationSelf_newSetFromMap() throws Exception {
2135        Integer testInt[] = new Integer[100];
2136        for (int i = 0; i < testInt.length; i++) {
2137            testInt[i] = new Integer(i);
2138        }
2139        Map<Integer, Boolean> map = new HashMap<Integer, Boolean>();
2140        Set<Integer> set = Collections.newSetFromMap(map);
2141        for (int i = 0; i < testInt.length; i++) {
2142            map.put(testInt[i], true);
2143        }
2144        SerializationTest.verifySelf(set);
2145    }
2146
2147    public void test_asLifoQueue() throws Exception {
2148        Integer testInt[] = new Integer[100];
2149        Integer test101 = new Integer(101);
2150        for (int i = 0; i < testInt.length; i++) {
2151            testInt[i] = new Integer(i);
2152        }
2153        Deque deque = new ArrayDeque<Integer>();
2154        Queue<Integer> que = Collections.asLifoQueue(deque);
2155        for (int i = 0; i < testInt.length; i++) {
2156            que.add(testInt[i]);
2157        }
2158        assertEquals(100, deque.size());
2159        assertEquals(100, que.size());
2160        for (int i = testInt.length - 1; i >= 0; i--) {
2161            assertEquals(testInt[i], deque.pop());
2162        }
2163        assertEquals(0, deque.size());
2164        assertEquals(0, que.size());
2165        for (int i = 0; i < testInt.length; i++) {
2166            deque.push(testInt[i]);
2167        }
2168        assertEquals(100, deque.size());
2169        assertEquals(100, que.size());
2170        Collection col = new LinkedList<Integer>();
2171        col.add(test101);
2172        que.addAll(col);
2173        assertEquals(test101, que.remove());
2174        for (int i = testInt.length - 1; i >= 0; i--) {
2175            assertEquals(testInt[i], que.remove());
2176        }
2177        assertEquals(0, deque.size());
2178        assertEquals(0, que.size());
2179    }
2180
2181    /**
2182     * serialization/deserialization.
2183     */
2184    @SuppressWarnings({ "unchecked", "boxing" })
2185    public void testSerializationSelf_asLifoQueue() throws Exception {
2186        Integer testInt[] = new Integer[100];
2187        for (int i = 0; i < testInt.length; i++) {
2188            testInt[i] = new Integer(i);
2189        }
2190        Deque deque = new ArrayDeque<Integer>();
2191        Queue<Integer> que = Collections.asLifoQueue(deque);
2192        for (int i = 0; i < testInt.length; i++) {
2193            que.add(testInt[i]);
2194        }
2195        SerializationTest.verifySelf(que, new SerializableAssert() {
2196            public void assertDeserialized(Serializable initial, Serializable deserialized) {
2197                Queue<Integer> initque = (Queue) initial;
2198                Queue<Integer> deserque = (Queue) deserialized;
2199                while (!initque.isEmpty()) {
2200                    assertEquals(initque.remove(), deserque.remove());
2201                }
2202            }
2203        });
2204    }
2205
2206    public void test_emptyList() {
2207        List<String> list = Collections.emptyList();
2208        assertTrue("should be true", list.isEmpty());
2209    }
2210
2211    @Override
2212    protected void setUp() throws Exception {
2213        super.setUp();
2214        objArray = new Integer[1000];
2215        myobjArray = new Object[1000];
2216        for (int i = 0; i < objArray.length; i++) {
2217            objArray[i] = i;
2218            myobjArray[i] = new MyInt(i);
2219        }
2220
2221        ll = new LinkedList();
2222        myll = new LinkedList();
2223        s = new HashSet();
2224        mys = new HashSet();
2225        reversedLinkedList = new LinkedList(); // to be sorted in reverse order
2226        myReversedLinkedList = new LinkedList(); // to be sorted in reverse
2227        // order
2228        hm = new HashMap();
2229        for (int i = 0; i < objArray.length; i++) {
2230            ll.add(objArray[i]);
2231            myll.add(myobjArray[i]);
2232            s.add(objArray[i]);
2233            mys.add(myobjArray[i]);
2234            reversedLinkedList.add(objArray[objArray.length - i - 1]);
2235            myReversedLinkedList.add(myobjArray[myobjArray.length - i - 1]);
2236            hm.put(objArray[i].toString(), objArray[i]);
2237        }
2238    }
2239
2240    /**
2241     * A class shared by various Map-related tests that checks the properties and contents of a
2242     * supplied Map and compares the some methods to the same map when wrapped with
2243     * {@link Collections#unmodifiableMap(java.util.Map)}.
2244     */
2245    static class MapTestSupport {
2246
2247        // must be a map containing the string keys "0"-"99" paired with the Integer
2248        // values Integer(0) to Integer(99)
2249        private final Map<String, Integer> modifiableMap;
2250        private final Map<String, Integer> unmodifiableMap;
2251
2252        public MapTestSupport(Map<String, Integer> modifiableMap) {
2253            this.modifiableMap = modifiableMap;
2254            unmodifiableMap = Collections.unmodifiableMap(modifiableMap);
2255        }
2256
2257        public void runTest() {
2258            testContents(modifiableMap);
2259            testContents(unmodifiableMap);
2260
2261            // values()
2262            new Support_UnmodifiableCollectionTest("values() from map test", modifiableMap.values())
2263                    .runTest();
2264            new Support_UnmodifiableCollectionTest("values() from unmodifiable map test",
2265                    unmodifiableMap.values()).runTest();
2266
2267            // entrySet()
2268            testEntrySet(modifiableMap.entrySet(), unmodifiableMap.entrySet());
2269
2270            // keySet()
2271            testKeySet(modifiableMap.keySet(), unmodifiableMap.keySet());
2272        }
2273
2274        private static void testContents(Map<String, Integer> map) {
2275            // size
2276            assertTrue("Size should return 100, returned: " + map.size(), map.size() == 100);
2277
2278            // containsKey
2279            assertTrue("Should contain the key \"0\"", map.containsKey("0"));
2280            assertTrue("Should contain the key \"50\"", map.containsKey("50"));
2281            assertTrue("Should not contain the key \"100\"", !map.containsKey("100"));
2282
2283            // containsValue
2284            assertTrue("Should contain the value 0", map.containsValue(0));
2285            assertTrue("Should contain the value 50", map.containsValue(50));
2286            assertTrue("Should not contain value 100", !map.containsValue(100));
2287
2288            // get
2289            assertTrue("getting \"0\" didn't return 0", map.get("0") == 0);
2290            assertTrue("getting \"50\" didn't return 50", map.get("50") == 50);
2291            assertNull("getting \"100\" didn't return null", map.get("100"));
2292
2293            // isEmpty
2294            assertTrue("should have returned false to isEmpty", !map.isEmpty());
2295        }
2296
2297        private static void testEntrySet(
2298                Set<Map.Entry<String, Integer>> referenceEntrySet,
2299                Set<Map.Entry<String, Integer>> entrySet) {
2300            // entrySet should be a set of mappings {"0", 0}, {"1",1}... {"99", 99}
2301            assertEquals(100, referenceEntrySet.size());
2302            assertEquals(100, entrySet.size());
2303
2304            // The ordering may be undefined for a map implementation but the ordering must be the
2305            // same across iterator(), toArray() and toArray(T[]) for a given map *and* the same for the
2306            // modifiable and unmodifiable map.
2307            crossCheckOrdering(referenceEntrySet, entrySet, Map.Entry.class);
2308        }
2309
2310        private static void testKeySet(Set<String> referenceKeySet, Set<String> keySet) {
2311            // keySet should be a set of the strings "0" to "99"
2312            testKeySetContents(referenceKeySet);
2313            testKeySetContents(keySet);
2314
2315            // The ordering may be undefined for a map implementation but the ordering must be the
2316            // same across iterator(), toArray() and toArray(T[]) for a given map *and* the same for the
2317            // modifiable and unmodifiable map.
2318            crossCheckOrdering(referenceKeySet, keySet, String.class);
2319        }
2320
2321        private static void testKeySetContents(Set<String> keySet) {
2322            // contains
2323            assertTrue("should contain \"0\"", keySet.contains("0"));
2324            assertTrue("should contain \"50\"", keySet.contains("50"));
2325            assertTrue("should not contain \"100\"", !keySet.contains("100"));
2326
2327            // containsAll
2328            HashSet<String> hs = new HashSet<String>();
2329            hs.add("0");
2330            hs.add("25");
2331            hs.add("99");
2332            assertTrue("Should contain set of \"0\", \"25\", and \"99\"", keySet.containsAll(hs));
2333            hs.add("100");
2334            assertTrue("Should not contain set of \"0\", \"25\", \"99\" and \"100\"",
2335                    !keySet.containsAll(hs));
2336
2337            // isEmpty
2338            assertTrue("Should not be empty", !keySet.isEmpty());
2339
2340            // size
2341            assertEquals("Returned wrong size.", 100, keySet.size());
2342        }
2343
2344        private static <T> void crossCheckOrdering(Set<T> set1, Set<T> set2, Class<?> elementType) {
2345            Iterator<T> set1Iterator = set1.iterator();
2346            Iterator<T> set2Iterator = set2.iterator();
2347
2348            T[] zeroLengthArray = createArray(elementType, 0);
2349            T[] set1TypedArray1 = set1.toArray(zeroLengthArray);
2350            assertEquals(set1.size(), set1TypedArray1.length);
2351
2352            // Compare set1.iterator(), set2.iterator() and set1.toArray(new T[0])
2353            int entryCount = 0;
2354            while (set1Iterator.hasNext()) {
2355                T set1Entry = set1Iterator.next();
2356                T set2Entry = set2Iterator.next();
2357
2358                // Compare set1 with set2
2359                assertEquals(set1Entry, set2Entry);
2360
2361                // Compare the iterator with the array. The arrays will be checked against each other.
2362                assertEquals(set1Entry, set1TypedArray1[entryCount]);
2363
2364                entryCount++;
2365            }
2366            assertFalse(set2Iterator.hasNext());
2367            assertEquals(set1.size(), entryCount);
2368
2369            // Compare the various arrays with each other.
2370
2371            // set1.toArray(new T[size])
2372            T[] parameterArray1 = createArray(elementType, set1.size());
2373            T[] set1TypedArray2 = set1.toArray(parameterArray1);
2374            assertSame(set1TypedArray2, parameterArray1);
2375            assertArrayEquals(set1TypedArray1, set1TypedArray2);
2376
2377            // set1.toArray()
2378            Object[] set1UntypedArray = set1.toArray();
2379            assertEquals(set1.size(), set1UntypedArray.length);
2380            assertArrayEquals(set1TypedArray1, set1UntypedArray);
2381
2382            // set2.toArray(new T[0])
2383            T[] set2TypedArray1 = set2.toArray(zeroLengthArray);
2384            assertEquals(set1.size(), set2TypedArray1.length);
2385            assertArrayEquals(set1TypedArray1, set2TypedArray1);
2386
2387            // set2.toArray(new T[size])
2388            T[] parameterArray2 = createArray(elementType, set2.size());
2389            T[] set2TypedArray2 = set1.toArray(parameterArray2);
2390            assertSame(set2TypedArray2, parameterArray2);
2391            assertArrayEquals(set1TypedArray1, set1TypedArray2);
2392
2393            // set2.toArray()
2394            Object[] set2UntypedArray = set2.toArray();
2395            assertArrayEquals(set1TypedArray1, set2UntypedArray);
2396        }
2397
2398        private static <T> void assertArrayEquals(T[] array1, T[] array2) {
2399            assertTrue(Arrays.equals(array1, array2));
2400        }
2401
2402        @SuppressWarnings("unchecked")
2403        private static <T> T[] createArray(Class<?> elementType, int size) {
2404            return (T[]) Array.newInstance(elementType, size);
2405        }
2406    }
2407}
2408