12290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn/* 22290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * Copyright (C) 2013 The Android Open Source Project 32290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * 42290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * Licensed under the Apache License, Version 2.0 (the "License"); 52290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * you may not use this file except in compliance with the License. 62290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * You may obtain a copy of the License at 72290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * 82290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * http://www.apache.org/licenses/LICENSE-2.0 92290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * 102290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * Unless required by applicable law or agreed to in writing, software 112290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * distributed under the License is distributed on an "AS IS" BASIS, 122290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 132290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * See the License for the specific language governing permissions and 142290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * limitations under the License. 152290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn */ 162290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 172290993eddf5262a8df7fc9478daed52401e325aDianne Hackbornpackage android.support.v4.util; 182290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 192290993eddf5262a8df7fc9478daed52401e325aDianne Hackbornimport java.util.Collection; 202290993eddf5262a8df7fc9478daed52401e325aDianne Hackbornimport java.util.Map; 212290993eddf5262a8df7fc9478daed52401e325aDianne Hackbornimport java.util.Set; 222290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 232290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn/** 242290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * ArrayMap is a generic key->value mapping data structure that is 252290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * designed to be more memory efficient than a traditional {@link java.util.HashMap}, 262290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * this implementation is a version of the platform's 272290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * {@link android.util.ArrayMap} that can be used on older versions of the platform. 282290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * It keeps its mappings in an array data structure -- an integer array of hash 292290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * codes for each item, and an Object array of the key/value pairs. This allows it to 302290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * avoid having to create an extra object for every entry put in to the map, and it 312290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * also tries to control the growth of the size of these arrays more aggressively 322290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * (since growing them only requires copying the entries in the array, not rebuilding 332290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * a hash map). 342290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * 352290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * <p>If you don't need the standard Java container APIs provided here (iterators etc), 362290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * consider using {@link SimpleArrayMap} instead.</p> 372290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * 382290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * <p>Note that this implementation is not intended to be appropriate for data structures 392290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * that may contain large numbers of items. It is generally slower than a traditional 402290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * HashMap, since lookups require a binary search and adds and removes require inserting 412290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * and deleting entries in the array. For containers holding up to hundreds of items, 422290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * the performance difference is not significant, less than 50%.</p> 432290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * 442290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * <p>Because this container is intended to better balance memory use, unlike most other 452290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * standard Java containers it will shrink its array as items are removed from it. Currently 462290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * you have no control over this shrinking -- if you set a capacity and then remove an 472290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * item, it may reduce the capacity to better match the current size. In the future an 482290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * explicit call to set the capacity should turn off this aggressive shrinking behavior.</p> 492290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn */ 502290993eddf5262a8df7fc9478daed52401e325aDianne Hackbornpublic class ArrayMap<K, V> extends SimpleArrayMap<K, V> implements Map<K, V> { 512290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn MapCollections<K, V> mCollections; 522290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 532290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn public ArrayMap() { 542290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn super(); 552290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 562290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 572290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn /** 582290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * Create a new ArrayMap with a given initial capacity. 592290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn */ 602290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn public ArrayMap(int capacity) { 612290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn super(capacity); 622290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 632290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 642290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn /** 652290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * Create a new ArrayMap with the mappings from the given ArrayMap. 662290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn */ 672290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn public ArrayMap(SimpleArrayMap map) { 682290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn super(map); 692290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 702290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 712290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn private MapCollections<K, V> getCollection() { 722290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (mCollections == null) { 732290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mCollections = new MapCollections<K, V>() { 742290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn @Override 752290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn protected int colGetSize() { 762290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return mSize; 772290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 782290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 792290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn @Override 802290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn protected Object colGetEntry(int index, int offset) { 812290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return mArray[(index<<1) + offset]; 822290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 832290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 842290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn @Override 852290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn protected int colIndexOfKey(Object key) { 8652d06f41556ffe0a60fbdd786c32898a09ca2a50Adam Lesinski return indexOfKey(key); 872290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 882290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 892290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn @Override 902290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn protected int colIndexOfValue(Object value) { 912290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return indexOfValue(value); 922290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 932290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 942290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn @Override 952290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn protected Map<K, V> colGetMap() { 962290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return ArrayMap.this; 972290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 982290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 992290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn @Override 1002290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn protected void colPut(K key, V value) { 1012290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn put(key, value); 1022290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 1032290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 1042290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn @Override 1052290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn protected V colSetValue(int index, V value) { 1062290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return setValueAt(index, value); 1072290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 1082290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 1092290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn @Override 1102290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn protected void colRemoveAt(int index) { 1112290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn removeAt(index); 1122290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 1132290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 1142290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn @Override 1152290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn protected void colClear() { 1162290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn clear(); 1172290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 1182290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn }; 1192290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 1202290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return mCollections; 1212290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 1222290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 1232290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn /** 1242290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * Determine if the array map contains all of the keys in the given collection. 1252290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * @param collection The collection whose contents are to be checked against. 1262290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * @return Returns true if this array map contains a key for every entry 1272290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * in <var>collection</var>, else returns false. 1282290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn */ 1292290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn public boolean containsAll(Collection<?> collection) { 1302290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return MapCollections.containsAllHelper(this, collection); 1312290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 1322290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 1332290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn /** 1342290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * Perform a {@link #put(Object, Object)} of all key/value pairs in <var>map</var> 1352290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * @param map The map whose contents are to be retrieved. 1362290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn */ 1372290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn @Override 1382290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn public void putAll(Map<? extends K, ? extends V> map) { 1392290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn ensureCapacity(mSize + map.size()); 1402290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn for (Map.Entry<? extends K, ? extends V> entry : map.entrySet()) { 1412290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn put(entry.getKey(), entry.getValue()); 1422290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 1432290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 1442290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 1452290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn /** 1462290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * Remove all keys in the array map that exist in the given collection. 1472290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * @param collection The collection whose contents are to be used to remove keys. 1482290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * @return Returns true if any keys were removed from the array map, else false. 1492290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn */ 1502290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn public boolean removeAll(Collection<?> collection) { 1512290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return MapCollections.removeAllHelper(this, collection); 1522290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 1532290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 1542290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn /** 1552290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * Remove all keys in the array map that do <b>not</b> exist in the given collection. 1562290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * @param collection The collection whose contents are to be used to determine which 1572290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * keys to keep. 1582290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * @return Returns true if any keys were removed from the array map, else false. 1592290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn */ 1602290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn public boolean retainAll(Collection<?> collection) { 1612290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return MapCollections.retainAllHelper(this, collection); 1622290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 1632290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 1642290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn /** 1652290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * Return a {@link java.util.Set} for iterating over and interacting with all mappings 1662290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * in the array map. 1672290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * 1682290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * <p><b>Note:</b> this is a very inefficient way to access the array contents, it 1692290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * requires generating a number of temporary objects.</p> 1702290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * 1712290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * <p><b>Note:</b></p> the semantics of this 1722290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * Set are subtly different than that of a {@link java.util.HashMap}: most important, 1732290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * the {@link java.util.Map.Entry Map.Entry} object returned by its iterator is a single 1742290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * object that exists for the entire iterator, so you can <b>not</b> hold on to it 1752290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * after calling {@link java.util.Iterator#next() Iterator.next}.</p> 1762290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn */ 1772290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn @Override 1782290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn public Set<Entry<K, V>> entrySet() { 1792290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return getCollection().getEntrySet(); 1802290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 1812290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 1822290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn /** 1832290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * Return a {@link java.util.Set} for iterating over and interacting with all keys 1842290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * in the array map. 1852290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * 1862290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * <p><b>Note:</b> this is a fairly inefficient way to access the array contents, it 1872290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * requires generating a number of temporary objects.</p> 1882290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn */ 1892290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn @Override 1902290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn public Set<K> keySet() { 1912290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return getCollection().getKeySet(); 1922290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 1932290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 1942290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn /** 1952290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * Return a {@link java.util.Collection} for iterating over and interacting with all values 1962290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * in the array map. 1972290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * 1982290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * <p><b>Note:</b> this is a fairly inefficient way to access the array contents, it 1992290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * requires generating a number of temporary objects.</p> 2002290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn */ 2012290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn @Override 2022290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn public Collection<V> values() { 2032290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return getCollection().getValues(); 2042290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 2052290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn} 206