Package arc.struct

Class IntSet

java.lang.Object
arc.struct.IntSet
public class IntSet extends Object
An unordered set that uses int keys. This implementation uses cuckoo hashing using 3 hashes, random walking, and a small stash for problematic keys. No allocation is done except when growing the table size.

This set performs very fast contains and remove (typically O(1), worst case O(log(n))). Add may be a bit slower, depending on hash collisions. Load factors greater than 0.91 greatly increase the chances the set will have to rehash to the next higher POT size.

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    static class 
    IntSet.IntSetIterator
     

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    int
    size
     

  • Constructor Summary

    Constructors
    Constructor
    Description
    IntSet()
    Creates a new set with an initial capacity of 51 and a load factor of 0.8.
    IntSet(int initialCapacity)
    Creates a new set with a load factor of 0.8.
    IntSet(int initialCapacity, float loadFactor)
    Creates a new set with the specified initial capacity and load factor.
    IntSet(IntSet set)
    Creates a new set identical to the specified set.

  • Method Summary

    Modifier and Type
    Method
    Description
    boolean
    add(int key)
    Returns true if the key was not already in the set.
    void
    addAll(int... array)
     
    void
    addAll(int[] array, int offset, int length)
     
    void
    addAll(IntSeq array)
     
    void
    addAll(IntSeq array, int offset, int length)
     
    void
    addAll(IntSet set)
     
    void
    clear()
     
    void
    clear(int maximumCapacity)
    Clears the set and reduces the size of the backing arrays to be the specified capacity if they are larger.
    boolean
    contains(int key)
     
    void
    each(Intc cons)
     
    void
    ensureCapacity(int additionalCapacity)
    Increases the size of the backing array to accommodate the specified number of additional items.
    boolean
    equals(Object obj)
     
    int
    first()
     
    int
    hashCode()
     
    boolean
    isEmpty()
    Returns true if the set is empty.
    IntSet.IntSetIterator
    iterator()
    Returns an iterator for the keys in the set.
    boolean
    remove(int key)
    Returns true if the key was removed.
    void
    shrink(int maximumCapacity)
    Reduces the size of the backing arrays to be the specified capacity or less.
    String
    toString()
     
    static IntSet
    with(int... array)
     

    Methods inherited from class java.lang.Object

    clone, finalize, getClass, notify, notifyAll, wait, wait, wait

  • Field Details

    • size

      public int size

  • Constructor Details

    • IntSet

      public IntSet()
      Creates a new set with an initial capacity of 51 and a load factor of 0.8.

    • IntSet

      public IntSet(int initialCapacity)
      Creates a new set with a load factor of 0.8.
      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.

    • IntSet

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

  • Method Details

    • with

      public static IntSet with(int... array)

    • each

      public void each(Intc cons)

    • add

      public boolean add(int key)
      Returns true if the key was not already in the set.

    • addAll

      public void addAll(IntSeq array)

    • addAll

      public void addAll(IntSeq array, int offset, int length)

    • addAll

      public void addAll(int... array)

    • addAll

      public void addAll(int[] array, int offset, int length)

    • addAll

      public void addAll(IntSet set)

    • remove

      public boolean remove(int key)
      Returns true if the key was removed.

    • isEmpty

      public boolean isEmpty()
      Returns true if the set is empty.

    • shrink

      public void shrink(int maximumCapacity)
      Reduces the size of the backing arrays to be the specified capacity 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 if they are larger.

    • clear

      public void clear()

    • contains

      public boolean contains(int key)

    • first

      public int first()

    • ensureCapacity

      public void ensureCapacity(int additionalCapacity)
      Increases the size of the backing array to accommodate the specified number of additional items. Useful before adding many items to avoid multiple backing array resizes.

    • hashCode

      public int hashCode()
      Overrides:
      hashCode in class Object

    • equals

      public boolean equals(Object obj)
      Overrides:
      equals in class Object

    • toString

      public String toString()
      Overrides:
      toString in class Object

    • iterator

      public IntSet.IntSetIterator iterator()
      Returns an iterator for the keys in the set. Remove is supported. Note that the same iterator instance is returned each time this method is called. Use the IntSet.IntSetIterator constructor for nested or multithreaded iteration.