Package com.github.tommyettinger.ds

Class IntOrderedSet

java.lang.Object
com.github.tommyettinger.ds.IntSet
com.github.tommyettinger.ds.IntOrderedSet
All Implemented Interfaces:
Arrangeable, Ordered.OfInt, PrimitiveCollection<Integer>, PrimitiveCollection.OfInt, PrimitiveSet<Integer>, PrimitiveSet.SetOfInt
public class IntOrderedSet extends IntSet implements Ordered.OfInt
A IntSet that also stores keys in a IntList using the insertion order. 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. 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 Ordered types like ObjectOrderedSet and ObjectObjectOrderedMap.

You can customize most behavior of this set by extending it. IntSet.place(int) can be overridden to change how hashCodes are calculated (which can be useful for types like StringBuilder that don't implement hashCode()).

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, just more slowly.

  • Field Details

    • items

      protected final IntList items

  • Constructor Details

    • IntOrderedSet

      public IntOrderedSet()

    • IntOrderedSet

      public IntOrderedSet(OrderType ordering)
      Creates an IntOrderedSet with the option to use an IntDeque or IntBag for keeping order.
      Parameters:
      ordering - determines what implementation order() will use

    • IntOrderedSet

      public IntOrderedSet(int initialCapacity, float loadFactor)

    • IntOrderedSet

      public IntOrderedSet(int initialCapacity, float loadFactor, OrderType ordering)

    • IntOrderedSet

      public IntOrderedSet(int initialCapacity, OrderType ordering)

    • IntOrderedSet

      public IntOrderedSet(int initialCapacity)

    • IntOrderedSet

      public IntOrderedSet(IntIterator 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

    • IntOrderedSet

      public IntOrderedSet(IntIterator 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

    • IntOrderedSet

      public IntOrderedSet(IntOrderedSet set, OrderType ordering)

    • IntOrderedSet

      public IntOrderedSet(IntOrderedSet set)

    • IntOrderedSet

      public IntOrderedSet(IntSet set)
      Creates a new set that contains all distinct elements in set.
      Parameters:
      set - a IntSet without an order

    • IntOrderedSet

      public IntOrderedSet(IntSet set, OrderType ordering)
      Creates a new set that contains all distinct elements in set.
      Parameters:
      set - a IntSet without an order
      ordering - determines what implementation order() will use

    • IntOrderedSet

      public IntOrderedSet(PrimitiveCollection.OfInt coll)
      Creates a new set that contains all distinct elements in coll.

    • IntOrderedSet

      public IntOrderedSet(PrimitiveCollection.OfInt coll, OrderType ordering)
      Creates a new set that contains all distinct elements in coll.
      Parameters:
      coll - any PrimitiveCollection.OfInt
      ordering - determines what implementation order() will use

    • IntOrderedSet

      public IntOrderedSet(Ordered.OfInt 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.OfInt
      offset - the first index in other's ordering to draw an item from
      count - how many items to copy from other

    • IntOrderedSet

      public IntOrderedSet(Ordered.OfInt 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.OfInt
      offset - the first index in other's ordering to draw an item from
      count - how many items to copy from other
      ordering - determines what implementation order() will use

    • IntOrderedSet

      public IntOrderedSet(int[] 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

    • IntOrderedSet

      public IntOrderedSet(int[] 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
      ordering - determines what implementation order() will use

    • IntOrderedSet

      public IntOrderedSet(int[] 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

    • IntOrderedSet

      public IntOrderedSet(int[] 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
      ordering - determines what implementation order() will use

  • Method Details

    • add

      public boolean add(int key)
      Description copied from class: IntSet
      Returns true if the key was not already in the set.
      Specified by:
      add in interface PrimitiveCollection.OfInt
      Overrides:
      add in class IntSet

    • add

      public boolean add(int index, int 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 int 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.OfInt 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.OfInt 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 IntSet.addAll(IntSet) does

    • addAll

      public boolean addAll(int insertionIndex, Ordered.OfInt 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.OfInt
      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 IntSet.addAll(IntSet) does

    • remove

      public boolean remove(int key)
      Description copied from class: IntSet
      Returns true if the key was removed.
      Specified by:
      remove in interface PrimitiveCollection.OfInt
      Overrides:
      remove in class IntSet

    • removeAt

      public int 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

    • 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.OfInt
      Parameters:
      start - the first index to remove, inclusive
      end - the last index (after what should be removed), exclusive

    • first

      public int first()
      Description copied from interface: PrimitiveCollection.OfInt
      Attempts to get the first item in this PrimitiveCollection, where "first" is only defined meaningfully if this type is ordered. Many times, this applies to a class that is not ordered, and in those cases it can get an arbitrary item, and that item is permitted to be different for different calls to first().
      This is useful for cases where you would normally be able to call something like List.get(int) to get an item, any item, from a collection, but whatever class you're using doesn't necessarily provide a get(), first(), peek(), or similar method.
      The default implementation uses PrimitiveCollection.OfInt.iterator(), tries to get the first item, or throws an IllegalStateException if this is empty.
      Specified by:
      first in interface PrimitiveCollection.OfInt
      Overrides:
      first in class IntSet
      Returns:
      the first item in this PrimitiveCollection, as produced by PrimitiveCollection.OfInt.iterator()

    • 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 IntSet
      Parameters:
      additionalCapacity - how many additional items this should be able to hold without resizing (probably)

    • alter

      public boolean alter(int before, int 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, int), 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, int 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(int, int), this operates in constant time.
      Parameters:
      index - the index in the order of the item to change; must be non-negative and less than IntSet.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 int getAt(int index)
      Gets the int item at the given index in the insertion order. The index should be between 0 (inclusive) and IntSet.size() (exclusive).
      Parameters:
      index - an index in the insertion order, between 0 (inclusive) and IntSet.size() (exclusive)
      Returns:
      the item at the given index

    • clear

      public void clear(int maximumCapacity)
      Description copied from class: IntSet
      Clears the set and reduces the size of the backing arrays to be the specified capacity / loadFactor, if they are larger.
      Overrides:
      clear in class IntSet

    • clear

      public void clear()
      Specified by:
      clear in interface PrimitiveCollection<Integer>
      Overrides:
      clear in class IntSet

    • order

      public IntList 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.OfInt
      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.

    • 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 IntSet
      Parameters:
      newSize - the target size to try to reach by removing items, if smaller than the current size

    • iterator

      public IntSet.IntSetIterator iterator()
      Iterates through items in the same order as order(). Reuses one of two iterators, and does not permit nested iteration; use IntOrderedSetIterator(IntOrderedSet) to nest iterators.
      Specified by:
      iterator in interface PrimitiveCollection<Integer>
      Specified by:
      iterator in interface PrimitiveCollection.OfInt
      Overrides:
      iterator in class IntSet
      Returns:
      an Iterator over the T items in this, in order

    • hashCode

      public int hashCode()
      Specified by:
      hashCode in interface PrimitiveCollection<Integer>
      Specified by:
      hashCode in interface PrimitiveSet<Integer>
      Overrides:
      hashCode in class IntSet

    • with

      public static IntOrderedSet with()
      Constructs an empty set. 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.
      Returns:
      a new set containing nothing

    • with

      public static IntOrderedSet with(int item)
      Creates a new IntOrderedSet that holds only the given item, but can be resized.
      Parameters:
      item - an int item
      Returns:
      a new IntOrderedSet that holds the given item

    • with

      public static IntOrderedSet with(int item0, int item1)
      Creates a new IntOrderedSet that holds only the given items, but can be resized.
      Parameters:
      item0 - an int item
      item1 - an int item
      Returns:
      a new IntOrderedSet that holds the given items

    • with

      public static IntOrderedSet with(int item0, int item1, int item2)
      Creates a new IntOrderedSet that holds only the given items, but can be resized.
      Parameters:
      item0 - an int item
      item1 - an int item
      item2 - an int item
      Returns:
      a new IntOrderedSet that holds the given items

    • with

      public static IntOrderedSet with(int item0, int item1, int item2, int item3)
      Creates a new IntOrderedSet that holds only the given items, but can be resized.
      Parameters:
      item0 - an int item
      item1 - an int item
      item2 - an int item
      item3 - an int item
      Returns:
      a new IntOrderedSet that holds the given items

    • with

      public static IntOrderedSet with(int item0, int item1, int item2, int item3, int item4)
      Creates a new IntOrderedSet that holds only the given items, but can be resized.
      Parameters:
      item0 - an int item
      item1 - an int item
      item2 - an int item
      item3 - an int item
      item4 - an int item
      Returns:
      a new IntOrderedSet that holds the given items

    • with

      public static IntOrderedSet with(int item0, int item1, int item2, int item3, int item4, int item5)
      Creates a new IntOrderedSet that holds only the given items, but can be resized.
      Parameters:
      item0 - an int item
      item1 - an int item
      item2 - an int item
      item3 - an int item
      item4 - an int item
      item5 - an int item
      Returns:
      a new IntOrderedSet that holds the given items

    • with

      public static IntOrderedSet with(int item0, int item1, int item2, int item3, int item4, int item5, int item6)
      Creates a new IntOrderedSet that holds only the given items, but can be resized.
      Parameters:
      item0 - an int item
      item1 - an int item
      item2 - an int item
      item3 - an int item
      item4 - an int item
      item5 - an int item
      item6 - an int item
      Returns:
      a new IntOrderedSet that holds the given items

    • with

      public static IntOrderedSet with(int item0, int item1, int item2, int item3, int item4, int item5, int item6, int item7)
      Creates a new IntOrderedSet that holds only the given items, but can be resized.
      Parameters:
      item0 - an int item
      item1 - an int item
      item2 - an int item
      item3 - an int item
      item4 - an int item
      item5 - an int item
      item6 - an int item
      Returns:
      a new IntOrderedSet that holds the given items

    • with

      public static IntOrderedSet with(int... varargs)
      Creates a new IntOrderedSet 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.
      Parameters:
      varargs - an int varargs or int array; remember that varargs allocate
      Returns:
      a new IntOrderedSet that holds the given items

    • parse

      public static IntOrderedSet parse(String str, String delimiter)
      Calls parse(String, String, boolean) with brackets set to false.
      Parameters:
      str - a String that will be parsed in full
      delimiter - the delimiter between items in str
      Returns:
      a new collection parsed from str

    • parse

      public static IntOrderedSet parse(String str, String delimiter, boolean brackets)
      Creates a new collection and fills it by calling PrimitiveCollection.OfInt.addLegible(String, String, 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
      brackets - if true, the first and last chars in str will be ignored
      Returns:
      a new collection parsed from str

    • parse

      public static IntOrderedSet parse(String str, String delimiter, int offset, int length)
      Creates a new collection and fills it by calling PrimitiveCollection.OfInt.addLegible(String, String, int, int) with the given four parameters as-is.
      Parameters:
      str - a String that will have the given section parsed
      delimiter - the delimiter between items in 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