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

public Class OrderedSet<T>

extends ObjectSet<T>
Class Inheritance
Imports
java.util.NoSuchElementException
A ObjectSet 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 is ordered and faster than an unordered set. Keys can also be accessed and the order changed using orderedItems(). There is some additional overhead for put and remove. When used for faster iteration versus ObjectSet and the order does not actually matter, copying during remove can be greatly reduced by setting Array#ordered to false for OrderedSet#orderedItems().

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

Field Summary

Modifier and TypeField and Description
pack-priv final Array<T>
items

pack-priv transient OrderedSet.OrderedSetIterator<K>
iterator1

Hides com.badlogic.gdx.utils.ObjectSet.iterator1.

pack-priv transient OrderedSet.OrderedSetIterator<K>
iterator2

Hides com.badlogic.gdx.utils.ObjectSet.iterator2.

Inherited from com.badlogic.gdx.utils.ObjectSet:
keyTableloadFactormaskshiftsizethreshold

Constructor Summary

AccessConstructor and Description
public
OrderedSet()

public
OrderedSet(int initialCapacity, float loadFactor)

public
OrderedSet(int initialCapacity)

public
OrderedSet(OrderedSet<? extends T> set)

Method Summary

Modifier and TypeMethod and Description
public boolean
add(T key)

Overrides com.badlogic.gdx.utils.ObjectSet.add.

Returns true if the key was added to the set or false if it was already in the set.

public boolean
add(T key, int index)

Sets the key at the specfied index.

public void
addAll(OrderedSet<T> set)

public boolean

Returns:

true if before was removed and after was added, false otherwise
alter(T
an item that must be present for this to succeed
before, T
an item that must not be in this set for this to succeed
after)

Changes the item before to after without changing its position in the order.

public boolean

Returns:

true if after successfully replaced the contents at index, false otherwise
alterIndex(int
the index in the order of the item to change; must be non-negative and less than size
index, T
the item that will replace the contents at index; this item must not be present for this to succeed
after)

Changes the item at the given index in the order to after, without changing the ordering of other items.

public void
clear(int maximumCapacity)

Overrides com.badlogic.gdx.utils.ObjectSet.clear.

Clears the set 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.ObjectSet.clear.

Clears the set, leaving the backing arrays at the current capacity.

public void
ensureCapacity(int additionalCapacity)

Overrides com.badlogic.gdx.utils.ObjectSet.ensureCapacity.

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

public boolean
equals(Object obj)

Overrides com.badlogic.gdx.utils.ObjectSet.equals.

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

public T
first()

Overrides com.badlogic.gdx.utils.ObjectSet.first.

public int
hashCode()

Overrides com.badlogic.gdx.utils.ObjectSet.hashCode.

Returns a hash code value for this object.

public OrderedSet.OrderedSetIterator<T>
iterator()

Overrides com.badlogic.gdx.utils.ObjectSet.iterator.

Implements java.lang.Iterable.iterator.

Returns an iterator for the keys in the set.

public Array<T>
orderedItems()

public boolean
remove(T key)

Overrides com.badlogic.gdx.utils.ObjectSet.remove.

Returns true if the key was removed.

public T
removeIndex(int index)

public String
toString()

Overrides com.badlogic.gdx.utils.ObjectSet.toString.

Returns a string representation of the object.

public String
toString(String separator)

Overrides com.badlogic.gdx.utils.ObjectSet.toString.

public static <T> OrderedSet<T>
with(T... array)

Hides com.badlogic.gdx.utils.ObjectSet.with.

Inherited from com.badlogic.gdx.utils.ObjectSet:
addAlladdAlladdAlladdAlladdAllcontainsgetisEmptylocateKeynotEmptyplaceshrinktableSize

Field Detail

itemsback to summary
pack-priv final Array<T> items
iterator1back to summary
pack-priv transient OrderedSet.OrderedSetIterator<K> iterator1

Hides com.badlogic.gdx.utils.ObjectSet.iterator1.

iterator2back to summary
pack-priv transient OrderedSet.OrderedSetIterator<K> iterator2

Hides com.badlogic.gdx.utils.ObjectSet.iterator2.

Constructor Detail

OrderedSetback to summary
public OrderedSet()
OrderedSetback to summary
public OrderedSet(int initialCapacity, float loadFactor)
OrderedSetback to summary
public OrderedSet(int initialCapacity)
OrderedSetback to summary
public OrderedSet(OrderedSet<? extends T> set)

Method Detail

addback to summary
public boolean add(T key)

Overrides com.badlogic.gdx.utils.ObjectSet.add.

Doc from com.badlogic.gdx.utils.ObjectSet.add.

Returns true if the key was added to the set or false if it was already in the set. If this set already contains the key, the call leaves the set unchanged and returns false.

addback to summary
public boolean add(T key, int index)

Sets the key at the specfied index. Returns true if the key was added to the set or false if it was already in the set. If this set already contains the key, the existing key's index is changed if needed and false is returned.

addAllback to summary
public void addAll(OrderedSet<T> set)
alterback to summary
public boolean alter(T before, T after)

Changes the item before to after without changing its position in the order. Returns true if after has been added to the OrderedSet and before has been removed; returns false if after is already present or before is not present. If you are iterating over an OrderedSet 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:T

an item that must be present for this to succeed

after:T

an item that must not be in this set for this to succeed

Returns:boolean

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

alterIndexback to summary
public boolean alterIndex(int index, T after)

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

Parameters
index:int

the index in the order of the item to change; must be non-negative and less than size

after:T

the item that will replace the contents at index; this item must not be present for this to succeed

Returns:boolean

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

clearback to summary
public void clear(int maximumCapacity)

Overrides com.badlogic.gdx.utils.ObjectSet.clear.

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

Clears the set and reduces the size of the backing arrays to be the specified capacity / loadFactor, if they are larger. The reduction is done by allocating new arrays, though for large arrays this can be faster than clearing the existing array.

clearback to summary
public void clear()

Overrides com.badlogic.gdx.utils.ObjectSet.clear.

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

Clears the set, leaving the backing arrays at the current capacity. When the capacity is high and the population is low, iteration can be unnecessarily slow. clear(int) can be used to reduce the capacity.

ensureCapacityback to summary
public void ensureCapacity(int additionalCapacity)

Overrides com.badlogic.gdx.utils.ObjectSet.ensureCapacity.

Doc from com.badlogic.gdx.utils.ObjectSet.ensureCapacity.

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.

equalsback to summary
public boolean equals(Object obj)

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

firstback to summary
public T first()

Overrides com.badlogic.gdx.utils.ObjectSet.first.

hashCodeback to summary
public int hashCode()

Overrides com.badlogic.gdx.utils.ObjectSet.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.
iteratorback to summary
public OrderedSet.OrderedSetIterator<T> iterator()

Overrides com.badlogic.gdx.utils.ObjectSet.iterator.

Implements java.lang.Iterable.iterator.

Doc from com.badlogic.gdx.utils.ObjectSet.iterator.

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

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

orderedItemsback to summary
public Array<T> orderedItems()
removeback to summary
public boolean remove(T key)

Overrides com.badlogic.gdx.utils.ObjectSet.remove.

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

Returns true if the key was removed.

removeIndexback to summary
public T removeIndex(int index)
toStringback to summary
public String toString()

Overrides com.badlogic.gdx.utils.ObjectSet.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
public String toString(String separator)

Overrides com.badlogic.gdx.utils.ObjectSet.toString.

withback to summary
public static <T> OrderedSet<T> with(T... array)

Hides com.badlogic.gdx.utils.ObjectSet.with.

com.badlogic.gdx.utils back to summary

public Class OrderedSet.OrderedSetIterator<K>

extends ObjectSet.ObjectSetIterator<K>
Class Inheritance

Field Summary

Modifier and TypeField and Description
private Array<K>
items

Inherited from com.badlogic.gdx.utils.ObjectSet.ObjectSetIterator:
currentIndexhasNextnextIndexsetvalid

Constructor Summary

AccessConstructor and Description
public
OrderedSetIterator(OrderedSet<K> set)

Method Summary

Modifier and TypeMethod and Description
public K
next()

Overrides com.badlogic.gdx.utils.ObjectSet.ObjectSetIterator.next.

Implements java.util.Iterator.next.

Returns the next element in the iteration.

public void
remove()

Overrides com.badlogic.gdx.utils.ObjectSet.ObjectSetIterator.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.ObjectSet.ObjectSetIterator.reset.

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

Overrides com.badlogic.gdx.utils.ObjectSet.ObjectSetIterator.toArray.

Adds the remaining values to the array.

public Array<K>
toArray()

Overrides com.badlogic.gdx.utils.ObjectSet.ObjectSetIterator.toArray.

Returns a new array containing the remaining values.

Inherited from com.badlogic.gdx.utils.ObjectSet.ObjectSetIterator:
hasNextiterator

Field Detail

itemsback to summary
private Array<K> items

Constructor Detail

OrderedSetIteratorback to summary
public OrderedSetIterator(OrderedSet<K> set)

Method Detail

nextback to summary
public K next()

Overrides com.badlogic.gdx.utils.ObjectSet.ObjectSetIterator.next.

Implements java.util.Iterator.next.

Doc from java.util.Iterator.next.

Returns the next element in the iteration.

removeback to summary
public void remove()

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

resetback to summary
public void reset()

Overrides com.badlogic.gdx.utils.ObjectSet.ObjectSetIterator.reset.

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

Overrides com.badlogic.gdx.utils.ObjectSet.ObjectSetIterator.toArray.

Doc from com.badlogic.gdx.utils.ObjectSet.ObjectSetIterator.toArray.

Adds the remaining values to the array.

toArrayback to summary
public Array<K> toArray()

Overrides com.badlogic.gdx.utils.ObjectSet.ObjectSetIterator.toArray.

Doc from com.badlogic.gdx.utils.ObjectSet.ObjectSetIterator.toArray.

Returns a new array containing the remaining values.