APIdia Launch Partner
Top Description Inners Fields Constructors Methods
com.badlogic.gdx.utils

public Class IntFloatMap

extends Object
implements Iterable<IntFloatMap.Entry>
Class Inheritance
All Implemented Interfaces
java.lang.Iterable
Imports
java.util.Arrays, .Iterator, .NoSuchElementException

An unordered map where the keys are unboxed ints and values are unboxed floats. No allocation is done except when growing the table size.

This class performs fast contains and remove (typically O(1), worst case O(n) but that is rare in practice). Add may be slightly slower, depending on hash collisions. Hashcodes are rehashed to reduce collisions and the need to resize. Load factors greater than 0.91 greatly increase the chances to resize to the next higher POT size.

Unordered sets and maps are not designed to provide especially fast iteration. Iteration is faster with OrderedSet and OrderedMap.

This implementation uses linear probing with the backward shift algorithm for removal. Hashcodes are rehashed using Fibonacci hashing, instead of the more common power-of-two mask, to better distribute poor hashCodes (see Malte Skarupke's blog post). Linear probing continues to work even when all hashCodes collide, just more slowly.

Authors
Nathan Sweet, Tommy Ettinger

Nested and Inner Type Summary

Modifier and TypeClass and Description
public static class
public static class
public static class
private static class
public static class

Field Summary

Modifier and TypeField and Description
private transient IntFloatMap.Entries
private transient IntFloatMap.Entries
pack-priv boolean
private transient IntFloatMap.Keys
private transient IntFloatMap.Keys
pack-priv int[]
private final float
protected int
mask

A bitmask used to confine hashcodes to the size of the table.

protected int
shift

Used by place(int) to bit shift the upper bits of a long into a usable range (>= 0 and <= mask).

public int
private int
private transient IntFloatMap.Values
private transient IntFloatMap.Values
pack-priv float[]
pack-priv float

Constructor Summary

AccessConstructor and Description
public
IntFloatMap()

Creates a new map with an initial capacity of 51 and a load factor of 0.8.

public
IntFloatMap(int
The backing array size is initialCapacity / loadFactor, increased to the next power of two.
initialCapacity
)

Creates a new map with a load factor of 0.8.

public
IntFloatMap(int
The backing array size is initialCapacity / loadFactor, increased to the next power of two.
initialCapacity
,
float loadFactor)

Creates a new map with the specified initial capacity and load factor.

public
IntFloatMap(IntFloatMap map)

Creates a new map identical to the specified map.

Method Summary

Modifier and TypeMethod and Description
public void
clear(int maximumCapacity)

Clears the map and reduces the size of the backing arrays to be the specified capacity / loadFactor, if they are larger.

public void
public boolean
containsKey(int key)

public boolean
containsValue(float value)

Returns true if the specified value is in the map.

public boolean
containsValue(float value, float epsilon)

Returns true if the specified value is in the map.

public void
ensureCapacity(int additionalCapacity)

Increases the size of the backing array to accommodate the specified number of additional items / loadFactor.

public IntFloatMap.Entries
entries()

Returns an iterator for the entries in the map.

public boolean
equals(Object obj)

Overrides java.lang.Object.equals.

Indicates whether some other object is "equal to" this one.

public int
findKey(float value, int notFound)

Returns the key for the specified value, or notFound if it is not in the map.

public int
findKey(float value, float epsilon, int notFound)

Returns the key for the specified value, or notFound if it is not in the map.

public float
get(int key, float
Float#NaN can be used for a value unlikely to be in the map.
defaultValue
)

public float
getAndIncrement(int key, float defaultValue, float increment)

Returns the key's current value and increments the stored value.

public int
hashCode()

Overrides java.lang.Object.hashCode.

Returns a hash code value for this object.

public boolean
isEmpty()

Returns true if the map is empty.

public Iterator<IntFloatMap.Entry>
iterator()

Implements java.lang.Iterable.iterator.

Returns an iterator over elements of type T.

public IntFloatMap.Keys
keys()

Returns an iterator for the keys in the map.

private int
locateKey(int key)

Returns the index of the key if already present, else -(index + 1) for the next empty index.

public boolean
notEmpty()

Returns true if the map has one or more items.

protected int
place(int item)

Returns an index >= 0 and <= mask for the specified item.

public void
put(int key, float value)

public float
put(int key, float value, float
Float#NaN can be used for a value unlikely to be in the map.
defaultValue
)

Returns the old value associated with the specified key, or the specified default value.

public void
public void
putMissing(int key, float value)

public float
putMissing(int key, float value, float defaultValue)

private void
putResize(int key, float value)

Skips checks for existing keys, doesn't increment size, doesn't need to handle key 0.

public float
remove(int key, float
Float#NaN can be used for a value unlikely to be in the map.
defaultValue
)

Returns the value for the removed key, or the default value if the key is not in the map.

private void
resize(int newSize)

public void
shrink(int maximumCapacity)

Reduces the size of the backing arrays to be the specified capacity / loadFactor, or less.

public String
toString()

Overrides java.lang.Object.toString.

Returns a string representation of the object.

public IntFloatMap.Values
values()

Returns an iterator for the values in the map.

Inherited from java.lang.Object:
clonefinalizegetClassnotifynotifyAllwaitwaitwait

Field Detail

entries1back to summary
private transient IntFloatMap.Entries entries1
entries2back to summary
private transient IntFloatMap.Entries entries2
hasZeroValueback to summary
pack-priv boolean hasZeroValue
keys1back to summary
private transient IntFloatMap.Keys keys1
keys2back to summary
private transient IntFloatMap.Keys keys2
keyTableback to summary
pack-priv int[] keyTable
loadFactorback to summary
private final float loadFactor
maskback to summary
protected int mask

A bitmask used to confine hashcodes to the size of the table. Must be all 1 bits in its low positions, ie a power of two minus 1. If place(int) is overridden, this can be used instead of shift to isolate usable bits of a hash.

shiftback to summary
protected int shift

Used by place(int) to bit shift the upper bits of a long into a usable range (>= 0 and <= mask). The shift can be negative, which is convenient to match the number of bits in mask: if mask is a 7-bit number, a shift of -7 shifts the upper 7 bits into the lowest 7 positions. This class sets the shift > 32 and < 64, which if used with an int will still move the upper bits of an int to the lower bits due to Java's implicit modulus on shifts.

mask can also be used to mask the low bits of a number, which may be faster for some hashcodes, if place(int) is overridden.

sizeback to summary
public int size
thresholdback to summary
private int threshold
values1back to summary
private transient IntFloatMap.Values values1
values2back to summary
private transient IntFloatMap.Values values2
valueTableback to summary
pack-priv float[] valueTable
zeroValueback to summary
pack-priv float zeroValue

Constructor Detail

IntFloatMapback to summary
public IntFloatMap()

Creates a new map with an initial capacity of 51 and a load factor of 0.8.

IntFloatMapback to summary
public IntFloatMap(int initialCapacity)

Creates a new map with a load factor of 0.8.

Parameters
initialCapacity:int

The backing array size is initialCapacity / loadFactor, increased to the next power of two.

IntFloatMapback to summary
public IntFloatMap(int initialCapacity, float loadFactor)

Creates a new map with the specified initial capacity and load factor. This map will hold initialCapacity items before growing the backing table.

Parameters
initialCapacity:int

The backing array size is initialCapacity / loadFactor, increased to the next power of two.

IntFloatMapback to summary
public IntFloatMap(IntFloatMap map)

Creates a new map identical to the specified map.

Method Detail

clearback to summary
public void clear(int maximumCapacity)

Clears the map and reduces the size of the backing arrays to be the specified capacity / loadFactor, if they are larger.

clearback to summary
public void clear()
containsKeyback to summary
public boolean containsKey(int key)
containsValueback to summary
public boolean containsValue(float value)

Returns true if the specified value is in the map. Note this traverses the entire map and compares every value, which may be an expensive operation.

containsValueback to summary
public boolean containsValue(float value, float epsilon)

Returns true if the specified value is in the map. Note this traverses the entire map and compares every value, which may be an expensive operation.

ensureCapacityback to summary
public void ensureCapacity(int additionalCapacity)

Increases the size of the backing array to accommodate the specified number of additional items / loadFactor. Useful before adding many items to avoid multiple backing array resizes.

entriesback to summary
public IntFloatMap.Entries entries()

Returns an iterator for the entries in the map. Remove is supported.

If Collections#allocateIterators is false, the same iterator instance is returned each time this method is called. Use the Entries constructor for nested or multithreaded iteration.

equalsback to summary
public boolean equals(Object obj)

Overrides java.lang.Object.equals.

Doc from java.lang.Object.equals.

Indicates whether some other object is "equal to" this one.

The equals method implements an equivalence relation on non-null object references:

  • It is reflexive: for any non-null reference value x, x.equals(x) should return true.
  • It is symmetric: for any non-null reference values x and y, x.equals(y) should return true if and only if y.equals(x) returns true.
  • It is transitive: for any non-null reference values x, y, and z, if x.equals(y) returns true and y.equals(z) returns true, then x.equals(z) should return true.
  • It is consistent: for any non-null reference values x and y, multiple invocations of x.equals(y) consistently return true or consistently return false, provided no information used in equals comparisons on the objects is modified.
  • For any non-null reference value x, x.equals(null) should return false.

An equivalence relation partitions the elements it operates on into equivalence classes; all the members of an equivalence class are equal to each other. Members of an equivalence class are substitutable for each other, at least for some purposes.

findKeyback to summary
public int findKey(float value, int notFound)

Returns the key for the specified value, or notFound if it is not in the map. Note this traverses the entire map and compares every value, which may be an expensive operation.

findKeyback to summary
public int findKey(float value, float epsilon, int notFound)

Returns the key for the specified value, or notFound if it is not in the map. Note this traverses the entire map and compares every value, which may be an expensive operation.

getback to summary
public float get(int key, float defaultValue)
Parameters
defaultValue:float

Float#NaN can be used for a value unlikely to be in the map.

getAndIncrementback to summary
public float getAndIncrement(int key, float defaultValue, float increment)

Returns the key's current value and increments the stored value. If the key is not in the map, defaultValue + increment is put into the map and defaultValue is returned.

hashCodeback to summary
public int hashCode()

Overrides java.lang.Object.hashCode.

Doc from java.lang.Object.hashCode.

Returns a hash code value for this object. This method is supported for the benefit of hash tables such as those provided by java.util.HashMap.

The general contract of hashCode is:

  • Whenever it is invoked on the same object more than once during an execution of a Java application, the hashCode method must consistently return the same integer, provided no information used in equals comparisons on the object is modified. This integer need not remain consistent from one execution of an application to another execution of the same application.
  • If two objects are equal according to the equals method, then calling the hashCode method on each of the two objects must produce the same integer result.
  • It is not required that if two objects are unequal according to the equals method, then calling the hashCode method on each of the two objects must produce distinct integer results. However, the programmer should be aware that producing distinct integer results for unequal objects may improve the performance of hash tables.
isEmptyback to summary
public boolean isEmpty()

Returns true if the map is empty.

iteratorback to summary
public Iterator<IntFloatMap.Entry> iterator()

Implements java.lang.Iterable.iterator.

Doc from java.lang.Iterable.iterator.

Returns an iterator over elements of type T.

keysback to summary
public IntFloatMap.Keys keys()

Returns an iterator for the keys in the map. Remove is supported.

If Collections#allocateIterators is false, the same iterator instance is returned each time this method is called. Use the Entries constructor for nested or multithreaded iteration.

locateKeyback to summary
private int locateKey(int key)

Returns the index of the key if already present, else -(index + 1) for the next empty index.

notEmptyback to summary
public boolean notEmpty()

Returns true if the map has one or more items.

placeback to summary
protected int place(int item)

Returns an index >= 0 and <= mask for the specified item.

The default implementation uses Fibonacci hashing on the item's Object#hashCode(): the hashcode is multiplied by a long constant (2 to the 64th, divided by the golden ratio) then the uppermost bits are shifted into the lowest positions to obtain an index in the desired range. Multiplication by a long may be slower than int (eg on GWT) but greatly improves rehashing, allowing even very poor hashcodes, such as those that only differ in their upper bits, to be used without high collision rates. Fibonacci hashing has increased collision rates when all or most hashcodes are multiples of larger Fibonacci numbers (see Malte Skarupke's blog post).

This method can be overridden to customizing hashing. This may be useful eg in the unlikely event that most hashcodes are Fibonacci numbers, if keys provide poor or incorrect hashcodes, or to simplify hashing if keys provide high quality hashcodes and don't need Fibonacci hashing.

putback to summary
public void put(int key, float value)
putback to summary
public float put(int key, float value, float defaultValue)

Returns the old value associated with the specified key, or the specified default value.

Parameters
defaultValue:float

Float#NaN can be used for a value unlikely to be in the map.

putAllback to summary
public void putAll(IntFloatMap map)
putMissingback to summary
public void putMissing(int key, float value)
putMissingback to summary
public float putMissing(int key, float value, float defaultValue)
putResizeback to summary
private void putResize(int key, float value)

Skips checks for existing keys, doesn't increment size, doesn't need to handle key 0.

removeback to summary
public float remove(int key, float defaultValue)

Returns the value for the removed key, or the default value if the key is not in the map.

Parameters
defaultValue:float

Float#NaN can be used for a value unlikely to be in the map.

resizeback to summary
private void resize(int newSize)
shrinkback to summary
public void shrink(int maximumCapacity)

Reduces the size of the backing arrays to be the specified capacity / loadFactor, or less. If the capacity is already less, nothing is done. If the map contains more items than the specified capacity, the next highest power of two capacity is used instead.

toStringback to summary
public String toString()

Overrides java.lang.Object.toString.

Doc from java.lang.Object.toString.

Returns a string representation of the object. Satisfying this method's contract implies a non-null result must be returned.

valuesback to summary
public IntFloatMap.Values values()

Returns an iterator for the values in the map. Remove is supported.

If Collections#allocateIterators is false, the same iterator instance is returned each time this method is called. Use the Entries constructor for nested or multithreaded iteration.

com.badlogic.gdx.utils back to summary

public Class IntFloatMap.Entries

extends MapIterator
implements Iterable<IntFloatMap.Entry>, Iterator<IntFloatMap.Entry>
Class Inheritance
All Implemented Interfaces
java.util.Iterator, java.lang.Iterable

Field Summary

Modifier and TypeField and Description
private final IntFloatMap.Entry
Inherited from com.badlogic.gdx.utils.IntFloatMap.MapIterator:
currentIndexhasNextINDEX_ZEROmapnextIndexvalid

Constructor Summary

AccessConstructor and Description
public

Method Summary

Modifier and TypeMethod and Description
public boolean
hasNext()

Implements java.util.Iterator.hasNext.

Returns true if the iteration has more elements.

public Iterator<IntFloatMap.Entry>
iterator()

Implements java.lang.Iterable.iterator.

Returns an iterator over elements of type T.

public IntFloatMap.Entry
next()

Implements java.util.Iterator.next.

Note the same entry instance is returned each time this method is called.

public void
remove()

Overrides com.badlogic.gdx.utils.IntFloatMap.MapIterator.remove.

Overrides default java.util.Iterator.remove.

Removes from the underlying collection the last element returned by this iterator (optional operation).

Inherited from com.badlogic.gdx.utils.IntFloatMap.MapIterator:
findNextIndexreset

Field Detail

entryback to summary
private final IntFloatMap.Entry entry

Constructor Detail

Entriesback to summary
public Entries(IntFloatMap map)

Method Detail

hasNextback to summary
public boolean hasNext()

Implements java.util.Iterator.hasNext.

Doc from java.util.Iterator.hasNext.

Returns true if the iteration has more elements. (In other words, returns true if next would return an element rather than throwing an exception.)

iteratorback to summary
public Iterator<IntFloatMap.Entry> iterator()

Implements java.lang.Iterable.iterator.

Doc from java.lang.Iterable.iterator.

Returns an iterator over elements of type T.

nextback to summary
public IntFloatMap.Entry next()

Implements java.util.Iterator.next.

Note the same entry instance is returned each time this method is called.

removeback to summary
public void remove()

Overrides com.badlogic.gdx.utils.IntFloatMap.MapIterator.remove.

Overrides default java.util.Iterator.remove.

Doc from java.util.Iterator.remove.

Removes from the underlying collection the last element returned by this iterator (optional operation). This method can be called only once per call to next.

The behavior of an iterator is unspecified if the underlying collection is modified while the iteration is in progress in any way other than by calling this method, unless an overriding class has specified a concurrent modification policy.

The behavior of an iterator is unspecified if this method is called after a call to the forEachRemaining method.

com.badlogic.gdx.utils back to summary

public Class IntFloatMap.Entry

extends Object
Class Inheritance

Field Summary

Modifier and TypeField and Description
public int
public float

Constructor Summary

AccessConstructor and Description
public

Method Summary

Modifier and TypeMethod and Description
public String
toString()

Overrides java.lang.Object.toString.

Returns a string representation of the object.

Inherited from java.lang.Object:
cloneequalsfinalizegetClasshashCodenotifynotifyAllwaitwaitwait

Field Detail

keyback to summary
public int key
valueback to summary
public float value

Constructor Detail

Entryback to summary
public Entry()

Method Detail

toStringback to summary
public String toString()

Overrides java.lang.Object.toString.

Doc from java.lang.Object.toString.

Returns a string representation of the object. Satisfying this method's contract implies a non-null result must be returned.

com.badlogic.gdx.utils back to summary

public Class IntFloatMap.Keys

extends MapIterator
Class Inheritance

Field Summary

Inherited from com.badlogic.gdx.utils.IntFloatMap.MapIterator:
currentIndexhasNextINDEX_ZEROmapnextIndexvalid

Constructor Summary

AccessConstructor and Description
public

Method Summary

Modifier and TypeMethod and Description
public int
next()

public IntArray
toArray()

Returns a new array containing the remaining keys.

public IntArray
toArray(IntArray array)

Adds the remaining values to the specified array.

Inherited from com.badlogic.gdx.utils.IntFloatMap.MapIterator:
findNextIndexremovereset

Constructor Detail

Keysback to summary
public Keys(IntFloatMap map)

Method Detail

nextback to summary
public int next()
toArrayback to summary
public IntArray toArray()

Returns a new array containing the remaining keys.

toArrayback to summary
public IntArray toArray(IntArray array)

Adds the remaining values to the specified array.

com.badlogic.gdx.utils back to summary

private Class IntFloatMap.MapIterator

extends Object
Class Inheritance
Known Direct Subclasses
com.badlogic.gdx.utils.IntFloatMap.Entries, com.badlogic.gdx.utils.IntFloatMap.Values, com.badlogic.gdx.utils.IntFloatMap.Keys

Field Summary

Modifier and TypeField and Description
pack-priv int
public boolean
private static final int
pack-priv static final int
pack-priv final IntFloatMap
pack-priv int
pack-priv boolean

Constructor Summary

AccessConstructor and Description
public

Method Summary

Modifier and TypeMethod and Description
pack-priv void
public void
public void
Inherited from java.lang.Object:
cloneequalsfinalizegetClasshashCodenotifynotifyAlltoStringwaitwaitwait

Field Detail

currentIndexback to summary
pack-priv int currentIndex
hasNextback to summary
public boolean hasNext
INDEX_ILLEGALback to summary
private static final int INDEX_ILLEGAL
INDEX_ZEROback to summary
pack-priv static final int INDEX_ZERO
mapback to summary
pack-priv final IntFloatMap map
nextIndexback to summary
pack-priv int nextIndex
validback to summary
pack-priv boolean valid

Constructor Detail

MapIteratorback to summary
public MapIterator(IntFloatMap map)

Method Detail

findNextIndexback to summary
pack-priv void findNextIndex()
removeback to summary
public void remove()
resetback to summary
public void reset()
com.badlogic.gdx.utils back to summary

public Class IntFloatMap.Values

extends MapIterator
Class Inheritance

Field Summary

Inherited from com.badlogic.gdx.utils.IntFloatMap.MapIterator:
currentIndexhasNextINDEX_ZEROmapnextIndexvalid

Constructor Summary

AccessConstructor and Description
public

Method Summary

Modifier and TypeMethod and Description
public boolean
public IntFloatMap.Values
public float
next()

public FloatArray
toArray()

Returns a new array containing the remaining values.

public FloatArray
toArray(FloatArray array)

Adds the remaining values to the specified array.

Inherited from com.badlogic.gdx.utils.IntFloatMap.MapIterator:
findNextIndexremovereset

Constructor Detail

Valuesback to summary
public Values(IntFloatMap map)

Method Detail

hasNextback to summary
public boolean hasNext()
iteratorback to summary
public IntFloatMap.Values iterator()
nextback to summary
public float next()
toArrayback to summary
public FloatArray toArray()

Returns a new array containing the remaining values.

toArrayback to summary
public FloatArray toArray(FloatArray array)

Adds the remaining values to the specified array.