SparseLongArray.java revision ebb47950f21d3c41955a591000dfb1f195e746fe
1021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov/* 2021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * Copyright (C) 2011 The Android Open Source Project 3021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * 4021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * Licensed under the Apache License, Version 2.0 (the "License"); 5021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * you may not use this file except in compliance with the License. 6021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * You may obtain a copy of the License at 7021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * 8021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * http://www.apache.org/licenses/LICENSE-2.0 9021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * 10021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * Unless required by applicable law or agreed to in writing, software 11021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * distributed under the License is distributed on an "AS IS" BASIS, 12021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * See the License for the specific language governing permissions and 14021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * limitations under the License. 15021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov */ 16021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 17021078554b902179442a345a9d080a165c3b5139Svetoslav Ganovpackage android.util; 18021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 19021078554b902179442a345a9d080a165c3b5139Svetoslav Ganovimport com.android.internal.util.ArrayUtils; 20021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 21021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov/** 22021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * SparseLongArrays map integers to longs. Unlike a normal array of longs, 23b993f41eb2f165425dfdf0f93ea0b1e354eca837Dianne Hackborn * there can be gaps in the indices. It is intended to be more memory efficient 24b993f41eb2f165425dfdf0f93ea0b1e354eca837Dianne Hackborn * than using a HashMap to map Integers to Longs, both because it avoids 25b993f41eb2f165425dfdf0f93ea0b1e354eca837Dianne Hackborn * auto-boxing keys and values and its data structure doesn't rely on an extra entry object 26b993f41eb2f165425dfdf0f93ea0b1e354eca837Dianne Hackborn * for each mapping. 27b993f41eb2f165425dfdf0f93ea0b1e354eca837Dianne Hackborn * 28b993f41eb2f165425dfdf0f93ea0b1e354eca837Dianne Hackborn * <p>Note that this container keeps its mappings in an array data structure, 29b993f41eb2f165425dfdf0f93ea0b1e354eca837Dianne Hackborn * using a binary search to find keys. The implementation is not intended to be appropriate for 30b993f41eb2f165425dfdf0f93ea0b1e354eca837Dianne Hackborn * data structures 31b993f41eb2f165425dfdf0f93ea0b1e354eca837Dianne Hackborn * that may contain large numbers of items. It is generally slower than a traditional 32b993f41eb2f165425dfdf0f93ea0b1e354eca837Dianne Hackborn * HashMap, since lookups require a binary search and adds and removes require inserting 33b993f41eb2f165425dfdf0f93ea0b1e354eca837Dianne Hackborn * and deleting entries in the array. For containers holding up to hundreds of items, 34b993f41eb2f165425dfdf0f93ea0b1e354eca837Dianne Hackborn * the performance difference is not significant, less than 50%.</p> 355771302ca13c31cb85f17bc58da8f6f8227c9b85Flavio Lerda * 365771302ca13c31cb85f17bc58da8f6f8227c9b85Flavio Lerda * <p>It is possible to iterate over the items in this container using 375771302ca13c31cb85f17bc58da8f6f8227c9b85Flavio Lerda * {@link #keyAt(int)} and {@link #valueAt(int)}. Iterating over the keys using 385771302ca13c31cb85f17bc58da8f6f8227c9b85Flavio Lerda * <code>keyAt(int)</code> with ascending values of the index will return the 395771302ca13c31cb85f17bc58da8f6f8227c9b85Flavio Lerda * keys in ascending order, or the values corresponding to the keys in ascending 40ebb47950f21d3c41955a591000dfb1f195e746feNewton Allen * order in the case of <code>valueAt(int)</code>.</p> 41021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov */ 42021078554b902179442a345a9d080a165c3b5139Svetoslav Ganovpublic class SparseLongArray implements Cloneable { 43021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov private int[] mKeys; 44021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov private long[] mValues; 45021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov private int mSize; 46021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 47021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov /** 48021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * Creates a new SparseLongArray containing no mappings. 49021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov */ 50021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov public SparseLongArray() { 51021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov this(10); 52021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov } 53021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 54021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov /** 55021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * Creates a new SparseLongArray containing no mappings that will not 56021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * require any additional memory allocation to store the specified 57f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * number of mappings. If you supply an initial capacity of 0, the 58f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * sparse array will be initialized with a light-weight representation 59f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * not requiring any additional array allocations. 60021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov */ 61021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov public SparseLongArray(int initialCapacity) { 62f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (initialCapacity == 0) { 633e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn mKeys = ContainerHelpers.EMPTY_INTS; 643e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn mValues = ContainerHelpers.EMPTY_LONGS; 65f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } else { 66f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn initialCapacity = ArrayUtils.idealLongArraySize(initialCapacity); 67f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mKeys = new int[initialCapacity]; 68f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn mValues = new long[initialCapacity]; 69f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 70021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov mSize = 0; 71021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov } 72021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 73021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov @Override 74021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov public SparseLongArray clone() { 75021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov SparseLongArray clone = null; 76021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov try { 77021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov clone = (SparseLongArray) super.clone(); 78021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov clone.mKeys = mKeys.clone(); 79021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov clone.mValues = mValues.clone(); 80021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov } catch (CloneNotSupportedException cnse) { 81021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov /* ignore */ 82021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov } 83021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov return clone; 84021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov } 85021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 86021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov /** 87021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * Gets the long mapped from the specified key, or <code>0</code> 88021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * if no such mapping has been made. 89021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov */ 90021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov public long get(int key) { 91021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov return get(key, 0); 92021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov } 93021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 94021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov /** 95021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * Gets the long mapped from the specified key, or the specified value 96021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * if no such mapping has been made. 97021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov */ 98021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov public long get(int key, long valueIfKeyNotFound) { 993e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn int i = ContainerHelpers.binarySearch(mKeys, mSize, key); 100021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 101021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov if (i < 0) { 102021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov return valueIfKeyNotFound; 103021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov } else { 104021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov return mValues[i]; 105021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov } 106021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov } 107021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 108021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov /** 109021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * Removes the mapping from the specified key, if there was any. 110021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov */ 111021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov public void delete(int key) { 1123e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn int i = ContainerHelpers.binarySearch(mKeys, mSize, key); 113021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 114021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov if (i >= 0) { 115021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov removeAt(i); 116021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov } 117021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov } 118021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 119021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov /** 120021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * Removes the mapping at the given index. 121021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov */ 122021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov public void removeAt(int index) { 123021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov System.arraycopy(mKeys, index + 1, mKeys, index, mSize - (index + 1)); 124021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov System.arraycopy(mValues, index + 1, mValues, index, mSize - (index + 1)); 125021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov mSize--; 126021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov } 127021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 128021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov /** 129021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * Adds a mapping from the specified key to the specified value, 130021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * replacing the previous mapping from the specified key if there 131021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * was one. 132021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov */ 133021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov public void put(int key, long value) { 1343e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn int i = ContainerHelpers.binarySearch(mKeys, mSize, key); 135021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 136021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov if (i >= 0) { 137021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov mValues[i] = value; 138021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov } else { 139021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov i = ~i; 140021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 141021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov if (mSize >= mKeys.length) { 142021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov growKeyAndValueArrays(mSize + 1); 143021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov } 144021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 145021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov if (mSize - i != 0) { 146021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov System.arraycopy(mKeys, i, mKeys, i + 1, mSize - i); 147021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov System.arraycopy(mValues, i, mValues, i + 1, mSize - i); 148021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov } 149021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 150021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov mKeys[i] = key; 151021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov mValues[i] = value; 152021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov mSize++; 153021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov } 154021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov } 155021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 156021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov /** 157021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * Returns the number of key-value mappings that this SparseIntArray 158021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * currently stores. 159021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov */ 160021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov public int size() { 161021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov return mSize; 162021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov } 163021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 164021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov /** 165021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * Given an index in the range <code>0...size()-1</code>, returns 166021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * the key from the <code>index</code>th key-value mapping that this 167021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * SparseLongArray stores. 1685771302ca13c31cb85f17bc58da8f6f8227c9b85Flavio Lerda * 1695771302ca13c31cb85f17bc58da8f6f8227c9b85Flavio Lerda * <p>The keys corresponding to indices in ascending order are guaranteed to 1705771302ca13c31cb85f17bc58da8f6f8227c9b85Flavio Lerda * be in ascending order, e.g., <code>keyAt(0)</code> will return the 1715771302ca13c31cb85f17bc58da8f6f8227c9b85Flavio Lerda * smallest key and <code>keyAt(size()-1)</code> will return the largest 1725771302ca13c31cb85f17bc58da8f6f8227c9b85Flavio Lerda * key.</p> 173021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov */ 174021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov public int keyAt(int index) { 175021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov return mKeys[index]; 176021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov } 177021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 178021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov /** 179021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * Given an index in the range <code>0...size()-1</code>, returns 180021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * the value from the <code>index</code>th key-value mapping that this 181021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * SparseLongArray stores. 1825771302ca13c31cb85f17bc58da8f6f8227c9b85Flavio Lerda * 1835771302ca13c31cb85f17bc58da8f6f8227c9b85Flavio Lerda * <p>The values corresponding to indices in ascending order are guaranteed 1845771302ca13c31cb85f17bc58da8f6f8227c9b85Flavio Lerda * to be associated with keys in ascending order, e.g., 1855771302ca13c31cb85f17bc58da8f6f8227c9b85Flavio Lerda * <code>valueAt(0)</code> will return the value associated with the 1865771302ca13c31cb85f17bc58da8f6f8227c9b85Flavio Lerda * smallest key and <code>valueAt(size()-1)</code> will return the value 1875771302ca13c31cb85f17bc58da8f6f8227c9b85Flavio Lerda * associated with the largest key.</p> 188021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov */ 189021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov public long valueAt(int index) { 190021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov return mValues[index]; 191021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov } 192021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 193021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov /** 194021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * Returns the index for which {@link #keyAt} would return the 195021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * specified key, or a negative number if the specified 196021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * key is not mapped. 197021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov */ 198021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov public int indexOfKey(int key) { 1993e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn return ContainerHelpers.binarySearch(mKeys, mSize, key); 200021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov } 201021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 202021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov /** 203021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * Returns an index for which {@link #valueAt} would return the 204021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * specified key, or a negative number if no keys map to the 205021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * specified value. 206021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * Beware that this is a linear search, unlike lookups by key, 207021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * and that multiple keys can map to the same value and this will 208021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * find only one of them. 209021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov */ 210021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov public int indexOfValue(long value) { 211021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov for (int i = 0; i < mSize; i++) 212021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov if (mValues[i] == value) 213021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov return i; 214021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 215021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov return -1; 216021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov } 217021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 218021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov /** 219021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * Removes all key-value mappings from this SparseIntArray. 220021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov */ 221021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov public void clear() { 222021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov mSize = 0; 223021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov } 224021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 225021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov /** 226021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * Puts a key/value pair into the array, optimizing for the case where 227021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * the key is greater than all existing keys in the array. 228021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov */ 229021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov public void append(int key, long value) { 230021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov if (mSize != 0 && key <= mKeys[mSize - 1]) { 231021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov put(key, value); 232021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov return; 233021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov } 234021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 235021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov int pos = mSize; 236021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov if (pos >= mKeys.length) { 237021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov growKeyAndValueArrays(pos + 1); 238021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov } 239021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 240021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov mKeys[pos] = key; 241021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov mValues[pos] = value; 242021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov mSize = pos + 1; 243021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov } 244021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 245021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov private void growKeyAndValueArrays(int minNeededSize) { 246021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov int n = ArrayUtils.idealLongArraySize(minNeededSize); 247021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 248021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov int[] nkeys = new int[n]; 249021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov long[] nvalues = new long[n]; 250021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 251021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length); 252021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov System.arraycopy(mValues, 0, nvalues, 0, mValues.length); 253021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 254021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov mKeys = nkeys; 255021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov mValues = nvalues; 256021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov } 2573e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn 2583e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn /** 2593e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn * {@inheritDoc} 2603e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn * 2613e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn * <p>This implementation composes a string by iterating over its mappings. 2623e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn */ 2633e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn @Override 2643e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn public String toString() { 2653e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn if (size() <= 0) { 2663e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn return "{}"; 2673e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn } 2683e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn 2693e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn StringBuilder buffer = new StringBuilder(mSize * 28); 2703e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn buffer.append('{'); 2713e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn for (int i=0; i<mSize; i++) { 2723e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn if (i > 0) { 2733e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn buffer.append(", "); 2743e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn } 2753e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn int key = keyAt(i); 2763e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn buffer.append(key); 2773e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn buffer.append('='); 2783e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn long value = valueAt(i); 2793e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn buffer.append(value); 2803e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn } 2813e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn buffer.append('}'); 2823e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn return buffer.toString(); 2833e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn } 284021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov} 285