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 static org.junit.Assert.assertEquals;
20import static org.junit.Assert.assertTrue;
21
22import android.support.annotation.NonNull;
23import android.support.test.filters.SmallTest;
24import android.support.test.runner.AndroidJUnit4;
25
26import org.junit.Before;
27import org.junit.Test;
28import org.junit.runner.RunWith;
29
30import java.util.Random;
31
32/**
33 * Internal tests for {@link SparseLongArray}.
34 */
35@SmallTest
36@RunWith(AndroidJUnit4.class)
37public class SparseLongArrayTest {
38
39    private static final int TEST_SIZE = 1000;
40
41    private SparseLongArray mSparseLongArray;
42    private int[] mKeys;
43    private long[] mValues;
44    private Random mRandom;
45
46    private static boolean isSame(@NonNull SparseLongArray array1,
47            @NonNull SparseLongArray array2) {
48        if (array1.size() != array2.size()) {
49            return false;
50        }
51        for (int i = 0; i < array1.size(); i++) {
52            if (array1.keyAt(i) != array2.keyAt(i) || array1.valueAt(i) != array2.valueAt(i)) {
53                return false;
54            }
55        }
56        return true;
57    }
58
59    private void assertRemoved(int startIndex, int endIndex) {
60        for (int i = 0; i < TEST_SIZE; i++) {
61            if (i >= startIndex && i <= endIndex) {
62                assertEquals("Entry not removed", Long.MIN_VALUE,
63                        mSparseLongArray.get(mKeys[i], Long.MIN_VALUE));
64            } else {
65                assertEquals("Untouched entry corrupted", mValues[i],
66                        mSparseLongArray.get(mKeys[i]));
67            }
68        }
69    }
70
71    /**
72     * Generates a sorted array of distinct and random keys
73     *
74     * @param size the number of keys to return in the array. Should be < (2^31)/1000.
75     * @return the array of keys
76     */
77    private int[] generateRandomKeys(int size) {
78        final int[] keys = new int[size];
79        keys[0] = -1 * mRandom.nextInt(size * 500);
80        for (int i = 1; i < size; i++) {
81            keys[i] = keys[i - 1] + 1 + mRandom.nextInt(1000);
82            assertTrue(keys[i] > keys[i - 1]);
83        }
84        return keys;
85    }
86
87    @Before
88    public void setUp() {
89        mSparseLongArray = new SparseLongArray();
90        mRandom = new Random(12345);
91        mKeys = generateRandomKeys(TEST_SIZE);
92        mValues = new long[TEST_SIZE];
93        for (int i = 0; i < TEST_SIZE; i++) {
94            mValues[i] = i + 1;
95            mSparseLongArray.put(mKeys[i], mValues[i]);
96        }
97    }
98
99    @Test
100    public void testRemoveAtRange_removeHead() {
101        mSparseLongArray.removeAtRange(0, 100);
102        assertEquals(TEST_SIZE - 100, mSparseLongArray.size());
103        assertRemoved(0, 99);
104    }
105
106    @Test
107    public void testRemoveAtRange_removeTail() {
108        mSparseLongArray.removeAtRange(TEST_SIZE - 200, 200);
109        assertEquals(TEST_SIZE - 200, mSparseLongArray.size());
110        assertRemoved(TEST_SIZE - 200, TEST_SIZE - 1);
111    }
112
113    @Test
114    public void testRemoveAtRange_removeOverflow() {
115        mSparseLongArray.removeAtRange(TEST_SIZE - 100, 200);
116        assertEquals(TEST_SIZE - 100, mSparseLongArray.size());
117        assertRemoved(TEST_SIZE - 100, TEST_SIZE - 1);
118    }
119
120    @Test
121    public void testRemoveAtRange_removeEverything() {
122        mSparseLongArray.removeAtRange(0, TEST_SIZE);
123        assertEquals(0, mSparseLongArray.size());
124        assertRemoved(0, TEST_SIZE - 1);
125    }
126
127    @Test
128    public void testRemoveAtRange_removeMiddle() {
129        mSparseLongArray.removeAtRange(200, 200);
130        assertEquals(TEST_SIZE - 200, mSparseLongArray.size());
131        assertRemoved(200, 399);
132    }
133
134    @Test
135    public void testRemoveAtRange_removeSingle() {
136        mSparseLongArray.removeAtRange(300, 1);
137        assertEquals(TEST_SIZE - 1, mSparseLongArray.size());
138        assertRemoved(300, 300);
139    }
140
141    @Test
142    public void testRemoveAtRange_compareRemoveAt() {
143        final SparseLongArray sparseLongArray2 = mSparseLongArray.clone();
144        assertTrue(isSame(mSparseLongArray, sparseLongArray2));
145
146        final int startIndex = 101;
147        final int endIndex = 200;
148        mSparseLongArray.removeAtRange(startIndex, endIndex - startIndex + 1);
149        for (int i = endIndex; i >= startIndex; i--) {
150            sparseLongArray2.removeAt(i);
151        }
152        assertEquals(TEST_SIZE - (endIndex - startIndex + 1), mSparseLongArray.size());
153        assertRemoved(startIndex, endIndex);
154        assertTrue(isSame(sparseLongArray2, mSparseLongArray));
155    }
156}
157