engine/src/core/com/jme3/util/IntMap.java - platform/external/jmonkeyengine - Git at Google

 /*
  * 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;
         }
     }
 }
	/*
	* 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;
	}
	}
	}