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

public Class ObjectFloatMap<K>

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

An unordered map where the keys are objects and the values are unboxed floats. Null keys are not allowed. 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
pack-priv transient ObjectFloatMap.Entries<K>
pack-priv transient ObjectFloatMap.Entries<K>
pack-priv transient ObjectFloatMap.Keys<K>
pack-priv transient ObjectFloatMap.Keys<K>
pack-priv K[]
pack-priv float
protected int
mask

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

protected int
shift

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

public int
pack-priv int
pack-priv transient ObjectFloatMap.Values
pack-priv transient ObjectFloatMap.Values
pack-priv float[]

Constructor Summary

AccessConstructor and Description
public
ObjectFloatMap()

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

public
ObjectFloatMap(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
ObjectFloatMap(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
ObjectFloatMap(ObjectFloatMap<? extends K> 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(K 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 ObjectFloatMap.Entries<K>
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 K
findKey(float value)

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

public K
findKey(float value, float epsilon)

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

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

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

public float
getAndIncrement(K 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 ObjectFloatMap.Entries<K>
iterator()

Implements java.lang.Iterable.iterator.

Returns an iterator over elements of type T.

public ObjectFloatMap.Keys<K>
keys()

Returns an iterator for the keys in the map.

pack-priv int
locateKey(K 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(K item)

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

public void
put(K key, float value)

public float
put(K 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
putAll(ObjectFloatMap<? extends K> map)

public void
putMissing(K key, float value)

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

private void
putResize(K key, float value)

Skips checks for existing keys, doesn't increment size.

public float
remove(K 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.

pack-priv final 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(String separator)

public String
toString()

Overrides java.lang.Object.toString.

Returns a string representation of the object.

private String
toString(String separator, boolean braces)

public ObjectFloatMap.Values
values()

Returns an iterator for the values in the map.

Inherited from java.lang.Object:
clonefinalizegetClassnotifynotifyAllwaitwaitwait

Field Detail

entries1back to summary
pack-priv transient ObjectFloatMap.Entries<K> entries1
entries2back to summary
pack-priv transient ObjectFloatMap.Entries<K> entries2
keys1back to summary
pack-priv transient ObjectFloatMap.Keys<K> keys1
keys2back to summary
pack-priv transient ObjectFloatMap.Keys<K> keys2
keyTableback to summary
pack-priv K[] keyTable
loadFactorback to summary
pack-priv 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(Object) 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(Object) 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(Object) is overridden.

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

Constructor Detail

ObjectFloatMapback to summary
public ObjectFloatMap()

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

ObjectFloatMapback to summary
public ObjectFloatMap(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.

ObjectFloatMapback to summary
public ObjectFloatMap(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.

ObjectFloatMapback to summary
public ObjectFloatMap(ObjectFloatMap<? extends K> 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(K 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 ObjectFloatMap.Entries<K> 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 K findKey(float value)

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

Annotations
@Null
findKeyback to summary
public K findKey(float value, float epsilon)

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

Annotations
@Null
getback to summary
public float get(K key, float defaultValue)

Returns the value for the specified 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.

getAndIncrementback to summary
public float getAndIncrement(K 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 ObjectFloatMap.Entries<K> iterator()

Implements java.lang.Iterable.iterator.

Doc from java.lang.Iterable.iterator.

Returns an iterator over elements of type T.

keysback to summary
public ObjectFloatMap.Keys<K> 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 Keys constructor for nested or multithreaded iteration.

locateKeyback to summary
pack-priv int locateKey(K key)

Returns the index of the key if already present, else -(index + 1) for the next empty index. This can be overridden in this pacakge to compare for equality differently than Object#equals(Object).

notEmptyback to summary
public boolean notEmpty()

Returns true if the map has one or more items.

placeback to summary
protected int place(K 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: return item.hashCode() & mask;

putback to summary
public void put(K key, float value)
putback to summary
public float put(K 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(ObjectFloatMap<? extends K> map)
putMissingback to summary
public void putMissing(K key, float value)
putMissingback to summary
public float putMissing(K key, float value, float defaultValue)
putResizeback to summary
private void putResize(K key, float value)

Skips checks for existing keys, doesn't increment size.

removeback to summary
public float remove(K 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
pack-priv final 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(String separator)
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.

toStringback to summary
private String toString(String separator, boolean braces)
valuesback to summary
public ObjectFloatMap.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 Values constructor for nested or multithreaded iteration.

com.badlogic.gdx.utils back to summary

public Class ObjectFloatMap.Entries<K>

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

Field Summary

Modifier and TypeField and Description
pack-priv ObjectFloatMap.Entry<K>
Inherited from com.badlogic.gdx.utils.ObjectFloatMap.MapIterator:
currentIndexhasNextmapnextIndexvalid

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 ObjectFloatMap.Entries<K>
iterator()

Implements java.lang.Iterable.iterator.

Returns an iterator over elements of type T.

public ObjectFloatMap.Entry<K>
next()

Implements java.util.Iterator.next.

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

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

Field Detail

entryback to summary
pack-priv ObjectFloatMap.Entry<K> entry

Constructor Detail

Entriesback to summary
public Entries(ObjectFloatMap<K> 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 ObjectFloatMap.Entries<K> iterator()

Implements java.lang.Iterable.iterator.

Doc from java.lang.Iterable.iterator.

Returns an iterator over elements of type T.

nextback to summary
public ObjectFloatMap.Entry<K> next()

Implements java.util.Iterator.next.

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

com.badlogic.gdx.utils back to summary

public Class ObjectFloatMap.Entry<K>

extends Object
Class Inheritance

Field Summary

Modifier and TypeField and Description
public K
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 K 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 ObjectFloatMap.Keys<K>

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

Field Summary

Inherited from com.badlogic.gdx.utils.ObjectFloatMap.MapIterator:
currentIndexhasNextmapnextIndexvalid

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 ObjectFloatMap.Keys<K>
iterator()

Implements java.lang.Iterable.iterator.

Returns an iterator over elements of type T.

public K
next()

Implements java.util.Iterator.next.

Returns the next element in the iteration.

public Array<K>
toArray()

Returns a new array containing the remaining keys.

public Array<K>
toArray(Array<K> array)

Adds the remaining keys to the array.

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

Constructor Detail

Keysback to summary
public Keys(ObjectFloatMap<K> 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 ObjectFloatMap.Keys<K> iterator()

Implements java.lang.Iterable.iterator.

Doc from java.lang.Iterable.iterator.

Returns an iterator over elements of type T.

nextback to summary
public K next()

Implements java.util.Iterator.next.

Doc from java.util.Iterator.next.

Returns the next element in the iteration.

toArrayback to summary
public Array<K> toArray()

Returns a new array containing the remaining keys.

toArrayback to summary
public Array<K> toArray(Array<K> array)

Adds the remaining keys to the array.

com.badlogic.gdx.utils back to summary

private Class ObjectFloatMap.MapIterator<K>

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

Field Summary

Modifier and TypeField and Description
pack-priv int
public boolean
pack-priv final ObjectFloatMap<K>
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
mapback to summary
pack-priv final ObjectFloatMap<K> map
nextIndexback to summary
pack-priv int nextIndex
validback to summary
pack-priv boolean valid

Constructor Detail

MapIteratorback to summary
public MapIterator(ObjectFloatMap<K> 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 ObjectFloatMap.Values

extends ObjectFloatMap.MapIterator<Object>
Class Inheritance

Field Summary

Inherited from com.badlogic.gdx.utils.ObjectFloatMap.MapIterator:
currentIndexhasNextmapnextIndexvalid

Constructor Summary

AccessConstructor and Description
public

Method Summary

Modifier and TypeMethod and Description
public boolean
public ObjectFloatMap.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.ObjectFloatMap.MapIterator:
findNextIndexremovereset

Constructor Detail

Valuesback to summary
public Values(ObjectFloatMap<?> map)

Method Detail

hasNextback to summary
public boolean hasNext()
iteratorback to summary
public ObjectFloatMap.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.