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