Class ObjectOrderedSet<T>

java.lang.Object
com.github.tommyettinger.ds.ObjectSet<T>
com.github.tommyettinger.ds.ObjectOrderedSet<T>
All Implemented Interfaces:
Arrangeable, EnhancedCollection<T>, Ordered<T>, Iterable<T>, Collection<T>, Set<T>
Direct Known Subclasses:
CaseInsensitiveOrderedSet, FilteredIterableOrderedSet, FilteredStringOrderedSet, IdentityOrderedSet

public class ObjectOrderedSet<T> extends ObjectSet<T> implements Ordered<T>
A 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.

  • Field Details

  • Constructor Details

    • ObjectOrderedSet

      public ObjectOrderedSet(OrderType ordering)
    • ObjectOrderedSet

      public ObjectOrderedSet(int initialCapacity, float loadFactor, OrderType ordering)
    • ObjectOrderedSet

      public ObjectOrderedSet(int initialCapacity, OrderType ordering)
    • ObjectOrderedSet

      public ObjectOrderedSet(Iterator<? extends T> coll, OrderType ordering)
      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

      public ObjectOrderedSet(ObjectOrderedSet<? extends T> set, OrderType ordering)
    • ObjectOrderedSet

      public ObjectOrderedSet(ObjectSet<? extends T> set, OrderType ordering)
      Creates a new set that contains all distinct elements in set.
    • ObjectOrderedSet

      public ObjectOrderedSet(Collection<? extends T> coll, OrderType ordering)
      Creates a new set that contains all distinct elements in coll.
    • ObjectOrderedSet

      public ObjectOrderedSet(T[] array, int offset, int length, OrderType ordering)
      Creates a new set using length items from the given array, starting at offset (inclusive).
      Parameters:
      array - an array to draw items from
      offset - the first index in array to draw an item from
      length - how many items to take from array; bounds-checking is the responsibility of the using code
    • ObjectOrderedSet

      public ObjectOrderedSet(T[] items, OrderType ordering)
      Creates a new set that contains all distinct elements in items.
      Parameters:
      items - an array that will be used in full, except for duplicate items
    • ObjectOrderedSet

      public ObjectOrderedSet(Ordered<T> other, int offset, int count, OrderType ordering)
      Creates a new set by copying count items from the given Ordered, starting at offset in that Ordered, into this.
      Parameters:
      other - another Ordered of the same type
      offset - the first index in other's ordering to draw an item from
      count - how many items to copy from other
    • ObjectOrderedSet

      public ObjectOrderedSet()
    • ObjectOrderedSet

      public ObjectOrderedSet(int initialCapacity, float loadFactor)
    • ObjectOrderedSet

      public ObjectOrderedSet(int initialCapacity)
    • ObjectOrderedSet

      public ObjectOrderedSet(Iterator<? extends T> coll)
      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

      public ObjectOrderedSet(ObjectOrderedSet<? extends T> set)
    • ObjectOrderedSet

      public ObjectOrderedSet(ObjectSet<? extends T> set)
      Creates a new set that contains all distinct elements in set.
    • ObjectOrderedSet

      public ObjectOrderedSet(Collection<? extends T> coll)
      Creates a new set that contains all distinct elements in coll.
    • ObjectOrderedSet

      public ObjectOrderedSet(T[] array, int offset, int length)
      Creates a new set using length items from the given array, starting at offset (inclusive).
      Parameters:
      array - an array to draw items from
      offset - the first index in array to draw an item from
      length - how many items to take from array; bounds-checking is the responsibility of the using code
    • ObjectOrderedSet

      public ObjectOrderedSet(T[] items)
      Creates a new set that contains all distinct elements in items.
      Parameters:
      items - an array that will be used in full, except for duplicate items
    • ObjectOrderedSet

      public ObjectOrderedSet(Ordered<T> other, int offset, int count)
      Creates a new set by copying count items from the given Ordered, starting at offset in that Ordered, into this.
      Parameters:
      other - another Ordered of the same type
      offset - the first index in other's ordering to draw an item from
      count - how many items to copy from other
  • Method Details

    • add

      public boolean add(T key)
      Description copied from class: ObjectSet
      Returns 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.
      Specified by:
      add in interface Collection<T>
      Specified by:
      add in interface Set<T>
      Overrides:
      add in class ObjectSet<T>
    • add

      public boolean add(int index, T key)
      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 in ObjectList and 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 present
      key - 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

      public boolean addAll(Ordered<T> other, int offset, int count)
      Adds up to count items, starting from offset, in the Ordered other to this set, inserting at the end of the iteration order.
      Parameters:
      other - a non-null Ordered of T
      offset - the first index in other to use
      count - how many indices in other to use
      Returns:
      true if this is modified by this call, as ObjectSet.addAll(Collection) does
    • addAll

      public boolean addAll(int insertionIndex, Ordered<T> other, int offset, int count)
      Adds up to count items, starting from offset, in the Ordered other to this set, inserting starting at insertionIndex in the iteration order.
      Parameters:
      insertionIndex - where to insert into the iteration order
      other - a non-null Ordered of T
      offset - the first index in other to use
      count - how many indices in other to use
      Returns:
      true if this is modified by this call, as ObjectSet.addAll(Collection) does
    • remove

      public boolean remove(Object key)
      Description copied from class: ObjectSet
      Returns true if the key was removed.
      Specified by:
      remove in interface Collection<T>
      Specified by:
      remove in interface Set<T>
      Overrides:
      remove in class ObjectSet<T>
    • removeAt

      public T removeAt(int index)
      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:
      ensureCapacity in class ObjectSet<T>
      Parameters:
      additionalCapacity - how many additional items this should be able to hold without resizing (probably)
    • alter

      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 ObjectOrderedSet and before has been removed; returns false if after is already present or before is not present. If you are iterating over an ObjectOrderedSet and have an index, you should prefer alterAt(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 succeed
      after - an item that must not be in this set for this to succeed
      Returns:
      true if before was removed and after was added, false otherwise
    • alterAt

      public boolean alterAt(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 - the index in the order of the item to change; must be non-negative and less than ObjectSet.size
      after - the item that will replace the contents at index; this item must not be present for this to succeed
      Returns:
      true if after successfully replaced the contents at index, false otherwise
    • getAt

      public T getAt(int index)
      Gets the T item at the given index in the insertion order. The index should be between 0 (inclusive) and ObjectSet.size() (exclusive).
      Parameters:
      index - an index in the insertion order, between 0 (inclusive) and ObjectSet.size() (exclusive)
      Returns:
      the item at the given index
    • first

      public T 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.
      Specified by:
      first in interface EnhancedCollection<T>
      Overrides:
      first in class ObjectSet<T>
      Returns:
      the first item in the order, or null if this set is empty
    • clear

      public void clear(int maximumCapacity)
      Description copied from class: ObjectSet
      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.
      Overrides:
      clear in class ObjectSet<T>
    • clear

      public void clear()
      Description copied from class: ObjectSet
      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. ObjectSet.clear(int) can be used to reduce the capacity.
      Specified by:
      clear in interface Collection<T>
      Specified by:
      clear in interface Set<T>
      Overrides:
      clear in class ObjectSet<T>
    • order

      public ObjectList<T> 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.
      Specified by:
      order in interface Ordered<T>
      Returns:
      the ObjectList of items, in iteration order (usually insertion-order), that this uses
    • sort

      public void sort()
      Sorts this ObjectOrderedSet in-place by the keys' natural ordering; T must implement Comparable.
    • sort

      public void sort(Comparator<? super T> comp)
      Sorts this ObjectOrderedSet in-place by the given Comparator used on the keys. If comp is null, then this will sort by the natural ordering of the keys, which requires T to Comparable.
      Specified by:
      sort in interface Ordered<T>
      Parameters:
      comp - a Comparator that can compare two T keys, or null to use the keys' natural ordering
    • 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:
      removeRange in interface Ordered<T>
      Parameters:
      start - the first index to remove, inclusive
      end - 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.
      Overrides:
      truncate in class ObjectSet<T>
      Parameters:
      newSize - the target size to try to reach by removing items, if smaller than the current size
    • iterator

      public ObjectSet.ObjectSetIterator<T> iterator()
      Iterates through items in the same order as order(). Reuses one of two iterators, and does not permit nested iteration; use ObjectOrderedSetIterator(ObjectOrderedSet) to nest iterators.
      Specified by:
      iterator in interface Collection<T>
      Specified by:
      iterator in interface Iterable<T>
      Specified by:
      iterator in interface Set<T>
      Overrides:
      iterator in class ObjectSet<T>
      Returns:
      an Iterator over the T items in this, in order
    • toString

      public String toString(String itemSeparator)
      Description copied from interface: EnhancedCollection
      Delegates to EnhancedCollection.toString(String, boolean) with the given itemSeparator and without surrounding brackets.
      Specified by:
      toString in interface EnhancedCollection<T>
      Parameters:
      itemSeparator - how to separate items, such as ", "
      Returns:
      a new String representing this map
    • hashCode

      public int hashCode()
      Specified by:
      hashCode in interface Collection<T>
      Specified by:
      hashCode in interface Set<T>
      Overrides:
      hashCode in class ObjectSet<T>
    • toString

      public String toString()
      Overrides:
      toString in class ObjectSet<T>
    • with

      public static <T> ObjectOrderedSet<T> 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

      public static <T> ObjectOrderedSet<T> with(T item)
      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

      public static <T> ObjectOrderedSet<T> with(T item0, T item1)
      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 item
      item1 - 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)
      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 item
      item1 - a T item
      item2 - 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)
      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 item
      item1 - a T item
      item2 - a T item
      item3 - 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)
      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 item
      item1 - a T item
      item2 - a T item
      item3 - a T item
      item4 - 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)
      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 item
      item1 - a T item
      item2 - a T item
      item3 - a T item
      item4 - a T item
      item5 - 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 item
      item1 - a T item
      item2 - a T item
      item3 - a T item
      item4 - a T item
      item5 - a T item
      item6 - 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 item
      item1 - a T item
      item2 - a T item
      item3 - a T item
      item4 - a T item
      item5 - a T item
      item6 - a T item
      Returns:
      a new ObjectOrderedSet that holds the given items
    • with

      @SafeVarargs public static <T> ObjectOrderedSet<T> with(T... varargs)
      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

      public static <T> ObjectOrderedSet<T> parse(String str, String delimiter, PartialParser<T> parser)
      Calls parse(String, String, PartialParser, boolean) with brackets set to false.
      Parameters:
      str - a String that will be parsed in full
      delimiter - the delimiter between items in str
      parser - a PartialParser that returns a T item from a section of str
      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 calling EnhancedCollection.addLegible(String, String, PartialParser, int, int) on either all of str (if brackets is false) or str without its first and last chars (if brackets is true). Each item is expected to be separated by delimiter.
      Parameters:
      str - a String that will be parsed in full (depending on brackets)
      delimiter - the delimiter between items in str
      parser - a PartialParser that returns a T item from a section of str
      brackets - 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 calling EnhancedCollection.addLegible(String, String, PartialParser, int, int) with the given five parameters as-is.
      Parameters:
      str - a String that will have the given section parsed
      delimiter - the delimiter between items in str
      parser - a PartialParser that returns a T item from a section of str
      offset - the first position to parse in str, inclusive
      length - how many chars to parse, starting from offset
      Returns:
      a new collection parsed from str