Package com.illumon.iris.db.v2.utils.rsp.container

Class BitmapContainer

java.lang.Object
com.illumon.iris.db.v2.utils.rsp.container.Container
com.illumon.iris.db.v2.utils.rsp.container.BitmapContainer
All Implemented Interfaces:
Cloneable
public final class BitmapContainer extends Container implements Cloneable
Simple bitset-like container.

  • Field Details

    • BITMAP_CAPACITY

      protected static final int BITMAP_CAPACITY
      See Also:

    • BITMAP_SIZE_IN_BYTES

      protected static final int BITMAP_SIZE_IN_BYTES
      See Also:

    • USE_BRANCHLESS

      public static final boolean USE_BRANCHLESS
      optimization flag: whether the cardinality of the bitmaps is maintained through branchless operations
      See Also:

  • Constructor Details

    • BitmapContainer

      public BitmapContainer()
      Create a bitmap container with all bits set to false

  • Method Details

    • getReverseShortIterator

      public static ShortAdvanceIterator getReverseShortIterator(long[] bitmap)
      Return a bitmap iterator over this array
      Parameters:
      bitmap - array to be iterated over
      Returns:
      an iterator

    • getShortIterator

      public static ShortIterator getShortIterator(long[] bitmap)
      Return a bitmap iterator over this array
      Parameters:
      bitmap - array to be iterated over
      Returns:
      an iterator

    • singleRange

      public static BitmapContainer singleRange(int start, int end)
      Create a bitmap container with a run of ones from start to end. Caller must ensure that the range isn't so small that an ArrayContainer should have been created instead
      Parameters:
      start - first index
      end - end index (exclusive)
      Returns:
      the new container.

    • add

      public Container add(int begin, int end)
      Description copied from class: Container
      Return a new container with all shorts in [begin,end) added using an unsigned interpretation.
      Specified by:
      add in class Container
      Parameters:
      begin - start of range (inclusive)
      end - end of range (exclusive)
      Returns:
      the new container

    • iset

      public Container iset(short x)
      Description copied from class: Container
      Insert a short to the container. May generate a new container.
      Specified by:
      iset in class Container
      Parameters:
      x - short to be added
      Returns:
      the resulting container

    • set

      public Container set(short x)
      Description copied from class: Container
      Return a new container with the short given as parameter added.
      Specified by:
      set in class Container
      Parameters:
      x - a short to be added
      Returns:
      a new container with x added

    • and

      public ArrayContainer and(ArrayContainer value2)
      Description copied from class: Container
      Computes the bitwise AND of this container with another (intersection). This container as well as the provided container are left unaffected.
      Specified by:
      and in class Container
      Parameters:
      value2 - Another container
      Returns:
      aggregated container

    • and

      public Container and(BitmapContainer value2)
      Description copied from class: Container
      Computes the bitwise AND of this container with another (intersection). This container as well as the provided container are left unaffected.
      Specified by:
      and in class Container
      Parameters:
      value2 - Another container
      Returns:
      aggregated container

    • and

      public Container and(RunContainer x)
      Description copied from class: Container
      Computes the bitwise AND of this container with another (intersection). This container as well as the provided container are left unaffected.
      Specified by:
      and in class Container
      Parameters:
      x - Another container
      Returns:
      aggregated container

    • andRange

      public Container andRange(int rangeStart, int rangeEnd)
      Description copied from class: Container
      Calculate the intersection of this container and a range, in a new container. The existing container is not modified.
      Specified by:
      andRange in class Container
      Parameters:
      rangeStart - start of range
      rangeEnd - end of range, exclusive.
      Returns:
      a new Container containing the intersction of this container and the given range.

    • iandRange

      public Container iandRange(int rangeStart, int rangeEnd)
      Description copied from class: Container
      Calculate the intersection of this container and a range; may overwrite the existing container or return a new one.
      Specified by:
      iandRange in class Container
      Parameters:
      rangeStart - start of range
      rangeEnd - end of range, exclusive.
      Returns:
      a Container containing the intersction of this container and the given range.

    • andNot

      public Container andNot(ArrayContainer value2)
      Description copied from class: Container
      Computes the bitwise ANDNOT of this container with another (difference). This container as well as the provided container are left unaffected.
      Specified by:
      andNot in class Container
      Parameters:
      value2 - Another container
      Returns:
      aggregated container

    • andNot

      public Container andNot(BitmapContainer value2)
      Description copied from class: Container
      Computes the bitwise ANDNOT of this container with another (difference). This container as well as the provided container are left unaffected.
      Specified by:
      andNot in class Container
      Parameters:
      value2 - Another container
      Returns:
      aggregated container

    • andNot

      public Container andNot(RunContainer x)
      Description copied from class: Container
      Computes the bitwise ANDNOT of this container with another (difference). This container as well as the provided container are left unaffected.
      Specified by:
      andNot in class Container
      Parameters:
      x - Another container
      Returns:
      aggregated container

    • cowRef

      public BitmapContainer cowRef()
      Description copied from class: Container
      Get a shared, copy-on-write copy of an existing container. Mutations on the returned container will always return a copy and leave the original container unchanged.

      This operation allows for cheap read-only references to the same values, at the cost of an additional copy for any first mutation.

      Specified by:
      cowRef in class Container
      Returns:
      A copy-on-write reference to the container.

    • deepCopy

      public BitmapContainer deepCopy()
      Description copied from class: Container
      Get a full deep copy of the container in a new container object.
      Specified by:
      deepCopy in class Container
      Returns:
      A copy of the container as a new object.

    • isEmpty

      public boolean isEmpty()
      Description copied from class: Container
      Checks whether the container is empty or not.
      Specified by:
      isEmpty in class Container
      Returns:
      true if the container is empty.

    • isAllOnes

      public boolean isAllOnes()
      Description copied from class: Container
      Checks whether the container spans the full 2^16 range (ie, contains every short value) This is an O(1) operation in all container types (some do not cache cardinality).
      Specified by:
      isAllOnes in class Container
      Returns:
      true if the container does not miss any single short value.

    • cardinalityInRange

      protected int cardinalityInRange(int start, int end)

    • updateCardinality

      protected void updateCardinality(int prevOnes, int newOnes)

    • contains

      public boolean contains(short i)
      Description copied from class: Container
      Checks whether the contain contains the provided value
      Specified by:
      contains in class Container
      Parameters:
      i - value to check
      Returns:
      whether the value is in the container

    • contains

      public boolean contains(int rangeStart, int rangeEnd)
      Description copied from class: Container
      Checks whether the container contains the entire range
      Specified by:
      contains in class Container
      Parameters:
      rangeStart - the inclusive lower bound of the range
      rangeEnd - the exclusive upper bound of the range
      Returns:
      true if the container contains the range

    • contains

      protected boolean contains(BitmapContainer bitmapContainer)
      Specified by:
      contains in class Container

    • contains

      protected boolean contains(RunContainer runContainer)
      Specified by:
      contains in class Container

    • contains

      protected boolean contains(ArrayContainer arrayContainer)
      Specified by:
      contains in class Container

    • bitValue

      protected long bitValue(short i)

    • fillArray

      protected void fillArray(short[] array)
      Fill the array with set bits
      Parameters:
      array - container (should be sufficiently large)

    • iflip

      public Container iflip(short x)
      Description copied from class: Container
      Add a short to the container if it is not present, otherwise remove it. May generate a new container.
      Specified by:
      iflip in class Container
      Parameters:
      x - short to be added
      Returns:
      the new container

    • getCardinality

      public int getCardinality()
      Description copied from class: Container
      Computes the distinct number of short values in the container. Can be expected to run in constant time.
      Specified by:
      getCardinality in class Container
      Returns:
      the cardinality

    • getReverseShortIterator

      public ShortAdvanceIterator getReverseShortIterator()
      Description copied from class: Container
      Iterator to visit the short values in the container in descending order.
      Specified by:
      getReverseShortIterator in class Container
      Returns:
      iterator

    • getShortIterator

      public ShortIterator getShortIterator()
      Description copied from class: Container
      Iterator to visit the short values in the container in ascending order.
      Specified by:
      getShortIterator in class Container
      Returns:
      iterator

    • getShortBatchIterator

      public ContainerShortBatchIterator getShortBatchIterator(int skipCount)
      Description copied from class: Container
      Gets an iterator to visit the contents of the container in batches of short values
      Specified by:
      getShortBatchIterator in class Container
      Parameters:
      skipCount - number of elements to skip from the start of the container.
      Returns:
      iterator

    • getShortRangeIterator

      public SearchRangeIterator getShortRangeIterator(int initialSeek)
      Description copied from class: Container
      Iterator to visit the short values in container in [start, end) ranges, in increasing order of start values.
      Specified by:
      getShortRangeIterator in class Container
      Returns:
      iterator

    • iadd

      public Container iadd(int begin, int end)
      Description copied from class: Container
      Add all shorts in [begin,end) using an unsigned interpretation. May generate a new container.
      Specified by:
      iadd in class Container
      Parameters:
      begin - start of range (inclusive)
      end - end of range (exclusive)
      Returns:
      the new container

    • iappend

      public Container iappend(int begin, int end)
      Description copied from class: Container
      Add all shorts in [begin,end) using an unsigned interpretation. May generate a new container. The beginning of the range should be strictly greater than the last value already present in the container, if there is one.
      Specified by:
      iappend in class Container
      Parameters:
      begin - start of range (inclusive)
      end - end of range (exclusive)
      Returns:
      the new container

    • iand

      public Container iand(ArrayContainer b2)
      Description copied from class: Container
      Computes the in-place bitwise AND of this container with another (intersection). The current container is generally modified, whereas the provided container (x) is unaffected. May generate a new container.
      Specified by:
      iand in class Container
      Parameters:
      b2 - Another container
      Returns:
      aggregated container

    • iand

      public Container iand(BitmapContainer b2)
      Description copied from class: Container
      Computes the in-place bitwise AND of this container with another (intersection). The current container is generally modified, whereas the provided container (x) is unaffected. May generate a new container.
      Specified by:
      iand in class Container
      Parameters:
      b2 - Another container
      Returns:
      aggregated container

    • iand

      public Container iand(RunContainer x)
      Description copied from class: Container
      Computes the in-place bitwise AND of this container with another (intersection). The current container is generally modified, whereas the provided container (x) is unaffected. May generate a new container.
      Specified by:
      iand in class Container
      Parameters:
      x - Another container
      Returns:
      aggregated container

    • iandNot

      public Container iandNot(ArrayContainer b2)
      Description copied from class: Container
      Computes the in-place bitwise ANDNOT of this container with another (difference). The current container is generally modified, whereas the provided container (x) is unaffected. May generate a new container.
      Specified by:
      iandNot in class Container
      Parameters:
      b2 - Another container
      Returns:
      aggregated container

    • iandNot

      public Container iandNot(BitmapContainer b2)
      Description copied from class: Container
      Computes the in-place bitwise ANDNOT of this container with another (difference). The current container is generally modified, whereas the provided container (x) is unaffected. May generate a new container.
      Specified by:
      iandNot in class Container
      Parameters:
      b2 - Another container
      Returns:
      aggregated container

    • iandNot

      public Container iandNot(RunContainer x)
      Description copied from class: Container
      Computes the in-place bitwise ANDNOT of this container with another (difference). The current container is generally modified, whereas the provided container (x) is unaffected. May generate a new container.
      Specified by:
      iandNot in class Container
      Parameters:
      x - Another container
      Returns:
      aggregated container

    • inot

      public Container inot(int firstOfRange, int lastOfRange)
      Description copied from class: Container
      Computes the in-place bitwise NOT of this container (complement). Only those bits within the range are affected. The current container is generally modified. May generate a new container.
      Specified by:
      inot in class Container
      Parameters:
      firstOfRange - beginning of range (inclusive); 0 is beginning of this container.
      lastOfRange - ending of range (exclusive)
      Returns:
      (partially) complemented container

    • ior

      public Container ior(ArrayContainer value2)
      Description copied from class: Container
      Computes the in-place bitwise OR of this container with another (union). The current container is generally modified, whereas the provided container (x) is unaffected. May generate a new container.
      Specified by:
      ior in class Container
      Parameters:
      value2 - Another container
      Returns:
      aggregated container

    • ior

      public Container ior(BitmapContainer b2)
      Description copied from class: Container
      Computes the in-place bitwise OR of this container with another (union). The current container is generally modified, whereas the provided container (x) is unaffected. May generate a new container.
      Specified by:
      ior in class Container
      Parameters:
      b2 - Another container
      Returns:
      aggregated container

    • ior

      public Container ior(RunContainer x)
      Description copied from class: Container
      Computes the in-place bitwise OR of this container with another (union). The current container is generally modified, whereas the provided container (x) is unaffected. May generate a new container.
      Specified by:
      ior in class Container
      Parameters:
      x - Another container
      Returns:
      aggregated container

    • iremove

      public Container iremove(int begin, int end)
      Description copied from class: Container
      Remove shorts in [begin,end) using an unsigned interpretation. May generate a new container.
      Specified by:
      iremove in class Container
      Parameters:
      begin - start of range (inclusive)
      end - end of range (exclusive)
      Returns:
      the new container

    • ixor

      public Container ixor(ArrayContainer value2)
      Description copied from class: Container
      Computes the in-place bitwise XOR of this container with another (symmetric difference). The current container is generally modified, whereas the provided container (x) is unaffected. May generate a new container.
      Specified by:
      ixor in class Container
      Parameters:
      value2 - Another container
      Returns:
      aggregated container

    • ixor

      public Container ixor(BitmapContainer b2)
      Description copied from class: Container
      Computes the in-place bitwise XOR of this container with another (symmetric difference). The current container is generally modified, whereas the provided container (x) is unaffected. May generate a new container.
      Specified by:
      ixor in class Container
      Parameters:
      b2 - Another container
      Returns:
      aggregated container

    • ixor

      public Container ixor(RunContainer x)
      Description copied from class: Container
      Computes the in-place bitwise XOR of this container with another (symmetric difference). The current container is generally modified, whereas the provided container (x) is unaffected. May generate a new container.
      Specified by:
      ixor in class Container
      Parameters:
      x - Another container
      Returns:
      aggregated container

    • loadData

      protected void loadData(ArrayContainer arrayContainer)

    • nextSetBit

      public int nextSetBit(int i)
      Find the index of the next set bit greater or equal to i, returns -1 if none found.
      Parameters:
      i - starting index
      Returns:
      index of the next set bit

    • not

      public Container not(int firstOfRange, int lastOfRange)
      Description copied from class: Container
      Computes the bitwise NOT of this container (complement). Only those bits within the range are affected. This is equivalent to an xor with a range of ones for the given range. The current container is left unaffected.
      Specified by:
      not in class Container
      Parameters:
      firstOfRange - beginning of range (inclusive); 0 is beginning of this container.
      lastOfRange - ending of range (exclusive)
      Returns:
      (partially) complemented container

    • or

      public Container or(ArrayContainer value2)
      Description copied from class: Container
      Computes the bitwise OR of this container with another (union). This container as well as the provided container are left unaffected.
      Specified by:
      or in class Container
      Parameters:
      value2 - Another container
      Returns:
      aggregated container

    • or

      public Container or(BitmapContainer value2)
      Description copied from class: Container
      Computes the bitwise OR of this container with another (union). This container as well as the provided container are left unaffected.
      Specified by:
      or in class Container
      Parameters:
      value2 - Another container
      Returns:
      aggregated container

    • or

      public Container or(RunContainer x)
      Description copied from class: Container
      Computes the bitwise OR of this container with another (union). This container as well as the provided container are left unaffected.
      Specified by:
      or in class Container
      Parameters:
      x - Another container
      Returns:
      aggregated container

    • prevSetBit

      public int prevSetBit(int i)
      Find the index of the previous set bit less than or equal to i, returns -1 if none found.
      Parameters:
      i - starting index
      Returns:
      index of the previous set bit

    • rank

      public int rank(short lowbits)
      Description copied from class: Container
      Rank returns the number of integers that are smaller or equal to x (Rank(infinity) would be GetCardinality()).
      Specified by:
      rank in class Container
      Parameters:
      lowbits - upper limit
      Returns:
      the rank

    • remove

      public Container remove(int begin, int end)
      Description copied from class: Container
      Return a new container with all shorts in [begin,end) remove using an unsigned interpretation.
      Specified by:
      remove in class Container
      Parameters:
      begin - start of range (inclusive)
      end - end of range (exclusive)
      Returns:
      the new container

    • iunset

      public Container iunset(short v)
      Description copied from class: Container
      Create a new container with the short removed.
      Specified by:
      iunset in class Container
      Parameters:
      v - to be removed
      Returns:
      New container without x.

    • unset

      public Container unset(short v)
      Description copied from class: Container
      Remove the short from this container. May create a new container.
      Specified by:
      unset in class Container
      Parameters:
      v - to be removed
      Returns:
      resulting container.

    • runOptimize

      public Container runOptimize()
      Description copied from class: Container
      Convert to RunContainers, when the result is smaller. Overridden by RunContainer to possibility switch from RunContainer to a smaller alternative. Overridden by BitmapContainer with a more efficient approach.
      Specified by:
      runOptimize in class Container
      Returns:
      the new container

    • select

      public short select(int j)
      Description copied from class: Container
      Return the jth value
      Specified by:
      select in class Container
      Parameters:
      j - index of the value
      Returns:
      the value

    • select

      public Container select(int startRank, int endRank)
      Description copied from class: Container
      Returns a new container with all values between ranks startPos and endPos.
      Specified by:
      select in class Container
      Parameters:
      startRank - rank for the start of the range
      endRank - rank for the end of the range, exclusive
      Returns:
      a new Container with all the values between ranks [startPos, endPos)

    • find

      public int find(short x)
      Description copied from class: Container
      Searches for the specified short value
      Specified by:
      find in class Container
      Parameters:
      x - value to search for
      Returns:
      Relative position of the value in the sorted set of elements in this container, in the range [0 .. cardinality - 1]. If not present, (-(insertion point) - 1) similar to Array.binarySearch.

      For values of x that Container.contains(short) returns true, this method returns the same value as Container.rank(short).

    • selectRanges

      public void selectRanges(RangeConsumer outValues, RangeIterator inPositions)
      Description copied from class: Container
      As select but for all the positions in a range.
      Specified by:
      selectRanges in class Container
      Parameters:
      outValues - accept is called in this consumer for each resulting range.
      inPositions - input iterator that provides the position ranges.

    • findRanges

      public boolean findRanges(RangeConsumer outPositions, RangeIterator inValues, int maxPos)
      Description copied from class: Container
      As find but for all the values in a range.
      Specified by:
      findRanges in class Container
      Parameters:
      outPositions - accept is called in this consumer for each resulting position range.
      inValues - input iterator that provides the key ranges; these must each exist in the container.
      maxPos - maximum position to add to outPositions; values of position > maxPos are not added.
      Returns:
      true if maxPos was reached, false otherwise.

    • toArrayContainer

      public ArrayContainer toArrayContainer()
      Copies the data to an array container
      Returns:
      the array container

    • toRunContainer

      public RunContainer toRunContainer()

    • trim

      public void trim()
      Description copied from class: Container
      If possible, recover wasted memory.
      Specified by:
      trim in class Container

    • xor

      public Container xor(ArrayContainer value2)
      Description copied from class: Container
      Computes the bitwise XOR of this container with another (symmetric difference). This container as well as the provided container are left unaffected.
      Specified by:
      xor in class Container
      Parameters:
      value2 - Another container
      Returns:
      aggregated container

    • xor

      public Container xor(BitmapContainer value2)
      Description copied from class: Container
      Computes the bitwise XOR of this container with another (symmetric difference). This container as well as the provided container are left unaffected.
      Specified by:
      xor in class Container
      Parameters:
      value2 - Another container
      Returns:
      aggregated container

    • xor

      public Container xor(RunContainer x)
      Description copied from class: Container
      Computes the bitwise XOR of this container with another (symmetric difference). This container as well as the provided container are left unaffected.
      Specified by:
      xor in class Container
      Parameters:
      x - Another container
      Returns:
      aggregated container

    • forEach

      public boolean forEach(ShortConsumer sc)
      Description copied from class: Container
      Iterate through the values of this container in order and pass them along to the ShortConsumer.
      Specified by:
      forEach in class Container
      Parameters:
      sc - a shortConsumer
      Returns:
      false if the consumer returned false at some point, true otherwise.

    • forEach

      public boolean forEach(int rankOffset, ShortConsumer sc)
      Description copied from class: Container
      Like forEach, but skipping the first rankOffset elements.
      Specified by:
      forEach in class Container
      Parameters:
      rankOffset - the position (rank) offset of the element where to start
      sc - a ShortConsumer
      Returns:
      false if the consumer returned false at some point, true otherwise.

    • forEachRange

      public boolean forEachRange(int rankOffset, ShortRangeConsumer sc)
      Specified by:
      forEachRange in class Container

    • toBitmapContainer

      public BitmapContainer toBitmapContainer()
      Description copied from class: Container
      Convert the current container to a BitmapContainer, if a conversion is needed. If the container is already a bitmap, the container is returned unchanged.

      When multiple container "merge" operations are done it might be more efficient to convert to bitmap first, and then at the end convert to the efficient container type, to avoid multiple container type conversions, since bitmap can always stay a bitmap.

      Specified by:
      toBitmapContainer in class Container
      Returns:
      a bitmap container

    • nextValue

      public int nextValue(short fromValue)
      Description copied from class: Container
      Gets the first value greater than or equal to the lower bound, or -1 if no such value exists.
      Specified by:
      nextValue in class Container
      Parameters:
      fromValue - the lower bound (inclusive)
      Returns:
      the next value

    • first

      public int first()
      Description copied from class: Container
      Get the first integer held in the container
      Specified by:
      first in class Container
      Returns:
      the first integer in the container

    • last

      public int last()
      Description copied from class: Container
      Get the last integer held in the container
      Specified by:
      last in class Container
      Returns:
      the last integer in the container

    • subsetOf

      public boolean subsetOf(ArrayContainer c)
      Specified by:
      subsetOf in class Container
      Parameters:
      c - Another container
      Returns:
      true if every key in this container is also a key in x.

    • subsetOf

      public boolean subsetOf(BitmapContainer c)
      Specified by:
      subsetOf in class Container
      Parameters:
      c - Another container
      Returns:
      true if every key in this container is also a key in x.

    • subsetOf

      public boolean subsetOf(RunContainer c)
      Specified by:
      subsetOf in class Container
      Parameters:
      c - Another container
      Returns:
      true if every key in this container is also a key in x.

    • overlapsRange

      public boolean overlapsRange(int rangeStart, int rangeEnd)
      Specified by:
      overlapsRange in class Container
      Parameters:
      rangeStart - the beginning of the range, as an int.
      rangeEnd - the end of the range (exclusive), as an int.
      Returns:
      true if there is any element in this container in the range provided.

    • overlaps

      public boolean overlaps(ArrayContainer c)
      Specified by:
      overlaps in class Container
      Parameters:
      c - Another container
      Returns:
      true if at least one key in this container is also a key in x.

    • overlaps

      public boolean overlaps(BitmapContainer c)
      Specified by:
      overlaps in class Container
      Parameters:
      c - Another container
      Returns:
      true if at least one key in this container is also a key in x.

    • overlaps

      public boolean overlaps(RunContainer c)
      Specified by:
      overlaps in class Container
      Parameters:
      c - Another container
      Returns:
      true if at least one key in this container is also a key in x.

    • setCopyOnWrite

      public void setCopyOnWrite()
      Specified by:
      setCopyOnWrite in class Container

    • bytesAllocated

      public int bytesAllocated()
      Specified by:
      bytesAllocated in class Container
      Returns:
      The allocated size in bytes of the underlying array backing store used by this container.

    • bytesUsed

      public int bytesUsed()
      Specified by:
      bytesUsed in class Container
      Returns:
      The size in bytes of the used portion out of the total allocated bytes for the underlying array backing store used by this container.

    • toLargeContainer

      public Container toLargeContainer()

    • validate

      public void validate()
      Specified by:
      validate in class Container

    • isShared

      public boolean isShared()
      Specified by:
      isShared in class Container