1 /* 2 * Copyright (C) 2013 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 17 package android.support.v4.util; 18 19 import java.util.Collection; 20 import java.util.Map; 21 import java.util.Set; 22 23 /** 24 * ArrayMap is a generic key->value mapping data structure that is 25 * designed to be more memory efficient than a traditional {@link java.util.HashMap}, 26 * this implementation is a version of the platform's 27 * {@link android.util.ArrayMap} that can be used on older versions of the platform. 28 * It keeps its mappings in an array data structure -- an integer array of hash 29 * codes for each item, and an Object array of the key/value pairs. This allows it to 30 * avoid having to create an extra object for every entry put in to the map, and it 31 * also tries to control the growth of the size of these arrays more aggressively 32 * (since growing them only requires copying the entries in the array, not rebuilding 33 * a hash map). 34 * 35 * <p>If you don't need the standard Java container APIs provided here (iterators etc), 36 * consider using {@link SimpleArrayMap} instead.</p> 37 * 38 * <p>Note that this implementation is not intended to be appropriate for data structures 39 * that may contain large numbers of items. It is generally slower than a traditional 40 * HashMap, since lookups require a binary search and adds and removes require inserting 41 * and deleting entries in the array. For containers holding up to hundreds of items, 42 * the performance difference is not significant, less than 50%.</p> 43 * 44 * <p>Because this container is intended to better balance memory use, unlike most other 45 * standard Java containers it will shrink its array as items are removed from it. Currently 46 * you have no control over this shrinking -- if you set a capacity and then remove an 47 * item, it may reduce the capacity to better match the current size. In the future an 48 * explicit call to set the capacity should turn off this aggressive shrinking behavior.</p> 49 */ 50 public class ArrayMap<K, V> extends SimpleArrayMap<K, V> implements Map<K, V> { 51 MapCollections<K, V> mCollections; 52 53 public ArrayMap() { 54 super(); 55 } 56 57 /** 58 * Create a new ArrayMap with a given initial capacity. 59 */ 60 public ArrayMap(int capacity) { 61 super(capacity); 62 } 63 64 /** 65 * Create a new ArrayMap with the mappings from the given ArrayMap. 66 */ 67 public ArrayMap(SimpleArrayMap map) { 68 super(map); 69 } 70 71 private MapCollections<K, V> getCollection() { 72 if (mCollections == null) { 73 mCollections = new MapCollections<K, V>() { 74 @Override 75 protected int colGetSize() { 76 return mSize; 77 } 78 79 @Override 80 protected Object colGetEntry(int index, int offset) { 81 return mArray[(index<<1) + offset]; 82 } 83 84 @Override 85 protected int colIndexOfKey(Object key) { 86 return indexOfKey(key); 87 } 88 89 @Override 90 protected int colIndexOfValue(Object value) { 91 return indexOfValue(value); 92 } 93 94 @Override 95 protected Map<K, V> colGetMap() { 96 return ArrayMap.this; 97 } 98 99 @Override 100 protected void colPut(K key, V value) { 101 put(key, value); 102 } 103 104 @Override 105 protected V colSetValue(int index, V value) { 106 return setValueAt(index, value); 107 } 108 109 @Override 110 protected void colRemoveAt(int index) { 111 removeAt(index); 112 } 113 114 @Override 115 protected void colClear() { 116 clear(); 117 } 118 }; 119 } 120 return mCollections; 121 } 122 123 /** 124 * Determine if the array map contains all of the keys in the given collection. 125 * @param collection The collection whose contents are to be checked against. 126 * @return Returns true if this array map contains a key for every entry 127 * in <var>collection</var>, else returns false. 128 */ 129 public boolean containsAll(Collection<?> collection) { 130 return MapCollections.containsAllHelper(this, collection); 131 } 132 133 /** 134 * Perform a {@link #put(Object, Object)} of all key/value pairs in <var>map</var> 135 * @param map The map whose contents are to be retrieved. 136 */ 137 @Override 138 public void putAll(Map<? extends K, ? extends V> map) { 139 ensureCapacity(mSize + map.size()); 140 for (Map.Entry<? extends K, ? extends V> entry : map.entrySet()) { 141 put(entry.getKey(), entry.getValue()); 142 } 143 } 144 145 /** 146 * Remove all keys in the array map that exist in the given collection. 147 * @param collection The collection whose contents are to be used to remove keys. 148 * @return Returns true if any keys were removed from the array map, else false. 149 */ 150 public boolean removeAll(Collection<?> collection) { 151 return MapCollections.removeAllHelper(this, collection); 152 } 153 154 /** 155 * Remove all keys in the array map that do <b>not</b> exist in the given collection. 156 * @param collection The collection whose contents are to be used to determine which 157 * keys to keep. 158 * @return Returns true if any keys were removed from the array map, else false. 159 */ 160 public boolean retainAll(Collection<?> collection) { 161 return MapCollections.retainAllHelper(this, collection); 162 } 163 164 /** 165 * Return a {@link java.util.Set} for iterating over and interacting with all mappings 166 * in the array map. 167 * 168 * <p><b>Note:</b> this is a very inefficient way to access the array contents, it 169 * requires generating a number of temporary objects.</p> 170 * 171 * <p><b>Note:</b></p> the semantics of this 172 * Set are subtly different than that of a {@link java.util.HashMap}: most important, 173 * the {@link java.util.Map.Entry Map.Entry} object returned by its iterator is a single 174 * object that exists for the entire iterator, so you can <b>not</b> hold on to it 175 * after calling {@link java.util.Iterator#next() Iterator.next}.</p> 176 */ 177 @Override 178 public Set<Entry<K, V>> entrySet() { 179 return getCollection().getEntrySet(); 180 } 181 182 /** 183 * Return a {@link java.util.Set} for iterating over and interacting with all keys 184 * in the array map. 185 * 186 * <p><b>Note:</b> this is a fairly inefficient way to access the array contents, it 187 * requires generating a number of temporary objects.</p> 188 */ 189 @Override 190 public Set<K> keySet() { 191 return getCollection().getKeySet(); 192 } 193 194 /** 195 * Return a {@link java.util.Collection} for iterating over and interacting with all values 196 * in the array map. 197 * 198 * <p><b>Note:</b> this is a fairly inefficient way to access the array contents, it 199 * requires generating a number of temporary objects.</p> 200 */ 201 @Override 202 public Collection<V> values() { 203 return getCollection().getValues(); 204 } 205 } 206