1/*
2 * Copyright (C) 2011 Google Inc.
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17package libcore.java.util;
18
19import java.io.Serializable;
20import java.util.ArrayList;
21import java.util.Collections;
22import java.util.Comparator;
23import java.util.ConcurrentModificationException;
24import java.util.Enumeration;
25import java.util.Iterator;
26import java.util.ListIterator;
27import java.util.NoSuchElementException;
28import junit.framework.TestCase;
29
30public final class CollectionsTest extends TestCase {
31
32    public void testEmptyEnumeration() {
33        Enumeration<Object> e = Collections.emptyEnumeration();
34        assertFalse(e instanceof Serializable);
35        assertFalse(e.hasMoreElements());
36        try {
37            e.nextElement();
38            fail();
39        } catch (NoSuchElementException expected) {
40        }
41    }
42
43    public void testEmptyIterator() {
44        testEmptyIterator(Collections.emptyIterator());
45        testEmptyIterator(Collections.emptyList().iterator());
46        testEmptyIterator(Collections.emptySet().iterator());
47        testEmptyIterator(Collections.emptyMap().keySet().iterator());
48        testEmptyIterator(Collections.emptyMap().entrySet().iterator());
49        testEmptyIterator(Collections.emptyMap().values().iterator());
50    }
51
52    private void testEmptyIterator(Iterator<?> i) {
53        assertFalse(i instanceof Serializable);
54        assertFalse(i.hasNext());
55        try {
56            i.next();
57            fail();
58        } catch (NoSuchElementException expected) {
59        }
60        try {
61            i.remove();
62            fail();
63        } catch (IllegalStateException expected) {
64        }
65    }
66
67    public void testEmptyListIterator() {
68        testEmptyListIterator(Collections.emptyListIterator());
69        testEmptyListIterator(Collections.emptyList().listIterator());
70        testEmptyListIterator(Collections.emptyList().listIterator(0));
71    }
72
73    private void testEmptyListIterator(ListIterator<?> i) {
74        assertFalse(i instanceof Serializable);
75        assertFalse(i.hasNext());
76        assertFalse(i.hasPrevious());
77        assertEquals(0, i.nextIndex());
78        try {
79            i.next();
80            fail();
81        } catch (NoSuchElementException expected) {
82        }
83        assertEquals(-1, i.previousIndex());
84        try {
85            i.previous();
86            fail();
87        } catch (NoSuchElementException expected) {
88        }
89        try {
90            i.add(null);
91            fail();
92        } catch (UnsupportedOperationException expected) {
93        }
94        try {
95            i.remove();
96            fail();
97        } catch (IllegalStateException expected) {
98        }
99    }
100
101    public void testSortFastPath_incrementsModcount() {
102        ArrayList<String> list = new ArrayList<String>(16);
103        list.add("coven");
104        list.add("asylum");
105        list.add("murder house");
106        list.add("freak show");
107
108        Iterator<String> it = list.iterator();
109        it.next();
110        Collections.sort(list);
111        try {
112            it.next();
113            fail();
114        } catch (ConcurrentModificationException expected) {
115        }
116    }
117
118    /**
119     * A value type whose {@code compareTo} method returns one of {@code 0},
120     * {@code Integer.MIN_VALUE} and {@code Integer.MAX_VALUE}.
121     */
122    static final class IntegerWithExtremeComparator
123            implements Comparable<IntegerWithExtremeComparator> {
124        private final int value;
125
126        public IntegerWithExtremeComparator(int value) {
127            this.value = value;
128        }
129
130        @Override
131        public int compareTo(IntegerWithExtremeComparator another) {
132            if (another.value == this.value) {
133                return 0;
134            } else if (another.value > this.value) {
135                return Integer.MIN_VALUE;
136            } else {
137                return Integer.MAX_VALUE;
138            }
139        }
140    }
141
142    // http://b/19749094
143    public void testBinarySearch_comparatorThatReturnsMinAndMaxValue() {
144        ArrayList<Integer> list = new ArrayList<Integer>(16);
145        list.add(4);
146        list.add(9);
147        list.add(11);
148        list.add(14);
149        list.add(16);
150
151        int index = Collections.binarySearch(list, 9, new Comparator<Integer>() {
152            @Override
153            public int compare(Integer lhs, Integer rhs) {
154                final int compare = lhs.compareTo(rhs);
155                if (compare == 0) {
156                    return 0;
157                } else if (compare < 0) {
158                    return Integer.MIN_VALUE;
159                } else {
160                    return Integer.MAX_VALUE;
161                }
162            }
163        });
164        assertEquals(1, index);
165
166        ArrayList<IntegerWithExtremeComparator> list2 =
167                new ArrayList<IntegerWithExtremeComparator>();
168        list2.add(new IntegerWithExtremeComparator(4));
169        list2.add(new IntegerWithExtremeComparator(9));
170        list2.add(new IntegerWithExtremeComparator(11));
171        list2.add(new IntegerWithExtremeComparator(14));
172        list2.add(new IntegerWithExtremeComparator(16));
173
174        assertEquals(1, Collections.binarySearch(list2, new IntegerWithExtremeComparator(9)));
175    }
176
177    public void testBinarySearch_emptyCollection() {
178        assertEquals(-1, Collections.binarySearch(new ArrayList<Integer>(), 9));
179
180        assertEquals(-1, Collections.binarySearch(new ArrayList<Integer>(), 9,
181                new Comparator<Integer>() {
182                    @Override
183                    public int compare(Integer lhs, Integer rhs) {
184                        return lhs.compareTo(rhs);
185                    }
186                }));
187    }
188}
189