1 /* 2 * Copyright (c) 2009-2010 jMonkeyEngine 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions are 7 * met: 8 * 9 * * Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * 12 * * Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in the 14 * documentation and/or other materials provided with the distribution. 15 * 16 * * Neither the name of 'jMonkeyEngine' nor the names of its contributors 17 * may be used to endorse or promote products derived from this software 18 * without specific prior written permission. 19 * 20 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 21 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 22 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 23 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR 24 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 25 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 26 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 27 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 28 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 29 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 30 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 31 */ 32 33 package com.jme3.util; 34 35 import java.io.Serializable; 36 import java.util.Collection; 37 import java.util.HashMap; 38 import java.util.Map; 39 import java.util.Map.Entry; 40 import java.util.Set; 41 42 /** 43 * Implementation of a Map that favors iteration speed rather than 44 * get/put speed. 45 * 46 * @author Kirill Vainer 47 */ 48 public final class ListMap<K, V> implements Map<K, V>, Cloneable, Serializable { 49 50 public static void main(String[] args){ 51 Map<String, String> map = new ListMap<String, String>(); 52 map.put( "bob", "hello"); 53 System.out.println(map.get("bob")); 54 map.remove("bob"); 55 System.out.println(map.size()); 56 57 map.put("abc", "1"); 58 map.put("def", "2"); 59 map.put("ghi", "3"); 60 map.put("jkl", "4"); 61 map.put("mno", "5"); 62 System.out.println(map.get("ghi")); 63 } 64 65 private final static class ListMapEntry<K, V> implements Map.Entry<K, V>, Cloneable { 66 67 private final K key; 68 private V value; 69 70 public ListMapEntry(K key, V value){ 71 this.key = key; 72 this.value = value; 73 } 74 75 public K getKey() { 76 return key; 77 } 78 79 public V getValue() { 80 return value; 81 } 82 83 public V setValue(V v) { 84 throw new UnsupportedOperationException(); 85 } 86 87 @Override 88 public ListMapEntry<K, V> clone(){ 89 return new ListMapEntry<K, V>(key, value); 90 } 91 92 } 93 94 private final HashMap<K, V> backingMap; 95 private ListMapEntry<K, V>[] entries; 96 97 // private final ArrayList<ListMapEntry<K,V>> entries; 98 99 public ListMap(){ 100 entries = new ListMapEntry[4]; 101 backingMap = new HashMap<K, V>(4); 102 // entries = new ArrayList<ListMapEntry<K,V>>(); 103 } 104 105 public ListMap(int initialCapacity){ 106 entries = new ListMapEntry[initialCapacity]; 107 backingMap = new HashMap<K, V>(initialCapacity); 108 // entries = new ArrayList<ListMapEntry<K, V>>(initialCapacity); 109 } 110 111 public ListMap(Map<? extends K, ? extends V> map){ 112 entries = new ListMapEntry[map.size()]; 113 backingMap = new HashMap<K, V>(map.size()); 114 // entries = new ArrayList<ListMapEntry<K, V>>(map.size()); 115 putAll(map); 116 } 117 118 public int size() { 119 // return entries.size(); 120 return backingMap.size(); 121 } 122 123 public Entry<K, V> getEntry(int index){ 124 // return entries.get(index); 125 return entries[index]; 126 } 127 128 public V getValue(int index){ 129 // return entries.get(index).value; 130 return entries[index].value; 131 } 132 133 public K getKey(int index){ 134 // return entries.get(index).key; 135 return entries[index].key; 136 } 137 138 public boolean isEmpty() { 139 return size() == 0; 140 } 141 142 private static boolean keyEq(Object keyA, Object keyB){ 143 return keyA.hashCode() == keyB.hashCode() ? (keyA == keyB) || keyA.equals(keyB) : false; 144 } 145 // 146 // private static boolean valEq(Object a, Object b){ 147 // return a == null ? (b == null) : a.equals(b); 148 // } 149 150 public boolean containsKey(Object key) { 151 return backingMap.containsKey( (K) key); 152 // if (key == null) 153 // throw new IllegalArgumentException(); 154 // 155 // for (int i = 0; i < entries.size(); i++){ 156 // ListMapEntry<K,V> entry = entries.get(i); 157 // if (keyEq(entry.key, key)) 158 // return true; 159 // } 160 // return false; 161 } 162 163 public boolean containsValue(Object value) { 164 return backingMap.containsValue( (V) value); 165 // for (int i = 0; i < entries.size(); i++){ 166 // if (valEq(entries.get(i).value, value)) 167 // return true; 168 // } 169 // return false; 170 } 171 172 public V get(Object key) { 173 return backingMap.get( (K) key); 174 // if (key == null) 175 // throw new IllegalArgumentException(); 176 // 177 // for (int i = 0; i < entries.size(); i++){ 178 // ListMapEntry<K,V> entry = entries.get(i); 179 // if (keyEq(entry.key, key)) 180 // return entry.value; 181 // } 182 // return null; 183 } 184 185 public V put(K key, V value) { 186 if (backingMap.containsKey(key)){ 187 // set the value on the entry 188 int size = size(); 189 for (int i = 0; i < size; i++){ 190 ListMapEntry<K, V> entry = entries[i]; 191 if (keyEq(entry.key, key)){ 192 entry.value = value; 193 break; 194 } 195 } 196 }else{ 197 int size = size(); 198 // expand list as necessary 199 if (size == entries.length){ 200 ListMapEntry<K, V>[] tmpEntries = entries; 201 entries = new ListMapEntry[size * 2]; 202 System.arraycopy(tmpEntries, 0, entries, 0, size); 203 } 204 entries[size] = new ListMapEntry<K, V>(key, value); 205 } 206 return backingMap.put(key, value); 207 // if (key == null) 208 // throw new IllegalArgumentException(); 209 // 210 // // check if entry exists, if yes, overwrite it with new value 211 // for (int i = 0; i < entries.size(); i++){ 212 // ListMapEntry<K,V> entry = entries.get(i); 213 // if (keyEq(entry.key, key)){ 214 // V prevValue = entry.value; 215 // entry.value = value; 216 // return prevValue; 217 // } 218 // } 219 // 220 // // add a new entry 221 // entries.add(new ListMapEntry<K, V>(key, value)); 222 // return null; 223 } 224 225 public V remove(Object key) { 226 V element = backingMap.remove( (K) key); 227 if (element != null){ 228 // find removed element 229 int size = size() + 1; // includes removed element 230 int removedIndex = -1; 231 for (int i = 0; i < size; i++){ 232 ListMapEntry<K, V> entry = entries[i]; 233 if (keyEq(entry.key, key)){ 234 removedIndex = i; 235 break; 236 } 237 } 238 assert removedIndex >= 0; 239 240 size --; 241 for (int i = removedIndex; i < size; i++){ 242 entries[i] = entries[i+1]; 243 } 244 } 245 return element; 246 // if (key == null) 247 // throw new IllegalArgumentException(); 248 // 249 // for (int i = 0; i < entries.size(); i++){ 250 // ListMapEntry<K,V> entry = entries.get(i); 251 // if (keyEq(entry.key, key)){ 252 // return entries.remove(i).value; 253 // } 254 // } 255 // return null; 256 } 257 258 public void putAll(Map<? extends K, ? extends V> map) { 259 for (Entry<? extends K, ? extends V> entry : map.entrySet()){ 260 put(entry.getKey(), entry.getValue()); 261 } 262 263 264 // if (map instanceof ListMap){ 265 // ListMap<K, V> listMap = (ListMap<K, V>) map; 266 // ArrayList<ListMapEntry<K, V>> otherEntries = listMap.entries; 267 // for (int i = 0; i < otherEntries.size(); i++){ 268 // ListMapEntry<K, V> entry = otherEntries.get(i); 269 // put(entry.key, entry.value); 270 // } 271 // }else{ 272 // for (Map.Entry<? extends K, ? extends V> entry : map.entrySet()){ 273 // put(entry.getKey(), entry.getValue()); 274 // } 275 // } 276 } 277 278 public void clear() { 279 backingMap.clear(); 280 // entries.clear(); 281 } 282 283 @Override 284 public ListMap<K, V> clone(){ 285 ListMap<K, V> clone = new ListMap<K, V>(size()); 286 clone.putAll(this); 287 return clone; 288 } 289 290 public Set<K> keySet() { 291 return backingMap.keySet(); 292 // HashSet<K> keys = new HashSet<K>(); 293 // for (int i = 0; i < entries.size(); i++){ 294 // ListMapEntry<K,V> entry = entries.get(i); 295 // keys.add(entry.key); 296 // } 297 // return keys; 298 } 299 300 public Collection<V> values() { 301 return backingMap.values(); 302 // ArrayList<V> values = new ArrayList<V>(); 303 // for (int i = 0; i < entries.size(); i++){ 304 // ListMapEntry<K,V> entry = entries.get(i); 305 // values.add(entry.value); 306 // } 307 // return values; 308 } 309 310 public Set<Entry<K, V>> entrySet() { 311 return backingMap.entrySet(); 312 // HashSet<Entry<K, V>> entryset = new HashSet<Entry<K, V>>(); 313 // entryset.addAll(entries); 314 // return entryset; 315 } 316 317 } 318