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 com.jme3.util.IntMap.Entry; 3659b2e6871c65f58fdad78cd7229c292f6a177578Scott Bartaimport java.util.Iterator; 3759b2e6871c65f58fdad78cd7229c292f6a177578Scott Bartaimport java.util.Map; 3859b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 3959b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta/** 4059b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta * Similar to a {@link Map} except that ints are used as keys. 4159b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta * 4259b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta * Taken from <a href="http://code.google.com/p/skorpios/">http://code.google.com/p/skorpios/</a> 4359b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta * 4459b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta * @author Nate 4559b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta */ 4659b2e6871c65f58fdad78cd7229c292f6a177578Scott Bartapublic final class IntMap<T> implements Iterable<Entry<T>>, Cloneable { 4759b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 4859b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta private Entry[] table; 4959b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta private final float loadFactor; 5059b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta private int size, mask, capacity, threshold; 5159b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 5259b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta public IntMap() { 5359b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta this(16, 0.75f); 5459b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 5559b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 5659b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta public IntMap(int initialCapacity) { 5759b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta this(initialCapacity, 0.75f); 5859b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 5959b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 6059b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta public IntMap(int initialCapacity, float loadFactor) { 6159b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta if (initialCapacity > 1 << 30){ 6259b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta throw new IllegalArgumentException("initialCapacity is too large."); 6359b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 6459b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta if (initialCapacity < 0){ 6559b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta throw new IllegalArgumentException("initialCapacity must be greater than zero."); 6659b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 6759b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta if (loadFactor <= 0){ 6859b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta throw new IllegalArgumentException("initialCapacity must be greater than zero."); 6959b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 7059b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta capacity = 1; 7159b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta while (capacity < initialCapacity){ 7259b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta capacity <<= 1; 7359b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 7459b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta this.loadFactor = loadFactor; 7559b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta this.threshold = (int) (capacity * loadFactor); 7659b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta this.table = new Entry[capacity]; 7759b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta this.mask = capacity - 1; 7859b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 7959b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 8059b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta @Override 8159b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta public IntMap<T> clone(){ 8259b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta try{ 8359b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta IntMap<T> clone = (IntMap<T>) super.clone(); 8459b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta Entry[] newTable = new Entry[table.length]; 8559b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta for (int i = table.length - 1; i >= 0; i--){ 8659b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta if (table[i] != null) 8759b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta newTable[i] = table[i].clone(); 8859b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 8959b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta clone.table = newTable; 9059b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta return clone; 9159b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta }catch (CloneNotSupportedException ex){ 9259b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 9359b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta return null; 9459b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 9559b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 9659b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta public boolean containsValue(Object value) { 9759b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta Entry[] table = this.table; 9859b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta for (int i = table.length; i-- > 0;){ 9959b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta for (Entry e = table[i]; e != null; e = e.next){ 10059b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta if (e.value.equals(value)){ 10159b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta return true; 10259b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 10359b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 10459b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 10559b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta return false; 10659b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 10759b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 10859b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta public boolean containsKey(int key) { 10959b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta int index = ((int) key) & mask; 11059b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta for (Entry e = table[index]; e != null; e = e.next){ 11159b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta if (e.key == key){ 11259b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta return true; 11359b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 11459b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 11559b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta return false; 11659b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 11759b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 11859b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta public T get(int key) { 11959b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta int index = key & mask; 12059b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta for (Entry e = table[index]; e != null; e = e.next){ 12159b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta if (e.key == key){ 12259b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta return (T) e.value; 12359b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 12459b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 12559b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta return null; 12659b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 12759b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 12859b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta public T put(int key, T value) { 12959b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta int index = key & mask; 13059b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta // Check if key already exists. 13159b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta for (Entry e = table[index]; e != null; e = e.next){ 13259b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta if (e.key != key){ 13359b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta continue; 13459b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 13559b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta Object oldValue = e.value; 13659b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta e.value = value; 13759b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta return (T) oldValue; 13859b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 13959b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta table[index] = new Entry(key, value, table[index]); 14059b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta if (size++ >= threshold){ 14159b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta // Rehash. 14259b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta int newCapacity = 2 * capacity; 14359b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta Entry[] newTable = new Entry[newCapacity]; 14459b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta Entry[] src = table; 14559b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta int bucketmask = newCapacity - 1; 14659b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta for (int j = 0; j < src.length; j++){ 14759b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta Entry e = src[j]; 14859b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta if (e != null){ 14959b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta src[j] = null; 15059b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta do{ 15159b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta Entry next = e.next; 15259b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta index = e.key & bucketmask; 15359b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta e.next = newTable[index]; 15459b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta newTable[index] = e; 15559b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta e = next; 15659b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta }while (e != null); 15759b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 15859b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 15959b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta table = newTable; 16059b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta capacity = newCapacity; 16159b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta threshold = (int) (newCapacity * loadFactor); 16259b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta mask = capacity - 1; 16359b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 16459b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta return null; 16559b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 16659b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 16759b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta public T remove(int key) { 16859b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta int index = key & mask; 16959b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta Entry prev = table[index]; 17059b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta Entry e = prev; 17159b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta while (e != null){ 17259b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta Entry next = e.next; 17359b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta if (e.key == key){ 17459b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta size--; 17559b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta if (prev == e){ 17659b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta table[index] = next; 17759b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta }else{ 17859b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta prev.next = next; 17959b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 18059b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta return (T) e.value; 18159b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 18259b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta prev = e; 18359b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta e = next; 18459b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 18559b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta return null; 18659b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 18759b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 18859b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta public int size() { 18959b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta return size; 19059b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 19159b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 19259b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta public void clear() { 19359b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta Entry[] table = this.table; 19459b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta for (int index = table.length; --index >= 0;){ 19559b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta table[index] = null; 19659b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 19759b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta size = 0; 19859b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 19959b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 20059b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta public Iterator<Entry<T>> iterator() { 201a6b44658eb1c55295f132a36233a11aa2bd8f9cfScott Barta IntMapIterator it = new IntMapIterator(); 202a6b44658eb1c55295f132a36233a11aa2bd8f9cfScott Barta it.beginUse(); 203a6b44658eb1c55295f132a36233a11aa2bd8f9cfScott Barta return it; 20459b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 20559b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 20659b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta final class IntMapIterator implements Iterator<Entry<T>> { 20759b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 20859b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta /** 20959b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta * Current entry. 21059b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta */ 21159b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta private Entry cur; 21259b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 21359b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta /** 21459b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta * Entry in the table 21559b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta */ 21659b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta private int idx = 0; 21759b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 21859b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta /** 21959b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta * Element in the entry 22059b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta */ 22159b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta private int el = 0; 22259b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 22359b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta public IntMapIterator() { 22459b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 22559b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 22659b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta public void beginUse(){ 22759b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta cur = table[0]; 22859b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta idx = 0; 22959b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta el = 0; 23059b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 23159b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 23259b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta public boolean hasNext() { 23359b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta return el < size; 23459b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 23559b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 23659b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta public Entry next() { 23759b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta if (el >= size) 23859b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta throw new IllegalStateException("No more elements!"); 23959b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 24059b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta if (cur != null){ 24159b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta Entry e = cur; 24259b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta cur = cur.next; 24359b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta el++; 24459b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta return e; 24559b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 24659b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// if (cur != null && cur.next != null){ 24759b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta // if we have a current entry, continue to the next entry in the list 24859b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// cur = cur.next; 24959b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// el++; 25059b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// return cur; 25159b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta// } 25259b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 25359b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta do { 25459b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta // either we exhausted the current entry list, or 25559b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta // the entry was null. find another non-null entry. 25659b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta cur = table[++idx]; 25759b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } while (cur == null); 25859b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 25959b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta Entry e = cur; 26059b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta cur = cur.next; 26159b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta el ++; 26259b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 26359b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta return e; 26459b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 26559b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 26659b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta public void remove() { 26759b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 26859b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 26959b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 27059b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 27159b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta public static final class Entry<T> implements Cloneable { 27259b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 27359b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta final int key; 27459b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta T value; 27559b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta Entry next; 27659b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 27759b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta Entry(int k, T v, Entry n) { 27859b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta key = k; 27959b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta value = v; 28059b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta next = n; 28159b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 28259b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 28359b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta public int getKey(){ 28459b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta return key; 28559b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 28659b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 28759b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta public T getValue(){ 28859b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta return value; 28959b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 29059b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 29159b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta @Override 29259b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta public String toString(){ 29359b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta return key + " => " + value; 29459b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 29559b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta 29659b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta @Override 29759b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta public Entry<T> clone(){ 29859b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta try{ 29959b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta Entry<T> clone = (Entry<T>) super.clone(); 30059b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta clone.next = next != null ? next.clone() : null; 30159b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta return clone; 30259b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta }catch (CloneNotSupportedException ex){ 30359b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 30459b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta return null; 30559b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 30659b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta } 30759b2e6871c65f58fdad78cd7229c292f6a177578Scott Barta} 308