Package com.github.tommyettinger.ds

Class OffsetBitSet

java.lang.Object
com.github.tommyettinger.ds.OffsetBitSet
All Implemented Interfaces:
PrimitiveCollection<Integer>, PrimitiveCollection.OfInt
public class OffsetBitSet extends Object implements PrimitiveCollection.OfInt
A bit set, which can be seen as a set of integer positions greater than some starting number, that has changeable offset, or starting position. If you know the integer positions will all be greater than or equal to some minimum value, such as -128, 0, or 1000, then you can use an offset of that minimum value to save memory. This is important because every possible integer position, whether contained in the bit set or not, takes up one bit of memory (rounded up to a multiple of 32), but positions less than the offset simply aren't stored, and the bit set can grow to fit positions arbitrarily higher than the offset. Allows comparison via bitwise operators to other bit sets, as long as the offsets are the same.
This was originally Bits in libGDX. Many methods have been renamed to more-closely match the Collection API. This has also had the offset functionality added. It was changed from using long to store 64 bits in one value, to int to store 32 bits in one value, because GWT is so slow at handling long.

  • Field Details

    • bits

      protected int[] bits
      The raw bits, each one representing the presence or absence of an integer at a position.

    • offset

      protected int offset
      This is the lowest integer position that this OffsetBitSet can store. If all positions are at least equal to some value, using that for the offset can save space.

    • iterator1

      protected transient OffsetBitSet.OffsetBitSetIterator iterator1

    • iterator2

      protected transient OffsetBitSet.OffsetBitSetIterator iterator2

  • Constructor Details

    • OffsetBitSet

      public OffsetBitSet()
      Creates a bit set with an initial size that can store positions between 0 and 31, inclusive, without needing to resize. This has an offset of 0 and can resize to fit larger positions.

    • OffsetBitSet

      public OffsetBitSet(int bitCapacity)
      Creates a bit set whose initial size is large enough to explicitly represent bits with indices in the range 0 through bitCapacity-1. This has an offset of 0 and can resize to fit larger positions.
      Parameters:
      bitCapacity - the initial size of the bit set

    • OffsetBitSet

      public OffsetBitSet(int start, int end)
      Creates a bit set whose initial size is large enough to explicitly represent bits with indices in the range start through end-1. This has an offset of start and can resize to fit larger positions.
      Parameters:
      start - the lowest value that can be stored in the bit set
      end - the initial end of the range of the bit set

    • OffsetBitSet

      public OffsetBitSet(OffsetBitSet toCopy)
      Creates a bit set from another bit set. This will copy the raw bits and will have the same offset.
      Parameters:
      toCopy - bitset to copy

    • OffsetBitSet

      public OffsetBitSet(PrimitiveCollection.OfInt toCopy)
      Creates a bit set from any primitive int collection, such as a IntList or IntSet. The offset of the new bit set will be the lowest int in the collection, which you should be aware of if you intend to use the bitwise methods such as and(OffsetBitSet) and or(OffsetBitSet).
      Parameters:
      toCopy - the primitive int collection to copy

    • OffsetBitSet

      public OffsetBitSet(int[] toCopy)
      Creates a bit set from an entire int array. The offset of the new bit set will be the lowest int in the collection, which you should be aware of if you intend to use the bitwise methods such as and(OffsetBitSet) and or(OffsetBitSet).
      Parameters:
      toCopy - the non-null int array to copy

    • OffsetBitSet

      public OffsetBitSet(int[] toCopy, int off, int length)
      Creates a bit set from an int array, starting reading at an offset and continuing for a given length. The offset of the new bit set will be the lowest int in the collection, which you should be aware of if you intend to use the bitwise methods such as and(OffsetBitSet) and or(OffsetBitSet).
      Parameters:
      toCopy - the int array to copy
      off - which index to start copying from toCopy
      length - how many items to copy from toCopy

  • Method Details

    • getOffset

      public int getOffset()
      Gets the lowest integer position that this OffsetBitSet can store. If all positions are at least equal to some value, using that for the offset can save space.

    • setOffset

      public void setOffset(int newOffset)
      Changes the offset without considering the previous value. This effectively adds newOffset - getOffset() to every int stored in this, in constant time. This also changes the minimum value in the process.
      Parameters:
      newOffset - the value to use instead of the current offset

    • changeOffset

      public void changeOffset(int addend)
      Adds addend to the current offset, effectively adding to every int stored in this, in constant time. This also changes the minimum value in the process.
      Parameters:
      addend - the value to add to the current offset

    • getRawBits

      public int[] getRawBits()
      This gets the internal int[] used to store bits in bulk. This is not meant for typical usage; it may be useful for serialization or other code that would typically need reflection to access the internals here. This may and often does include padding at the end.
      Returns:
      the raw int array used to store positions, one bit per on and per off position

    • setRawBits

      public void setRawBits(int[] bits)
      This allows setting the internal int[] used to store bits in bulk. This is not meant for typical usage; it may be useful for serialization or other code that would typically need reflection to access the internals here. Be very careful with this method. If bits is null or empty, it is ignored; this is the only error validation this does.
      Parameters:
      bits - a non-null, non-empty int array storing positions, typically obtained from getRawBits()

    • contains

      public boolean contains(int index)
      Returns true if the given position is contained in this bit set. If the index is less than the offset, this returns false.
      Specified by:
      contains in interface PrimitiveCollection.OfInt
      Parameters:
      index - the index of the bit
      Returns:
      whether the bit is set

    • remove

      public boolean remove(int index)
      Deactivates the given position and returns true if the bit set was modified in the process. If the index is less than the offset, this does not modify the bit set and returns false.
      Specified by:
      remove in interface PrimitiveCollection.OfInt
      Parameters:
      index - the index of the bit
      Returns:
      true if this modified the bit set

    • add

      public boolean add(int index)
      Activates the given position and returns true if the bit set was modified in the process. If the index is less than the offset, this does not modify the bit set and returns false.
      Specified by:
      add in interface PrimitiveCollection.OfInt
      Parameters:
      index - the index of the bit
      Returns:
      true if this modified the bit set

    • addAll

      public boolean addAll(int[] indices)
      Specified by:
      addAll in interface PrimitiveCollection.OfInt

    • addAll

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

    • addAll

      public boolean addAll(short[] indices)

    • addAll

      public boolean addAll(short[] indices, int off, int length)

    • addAll

      public boolean addAll(byte[] indices)

    • addAll

      public boolean addAll(byte[] indices, int off, int length)

    • addAll

      public boolean addAll(char[] indices)

    • addAll

      public boolean addAll(char[] indices, int off, int length)

    • addAll

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

    • iterator

      public OffsetBitSet.OffsetBitSetIterator iterator()
      Returns an iterator for the keys in the set. Remove is supported.

      Use the OffsetBitSet.OffsetBitSetIterator constructor for nested or multithreaded iteration.

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

    • activate

      public void activate(int index)
      Sets the given int position to true, unless the position is less than the offset (then it does nothing).
      Parameters:
      index - the index of the bit to set

    • deactivate

      public void deactivate(int index)
      Sets the given int position to false, unless the position is less than the offset (then it does nothing).
      Parameters:
      index - the index of the bit to clear

    • toggle

      public void toggle(int index)
      Changes the given int position from true to false, or from false to true, unless the position is less than the offset (then it does nothing).
      Parameters:
      index - the index of the bit to flip

    • clear

      public void clear()
      Clears the entire bitset, removing all contained ints. Doesn't change the capacity.
      Specified by:
      clear in interface PrimitiveCollection<Integer>

    • numBits

      public int numBits()
      Gets the capacity in bits, including both true and false values, and including any false values that may be after the last contained position, but does not include the offset. Runs in O(1) time.
      Returns:
      the number of bits currently stored, not the highest set bit; doesn't include offset either

    • length

      public int length()
      Returns the "logical extent" of this bitset: the index of the highest set bit in the bitset plus one. Returns zero if the bitset contains no set bits. If this has any set bits, it will return an int at least equal to offset. Runs in O(n) time.
      Returns:
      the logical extent of this bitset

    • size

      public int size()
      Returns the size of the set, or its cardinality; this is the count of distinct activated positions in the set. Note that unlike most Collection types, which typically have O(1) size() runtime, this runs in O(n) time, where n is on the order of the capacity.
      Specified by:
      size in interface PrimitiveCollection<Integer>
      Returns:
      the count of distinct activated positions in the set.

    • notEmpty

      public boolean notEmpty()
      Checks if there are any positions contained in this at all. Run in O(n) time, but usually takes less.
      Specified by:
      notEmpty in interface PrimitiveCollection<Integer>
      Returns:
      true if this bitset contains at least one bit set to true

    • isEmpty

      public boolean isEmpty()
      Checks if there are no positions contained in this at all. Run in O(n) time, but usually takes less.
      Specified by:
      isEmpty in interface PrimitiveCollection<Integer>
      Returns:
      true if this bitset contains no bits that are set to true

    • nextSetBit

      public int nextSetBit(int fromIndex)
      Returns the index of the first bit that is set to true that occurs on or after the specified starting index. If no such bit exists then getOffset() - 1 is returned.
      Parameters:
      fromIndex - the index to start looking at
      Returns:
      the first position that is set to true that occurs on or after the specified starting index

    • nextClearBit

      public int nextClearBit(int fromIndex)
      Returns the index of the first bit that is set to false that occurs on or after the specified starting index. If no such bit exists then numBits() + getOffset() is returned.
      Parameters:
      fromIndex - the index to start looking at
      Returns:
      the first position that is set to true that occurs on or after the specified starting index

    • and

      public void and(OffsetBitSet other)
      Performs a logical AND of this target bit set with the argument bit set. This bit set is modified so that each bit in it has the value true if and only if it both initially had the value true and the corresponding bit in the bit set argument also had the value true. Both this OffsetBitSet and other must have the same offset.
      Parameters:
      other - another OffsetBitSet; must have the same offset as this

    • andNot

      public void andNot(OffsetBitSet other)
      Clears all the bits in this bit set whose corresponding bit is set in the specified bit set. This can be seen as an optimized version of PrimitiveCollection.OfInt.removeAll(OfInt) that only works if both OffsetBitSet objects have the same offset. Both this OffsetBitSet and other must have the same offset.
      Parameters:
      other - another OffsetBitSet; must have the same offset as this

    • or

      public void or(OffsetBitSet other)
      Performs a logical OR of this bit set with the bit set argument. This bit set is modified so that a bit in it has the value true if and only if it either already had the value true or the corresponding bit in the bit set argument has the value true. Both this OffsetBitSet and other must have the same offset.
      Parameters:
      other - another OffsetBitSet; must have the same offset as this

    • xor

      public void xor(OffsetBitSet other)
      Performs a logical XOR of this bit set with the bit set argument. This bit set is modified so that a bit in it has the value true if and only if one of the following statements holds:
      • The bit initially has the value true, and the corresponding bit in the argument has the value false.
      • The bit initially has the value false, and the corresponding bit in the argument has the value true.
      Both this OffsetBitSet and other must have the same offset.
      Parameters:
      other - another OffsetBitSet; must have the same offset as this

    • intersects

      public boolean intersects(OffsetBitSet other)
      Returns true if the specified OffsetBitSet has any bits set to true that are also set to true in this OffsetBitSet. Both this OffsetBitSet and other must have the same offset.
      Parameters:
      other - another OffsetBitSet; must have the same offset as this
      Returns:
      boolean indicating whether this bit set intersects the specified bit set

    • containsAll

      public boolean containsAll(OffsetBitSet other)
      Returns true if this bit set is a super set of the specified set, i.e. it has all bits set to true that are also set to true in the specified OffsetBitSet. If this OffsetBitSet and other have the same offset, this is much more efficient, but it will work even if the offsets are different.
      Parameters:
      other - another OffsetBitSet
      Returns:
      boolean indicating whether this bit set is a super set of the specified set

    • hashCode

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

    • equals

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

    • appendContents

      public StringBuilder appendContents(StringBuilder builder, String delimiter)
      Given a StringBuilder, this appends part of the toString() representation of this OffsetBitSet, without allocating a String. This does not include the opening [ and closing ] chars, and only appends the int positions in this OffsetBitSet, each pair separated by the given delimiter String. You can use this to choose a different delimiter from what toString() uses.
      Parameters:
      builder - a StringBuilder that will be modified in-place and returned
      delimiter - the String that separates every pair of integers in the result
      Returns:
      the given StringBuilder, after modifications

    • appendTo

      public StringBuilder appendTo(StringBuilder builder)
      Given a StringBuilder, this appends the toString() representation of this OffsetBitSet, without allocating a String. This includes the opening [ and closing ] chars; it uses ", " as its delimiter.
      Parameters:
      builder - a StringBuilder that will be modified in-place and returned
      Returns:
      the given StringBuilder, after modifications

    • appendTo

      public <S extends CharSequence & Appendable> S appendTo(S sb, String separator, boolean brackets, IntAppender appender)
      Appends to a StringBuilder from the contents of this PrimitiveCollection, but uses the given IntAppender to convert each item to a customizable representation and append them to a StringBuilder. To use the default String representation, you can use IntAppender.DEFAULT as an appender.
      Specified by:
      appendTo in interface PrimitiveCollection.OfInt
      Type Parameters:
      S - any type that is both a CharSequence and an Appendable, such as StringBuilder, StringBuffer, CharBuffer, or CharList
      Parameters:
      sb - a StringBuilder that this can append to
      separator - how to separate items, such as ", "
      brackets - true to wrap the output in square brackets, or false to omit them
      appender - a function that takes a StringBuilder and an int, and returns the modified StringBuilder
      Returns:
      sb, with the appended items of this PrimitiveCollection

    • toString

      public String toString()
      Overrides:
      toString in class Object

    • with

      public static OffsetBitSet with(int index)
      Static builder for an OffsetBitSet; this overload does not allocate an array for the index/indices, but only takes one index. This always has an offset of 0.
      Parameters:
      index - the one position to place in the built bit set; must be non-negative
      Returns:
      a new OffsetBitSet with the given item

    • with

      public static OffsetBitSet with(int... indices)
      Static builder for an OffsetBitSet; this overload allocates an array for the indices unless given an array already, and can take many indices. This always has an offset of 0.
      Parameters:
      indices - the positions to place in the built bit set; must be non-negative
      Returns:
      a new OffsetBitSet with the given items

    • parse

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