Package com.github.tommyettinger.ds

Class LongOrderedSet

java.lang.Object
com.github.tommyettinger.ds.LongSet
com.github.tommyettinger.ds.LongOrderedSet
All Implemented Interfaces:
Arrangeable, Ordered.OfLong, PrimitiveCollection<Long>, PrimitiveCollection.OfLong, PrimitiveSet<Long>, PrimitiveSet.SetOfLong
public class LongOrderedSet extends LongSet implements Ordered.OfLong
A LongSet that also stores keys in a LongList 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. LongSet.place(long) 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 LongList items

  • Constructor Details

    • LongOrderedSet

      public LongOrderedSet()

    • LongOrderedSet

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

    • LongOrderedSet

      public LongOrderedSet(int initialCapacity, float loadFactor)

    • LongOrderedSet

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

    • LongOrderedSet

      public LongOrderedSet(int initialCapacity, OrderType ordering)

    • LongOrderedSet

      public LongOrderedSet(int initialCapacity)

    • LongOrderedSet

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

    • LongOrderedSet

      public LongOrderedSet(LongOrderedSet set, OrderType ordering)

    • LongOrderedSet

      public LongOrderedSet(LongOrderedSet set)

    • LongOrderedSet

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

    • LongOrderedSet

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

    • LongOrderedSet

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

    • LongOrderedSet

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

    • LongOrderedSet

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

    • LongOrderedSet

      public LongOrderedSet(Ordered.OfLong 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.OfLong
      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

    • LongOrderedSet

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

    • LongOrderedSet

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

    • LongOrderedSet

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

    • LongOrderedSet

      public LongOrderedSet(long[] 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(long key)
      Description copied from class: LongSet
      Returns true if the key was not already in the set.
      Specified by:
      add in interface PrimitiveCollection.OfLong
      Overrides:
      add in class LongSet

    • add

      public boolean add(int index, long 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 long 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.OfLong 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.OfLong 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 LongSet.addAll(LongSet) does

    • addAll

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

    • remove

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

    • removeAt

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

    • 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
      Overrides:
      first in class LongSet
      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.
      Overrides:
      ensureCapacity in class LongSet
      Parameters:
      additionalCapacity - how many additional items this should be able to hold without resizing (probably)

    • alter

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

    • clear

      public void clear(int maximumCapacity)
      Description copied from class: LongSet
      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 LongSet

    • clear

      public void clear()
      Specified by:
      clear in interface PrimitiveCollection<Long>
      Overrides:
      clear in class LongSet

    • order

      public LongList 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.OfLong
      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.

    • iterator

      public LongSet.LongSetIterator iterator()
      Iterates through items in the same order as order(). Reuses one of two iterators, and does not permit nested iteration; use LongOrderedSetIterator(LongOrderedSet) to nest iterators.
      Specified by:
      iterator in interface PrimitiveCollection<Long>
      Specified by:
      iterator in interface PrimitiveCollection.OfLong
      Overrides:
      iterator in class LongSet
      Returns:
      an Iterator over the T items in this, in order

    • hashCode

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

    • toString

      public String toString(String separator)
      Description copied from interface: PrimitiveCollection.OfLong
      Delegates to PrimitiveCollection.OfLong.toString(String, boolean) with the given separator and without brackets.
      Specified by:
      toString in interface PrimitiveCollection.OfLong
      Parameters:
      separator - how to separate items, such as ", "
      Returns:
      a new String representing this PrimitiveCollection

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

    • with

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

    • with

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

    • with

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

    • with

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

    • with

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

    • with

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

    • with

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

    • with

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

    • with

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

    • parse

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