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