aboutsummaryrefslogtreecommitdiff
path: root/src/main/java/gtPlusPlus/api/objects/data/ObjMap.java
diff options
context:
space:
mode:
Diffstat (limited to 'src/main/java/gtPlusPlus/api/objects/data/ObjMap.java')
-rw-r--r--src/main/java/gtPlusPlus/api/objects/data/ObjMap.java278
1 files changed, 116 insertions, 162 deletions
diff --git a/src/main/java/gtPlusPlus/api/objects/data/ObjMap.java b/src/main/java/gtPlusPlus/api/objects/data/ObjMap.java
index 49dd70d2b8..1f8a4baa2c 100644
--- a/src/main/java/gtPlusPlus/api/objects/data/ObjMap.java
+++ b/src/main/java/gtPlusPlus/api/objects/data/ObjMap.java
@@ -5,8 +5,7 @@ import java.util.Arrays;
/**
* Object-2-object map based on IntIntMap4a
*/
-public class ObjMap<K, V>
-{
+public class ObjMap<K, V> {
private static final Object FREE_KEY = new Object();
private static final Object REMOVED_KEY = new Object();
@@ -15,6 +14,7 @@ public class ObjMap<K, V>
/** Value for the null key (if inserted into a map) */
private Object m_nullValue;
+
private boolean m_hasNull;
/** Fill factor, must be between (0 and 1) */
@@ -28,159 +28,120 @@ public class ObjMap<K, V>
/** Mask to wrap the actual array pointer */
private int m_mask2;
- public ObjMap( final int size, final float fillFactor )
- {
- if ( fillFactor <= 0 || fillFactor >= 1 )
- throw new IllegalArgumentException( "FillFactor must be in (0, 1)" );
- if ( size <= 0 )
- throw new IllegalArgumentException( "Size must be positive!" );
+ public ObjMap(final int size, final float fillFactor) {
+ if (fillFactor <= 0 || fillFactor >= 1) throw new IllegalArgumentException("FillFactor must be in (0, 1)");
+ if (size <= 0) throw new IllegalArgumentException("Size must be positive!");
final int capacity = arraySize(size, fillFactor);
m_mask = capacity - 1;
m_mask2 = capacity * 2 - 1;
m_fillFactor = fillFactor;
m_data = new Object[capacity * 2];
- Arrays.fill( m_data, FREE_KEY );
+ Arrays.fill(m_data, FREE_KEY);
m_threshold = (int) (capacity * fillFactor);
}
@SuppressWarnings("unchecked")
- public V get( final K key )
- {
- if ( key == null )
- return (V) m_nullValue; //we null it on remove, so safe not to check a flag here
+ public V get(final K key) {
+ if (key == null) return (V) m_nullValue; // we null it on remove, so safe not to check a flag here
int ptr = (key.hashCode() & m_mask) << 1;
- Object k = m_data[ ptr ];
+ Object k = m_data[ptr];
- if ( k == FREE_KEY )
- return null; //end of chain already
- if ( k.equals( key ) ) //we check FREE and REMOVED prior to this call
- return (V) m_data[ ptr + 1 ];
- while ( true )
- {
- ptr = (ptr + 2) & m_mask2; //that's next index
- k = m_data[ ptr ];
- if ( k == FREE_KEY )
- return null;
- if ( k.equals( key ) )
- return (V) m_data[ ptr + 1 ];
+ if (k == FREE_KEY) return null; // end of chain already
+ if (k.equals(key)) // we check FREE and REMOVED prior to this call
+ return (V) m_data[ptr + 1];
+ while (true) {
+ ptr = (ptr + 2) & m_mask2; // that's next index
+ k = m_data[ptr];
+ if (k == FREE_KEY) return null;
+ if (k.equals(key)) return (V) m_data[ptr + 1];
}
}
@SuppressWarnings("unchecked")
- public V put( final K key, final V value )
- {
- if ( key == null )
- return insertNullKey(value);
+ public V put(final K key, final V value) {
+ if (key == null) return insertNullKey(value);
int ptr = getStartIndex(key) << 1;
Object k = m_data[ptr];
- if ( k == FREE_KEY ) //end of chain already
+ if (k == FREE_KEY) // end of chain already
{
- m_data[ ptr ] = key;
- m_data[ ptr + 1 ] = value;
- if ( m_size >= m_threshold )
- rehash( m_data.length * 2 ); //size is set inside
- else
- ++m_size;
+ m_data[ptr] = key;
+ m_data[ptr + 1] = value;
+ if (m_size >= m_threshold) rehash(m_data.length * 2); // size is set inside
+ else ++m_size;
return null;
- }
- else if ( k.equals( key ) ) //we check FREE and REMOVED prior to this call
+ } else if (k.equals(key)) // we check FREE and REMOVED prior to this call
{
- final Object ret = m_data[ ptr + 1 ];
- m_data[ ptr + 1 ] = value;
+ final Object ret = m_data[ptr + 1];
+ m_data[ptr + 1] = value;
return (V) ret;
}
int firstRemoved = -1;
- if ( k == REMOVED_KEY )
- firstRemoved = ptr; //we may find a key later
-
- while ( true )
- {
- ptr = ( ptr + 2 ) & m_mask2; //that's next index calculation
- k = m_data[ ptr ];
- if ( k == FREE_KEY )
- {
- if ( firstRemoved != -1 )
- ptr = firstRemoved;
- m_data[ ptr ] = key;
- m_data[ ptr + 1 ] = value;
- if ( m_size >= m_threshold )
- rehash( m_data.length * 2 ); //size is set inside
- else
- ++m_size;
+ if (k == REMOVED_KEY) firstRemoved = ptr; // we may find a key later
+
+ while (true) {
+ ptr = (ptr + 2) & m_mask2; // that's next index calculation
+ k = m_data[ptr];
+ if (k == FREE_KEY) {
+ if (firstRemoved != -1) ptr = firstRemoved;
+ m_data[ptr] = key;
+ m_data[ptr + 1] = value;
+ if (m_size >= m_threshold) rehash(m_data.length * 2); // size is set inside
+ else ++m_size;
return null;
- }
- else if ( k.equals( key ) )
- {
- final Object ret = m_data[ ptr + 1 ];
- m_data[ ptr + 1 ] = value;
+ } else if (k.equals(key)) {
+ final Object ret = m_data[ptr + 1];
+ m_data[ptr + 1] = value;
return (V) ret;
- }
- else if ( k == REMOVED_KEY )
- {
- if ( firstRemoved == -1 )
- firstRemoved = ptr;
+ } else if (k == REMOVED_KEY) {
+ if (firstRemoved == -1) firstRemoved = ptr;
}
}
}
@SuppressWarnings("unchecked")
- public V remove( final K key )
- {
- if ( key == null )
- return removeNullKey();
+ public V remove(final K key) {
+ if (key == null) return removeNullKey();
int ptr = getStartIndex(key) << 1;
- Object k = m_data[ ptr ];
- if ( k == FREE_KEY )
- return null; //end of chain already
- else if ( k.equals( key ) ) //we check FREE and REMOVED prior to this call
+ Object k = m_data[ptr];
+ if (k == FREE_KEY) return null; // end of chain already
+ else if (k.equals(key)) // we check FREE and REMOVED prior to this call
{
--m_size;
- if ( m_data[ ( ptr + 2 ) & m_mask2 ] == FREE_KEY )
- m_data[ ptr ] = FREE_KEY;
- else
- m_data[ ptr ] = REMOVED_KEY;
- final V ret = (V) m_data[ ptr + 1 ];
- m_data[ ptr + 1 ] = null;
+ if (m_data[(ptr + 2) & m_mask2] == FREE_KEY) m_data[ptr] = FREE_KEY;
+ else m_data[ptr] = REMOVED_KEY;
+ final V ret = (V) m_data[ptr + 1];
+ m_data[ptr + 1] = null;
return ret;
}
- while ( true )
- {
- ptr = ( ptr + 2 ) & m_mask2; //that's next index calculation
- k = m_data[ ptr ];
- if ( k == FREE_KEY )
- return null;
- else if ( k.equals( key ) )
- {
+ while (true) {
+ ptr = (ptr + 2) & m_mask2; // that's next index calculation
+ k = m_data[ptr];
+ if (k == FREE_KEY) return null;
+ else if (k.equals(key)) {
--m_size;
- if ( m_data[ ( ptr + 2 ) & m_mask2 ] == FREE_KEY )
- m_data[ ptr ] = FREE_KEY;
- else
- m_data[ ptr ] = REMOVED_KEY;
- final V ret = (V) m_data[ ptr + 1 ];
- m_data[ ptr + 1 ] = null;
+ if (m_data[(ptr + 2) & m_mask2] == FREE_KEY) m_data[ptr] = FREE_KEY;
+ else m_data[ptr] = REMOVED_KEY;
+ final V ret = (V) m_data[ptr + 1];
+ m_data[ptr + 1] = null;
return ret;
}
}
}
@SuppressWarnings("unchecked")
- private V insertNullKey(final V value)
- {
- if ( m_hasNull )
- {
+ private V insertNullKey(final V value) {
+ if (m_hasNull) {
final Object ret = m_nullValue;
m_nullValue = value;
return (V) ret;
- }
- else
- {
+ } else {
m_nullValue = value;
++m_size;
return null;
@@ -188,98 +149,91 @@ public class ObjMap<K, V>
}
@SuppressWarnings("unchecked")
- private V removeNullKey()
- {
- if ( m_hasNull )
- {
+ private V removeNullKey() {
+ if (m_hasNull) {
final Object ret = m_nullValue;
m_nullValue = null;
m_hasNull = false;
--m_size;
return (V) ret;
- }
- else
- {
+ } else {
return null;
}
}
- public int size()
- {
+ public int size() {
return m_size;
}
@SuppressWarnings("unchecked")
- private void rehash( final int newCapacity )
- {
- m_threshold = (int) (newCapacity/2 * m_fillFactor);
- m_mask = newCapacity/2 - 1;
+ private void rehash(final int newCapacity) {
+ m_threshold = (int) (newCapacity / 2 * m_fillFactor);
+ m_mask = newCapacity / 2 - 1;
m_mask2 = newCapacity - 1;
final int oldCapacity = m_data.length;
final Object[] oldData = m_data;
- m_data = new Object[ newCapacity ];
- Arrays.fill( m_data, FREE_KEY );
+ m_data = new Object[newCapacity];
+ Arrays.fill(m_data, FREE_KEY);
m_size = m_hasNull ? 1 : 0;
- for ( int i = 0; i < oldCapacity; i += 2 ) {
- final Object oldKey = oldData[ i ];
- if( oldKey != FREE_KEY && oldKey != REMOVED_KEY )
- put( (K)oldKey, (V)oldData[ i + 1 ]);
+ for (int i = 0; i < oldCapacity; i += 2) {
+ final Object oldKey = oldData[i];
+ if (oldKey != FREE_KEY && oldKey != REMOVED_KEY) put((K) oldKey, (V) oldData[i + 1]);
}
}
- public int getStartIndex( final Object key )
- {
- //key is not null here
+ public int getStartIndex(final Object key) {
+ // key is not null here
return key.hashCode() & m_mask;
}
-
+
public Object[] values() {
- return m_data;
+ return m_data;
}
-
+
/** Taken from FastUtil implementation */
/** Return the least power of two greater than or equal to the specified value.
- *
- * <p>Note that this function will return 1 when the argument is 0.
- *
- * @param x a long integer smaller than or equal to 2<sup>62</sup>.
- * @return the least power of two greater than or equal to the specified value.
- */
- public static long nextPowerOfTwo( long x ) {
- if ( x == 0 ) return 1;
- x--;
- x |= x >> 1;
- x |= x >> 2;
- x |= x >> 4;
- x |= x >> 8;
- x |= x >> 16;
- return ( x | x >> 32 ) + 1;
- }
+ *
+ * <p>Note that this function will return 1 when the argument is 0.
+ *
+ * @param x a long integer smaller than or equal to 2<sup>62</sup>.
+ * @return the least power of two greater than or equal to the specified value.
+ */
+ public static long nextPowerOfTwo(long x) {
+ if (x == 0) return 1;
+ x--;
+ x |= x >> 1;
+ x |= x >> 2;
+ x |= x >> 4;
+ x |= x >> 8;
+ x |= x >> 16;
+ return (x | x >> 32) + 1;
+ }
/** Returns the least power of two smaller than or equal to 2<sup>30</sup> and larger than or equal to <code>Math.ceil( expected / f )</code>.
- *
- * @param expected the expected number of elements in a hash table.
- * @param f the load factor.
- * @return the minimum possible size for a backing array.
- * @throws IllegalArgumentException if the necessary size is larger than 2<sup>30</sup>.
- */
- public static int arraySize( final int expected, final float f ) {
- final long s = Math.max( 2, nextPowerOfTwo( (long)Math.ceil( expected / f ) ) );
- if ( s > (1 << 30) ) throw new IllegalArgumentException( "Too large (" + expected + " expected elements with load factor " + f + ")" );
- return (int)s;
- }
-
- //taken from FastUtil
+ *
+ * @param expected the expected number of elements in a hash table.
+ * @param f the load factor.
+ * @return the minimum possible size for a backing array.
+ * @throws IllegalArgumentException if the necessary size is larger than 2<sup>30</sup>.
+ */
+ public static int arraySize(final int expected, final float f) {
+ final long s = Math.max(2, nextPowerOfTwo((long) Math.ceil(expected / f)));
+ if (s > (1 << 30))
+ throw new IllegalArgumentException(
+ "Too large (" + expected + " expected elements with load factor " + f + ")");
+ return (int) s;
+ }
+
+ // taken from FastUtil
private static final int INT_PHI = 0x9E3779B9;
- public static int phiMix( final int x ) {
- final int h = x * INT_PHI;
- return h ^ (h >> 16);
-}
-
+ public static int phiMix(final int x) {
+ final int h = x * INT_PHI;
+ return h ^ (h >> 16);
+ }
}
generated by cgit (git 2.46.0) at 2025-03-09 00:52:57 +0000