An ObjectMap that also stores keys in an Array using the insertion order. Null keys are not allowed. No allocation is done except when growing the table size.

Iteration over the entries(), keys(), and values() is ordered and faster than an unordered map. Keys can also be accessed and the order changed using orderedKeys(). There is some additional overhead for put and remove. When used for faster iteration versus ObjectMap and the order does not actually matter, copying during remove can be greatly reduced by setting Array#ordered to false for OrderedMap#orderedKeys().

This class performs fast contains (typically O(1), worst case O(n) but that is rare in practice). Remove is somewhat slower due to orderedKeys(). 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.

Nested and Inner Type Summary

Modifier and Type	Class and Description
public static class	OrderedMap.OrderedMapEntries<K, V>
public static class	OrderedMap.OrderedMapKeys<K>
public static class	OrderedMap.OrderedMapValues<V>

Field Summary

Modifier and Type	Field and Description
pack-priv final Array<K>	keys

Inherited from com.badlogic.gdx.utils.ObjectMap:: dummy entries1 entries2 keys1 keys2 keyTable loadFactor mask shift size threshold values1 values2 valueTable

Constructor Summary

Access	Constructor and Description
public	OrderedMap() Creates a new map with an initial capacity of 51 and a load factor of 0.8.
public	OrderedMap(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	OrderedMap(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	OrderedMap(OrderedMap<? extends K, ? extends V> map) Creates a new map containing the items in the specified map.

Method Summary

Modifier and Type	Method and Description
public boolean	Returns: true if `before` was removed and `after` was added, false otherwise alter(K a key that must be present for this to succeed before, K a key that must not be in this map for this to succeed after) Changes the key `before` to `after` without changing its position in the order or its value.
public boolean	Returns: true if `after` successfully replaced the key at `index`, false otherwise alterIndex(int the index in the order of the key to change; must be non-negative and less than `size` index, K the key that will replace the contents at `index`; this key must not be present for this to succeed after) Changes the key at the given `index` in the order to `after`, without changing the ordering of other entries or any values.
public void	clear(int maximumCapacity) Overrides com.badlogic.gdx.utils.ObjectMap.clear. Clears the map and reduces the size of the backing arrays to be the specified capacity / loadFactor, if they are larger.
public void	clear() Overrides com.badlogic.gdx.utils.ObjectMap.clear.
public ObjectMap.Entries<K, V>	entries() Overrides com.badlogic.gdx.utils.ObjectMap.entries. Returns an iterator for the entries in the map.
public ObjectMap.Entries<K, V>	iterator() Overrides com.badlogic.gdx.utils.ObjectMap.iterator. Implements java.lang.Iterable.iterator. Returns an iterator over elements of type `T`.
public ObjectMap.Keys<K>	keys() Overrides com.badlogic.gdx.utils.ObjectMap.keys. Returns an iterator for the keys in the map.
public Array<K>	orderedKeys()
public V	put(K key, V value) Overrides com.badlogic.gdx.utils.ObjectMap.put. Returns the old value associated with the specified key, or null.
public <T extends K> void	putAll(OrderedMap<T, ? extends V> map)
public V	putMissing(K key, V value) Overrides com.badlogic.gdx.utils.ObjectMap.putMissing.
public V	remove(K key) Overrides com.badlogic.gdx.utils.ObjectMap.remove. Returns the value for the removed key, or null if the key is not in the map.
public V	removeIndex(int index)
protected String	toString(String separator, boolean braces) Overrides com.badlogic.gdx.utils.ObjectMap.toString.
public ObjectMap.Values<V>	values() Overrides com.badlogic.gdx.utils.ObjectMap.values. Returns an iterator for the values in the map.

Inherited from com.badlogic.gdx.utils.ObjectMap:: containsKey containsValue ensureCapacity equals equalsIdentity findKey get get hashCode isEmpty locateKey notEmpty place putAll resize shrink toString toString

Field Detail

keys	back to summary
pack-priv final Array<K> keys

Constructor Detail

OrderedMap	back to summary
public OrderedMap() Creates a new map with an initial capacity of 51 and a load factor of 0.8.

OrderedMap	back to summary
public OrderedMap(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.

OrderedMap

back to summary

public OrderedMap(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.

OrderedMap	back to summary
public OrderedMap(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.

OrderedMap

back to summary

public OrderedMap(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.

OrderedMap	back to summary
public OrderedMap(OrderedMap<? extends K, ? extends V> map) Creates a new map containing the items in the specified map.

Method Detail

alter back to summary

alter	back to summary
public boolean alter(K before, K after) Changes the key `before` to `after` without changing its position in the order or its value. Returns true if `after` has been added to the OrderedMap and `before` has been removed; returns false if `after` is already present or `before` is not present. If you are iterating over an OrderedMap and have an index, you should prefer `alterIndex(int, Object)`, which doesn't need to search for an index like this does and so can be faster. Parameters before:K a key that must be present for this to succeed after:K a key that must not be in this map for this to succeed Returns:boolean true if `before` was removed and `after` was added, false otherwise

public boolean alter(K before, K after)

Changes the key before to after without changing its position in the order or its value. Returns true if after has been added to the OrderedMap and before has been removed; returns false if after is already present or before is not present. If you are iterating over an OrderedMap and have an index, you should prefer alterIndex(int, Object), which doesn't need to search for an index like this does and so can be faster.

Parameters

before:K: a key that must be present for this to succeed
after:K: a key that must not be in this map for this to succeed

Returns:boolean

true if before was removed and after was added, false otherwise

alterIndex back to summary

alterIndex	back to summary
public boolean alterIndex(int index, K after) Changes the key at the given `index` in the order to `after`, without changing the ordering of other entries or any values. If `after` is already present, this returns false; it will also return false if `index` is invalid for the size of this map. Otherwise, it returns true. Unlike `alter(Object, Object)`, this operates in constant time. Parameters index:int the index in the order of the key to change; must be non-negative and less than `size` after:K the key that will replace the contents at `index`; this key must not be present for this to succeed Returns:boolean true if `after` successfully replaced the key at `index`, false otherwise

public boolean alterIndex(int index, K after)

Changes the key at the given index in the order to after, without changing the ordering of other entries or any values. If after is already present, this returns false; it will also return false if index is invalid for the size of this map. Otherwise, it returns true. Unlike alter(Object, Object), this operates in constant time.

Parameters

index:int: the index in the order of the key to change; must be non-negative and less than size
after:K: the key that will replace the contents at index; this key must not be present for this to succeed

Returns:boolean

true if after successfully replaced the key at index, false otherwise

clear	back to summary
public void clear(int maximumCapacity) Overrides com.badlogic.gdx.utils.ObjectMap.clear. Doc from com.badlogic.gdx.utils.ObjectMap.clear. Clears the map and reduces the size of the backing arrays to be the specified capacity / loadFactor, if they are larger.

clear

back to summary

public void clear(int maximumCapacity)

Overrides com.badlogic.gdx.utils.ObjectMap.clear.

Doc from com.badlogic.gdx.utils.ObjectMap.clear.

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

clear	back to summary
public void clear() Overrides com.badlogic.gdx.utils.ObjectMap.clear.

entries back to summary

entries	back to summary
public ObjectMap.Entries<K, V> entries() Overrides com.badlogic.gdx.utils.ObjectMap.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 `OrderedMapEntries` constructor for nested or multithreaded iteration.

public ObjectMap.Entries<K, V> entries()

Overrides com.badlogic.gdx.utils.ObjectMap.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 OrderedMapEntries constructor for nested or multithreaded iteration.

iterator back to summary

iterator	back to summary
public ObjectMap.Entries<K, V> iterator() Overrides com.badlogic.gdx.utils.ObjectMap.iterator. Implements java.lang.Iterable.iterator. Doc from java.lang.Iterable.iterator. Returns an iterator over elements of type `T`.

public ObjectMap.Entries<K, V> iterator()

Overrides com.badlogic.gdx.utils.ObjectMap.iterator.

Implements java.lang.Iterable.iterator.

Doc from java.lang.Iterable.iterator.

Returns an iterator over elements of type T.

keys back to summary

keys	back to summary
public ObjectMap.Keys<K> keys() Overrides com.badlogic.gdx.utils.ObjectMap.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 `OrderedMapKeys` constructor for nested or multithreaded iteration.

public ObjectMap.Keys<K> keys()

Overrides com.badlogic.gdx.utils.ObjectMap.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 OrderedMapKeys constructor for nested or multithreaded iteration.

orderedKeys	back to summary
public Array<K> orderedKeys()

put	back to summary
public V put(K key, V value) Overrides com.badlogic.gdx.utils.ObjectMap.put. Doc from com.badlogic.gdx.utils.ObjectMap.put. Returns the old value associated with the specified key, or null.

put

back to summary

public V put(K key, V value)

Overrides com.badlogic.gdx.utils.ObjectMap.put.

Doc from com.badlogic.gdx.utils.ObjectMap.put.

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

putAll	back to summary
public <T extends K> void putAll(OrderedMap<T, ? extends V> map)

putMissing	back to summary
public V putMissing(K key, V value) Overrides com.badlogic.gdx.utils.ObjectMap.putMissing. Annotations @Null

putMissing

back to summary

public V putMissing(K key, V value)

Overrides com.badlogic.gdx.utils.ObjectMap.putMissing.

Annotations

@Null

remove	back to summary
public V remove(K key) Overrides com.badlogic.gdx.utils.ObjectMap.remove. Doc from com.badlogic.gdx.utils.ObjectMap.remove. Returns the value for the removed key, or null if the key is not in the map.

remove

back to summary

public V remove(K key)

Overrides com.badlogic.gdx.utils.ObjectMap.remove.

Doc from com.badlogic.gdx.utils.ObjectMap.remove.

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

removeIndex	back to summary
public V removeIndex(int index)

toString	back to summary
protected String toString(String separator, boolean braces) Overrides com.badlogic.gdx.utils.ObjectMap.toString.

values back to summary

values	back to summary
public ObjectMap.Values<V> values() Overrides com.badlogic.gdx.utils.ObjectMap.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 `OrderedMapValues` constructor for nested or multithreaded iteration.

public ObjectMap.Values<V> values()

Overrides com.badlogic.gdx.utils.ObjectMap.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 OrderedMapValues constructor for nested or multithreaded iteration.

com.badlogic.gdx.utils back to summary

public Class OrderedMap.OrderedMapEntries<K, V>

Class Inheritance

extends ObjectMap.Entries<K, V>

java.lang.Object
com.badlogic.gdx.utils.ObjectMap.MapIterator
com.badlogic.gdx.utils.ObjectMap.Entries
com.badlogic.gdx.utils.OrderedMap.OrderedMapEntries

Field Summary

Modifier and Type	Field and Description
private Array<K>	keys

Inherited from com.badlogic.gdx.utils.ObjectMap.Entries:: entry

Constructor Summary

Access	Constructor and Description
public	OrderedMapEntries(OrderedMap<K, V> map)

Method Summary

Modifier and Type	Method and Description
public ObjectMap.Entry<K, V>	next() Overrides com.badlogic.gdx.utils.ObjectMap.Entries.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.ObjectMap.MapIterator.remove. Overrides default java.util.Iterator.remove. Removes from the underlying collection the last element returned by this iterator (optional operation).
public void	reset() Overrides com.badlogic.gdx.utils.ObjectMap.MapIterator.reset.

Inherited from com.badlogic.gdx.utils.ObjectMap.Entries:: hasNext iterator

Field Detail

keys	back to summary
private Array<K> keys

Constructor Detail

OrderedMapEntries	back to summary
public OrderedMapEntries(OrderedMap<K, V> map)

Method Detail

next	back to summary
public ObjectMap.Entry<K, V> next() Overrides com.badlogic.gdx.utils.ObjectMap.Entries.next. Implements java.util.Iterator.next. Doc from com.badlogic.gdx.utils.ObjectMap.Entries.next. Note the same entry instance is returned each time this method is called.

back to summary

public ObjectMap.Entry<K, V> next()

Overrides com.badlogic.gdx.utils.ObjectMap.Entries.next.

Implements java.util.Iterator.next.

Doc from com.badlogic.gdx.utils.ObjectMap.Entries.next.

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

remove back to summary

remove	back to summary
public void remove() Overrides com.badlogic.gdx.utils.ObjectMap.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.

public void remove()

Overrides com.badlogic.gdx.utils.ObjectMap.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.

reset	back to summary
public void reset() Overrides com.badlogic.gdx.utils.ObjectMap.MapIterator.reset.

com.badlogic.gdx.utils back to summary

public Class OrderedMap.OrderedMapKeys<K>

Class Inheritance

extends ObjectMap.Keys<K>

java.lang.Object
com.badlogic.gdx.utils.ObjectMap.MapIterator
com.badlogic.gdx.utils.ObjectMap.Keys
com.badlogic.gdx.utils.OrderedMap.OrderedMapKeys

Field Summary

Modifier and Type	Field and Description
private Array<K>	keys

Constructor Summary

Access	Constructor and Description
public	OrderedMapKeys(OrderedMap<K, ?> map)

Method Summary

Modifier and Type	Method and Description
public K	next() Overrides com.badlogic.gdx.utils.ObjectMap.Keys.next. Implements java.util.Iterator.next. Returns the next element in the iteration.
public void	remove() Overrides com.badlogic.gdx.utils.ObjectMap.MapIterator.remove. Overrides default java.util.Iterator.remove. Removes from the underlying collection the last element returned by this iterator (optional operation).
public void	reset() Overrides com.badlogic.gdx.utils.ObjectMap.MapIterator.reset.
public Array<K>	toArray(Array<K> array) Overrides com.badlogic.gdx.utils.ObjectMap.Keys.toArray. Adds the remaining keys to the array.
public Array<K>	toArray() Overrides com.badlogic.gdx.utils.ObjectMap.Keys.toArray. Returns a new array containing the remaining keys.

Inherited from com.badlogic.gdx.utils.ObjectMap.Keys:: hasNext iterator

Field Detail

keys	back to summary
private Array<K> keys

Constructor Detail

OrderedMapKeys	back to summary
public OrderedMapKeys(OrderedMap<K, ?> map)

Method Detail

next	back to summary
public K next() Overrides com.badlogic.gdx.utils.ObjectMap.Keys.next. Implements java.util.Iterator.next. Doc from java.util.Iterator.next. Returns the next element in the iteration.

back to summary

public K next()

Overrides com.badlogic.gdx.utils.ObjectMap.Keys.next.

Implements java.util.Iterator.next.

Doc from java.util.Iterator.next.

Returns the next element in the iteration.

remove back to summary

remove	back to summary
public void remove() Overrides com.badlogic.gdx.utils.ObjectMap.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.

public void remove()

Overrides com.badlogic.gdx.utils.ObjectMap.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 this method is called after a call to the forEachRemaining method.

reset	back to summary
public void reset() Overrides com.badlogic.gdx.utils.ObjectMap.MapIterator.reset.

toArray	back to summary
public Array<K> toArray(Array<K> array) Overrides com.badlogic.gdx.utils.ObjectMap.Keys.toArray. Doc from com.badlogic.gdx.utils.ObjectMap.Keys.toArray. Adds the remaining keys to the array.

toArray

back to summary

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

Overrides com.badlogic.gdx.utils.ObjectMap.Keys.toArray.

Doc from com.badlogic.gdx.utils.ObjectMap.Keys.toArray.

Adds the remaining keys to the array.

toArray	back to summary
public Array<K> toArray() Overrides com.badlogic.gdx.utils.ObjectMap.Keys.toArray. Doc from com.badlogic.gdx.utils.ObjectMap.Keys.toArray. Returns a new array containing the remaining keys.

toArray

back to summary

public Array<K> toArray()

Overrides com.badlogic.gdx.utils.ObjectMap.Keys.toArray.

Doc from com.badlogic.gdx.utils.ObjectMap.Keys.toArray.

Returns a new array containing the remaining keys.

com.badlogic.gdx.utils back to summary

public Class OrderedMap.OrderedMapValues<V>

Class Inheritance

extends ObjectMap.Values<V>

java.lang.Object
com.badlogic.gdx.utils.ObjectMap.MapIterator
com.badlogic.gdx.utils.ObjectMap.Values
com.badlogic.gdx.utils.OrderedMap.OrderedMapValues

Field Summary

Modifier and Type	Field and Description
private Array<T>	keys

Constructor Summary

Access	Constructor and Description
public	OrderedMapValues(OrderedMap<?, V> map)

Method Summary

Modifier and Type	Method and Description
public V	next() Overrides com.badlogic.gdx.utils.ObjectMap.Values.next. Implements java.util.Iterator.next. Returns the next element in the iteration.
public void	remove() Overrides com.badlogic.gdx.utils.ObjectMap.MapIterator.remove. Overrides default java.util.Iterator.remove. Removes from the underlying collection the last element returned by this iterator (optional operation).
public void	reset() Overrides com.badlogic.gdx.utils.ObjectMap.MapIterator.reset.
public Array<V>	toArray(Array<V> array) Overrides com.badlogic.gdx.utils.ObjectMap.Values.toArray. Adds the remaining values to the specified array.
public Array<V>	toArray() Overrides com.badlogic.gdx.utils.ObjectMap.Values.toArray. Returns a new array containing the remaining values.

Inherited from com.badlogic.gdx.utils.ObjectMap.Values:: hasNext iterator

Field Detail

keys	back to summary
private Array<T> keys

Constructor Detail

OrderedMapValues	back to summary
public OrderedMapValues(OrderedMap<?, V> map)

Method Detail

next	back to summary
public V next() Overrides com.badlogic.gdx.utils.ObjectMap.Values.next. Implements java.util.Iterator.next. Doc from java.util.Iterator.next. Returns the next element in the iteration.

back to summary

public V next()

Overrides com.badlogic.gdx.utils.ObjectMap.Values.next.

Implements java.util.Iterator.next.

Doc from java.util.Iterator.next.

Returns the next element in the iteration.

remove back to summary

remove	back to summary
public void remove() Overrides com.badlogic.gdx.utils.ObjectMap.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.

public void remove()

Overrides com.badlogic.gdx.utils.ObjectMap.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 this method is called after a call to the forEachRemaining method.

reset	back to summary
public void reset() Overrides com.badlogic.gdx.utils.ObjectMap.MapIterator.reset.

toArray

back to summary

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

Overrides com.badlogic.gdx.utils.ObjectMap.Values.toArray.

Doc from com.badlogic.gdx.utils.ObjectMap.Values.toArray.

Adds the remaining values to the specified array.

toArray

back to summary

public Array<V> toArray()

Overrides com.badlogic.gdx.utils.ObjectMap.Values.toArray.

Doc from com.badlogic.gdx.utils.ObjectMap.Values.toArray.

Returns a new array containing the remaining values.

public Class OrderedMap<K, V>

Nested and Inner Type Summary

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail

public Class OrderedMap.OrderedMapEntries<K, V>

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail

public Class OrderedMap.OrderedMapKeys<K>

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail

public Class OrderedMap.OrderedMapValues<V>

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail