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 java.io.ByteArrayInputStream;
21import java.io.ByteArrayOutputStream;
22import java.io.IOException;
23import java.io.ObjectInputStream;
24import java.io.ObjectOutputStream;
25import java.lang.reflect.Method;
26import java.util.Collection;
27import java.util.HashMap;
28import java.util.Iterator;
29import java.util.Map;
30import java.util.NoSuchElementException;
31import java.util.Random;
32import java.util.Set;
33import java.util.SortedMap;
34import java.util.TreeMap;
35
36import junit.framework.TestCase;
37
38public abstract class SortedMapTestBase extends TestCase {
39
40    final int N = 1000;
41    final int TRIES = 100;
42
43    SortedMap<Integer, Integer> map;
44    SortedMap<Integer, Integer> ref;
45
46    Random rnd;
47
48    protected void setUp() throws Exception {
49        rnd = new Random(-1);
50        for (int i = 0; i < N; i++) {
51            ref.put(rnd.nextInt(N) * 2, rnd.nextBoolean() ? null : rnd.nextInt(N) * 2);
52        }
53    }
54
55    public final void testClear() {
56        map.clear();
57        assertTrue(map.isEmpty());
58    }
59
60    public final void testContainsKey() {
61        for (int i = 0; i < TRIES; i++) {
62            int key = rnd.nextInt(N);
63            assertEquals(ref.containsKey(key), map.containsKey(key));
64        }
65    }
66
67
68    public final void testContainsValue() {
69        for (int i = 0; i < TRIES; i++) {
70            int value = rnd.nextInt(N);
71            assertEquals(ref.containsValue(value), map.containsValue(value));
72        }
73    }
74
75
76    public final void testEntrySet() {
77        Set<Map.Entry<Integer, Integer>> refSet = ref.entrySet();
78        Set<Map.Entry<Integer, Integer>> mapSet = map.entrySet();
79        for (Map.Entry<Integer, Integer> e : refSet) {
80            assertTrue(mapSet.contains(e));
81        }
82        for (Map.Entry<Integer, Integer> e : mapSet) {
83            assertTrue(refSet.contains(e));
84        }
85        assertEquals(ref.entrySet(), map.entrySet());
86    }
87
88
89    public final void testGet() {
90        for (int i = 0; i < TRIES; i++) {
91            int key = rnd.nextInt(N);
92            assertEquals(ref.get(key), map.get(key));
93        }
94    }
95
96
97    public final void testKeySet() {
98        assertEquals(ref.keySet(), map.keySet());
99        Iterator<Integer> i = ref.keySet().iterator();
100        Iterator<Integer> j = map.keySet().iterator();
101        while (i.hasNext()) {
102            assertEquals(i.next(), j.next());
103            if (rnd.nextBoolean()) {
104                j.remove();
105                i.remove();
106            }
107        }
108    }
109
110
111    public final void testPut() {
112        for (int i = 0; i < TRIES; i++) {
113            int key = rnd.nextInt(N);
114            int value = rnd.nextInt(N);
115            assertEquals(ref.put(key, value), map.put(key, value));
116            assertEquals(ref.get(key), map.get(key));
117            assertEquals(ref, map);
118        }
119    }
120
121    public final void testPut0() {
122        ref.clear();
123        map.clear();
124        for (int i = 0; i < N; i++) {
125            int key = rnd.nextInt(N);
126            int value = rnd.nextInt(N);
127            assertEquals(ref.put(key, value), map.put(key, value));
128            assertEquals(ref.get(key), map.get(key));
129        }
130    }
131
132    public final void testPutAll() {
133        Map<Integer, Integer> mixin = new HashMap<Integer, Integer>(TRIES);
134        for (int i = 0; i < TRIES; i++) {
135            mixin.put(rnd.nextInt(N), rnd.nextInt(N));
136        }
137        ref.putAll(mixin);
138        map.putAll(mixin);
139        assertEquals(ref, map);
140    }
141
142
143    public final void testRemove() {
144        for (int i = 0; i < N; i++) {
145            int key = rnd.nextInt(N);
146            assertEquals(ref.remove(key), map.remove(key));
147            if (i % (N / TRIES) == 0) {
148                assertEquals(ref, map);
149            }
150        }
151    }
152
153    public final void testRemove0() {
154        while (!ref.isEmpty()) {
155            int key = ref.tailMap((ref.firstKey() + ref.lastKey()) / 2)
156                    .firstKey();
157            assertEquals(ref.remove(key), map.remove(key));
158        }
159    }
160
161    public final void testSize() {
162        assertEquals(ref.size(), map.size());
163    }
164
165
166    public final void testValues() {
167        assertEquals(ref.values().size(), map.values().size());
168        assertTrue(ref.values().containsAll(map.values()));
169        assertTrue(map.values().containsAll(ref.values()));
170
171        Iterator<Integer> i = ref.values().iterator();
172        Iterator<Integer> j = map.values().iterator();
173        while (i.hasNext()) {
174            assertEquals(i.next(), j.next());
175            if (rnd.nextBoolean()) {
176                j.remove();
177                i.remove();
178            }
179        }
180    }
181
182    public final void testComparator() {
183        assertEquals(ref.comparator(), map.comparator());
184    }
185
186
187    public final void testFirstKey() {
188        assertEquals(ref.firstKey(), map.firstKey());
189    }
190
191
192    public final void testHeadMap() {
193        for (int i = 0; i < TRIES; i++) {
194            int key = rnd.nextInt(N);
195            checkSubMap(ref.headMap(key), map.headMap(key));
196        }
197        checkSubMap(ref.headMap(-1), map.headMap(-1));
198    }
199
200    public final void testLastKey() {
201        assertEquals(ref.lastKey(), map.lastKey());
202    }
203
204    public final void testSubMap() {
205        for (int i = 0; i < TRIES; i++) {
206            int key0 = rnd.nextInt(N / 2);
207            int key1 = rnd.nextInt(N / 2) + N / 2;
208            if (ref.comparator() != null &&
209                    ref.comparator().compare(key0, key1) > 0) {
210
211                int tmp = key0;
212                key0 = key1;
213                key1 = tmp;
214            }
215            checkSubMap(ref.subMap(key0, key1), map.subMap(key0, key1));
216        }
217        boolean caught = false;
218        try {
219            if (ref.comparator() != null && ref.comparator().compare(100, 0) < 0) {
220                map.subMap(0, 100);
221            } else {
222                map.subMap(100, 0);
223            }
224        } catch (IllegalArgumentException e) {
225            caught = true;
226        }
227        assertTrue(caught);
228
229        int firstKey = ref.firstKey();
230        Map.Entry<Integer, Integer> refE = ref.entrySet().iterator().next();
231        Map.Entry<Integer, Integer> mapE = map.entrySet().iterator().next();
232        mapE.setValue(-1);
233        refE.setValue(-1);
234        assertEquals(ref.get(firstKey), map.get(firstKey));
235    }
236
237
238    public final void testTailMap() {
239        for (int i = 0; i < TRIES; i++) {
240            int key = rnd.nextInt(2 * N);
241            checkSubMap(ref.tailMap(key), map.tailMap(key));
242        }
243        checkSubMap(ref.tailMap(2 * N + 1), map.tailMap(2 * N + 1));
244    }
245
246
247    public final void testHashCode() {
248        assertEquals(ref.hashCode(), map.hashCode());
249    }
250
251    public final void testEqualsObject() {
252        assertTrue(map.equals(ref));
253        map.put(N + 1, N + 1);
254        assertFalse(map.equals(ref));
255    }
256
257
258    public final void testIsEmpty() {
259        assertEquals(ref.isEmpty(), map.isEmpty());
260    }
261
262    public final void testIsEmpty2() {
263        TreeMap<String, String> map = new TreeMap<String, String>();
264        map.put("one", "1");
265        assertEquals("size should be one", 1, map.size());
266        map.clear();
267        assertEquals("size should be zero", 0, map.size());
268        assertTrue("Should not have entries", !map.entrySet().iterator()
269                .hasNext());
270
271        map.put("one", "1");
272        assertEquals("size should be one", 1, map.size());
273        map.remove("one");
274        assertEquals("size should be zero", 0, map.size());
275        assertTrue("Should not have entries", !map.entrySet().iterator()
276                .hasNext());
277
278        map.clear();
279        map.put("0", "1");
280        map.clear();
281        assertTrue(map.isEmpty());
282        assertFalse(map.entrySet().iterator().hasNext());
283        assertFalse(map.keySet().iterator().hasNext());
284        assertFalse(map.values().iterator().hasNext());
285    }
286
287    public final void testToString() {
288        assertEquals(ref.toString(), map.toString());
289    }
290
291    private void checkSubMap(SortedMap<Integer, Integer> ref,
292            SortedMap<Integer, Integer> map) {
293
294        assertEquals(ref.size(), map.size());
295        assertEquals(ref, map);
296        assertEquals(ref.isEmpty(), map.isEmpty());
297        if (!ref.isEmpty()) {
298            assertEquals(ref.firstKey(), map.firstKey());
299            assertEquals(ref.lastKey(), map.lastKey());
300
301            testViews(ref, map);
302        } else {
303            boolean caught = false;
304            try {
305                map.firstKey();
306            } catch (NoSuchElementException e) {
307                caught = true;
308            }
309            caught = false;
310            try {
311                map.lastKey();
312            } catch (NoSuchElementException e) {
313                caught = true;
314            }
315            assertTrue(caught);
316        }
317
318    }
319
320    public final void testViews() {
321        testViews(ref, map);
322    }
323
324    private void testViews(SortedMap<Integer, Integer> ref, SortedMap<Integer, Integer> map) {
325        assertEquals(ref.keySet().size(), map.keySet().size());
326        assertEquals(ref.keySet(), map.keySet());
327        compareIterators(ref.keySet(), map.keySet());
328
329        assertEquals(ref.values().size(), map.values().size());
330        compareIterators(ref.values(), map.values());
331
332        assertEquals(ref.entrySet(), map.entrySet());
333        compareIterators(ref.entrySet(), map.entrySet());
334    }
335
336    private void compareIterators(Collection ref, Collection map) {
337        Iterator i = ref.iterator();
338        Iterator j = map.iterator();
339        while (i.hasNext()) {
340            assertEquals(i.next(), j.next());
341            if (rnd.nextBoolean()) {
342                j.remove();
343                i.remove();
344                assertEquals(ref.size(), map.size());
345            }
346        }
347    }
348
349    @SuppressWarnings("unchecked")
350    public final void testSerialization() throws IOException, ClassNotFoundException {
351        ByteArrayOutputStream baos = new ByteArrayOutputStream();
352        ObjectOutputStream oos = new ObjectOutputStream(baos);
353        oos.writeObject(map);
354        oos.close();
355        ObjectInputStream ois = new ObjectInputStream(new ByteArrayInputStream(baos.toByteArray()));
356        Object read = ois.readObject();
357        assertEquals(ref, read);
358    }
359
360    public final void testClone() throws Exception {
361        Method refClone = ref.getClass().getMethod("clone", new Class[0]);
362        Method mapClone = map.getClass().getMethod("clone", new Class[0]);
363        SortedMap<Integer, Integer> map2 = (SortedMap<Integer, Integer>) mapClone.invoke(map, new Object[0]);
364        assertEquals(refClone.invoke(ref, new Object[0]), map2);
365        map2.remove(map2.lastKey());
366        assertFalse(ref.equals(map2));
367    }
368
369}
370