diff options
Diffstat (limited to 'engine/src/core/com/jme3/util/IntMap.java')
| -rw-r--r-- | engine/src/core/com/jme3/util/IntMap.java | 308 |
1 files changed, 308 insertions, 0 deletions
diff --git a/engine/src/core/com/jme3/util/IntMap.java b/engine/src/core/com/jme3/util/IntMap.java new file mode 100644 index 0000000..edf659b --- /dev/null +++ b/engine/src/core/com/jme3/util/IntMap.java @@ -0,0 +1,308 @@ +/* + * Copyright (c) 2009-2010 jMonkeyEngine + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * * Neither the name of 'jMonkeyEngine' nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED + * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF + * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING + * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +package com.jme3.util; + +import com.jme3.util.IntMap.Entry; +import java.util.Iterator; +import java.util.Map; + +/** + * Similar to a {@link Map} except that ints are used as keys. + * + * Taken from <a href="http://code.google.com/p/skorpios/">http://code.google.com/p/skorpios/</a> + * + * @author Nate + */ +public final class IntMap<T> implements Iterable<Entry<T>>, Cloneable { + + private final IntMapIterator iterator = new IntMapIterator(); + + private Entry[] table; + private final float loadFactor; + private int size, mask, capacity, threshold; + + public IntMap() { + this(16, 0.75f); + } + + public IntMap(int initialCapacity) { + this(initialCapacity, 0.75f); + } + + public IntMap(int initialCapacity, float loadFactor) { + if (initialCapacity > 1 << 30){ + throw new IllegalArgumentException("initialCapacity is too large."); + } + if (initialCapacity < 0){ + throw new IllegalArgumentException("initialCapacity must be greater than zero."); + } + if (loadFactor <= 0){ + throw new IllegalArgumentException("initialCapacity must be greater than zero."); + } + capacity = 1; + while (capacity < initialCapacity){ + capacity <<= 1; + } + this.loadFactor = loadFactor; + this.threshold = (int) (capacity * loadFactor); + this.table = new Entry[capacity]; + this.mask = capacity - 1; + } + + @Override + public IntMap<T> clone(){ + try{ + IntMap<T> clone = (IntMap<T>) super.clone(); + Entry[] newTable = new Entry[table.length]; + for (int i = table.length - 1; i >= 0; i--){ + if (table[i] != null) + newTable[i] = table[i].clone(); + } + clone.table = newTable; + return clone; + }catch (CloneNotSupportedException ex){ + } + return null; + } + + public boolean containsValue(Object value) { + Entry[] table = this.table; + for (int i = table.length; i-- > 0;){ + for (Entry e = table[i]; e != null; e = e.next){ + if (e.value.equals(value)){ + return true; + } + } + } + return false; + } + + public boolean containsKey(int key) { + int index = ((int) key) & mask; + for (Entry e = table[index]; e != null; e = e.next){ + if (e.key == key){ + return true; + } + } + return false; + } + + public T get(int key) { + int index = key & mask; + for (Entry e = table[index]; e != null; e = e.next){ + if (e.key == key){ + return (T) e.value; + } + } + return null; + } + + public T put(int key, T value) { + int index = key & mask; + // Check if key already exists. + for (Entry e = table[index]; e != null; e = e.next){ + if (e.key != key){ + continue; + } + Object oldValue = e.value; + e.value = value; + return (T) oldValue; + } + table[index] = new Entry(key, value, table[index]); + if (size++ >= threshold){ + // Rehash. + int newCapacity = 2 * capacity; + Entry[] newTable = new Entry[newCapacity]; + Entry[] src = table; + int bucketmask = newCapacity - 1; + for (int j = 0; j < src.length; j++){ + Entry e = src[j]; + if (e != null){ + src[j] = null; + do{ + Entry next = e.next; + index = e.key & bucketmask; + e.next = newTable[index]; + newTable[index] = e; + e = next; + }while (e != null); + } + } + table = newTable; + capacity = newCapacity; + threshold = (int) (newCapacity * loadFactor); + mask = capacity - 1; + } + return null; + } + + public T remove(int key) { + int index = key & mask; + Entry prev = table[index]; + Entry e = prev; + while (e != null){ + Entry next = e.next; + if (e.key == key){ + size--; + if (prev == e){ + table[index] = next; + }else{ + prev.next = next; + } + return (T) e.value; + } + prev = e; + e = next; + } + return null; + } + + public int size() { + return size; + } + + public void clear() { + Entry[] table = this.table; + for (int index = table.length; --index >= 0;){ + table[index] = null; + } + size = 0; + } + + public Iterator<Entry<T>> iterator() { + iterator.beginUse(); + return iterator; + } + + final class IntMapIterator implements Iterator<Entry<T>> { + + /** + * Current entry. + */ + private Entry cur; + + /** + * Entry in the table + */ + private int idx = 0; + + /** + * Element in the entry + */ + private int el = 0; + + public IntMapIterator() { + } + + public void beginUse(){ + cur = table[0]; + idx = 0; + el = 0; + } + + public boolean hasNext() { + return el < size; + } + + public Entry next() { + if (el >= size) + throw new IllegalStateException("No more elements!"); + + if (cur != null){ + Entry e = cur; + cur = cur.next; + el++; + return e; + } +// if (cur != null && cur.next != null){ + // if we have a current entry, continue to the next entry in the list +// cur = cur.next; +// el++; +// return cur; +// } + + do { + // either we exhausted the current entry list, or + // the entry was null. find another non-null entry. + cur = table[++idx]; + } while (cur == null); + + Entry e = cur; + cur = cur.next; + el ++; + + return e; + } + + public void remove() { + } + + } + + public static final class Entry<T> implements Cloneable { + + final int key; + T value; + Entry next; + + Entry(int k, T v, Entry n) { + key = k; + value = v; + next = n; + } + + public int getKey(){ + return key; + } + + public T getValue(){ + return value; + } + + @Override + public String toString(){ + return key + " => " + value; + } + + @Override + public Entry<T> clone(){ + try{ + Entry<T> clone = (Entry<T>) super.clone(); + clone.next = next != null ? next.clone() : null; + return clone; + }catch (CloneNotSupportedException ex){ + } + return null; + } + } +} |