Package com.github.tommyettinger.ds

Class LongSet

java.lang.Object
com.github.tommyettinger.ds.LongSet
All Implemented Interfaces:
PrimitiveCollection<Long>, PrimitiveCollection.OfLong, PrimitiveSet<Long>, PrimitiveSet.SetOfLong
Direct Known Subclasses:
LongOrderedSet
public class LongSet extends Object implements PrimitiveSet.SetOfLong
An unordered set where the items are unboxed longs. 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 long[] 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(long) 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(long) is overridden.

    • mask

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

    • hashMultiplier

      protected int hashMultiplier
      Used by place(long) 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 LongOrderedSet.

    • iterator1

      protected transient LongSet.LongSetIterator iterator1

    • iterator2

      protected transient LongSet.LongSetIterator iterator2

  • Constructor Details

    • LongSet

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

    • LongSet

      public LongSet(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.

    • LongSet

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

    • LongSet

      public LongSet(LongIterator 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

    • LongSet

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

    • LongSet

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

    • LongSet

      public LongSet(long[] 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

    • LongSet

      public LongSet(long[] array)
      Creates a new set containing all of 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(long item)
      Returns an index >= 0 and <= mask for the specified item.
      Parameters:
      item - any long; it is usually mixed or masked here
      Returns:
      an index between 0 and mask (both inclusive)

    • add

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

    • addAll

      public boolean addAll(LongList array)

    • addAll

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

    • addAll

      public boolean addAll(long... array)
      Specified by:
      addAll in interface PrimitiveCollection.OfLong

    • addAll

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

    • addAll

      public boolean addAll(LongSet set)

    • addResize

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

    • remove

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

    • notEmpty

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

    • isEmpty

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

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

    • contains

      public boolean contains(long key)
      Specified by:
      contains in interface PrimitiveCollection.OfLong

    • first

      public long first()
      Description copied from interface: PrimitiveCollection.OfLong
      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.OfLong.iterator(), tries to get the first item, or throws an IllegalStateException if this is empty.
      Specified by:
      first in interface PrimitiveCollection.OfLong
      Returns:
      the first item in this PrimitiveCollection, as produced by PrimitiveCollection.OfLong.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.

    • size

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

    • resize

      protected void resize(int newSize)

    • getHashMultiplier

      public int getHashMultiplier()
      Gets the current hashMultiplier, used in place(long) 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.

    • getTableSize

      public int getTableSize()
      Gets the length of the internal array used to store all items, as well as empty space awaiting more items to be entered. This is also called the capacity.
      Returns:
      the length of the internal array that holds all items

    • getLoadFactor

      public float getLoadFactor()

    • setLoadFactor

      public void setLoadFactor(float loadFactor)

    • hashCode

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

    • equals

      public boolean equals(Object o)
      Specified by:
      equals in interface PrimitiveCollection<Long>
      Specified by:
      equals in interface PrimitiveSet<Long>
      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 LongSet.LongSetIterator iterator()
      Returns an iterator for the keys in the set. Remove is supported.

      Use the LongSet.LongSetIterator constructor for nested or multithreaded iteration.

      Specified by:
      iterator in interface PrimitiveCollection<Long>
      Specified by:
      iterator in interface PrimitiveCollection.OfLong

    • with

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

    • with

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

    • with

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

    • with

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

    • with

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

    • with

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

    • with

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

    • with

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

    • with

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

    • parse

      public static LongSet 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 LongSet parse(String str, String delimiter, boolean brackets)
      Creates a new collection and fills it by calling PrimitiveCollection.OfLong.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 LongSet parse(String str, String delimiter, int offset, int length)
      Creates a new collection and fills it by calling PrimitiveCollection.OfLong.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