159b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta/* 259b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta * Copyright (c) 2009-2010 jMonkeyEngine 359b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta * All rights reserved. 459b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta * 559b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta * Redistribution and use in source and binary forms, with or without 659b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta * modification, are permitted provided that the following conditions are 759b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta * met: 859b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta * 959b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta * * Redistributions of source code must retain the above copyright 1059b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta * notice, this list of conditions and the following disclaimer. 1159b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta * 1259b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta * * Redistributions in binary form must reproduce the above copyright 1359b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta * notice, this list of conditions and the following disclaimer in the 1459b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta * documentation and/or other materials provided with the distribution. 1559b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta * 1659b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta * * Neither the name of 'jMonkeyEngine' nor the names of its contributors 1759b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta * may be used to endorse or promote products derived from this software 1859b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta * without specific prior written permission. 1959b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta * 2059b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 2159b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 2259b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 2359b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR 2459b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 2559b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 2659b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 2759b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 2859b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 2959b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 3059b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 3159b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta */ 3259b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 3359b2e6871c65f58fdad78cd7229c292f6a177578Scott Bartapackage com.jme3.util; 3459b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 3559b2e6871c65f58fdad78cd7229c292f6a177578Scott Bartaimport java.io.Serializable; 3659b2e6871c65f58fdad78cd7229c292f6a177578Scott Bartaimport java.util.Collection; 3759b2e6871c65f58fdad78cd7229c292f6a177578Scott Bartaimport java.util.HashMap; 3859b2e6871c65f58fdad78cd7229c292f6a177578Scott Bartaimport java.util.Map; 3959b2e6871c65f58fdad78cd7229c292f6a177578Scott Bartaimport java.util.Map.Entry; 4059b2e6871c65f58fdad78cd7229c292f6a177578Scott Bartaimport java.util.Set; 4159b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 4259b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta/** 4359b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta * Implementation of a Map that favors iteration speed rather than 4459b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta * get/put speed. 4559b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta * 4659b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta * @author Kirill Vainer 4759b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta */ 4859b2e6871c65f58fdad78cd7229c292f6a177578Scott Bartapublic final class ListMap<K, V> implements Map<K, V>, Cloneable, Serializable { 4959b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 5059b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta public static void main(String[] args){ 5159b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta Map<String, String> map = new ListMap<String, String>(); 5259b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta map.put( "bob", "hello"); 5359b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta System.out.println(map.get("bob")); 5459b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta map.remove("bob"); 5559b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta System.out.println(map.size()); 5659b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 5759b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta map.put("abc", "1"); 5859b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta map.put("def", "2"); 5959b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta map.put("ghi", "3"); 6059b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta map.put("jkl", "4"); 6159b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta map.put("mno", "5"); 6259b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta System.out.println(map.get("ghi")); 6359b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 6459b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 6559b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta private final static class ListMapEntry<K, V> implements Map.Entry<K, V>, Cloneable { 6659b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 6759b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta private final K key; 6859b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta private V value; 6959b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 7059b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta public ListMapEntry(K key, V value){ 7159b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta this.key = key; 7259b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta this.value = value; 7359b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 7459b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 7559b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta public K getKey() { 7659b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta return key; 7759b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 7859b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 7959b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta public V getValue() { 8059b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta return value; 8159b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 8259b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 8359b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta public V setValue(V v) { 8459b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta throw new UnsupportedOperationException(); 8559b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 8659b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 8759b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta @Override 8859b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta public ListMapEntry<K, V> clone(){ 8959b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta return new ListMapEntry<K, V>(key, value); 9059b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 9159b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 9259b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 9359b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 9459b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta private final HashMap<K, V> backingMap; 9559b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta private ListMapEntry<K, V>[] entries; 9659b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 9759b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// private final ArrayList<ListMapEntry<K,V>> entries; 9859b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 9959b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta public ListMap(){ 10059b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta entries = new ListMapEntry[4]; 10159b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta backingMap = new HashMap<K, V>(4); 10259b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// entries = new ArrayList<ListMapEntry<K,V>>(); 10359b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 10459b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 10559b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta public ListMap(int initialCapacity){ 10659b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta entries = new ListMapEntry[initialCapacity]; 10759b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta backingMap = new HashMap<K, V>(initialCapacity); 10859b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// entries = new ArrayList<ListMapEntry<K, V>>(initialCapacity); 10959b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 11059b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 11159b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta public ListMap(Map<? extends K, ? extends V> map){ 11259b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta entries = new ListMapEntry[map.size()]; 11359b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta backingMap = new HashMap<K, V>(map.size()); 11459b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// entries = new ArrayList<ListMapEntry<K, V>>(map.size()); 11559b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta putAll(map); 11659b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 11759b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 11859b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta public int size() { 11959b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// return entries.size(); 12059b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta return backingMap.size(); 12159b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 12259b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 12359b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta public Entry<K, V> getEntry(int index){ 12459b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// return entries.get(index); 12559b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta return entries[index]; 12659b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 12759b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 12859b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta public V getValue(int index){ 12959b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// return entries.get(index).value; 13059b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta return entries[index].value; 13159b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 13259b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 13359b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta public K getKey(int index){ 13459b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// return entries.get(index).key; 13559b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta return entries[index].key; 13659b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 13759b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 13859b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta public boolean isEmpty() { 13959b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta return size() == 0; 14059b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 14159b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 14259b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta private static boolean keyEq(Object keyA, Object keyB){ 14359b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta return keyA.hashCode() == keyB.hashCode() ? (keyA == keyB) || keyA.equals(keyB) : false; 14459b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 14559b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// 14659b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// private static boolean valEq(Object a, Object b){ 14759b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// return a == null ? (b == null) : a.equals(b); 14859b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// } 14959b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 15059b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta public boolean containsKey(Object key) { 15159b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta return backingMap.containsKey( (K) key); 15259b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// if (key == null) 15359b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// throw new IllegalArgumentException(); 15459b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// 15559b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// for (int i = 0; i < entries.size(); i++){ 15659b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// ListMapEntry<K,V> entry = entries.get(i); 15759b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// if (keyEq(entry.key, key)) 15859b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// return true; 15959b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// } 16059b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// return false; 16159b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 16259b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 16359b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta public boolean containsValue(Object value) { 16459b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta return backingMap.containsValue( (V) value); 16559b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// for (int i = 0; i < entries.size(); i++){ 16659b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// if (valEq(entries.get(i).value, value)) 16759b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// return true; 16859b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// } 16959b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// return false; 17059b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 17159b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 17259b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta public V get(Object key) { 17359b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta return backingMap.get( (K) key); 17459b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// if (key == null) 17559b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// throw new IllegalArgumentException(); 17659b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// 17759b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// for (int i = 0; i < entries.size(); i++){ 17859b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// ListMapEntry<K,V> entry = entries.get(i); 17959b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// if (keyEq(entry.key, key)) 18059b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// return entry.value; 18159b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// } 18259b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// return null; 18359b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 18459b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 18559b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta public V put(K key, V value) { 18659b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta if (backingMap.containsKey(key)){ 18759b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta // set the value on the entry 18859b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta int size = size(); 18959b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta for (int i = 0; i < size; i++){ 19059b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta ListMapEntry<K, V> entry = entries[i]; 19159b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta if (keyEq(entry.key, key)){ 19259b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta entry.value = value; 19359b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta break; 19459b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 19559b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 19659b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta }else{ 19759b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta int size = size(); 19859b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta // expand list as necessary 19959b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta if (size == entries.length){ 20059b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta ListMapEntry<K, V>[] tmpEntries = entries; 20159b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta entries = new ListMapEntry[size * 2]; 20259b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta System.arraycopy(tmpEntries, 0, entries, 0, size); 20359b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 20459b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta entries[size] = new ListMapEntry<K, V>(key, value); 20559b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 20659b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta return backingMap.put(key, value); 20759b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// if (key == null) 20859b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// throw new IllegalArgumentException(); 20959b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// 21059b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// // check if entry exists, if yes, overwrite it with new value 21159b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// for (int i = 0; i < entries.size(); i++){ 21259b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// ListMapEntry<K,V> entry = entries.get(i); 21359b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// if (keyEq(entry.key, key)){ 21459b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// V prevValue = entry.value; 21559b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// entry.value = value; 21659b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// return prevValue; 21759b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// } 21859b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// } 21959b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// 22059b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// // add a new entry 22159b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// entries.add(new ListMapEntry<K, V>(key, value)); 22259b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// return null; 22359b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 22459b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 22559b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta public V remove(Object key) { 22659b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta V element = backingMap.remove( (K) key); 22759b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta if (element != null){ 22859b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta // find removed element 22959b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta int size = size() + 1; // includes removed element 23059b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta int removedIndex = -1; 23159b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta for (int i = 0; i < size; i++){ 23259b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta ListMapEntry<K, V> entry = entries[i]; 23359b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta if (keyEq(entry.key, key)){ 23459b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta removedIndex = i; 23559b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta break; 23659b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 23759b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 23859b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta assert removedIndex >= 0; 23959b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 24059b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta size --; 24159b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta for (int i = removedIndex; i < size; i++){ 24259b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta entries[i] = entries[i+1]; 24359b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 24459b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 24559b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta return element; 24659b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// if (key == null) 24759b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// throw new IllegalArgumentException(); 24859b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// 24959b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// for (int i = 0; i < entries.size(); i++){ 25059b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// ListMapEntry<K,V> entry = entries.get(i); 25159b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// if (keyEq(entry.key, key)){ 25259b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// return entries.remove(i).value; 25359b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// } 25459b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// } 25559b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// return null; 25659b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 25759b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 25859b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta public void putAll(Map<? extends K, ? extends V> map) { 25959b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta for (Entry<? extends K, ? extends V> entry : map.entrySet()){ 26059b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta put(entry.getKey(), entry.getValue()); 26159b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 26259b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 26359b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 26459b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// if (map instanceof ListMap){ 26559b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// ListMap<K, V> listMap = (ListMap<K, V>) map; 26659b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// ArrayList<ListMapEntry<K, V>> otherEntries = listMap.entries; 26759b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// for (int i = 0; i < otherEntries.size(); i++){ 26859b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// ListMapEntry<K, V> entry = otherEntries.get(i); 26959b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// put(entry.key, entry.value); 27059b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// } 27159b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// }else{ 27259b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// for (Map.Entry<? extends K, ? extends V> entry : map.entrySet()){ 27359b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// put(entry.getKey(), entry.getValue()); 27459b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// } 27559b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// } 27659b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 27759b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 27859b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta public void clear() { 27959b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta backingMap.clear(); 28059b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// entries.clear(); 28159b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 28259b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 28359b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta @Override 28459b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta public ListMap<K, V> clone(){ 28559b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta ListMap<K, V> clone = new ListMap<K, V>(size()); 28659b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta clone.putAll(this); 28759b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta return clone; 28859b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 28959b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 29059b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta public Set<K> keySet() { 29159b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta return backingMap.keySet(); 29259b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// HashSet<K> keys = new HashSet<K>(); 29359b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// for (int i = 0; i < entries.size(); i++){ 29459b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// ListMapEntry<K,V> entry = entries.get(i); 29559b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// keys.add(entry.key); 29659b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// } 29759b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// return keys; 29859b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 29959b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 30059b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta public Collection<V> values() { 30159b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta return backingMap.values(); 30259b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// ArrayList<V> values = new ArrayList<V>(); 30359b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// for (int i = 0; i < entries.size(); i++){ 30459b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// ListMapEntry<K,V> entry = entries.get(i); 30559b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// values.add(entry.value); 30659b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// } 30759b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// return values; 30859b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 30959b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 31059b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta public Set<Entry<K, V>> entrySet() { 31159b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta return backingMap.entrySet(); 31259b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// HashSet<Entry<K, V>> entryset = new HashSet<Entry<K, V>>(); 31359b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// entryset.addAll(entries); 31459b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// return entryset; 31559b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 31659b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 31759b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta} 318