1/*
2 * Copyright (C) 2007 The Android Open Source Project
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 android.util;
18
19import junit.framework.TestCase;
20
21import java.util.HashMap;
22import java.util.Iterator;
23import java.util.Map;
24import java.util.Random;
25
26/**
27 * Tests for {@link LongSparseLongArray}.
28 */
29public class LongSparseLongArrayTest extends TestCase {
30    private static final String TAG = "LongSparseLongArrayTest";
31
32    public void testSimplePut() throws Exception {
33        final LongSparseLongArray array = new LongSparseLongArray(5);
34        for (int i = 0; i < 48; i++) {
35            final long value = 1 << i;
36            array.put(value, value);
37        }
38        for (int i = 0; i < 48; i++) {
39            final long value = 1 << i;
40            assertEquals(value, array.get(value, -1));
41            assertEquals(-1, array.get(-value, -1));
42        }
43    }
44
45    public void testSimplePutBackwards() throws Exception {
46        final LongSparseLongArray array = new LongSparseLongArray(5);
47        for (int i = 47; i >= 0; i--) {
48            final long value = 1 << i;
49            array.put(value, value);
50        }
51        for (int i = 0; i < 48; i++) {
52            final long value = 1 << i;
53            assertEquals(value, array.get(value, -1));
54            assertEquals(-1, array.get(-value, -1));
55        }
56    }
57
58    public void testMiddleInsert() throws Exception {
59        final LongSparseLongArray array = new LongSparseLongArray(5);
60        for (int i = 0; i < 48; i++) {
61            final long value = 1 << i;
62            array.put(value, value);
63        }
64        final long special = (1 << 24) + 5;
65        array.put(special, 1024);
66        for (int i = 0; i < 48; i++) {
67            final long value = 1 << i;
68            assertEquals(value, array.get(value, -1));
69            assertEquals(-1, array.get(-value, -1));
70        }
71        assertEquals(1024, array.get(special, -1));
72    }
73
74    public void testFuzz() throws Exception {
75        final Random r = new Random();
76
77        final HashMap<Long, Long> map = new HashMap<Long, Long>();
78        final LongSparseLongArray array = new LongSparseLongArray(r.nextInt(128));
79
80        for (int i = 0; i < 10240; i++) {
81            if (r.nextBoolean()) {
82                final long key = r.nextLong();
83                final long value = r.nextLong();
84                map.put(key, value);
85                array.put(key, value);
86            }
87            if (r.nextBoolean() && map.size() > 0) {
88                final int index = r.nextInt(map.size());
89                final long key = getKeyAtIndex(map, index);
90                map.remove(key);
91                array.delete(key);
92            }
93        }
94
95        Log.d(TAG, "verifying a map with " + map.size() + " entries");
96
97        for (Map.Entry<Long, Long> e : map.entrySet()) {
98            final long key = e.getKey();
99            final long value = e.getValue();
100            assertEquals(value, array.get(key));
101        }
102    }
103
104    private static <E> E getKeyAtIndex(Map<E, ?> map, int index) {
105        final Iterator<E> keys = map.keySet().iterator();
106        for (int i = 0; i < index; i++) {
107            keys.next();
108        }
109        return keys.next();
110    }
111}
112