Package com.github.tommyettinger.ds

Class IntSet

java.lang.Object
com.github.tommyettinger.ds.IntSet
All Implemented Interfaces:
PrimitiveCollection<Integer>, PrimitiveCollection.OfInt, PrimitiveSet<Integer>, PrimitiveSet.SetOfInt
Direct Known Subclasses:
IntOrderedSet
public class IntSet extends Object implements PrimitiveSet.SetOfInt
An unordered set where the items are unboxed ints. No allocation is done except when growing the table size.

This class performs fast contains and remove (typically O(1), worst case O(n) but that is rare in practice). 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.

This implementation uses linear probing with the backward shift algorithm for removal. Linear probing continues to work even when all hashCodes collide; it just works more slowly in that case.

  • Field Details

    • size

      protected int size

    • keyTable

      protected int[] keyTable

    • hasZeroValue

      protected boolean hasZeroValue

    • loadFactor

      protected float loadFactor
      Between 0f (exclusive) and 1f (inclusive, if you're careful), this determines how full the backing table can get before this increases their size. Larger values use less memory but make the data structure slower.

    • threshold

      protected int threshold
      Precalculated value of (int)(keyTable.length * loadFactor), used to determine when to resize.

    • shift

      protected int shift
      Used by place(int) to bit shift the upper bits of an int into a usable range (>= 0 and <= mask). The shift can be negative, which is convenient to match the number of bits in mask: if mask is a 7-bit number, a shift of -7 shifts the upper 7 bits into the lowest 7 positions. This class sets the shift > 32 and < 64, which when used with an int will still move the upper bits of an int to the lower bits due to Java's implicit modulus on shifts.

      mask can also be used to mask the low bits of a number, which may be faster for some hashcodes, if place(int) is overridden.

    • mask

      protected int mask
      A bitmask used to confine hash codes to the size of the table. Must be all 1-bits in its low positions, ie a power of two minus 1. If place(int) is overridden, this can be used instead of shift to isolate usable bits of a hash.

    • hashMultiplier

      protected int hashMultiplier
      Used by place(int) to mix hashCode() results. Changes on every call to resize(int) by default. This should always change when shift changes, meaning, when the backing table resizes. This only needs to be serialized if the full key and value tables are serialized, or if the iteration order should be the same before and after serialization. Iteration order is better handled by using IntOrderedSet.

    • iterator1

      protected transient IntSet.IntSetIterator iterator1

    • iterator2

      protected transient IntSet.IntSetIterator iterator2

  • Constructor Details

    • IntSet

      public IntSet()
      Creates a new set with an initial capacity of Utilities.getDefaultTableCapacity() and a load factor of Utilities.getDefaultLoadFactor().

    • IntSet

      public IntSet(int initialCapacity)
      Creates a new set with a load factor of Utilities.getDefaultLoadFactor().
      Parameters:
      initialCapacity - If not a power of two, it is increased to the next nearest power of two.

    • IntSet

      public IntSet(int initialCapacity, float loadFactor)
      Creates a new set with the specified initial capacity and load factor. This set will hold initialCapacity items before growing the backing table.
      Parameters:
      initialCapacity - If not a power of two, it is increased to the next nearest power of two.
      loadFactor - what fraction of the capacity can be filled before this has to resize; 0 < loadFactor <= 1

    • IntSet

      public IntSet(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

    • IntSet

      public IntSet(IntSet set)
      Creates a new set identical to the specified set.

    • IntSet

      public IntSet(PrimitiveCollection.OfInt coll)
      Creates a new set using all distinct items in the given PrimitiveCollection, such as a IntList or IntObjectMap.Keys.
      Parameters:
      coll - a PrimitiveCollection that will be used in full, except for duplicate items

    • IntSet

      public IntSet(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

    • IntSet

      public IntSet(int[] array)
      Creates a new set containing all the items in the given array.
      Parameters:
      array - an array that will be used in full, except for duplicate items

  • Method Details

    • place

      protected int place(int item)
      Returns an index >= 0 and <= mask for the specified item.
      Parameters:
      item - any int; it is usually mixed and shifted or masked here
      Returns:
      an index between 0 and mask (both inclusive)

    • add

      public boolean add(int key)
      Returns true if the key was not already in the set.
      Specified by:
      add in interface PrimitiveCollection.OfInt

    • addAll

      public boolean addAll(IntList array)

    • addAll

      public boolean addAll(IntList array, int offset, int length)

    • addAll

      public boolean addAll(int... array)
      Specified by:
      addAll in interface PrimitiveCollection.OfInt

    • addAll

      public boolean addAll(int[] array, int offset, int length)
      Specified by:
      addAll in interface PrimitiveCollection.OfInt

    • addAll

      public boolean addAll(IntSet set)

    • addResize

      protected void addResize(int key)
      Skips checks for existing keys, doesn't increment size, doesn't need to handle key 0.

    • remove

      public boolean remove(int key)
      Returns true if the key was removed.
      Specified by:
      remove in interface PrimitiveCollection.OfInt

    • notEmpty

      public boolean notEmpty()
      Returns true if the set has one or more items.
      Specified by:
      notEmpty in interface PrimitiveCollection<Integer>

    • isEmpty

      public boolean isEmpty()
      Returns true if the set is empty.
      Specified by:
      isEmpty in interface PrimitiveCollection<Integer>

    • shrink

      public void shrink(int maximumCapacity)
      Reduces the size of the backing arrays to be the specified capacity / loadFactor, or less. If the capacity is already less, nothing is done. If the set contains more items than the specified capacity, the next highest power of two capacity is used instead.

    • clear

      public void clear(int maximumCapacity)
      Clears the set and reduces the size of the backing arrays to be the specified capacity / loadFactor, if they are larger.

    • clear

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

    • contains

      public boolean contains(int key)
      Specified by:
      contains in interface PrimitiveCollection.OfInt

    • 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
      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.

    • resize

      protected void resize(int newSize)

    • getHashMultiplier

      public int getHashMultiplier()
      Gets the current hashMultiplier, used in place(int) to mix hash codes. If setHashMultiplier(int) is never called, the hashMultiplier will always be drawn from Utilities.GOOD_MULTIPLIERS, with the index equal to 64 - shift.
      Returns:
      the current hashMultiplier

    • setHashMultiplier

      public void setHashMultiplier(int hashMultiplier)
      Sets the hashMultiplier to the given int, which will be made odd if even and always negative (by OR-ing with 0x80000001). This can be any negative, odd int, but should almost always be drawn from Utilities.GOOD_MULTIPLIERS or something like it.
      Parameters:
      hashMultiplier - any int; will be made odd if even.

    • getLoadFactor

      public float getLoadFactor()

    • setLoadFactor

      public void setLoadFactor(float loadFactor)

    • hashCode

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

    • equals

      public boolean equals(Object o)
      Specified by:
      equals in interface PrimitiveCollection<Integer>
      Specified by:
      equals in interface PrimitiveSet<Integer>
      Overrides:
      equals in class Object

    • appendTo

      public StringBuilder appendTo(StringBuilder builder)

    • toString

      public String toString()
      Overrides:
      toString in class Object

    • 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. This indiscriminately removes items from the backing array until the requested newSize is reached, or until the full backing array has had its elements removed.
      This tries to remove from the end of the iteration order, but because the iteration order is not guaranteed by an unordered set, this can remove essentially any item(s) from the set if it is larger than newSize.
      Parameters:
      newSize - the target size to try to reach by removing items, if smaller than the current size

    • iterator

      public IntSet.IntSetIterator iterator()
      Returns an iterator for the keys in the set. Remove is supported.

      Use the IntSet.IntSetIterator constructor for nested or multithreaded iteration.

      Specified by:
      iterator in interface PrimitiveCollection<Integer>
      Specified by:
      iterator in interface PrimitiveCollection.OfInt

    • size

      public int size()
      Specified by:
      size in interface PrimitiveCollection<Integer>

    • with

      public static IntSet 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 IntSet with(int item)
      Creates a new IntSet that holds only the given item, but can be resized.
      Parameters:
      item - an int item
      Returns:
      a new IntSet that holds the given item

    • with

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

    • with

      public static IntSet with(int item0, int item1, int item2)
      Creates a new IntSet 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 IntSet that holds the given items

    • with

      public static IntSet with(int item0, int item1, int item2, int item3)
      Creates a new IntSet 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 IntSet that holds the given items

    • with

      public static IntSet with(int item0, int item1, int item2, int item3, int item4)
      Creates a new IntSet 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 IntSet that holds the given items

    • with

      public static IntSet with(int item0, int item1, int item2, int item3, int item4, int item5)
      Creates a new IntSet 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 IntSet that holds the given items

    • with

      public static IntSet with(int item0, int item1, int item2, int item3, int item4, int item5, int item6)
      Creates a new IntSet 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 IntSet that holds the given items

    • with

      public static IntSet with(int item0, int item1, int item2, int item3, int item4, int item5, int item6, int item7)
      Creates a new IntSet 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 IntSet that holds the given items

    • with

      public static IntSet with(int... varargs)
      Creates a new IntSet 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 IntSet that holds the given items

    • parse

      public static IntSet 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 IntSet 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 IntSet 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