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