1dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey/* 2dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey * Copyright (C) 2007 The Android Open Source Project 3dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey * 4dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey * Licensed under the Apache License, Version 2.0 (the "License"); 5dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey * you may not use this file except in compliance with the License. 6dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey * You may obtain a copy of the License at 7dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey * 8dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey * http://www.apache.org/licenses/LICENSE-2.0 9dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey * 10dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey * Unless required by applicable law or agreed to in writing, software 11dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey * distributed under the License is distributed on an "AS IS" BASIS, 12dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey * See the License for the specific language governing permissions and 14dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey * limitations under the License. 15dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey */ 16dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey 17dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkeypackage android.util; 18dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey 19bdbde55592792efe350acd6a46733f439f6a3f3dAurimas Liutikasimport android.support.test.filters.LargeTest; 20bdbde55592792efe350acd6a46733f439f6a3f3dAurimas Liutikas 21dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkeyimport junit.framework.TestCase; 22dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey 23dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkeyimport java.util.HashMap; 24dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkeyimport java.util.Iterator; 25dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkeyimport java.util.Map; 26dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkeyimport java.util.Random; 27dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey 28dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey/** 29dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey * Tests for {@link LongSparseLongArray}. 30dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey */ 31bdbde55592792efe350acd6a46733f439f6a3f3dAurimas Liutikas@LargeTest 32dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkeypublic class LongSparseLongArrayTest extends TestCase { 33dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey private static final String TAG = "LongSparseLongArrayTest"; 34dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey 35dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey public void testSimplePut() throws Exception { 36dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey final LongSparseLongArray array = new LongSparseLongArray(5); 37dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey for (int i = 0; i < 48; i++) { 38dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey final long value = 1 << i; 39dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey array.put(value, value); 40dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey } 41dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey for (int i = 0; i < 48; i++) { 42dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey final long value = 1 << i; 43dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey assertEquals(value, array.get(value, -1)); 44dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey assertEquals(-1, array.get(-value, -1)); 45dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey } 46dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey } 47dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey 48dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey public void testSimplePutBackwards() throws Exception { 49dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey final LongSparseLongArray array = new LongSparseLongArray(5); 50dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey for (int i = 47; i >= 0; i--) { 51dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey final long value = 1 << i; 52dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey array.put(value, value); 53dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey } 54dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey for (int i = 0; i < 48; i++) { 55dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey final long value = 1 << i; 56dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey assertEquals(value, array.get(value, -1)); 57dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey assertEquals(-1, array.get(-value, -1)); 58dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey } 59dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey } 60dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey 61dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey public void testMiddleInsert() throws Exception { 62dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey final LongSparseLongArray array = new LongSparseLongArray(5); 63dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey for (int i = 0; i < 48; i++) { 64dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey final long value = 1 << i; 65dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey array.put(value, value); 66dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey } 67dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey final long special = (1 << 24) + 5; 68dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey array.put(special, 1024); 69dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey for (int i = 0; i < 48; i++) { 70dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey final long value = 1 << i; 71dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey assertEquals(value, array.get(value, -1)); 72dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey assertEquals(-1, array.get(-value, -1)); 73dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey } 74dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey assertEquals(1024, array.get(special, -1)); 75dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey } 76dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey 77dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey public void testFuzz() throws Exception { 78dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey final Random r = new Random(); 79dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey 80dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey final HashMap<Long, Long> map = new HashMap<Long, Long>(); 81dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey final LongSparseLongArray array = new LongSparseLongArray(r.nextInt(128)); 82dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey 83dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey for (int i = 0; i < 10240; i++) { 84dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey if (r.nextBoolean()) { 85dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey final long key = r.nextLong(); 86dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey final long value = r.nextLong(); 87dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey map.put(key, value); 88dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey array.put(key, value); 89dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey } 90dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey if (r.nextBoolean() && map.size() > 0) { 91dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey final int index = r.nextInt(map.size()); 92dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey final long key = getKeyAtIndex(map, index); 93dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey map.remove(key); 94dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey array.delete(key); 95dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey } 96dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey } 97dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey 98dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey Log.d(TAG, "verifying a map with " + map.size() + " entries"); 99dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey 100dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey for (Map.Entry<Long, Long> e : map.entrySet()) { 101dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey final long key = e.getKey(); 102dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey final long value = e.getValue(); 103dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey assertEquals(value, array.get(key)); 104dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey } 105dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey } 106dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey 107dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey private static <E> E getKeyAtIndex(Map<E, ?> map, int index) { 108dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey final Iterator<E> keys = map.keySet().iterator(); 109dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey for (int i = 0; i < index; i++) { 110dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey keys.next(); 111dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey } 112dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey return keys.next(); 113dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey } 114dda73b5dcd92006762a1c71e2fb352e64fa265efJeff Sharkey} 115