Class ObjectOrderedSet<T>
- All Implemented Interfaces:
Arrangeable,EnhancedCollection<T>,Ordered<T>,Iterable<T>,Collection<T>,Set<T>
- Direct Known Subclasses:
CaseInsensitiveOrderedSet,FilteredIterableOrderedSet,FilteredStringOrderedSet,IdentityOrderedSet
ObjectSet that also stores keys in an ObjectList 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 order(). There is some additional overhead for put and remove.
This class performs fast contains (typically O(1), worst case O(n) but that is rare in practice). Remove is somewhat slower due
to order(). Add may be slightly slower, depending on hash collisions. Load factors greater than 0.9 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 Ordered types like
ObjectOrderedSet and ObjectObjectOrderedMap.
You can customize most behavior of this map by extending it. ObjectSet.place(Object) can be overridden to change how hashCodes
are calculated (which can be useful for types like StringBuilder that don't implement hashCode()), and
ObjectSet.equate(Object, Object) can be overridden to change how equality is calculated.
This implementation uses linear probing with the backward shift algorithm for removal. It tries different hashes from a simple family, with the hash changing on resize. Linear probing continues to work even when all hashCodes collide; it just works more slowly in that case.
-
Nested Class Summary
Nested ClassesNested classes/interfaces inherited from class com.github.tommyettinger.ds.ObjectSet
ObjectSet.ObjectSetIterator<T>Nested classes/interfaces inherited from interface com.github.tommyettinger.ds.Arrangeable
Arrangeable.ArrangeableList<T>Nested classes/interfaces inherited from interface com.github.tommyettinger.ds.Ordered
Ordered.OfBoolean, Ordered.OfByte, Ordered.OfChar, Ordered.OfDouble, Ordered.OfFloat, Ordered.OfInt, Ordered.OfLong, Ordered.OfShort -
Field Summary
FieldsFields inherited from class com.github.tommyettinger.ds.ObjectSet
hashMultiplier, iterator1, iterator2, keyTable, loadFactor, mask, shift, size, threshold -
Constructor Summary
ConstructorsConstructorDescriptionObjectOrderedSet(int initialCapacity) ObjectOrderedSet(int initialCapacity, float loadFactor) ObjectOrderedSet(int initialCapacity, float loadFactor, OrderType ordering) ObjectOrderedSet(int initialCapacity, OrderType ordering) ObjectOrderedSet(ObjectOrderedSet<? extends T> set) ObjectOrderedSet(ObjectOrderedSet<? extends T> set, OrderType ordering) ObjectOrderedSet(ObjectSet<? extends T> set) Creates a new set that contains all distinct elements inset.ObjectOrderedSet(ObjectSet<? extends T> set, OrderType ordering) Creates a new set that contains all distinct elements inset.ObjectOrderedSet(Ordered<T> other, int offset, int count) Creates a new set by copyingcountitems from the given Ordered, starting atoffsetin that Ordered, into this.ObjectOrderedSet(Ordered<T> other, int offset, int count, OrderType ordering) Creates a new set by copyingcountitems from the given Ordered, starting atoffsetin that Ordered, into this.ObjectOrderedSet(OrderType ordering) ObjectOrderedSet(Collection<? extends T> coll) Creates a new set that contains all distinct elements incoll.ObjectOrderedSet(Collection<? extends T> coll, OrderType ordering) Creates a new set that contains all distinct elements incoll.ObjectOrderedSet(Iterator<? extends T> coll) Creates a new instance containing the items in the specified iterator.ObjectOrderedSet(Iterator<? extends T> coll, OrderType ordering) Creates a new instance containing the items in the specified iterator.ObjectOrderedSet(T[] items) Creates a new set that contains all distinct elements initems.ObjectOrderedSet(T[] array, int offset, int length) Creates a new set usinglengthitems from the givenarray, starting at offset (inclusive).ObjectOrderedSet(T[] array, int offset, int length, OrderType ordering) Creates a new set usinglengthitems from the givenarray, starting at offset (inclusive).ObjectOrderedSet(T[] items, OrderType ordering) Creates a new set that contains all distinct elements initems. -
Method Summary
Modifier and TypeMethodDescriptionbooleanSets the key at the specified index.booleanReturns true if the key was not already in the set.booleanAdds up tocountitems, starting fromoffset, in the Orderedotherto this set, inserting starting atinsertionIndexin the iteration order.booleanAdds up tocountitems, starting fromoffset, in the Orderedotherto this set, inserting at the end of the iteration order.booleanChanges the itembeforetoafterwithout changing its position in the order.booleanChanges the item at the givenindexin the order toafter, without changing the ordering of other items.voidclear()Clears the set, leaving the backing arrays at the current capacity.voidclear(int maximumCapacity) Clears the set and reduces the size of the backing arrays to be the specified capacity / loadFactor, if they are larger.voidensureCapacity(int additionalCapacity) Increases the size of the backing array to accommodate the specified number of additional items / loadFactor.first()Returns the first item in the order of this set, or null if the set is empty.getAt(int index) Gets the T item at the givenindexin the insertion order.inthashCode()iterator()Iterates through items in the same order asorder().order()Gets the ObjectList of items in the order this class will iterate through them.static <T> ObjectOrderedSet<T>parse(String str, String delimiter, PartialParser<T> parser) Callsparse(String, String, PartialParser, boolean)with brackets set to false.static <T> ObjectOrderedSet<T>parse(String str, String delimiter, PartialParser<T> parser, boolean brackets) Creates a new collection and fills it by callingEnhancedCollection.addLegible(String, String, PartialParser, int, int)on either all ofstr(ifbracketsis false) orstrwithout its first and last chars (ifbracketsis true).static <T> ObjectOrderedSet<T>parse(String str, String delimiter, PartialParser<T> parser, int offset, int length) Creates a new collection and fills it by callingEnhancedCollection.addLegible(String, String, PartialParser, int, int)with the given five parameters as-is.booleanReturns true if the key was removed.removeAt(int index) Removes and returns the item at the given index in this set's order.voidremoveRange(int start, int end) Removes the items between the specified start index, inclusive, and end index, exclusive.voidsort()Sorts this ObjectOrderedSet in-place by the keys' natural ordering;Tmust implementComparable.voidsort(Comparator<? super T> comp) Sorts this ObjectOrderedSet in-place by the given Comparator used on the keys.toString()Delegates toEnhancedCollection.toString(String, boolean)with the given itemSeparator and without surrounding brackets.voidtruncate(int newSize) Reduces the size of the set to the specified size.static <T> ObjectOrderedSet<T>with()Constructs an empty set given the type as a generic type argument.static <T> ObjectOrderedSet<T>with(T item) Creates a new ObjectOrderedSet that holds only the given item, but can be resized.static <T> ObjectOrderedSet<T>with(T... varargs) Creates a new ObjectOrderedSet that holds only the given items, but can be resized.static <T> ObjectOrderedSet<T>with(T item0, T item1) Creates a new ObjectOrderedSet that holds only the given items, but can be resized.static <T> ObjectOrderedSet<T>with(T item0, T item1, T item2) Creates a new ObjectOrderedSet that holds only the given items, but can be resized.static <T> ObjectOrderedSet<T>with(T item0, T item1, T item2, T item3) Creates a new ObjectOrderedSet that holds only the given items, but can be resized.static <T> ObjectOrderedSet<T>with(T item0, T item1, T item2, T item3, T item4) Creates a new ObjectOrderedSet that holds only the given items, but can be resized.static <T> ObjectOrderedSet<T>with(T item0, T item1, T item2, T item3, T item4, T item5) Creates a new ObjectOrderedSet that holds only the given items, but can be resized.static <T> ObjectOrderedSet<T>with(T item0, T item1, T item2, T item3, T item4, T item5, T item6) Creates a new ObjectOrderedSet that holds only the given items, but can be resized.static <T> ObjectOrderedSet<T>with(T item0, T item1, T item2, T item3, T item4, T item5, T item6, T item7) Creates a new ObjectOrderedSet that holds only the given items, but can be resized.Methods inherited from class com.github.tommyettinger.ds.ObjectSet
addAll, addAll, addAll, addAll, addResize, appendTo, contains, containsAll, containsAll, containsAll, containsAny, containsAny, containsAnyIterable, equals, equate, get, getHashMultiplier, getLoadFactor, getTableSize, isEmpty, locateKey, notEmpty, place, removeAll, removeAll, removeAll, resize, retainAll, setHashMultiplier, setLoadFactor, shrink, size, toArray, toArrayMethods inherited from class java.lang.Object
clone, finalize, getClass, notify, notifyAll, wait, wait, waitMethods inherited from interface com.github.tommyettinger.ds.Arrangeable
rearrange, shuffle, sizeMethods inherited from interface java.util.Collection
parallelStream, removeIf, stream, toArrayMethods inherited from interface com.github.tommyettinger.ds.EnhancedCollection
add, add, add, addAll, addAllIterable, addLegible, addLegible, addVarargs, appendTo, appendTo, containsAll, containsAllIterable, containsAny, removeAll, removeAllIterable, removeEach, removeEach, removeEach, removeEachIterable, toString, toStringMethods inherited from interface com.github.tommyettinger.ds.Ordered
getOrderType, random, random, reverse, selectRanked, selectRankedIndex, shuffle, swapMethods inherited from interface java.util.Set
spliterator
-
Field Details
-
items
-
-
Constructor Details
-
ObjectOrderedSet
-
ObjectOrderedSet
-
ObjectOrderedSet
-
ObjectOrderedSet
Creates a new instance containing the items in the specified iterator.- Parameters:
coll- an iterator that will have its remaining contents added to this
-
ObjectOrderedSet
-
ObjectOrderedSet
Creates a new set that contains all distinct elements inset. -
ObjectOrderedSet
Creates a new set that contains all distinct elements incoll. -
ObjectOrderedSet
Creates a new set usinglengthitems from the givenarray, starting at offset (inclusive).- Parameters:
array- an array to draw items fromoffset- the first index in array to draw an item fromlength- how many items to take from array; bounds-checking is the responsibility of the using code
-
ObjectOrderedSet
Creates a new set that contains all distinct elements initems.- Parameters:
items- an array that will be used in full, except for duplicate items
-
ObjectOrderedSet
Creates a new set by copyingcountitems from the given Ordered, starting atoffsetin that Ordered, into this.- Parameters:
other- another Ordered of the same typeoffset- the first index in other's ordering to draw an item fromcount- how many items to copy from other
-
ObjectOrderedSet
public ObjectOrderedSet() -
ObjectOrderedSet
public ObjectOrderedSet(int initialCapacity, float loadFactor) -
ObjectOrderedSet
public ObjectOrderedSet(int initialCapacity) -
ObjectOrderedSet
Creates a new instance containing the items in the specified iterator.- Parameters:
coll- an iterator that will have its remaining contents added to this
-
ObjectOrderedSet
-
ObjectOrderedSet
Creates a new set that contains all distinct elements inset. -
ObjectOrderedSet
Creates a new set that contains all distinct elements incoll. -
ObjectOrderedSet
Creates a new set usinglengthitems from the givenarray, starting at offset (inclusive).- Parameters:
array- an array to draw items fromoffset- the first index in array to draw an item fromlength- how many items to take from array; bounds-checking is the responsibility of the using code
-
ObjectOrderedSet
Creates a new set that contains all distinct elements initems.- Parameters:
items- an array that will be used in full, except for duplicate items
-
ObjectOrderedSet
Creates a new set by copyingcountitems from the given Ordered, starting atoffsetin that Ordered, into this.- Parameters:
other- another Ordered of the same typeoffset- the first index in other's ordering to draw an item fromcount- how many items to copy from other
-
-
Method Details
-
add
Description copied from class:ObjectSetReturns true if the key was not already in the set. If this set already contains the key, the call leaves the set unchanged and returns false. -
add
Sets the key at the specified index. Returns true if the key was not already in the set. If this set already contains the key, the existing key's index is changed if needed and false is returned. Note, the order of the parameters matches the order inObjectListand the rest of the JDK, not OrderedSet in libGDX.- Parameters:
index- where in the iteration order to add the given key, or to move it if already presentkey- what T item to try to add, if not already present- Returns:
- true if the key was added for the first time, or false if the key was already present (even if moved)
-
addAll
Adds up tocountitems, starting fromoffset, in the Orderedotherto this set, inserting at the end of the iteration order.- Parameters:
other- a non-nullOrderedofToffset- the first index inotherto usecount- how many indices inotherto use- Returns:
- true if this is modified by this call, as
ObjectSet.addAll(Collection)does
-
addAll
Adds up tocountitems, starting fromoffset, in the Orderedotherto this set, inserting starting atinsertionIndexin the iteration order.- Parameters:
insertionIndex- where to insert into the iteration orderother- a non-nullOrderedofToffset- the first index inotherto usecount- how many indices inotherto use- Returns:
- true if this is modified by this call, as
ObjectSet.addAll(Collection)does
-
remove
Description copied from class:ObjectSetReturns true if the key was removed. -
removeAt
Removes and returns the item at the given index in this set's order.- Parameters:
index- the index of the item to remove- Returns:
- the removed item
-
ensureCapacity
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.- Overrides:
ensureCapacityin classObjectSet<T>- Parameters:
additionalCapacity- how many additional items this should be able to hold without resizing (probably)
-
alter
Changes the itembeforetoafterwithout changing its position in the order. Returns true ifafterhas been added to the ObjectOrderedSet andbeforehas been removed; returns false ifafteris already present orbeforeis not present. If you are iterating over an ObjectOrderedSet and have an index, you should preferalterAt(int, Object), which doesn't need to search for an index like this does and so can be faster.- Parameters:
before- an item that must be present for this to succeedafter- an item that must not be in this set for this to succeed- Returns:
- true if
beforewas removed andafterwas added, false otherwise
-
alterAt
Changes the item at the givenindexin the order toafter, without changing the ordering of other items. Ifafteris already present, this returns false; it will also return false ifindexis invalid for the size of this set. Otherwise, it returns true. Unlikealter(Object, Object), this operates in constant time.- Parameters:
index- the index in the order of the item to change; must be non-negative and less thanObjectSet.sizeafter- the item that will replace the contents atindex; this item must not be present for this to succeed- Returns:
- true if
aftersuccessfully replaced the contents atindex, false otherwise
-
getAt
Gets the T item at the givenindexin the insertion order. The index should be between 0 (inclusive) andObjectSet.size()(exclusive).- Parameters:
index- an index in the insertion order, between 0 (inclusive) andObjectSet.size()(exclusive)- Returns:
- the item at the given index
-
first
Returns the first item in the order of this set, or null if the set is empty. This set can never contain null normally, so if this returns null, that indicates an abnormal situation, and you can opt to throw an Exception. -
clear
public void clear(int maximumCapacity) Description copied from class:ObjectSetClears 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. -
clear
public void clear()Description copied from class:ObjectSetClears 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.ObjectSet.clear(int)can be used to reduce the capacity. -
order
Gets the ObjectList of items in the order this class will iterate through them. Returns a direct reference to the same ObjectList this uses, so changes to the returned list will also change the iteration order here. -
sort
public void sort()Sorts this ObjectOrderedSet in-place by the keys' natural ordering;Tmust implementComparable. -
sort
Sorts this ObjectOrderedSet in-place by the given Comparator used on the keys. Ifcompis null, then this will sort by the natural ordering of the keys, which requiresTtoComparable. -
removeRange
public void removeRange(int start, int end) Removes the items between the specified start index, inclusive, and end index, exclusive. Note that this takes different arguments than some other range-related methods; this needs a start index and an end index, rather than a count of items. This matches the behavior in the JDK collections.- Specified by:
removeRangein interfaceOrdered<T>- Parameters:
start- the first index to remove, inclusiveend- the last index (after what should be removed), exclusive
-
truncate
public void truncate(int newSize) Reduces the size of the set to the specified size. If the set is already smaller than the specified size, no action is taken. -
iterator
Iterates through items in the same order asorder(). Reuses one of two iterators, and does not permit nested iteration; useObjectOrderedSetIterator(ObjectOrderedSet)to nest iterators. -
toString
Description copied from interface:EnhancedCollectionDelegates toEnhancedCollection.toString(String, boolean)with the given itemSeparator and without surrounding brackets.- Specified by:
toStringin interfaceEnhancedCollection<T>- Parameters:
itemSeparator- how to separate items, such as", "- Returns:
- a new String representing this map
-
hashCode
public int hashCode() -
toString
-
with
Constructs an empty set given the type as a generic type argument. This is usually less useful than just using the constructor, but can be handy in some code-generation scenarios when you don't know how many arguments you will have.- Type Parameters:
T- the type of items; must be given explicitly- Returns:
- a new set containing nothing
-
with
Creates a new ObjectOrderedSet that holds only the given item, but can be resized.- Type Parameters:
T- the type of item, typically inferred- Parameters:
item- one T item- Returns:
- a new ObjectOrderedSet that holds the given item
-
with
Creates a new ObjectOrderedSet that holds only the given items, but can be resized.- Type Parameters:
T- the type of item, typically inferred- Parameters:
item0- a T itemitem1- a T item- Returns:
- a new ObjectOrderedSet that holds the given items
-
with
Creates a new ObjectOrderedSet that holds only the given items, but can be resized.- Type Parameters:
T- the type of item, typically inferred- Parameters:
item0- a T itemitem1- a T itemitem2- a T item- Returns:
- a new ObjectOrderedSet that holds the given items
-
with
Creates a new ObjectOrderedSet that holds only the given items, but can be resized.- Type Parameters:
T- the type of item, typically inferred- Parameters:
item0- a T itemitem1- a T itemitem2- a T itemitem3- a T item- Returns:
- a new ObjectOrderedSet that holds the given items
-
with
Creates a new ObjectOrderedSet that holds only the given items, but can be resized.- Type Parameters:
T- the type of item, typically inferred- Parameters:
item0- a T itemitem1- a T itemitem2- a T itemitem3- a T itemitem4- a T item- Returns:
- a new ObjectOrderedSet that holds the given items
-
with
Creates a new ObjectOrderedSet that holds only the given items, but can be resized.- Type Parameters:
T- the type of item, typically inferred- Parameters:
item0- a T itemitem1- a T itemitem2- a T itemitem3- a T itemitem4- a T itemitem5- a T item- Returns:
- a new ObjectOrderedSet that holds the given items
-
with
public static <T> ObjectOrderedSet<T> with(T item0, T item1, T item2, T item3, T item4, T item5, T item6) Creates a new ObjectOrderedSet that holds only the given items, but can be resized.- Type Parameters:
T- the type of item, typically inferred- Parameters:
item0- a T itemitem1- a T itemitem2- a T itemitem3- a T itemitem4- a T itemitem5- a T itemitem6- a T item- Returns:
- a new ObjectOrderedSet that holds the given items
-
with
public static <T> ObjectOrderedSet<T> with(T item0, T item1, T item2, T item3, T item4, T item5, T item6, T item7) Creates a new ObjectOrderedSet that holds only the given items, but can be resized.- Type Parameters:
T- the type of item, typically inferred- Parameters:
item0- a T itemitem1- a T itemitem2- a T itemitem3- a T itemitem4- a T itemitem5- a T itemitem6- a T item- Returns:
- a new ObjectOrderedSet that holds the given items
-
with
Creates a new ObjectOrderedSet that holds only the given items, but can be resized. This overload will only be used when an array is supplied and the type of the items requested is the component type of the array, or if varargs are used and there are 9 or more arguments.- Type Parameters:
T- the type of item, typically inferred- Parameters:
varargs- a T varargs or T array; remember that varargs allocate- Returns:
- a new ObjectOrderedSet that holds the given items
-
parse
Callsparse(String, String, PartialParser, boolean)with brackets set to false.- Parameters:
str- a String that will be parsed in fulldelimiter- the delimiter between items in strparser- a PartialParser that returns aTitem from a section ofstr- Returns:
- a new collection parsed from str
-
parse
public static <T> ObjectOrderedSet<T> parse(String str, String delimiter, PartialParser<T> parser, boolean brackets) Creates a new collection and fills it by callingEnhancedCollection.addLegible(String, String, PartialParser, int, int)on either all ofstr(ifbracketsis false) orstrwithout its first and last chars (ifbracketsis true). Each item is expected to be separated bydelimiter.- Parameters:
str- a String that will be parsed in full (depending on brackets)delimiter- the delimiter between items in strparser- a PartialParser that returns aTitem from a section ofstrbrackets- if true, the first and last chars in str will be ignored- Returns:
- a new collection parsed from str
-
parse
public static <T> ObjectOrderedSet<T> parse(String str, String delimiter, PartialParser<T> parser, int offset, int length) Creates a new collection and fills it by callingEnhancedCollection.addLegible(String, String, PartialParser, int, int)with the given five parameters as-is.- Parameters:
str- a String that will have the given section parseddelimiter- the delimiter between items in strparser- a PartialParser that returns aTitem from a section ofstroffset- the first position to parse in str, inclusivelength- how many chars to parse, starting from offset- Returns:
- a new collection parsed from str
-