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

Class RunContainer

java.lang.Object
com.illumon.iris.db.v2.utils.rsp.container.Container
com.illumon.iris.db.v2.utils.rsp.container.RunContainer
public final class RunContainer extends Container
This container takes the form of runs of consecutive values (effectively, run-length encoding).

Adding and removing content from this container might make it wasteful so regular calls to "runOptimize" might be warranted.

  • Constructor Details

    • RunContainer

      public RunContainer()
      Create a container with default capacity

    • RunContainer

      public RunContainer(RunContainer rc)

    • RunContainer

      protected RunContainer(ArrayContainer arr, int nbrRunsCapacity)

    • RunContainer

      public RunContainer(int start, int end)
      Create an run container with a run of ones from start to end.
      Parameters:
      start - first index
      end - last index (range is exclusive)

    • RunContainer

      public RunContainer(int start1, int end1, int start2, int end2)

    • RunContainer

      protected RunContainer(BitmapContainer bc)

    • RunContainer

      public RunContainer(int runsCapacity)
      Create an array container with specified initial capacity
      Parameters:
      runsCapacity - The initial capacity of the container in number of runs.

  • Method Details

    • sizeInBytes

      protected static int sizeInBytes(int numberOfRuns)

    • select

      public static RunContainer select(RunContainer src, int startRank, int endRank)

    • makeByWrapping

      public static RunContainer makeByWrapping(short[] valueslength, int nbrruns, int cardinality)
      Construct a new RunContainer using the provided array. The container takes ownership of the array.
      Parameters:
      valueslength - array with valid runs, in increasing unsigned short order. The container takes ownership of this array.
      nbrruns - number of runs (the array should contain 2*n elements).
      cardinality - total cardinality in the runs.

    • 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

    • 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 k)
      Description copied from class: Container
      Insert a short to the container. May generate a new container.
      Specified by:
      iset in class Container
      Parameters:
      k - short to be added
      Returns:
      the resulting container

    • set

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

    • and

      public Container and(ArrayContainer 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

    • and

      public Container and(BitmapContainer 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

    • 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 start, int end)
      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:
      start - start of range
      end - end of range, exclusive.
      Returns:
      a new Container containing the intersction of this container and the given range.

    • iandRange

      public Container iandRange(int start, int end)
      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:
      start - start of range
      end - end of range, exclusive.
      Returns:
      a Container containing the intersction of this container and the given range.

    • andNot

      public Container andNot(ArrayContainer 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

    • andNot

      public Container andNot(BitmapContainer 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

    • 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

    • clear

      public void clear()

    • deepCopy

      public RunContainer 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.

    • cowRef

      public RunContainer 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.

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

    • isSingleElement

      public boolean isSingleElement()
      Description copied from class: Container
      Checks whether the container has exactly one element (meaningful since cardinality may not be cached in some Container types, eg, Run).
      Overrides:
      isSingleElement in class Container
      Returns:
      true if the container contains exactly one element, false otherwise.

    • contains

      public boolean contains(short x)
      Description copied from class: Container
      Checks whether the contain contains the provided value
      Specified by:
      contains in class Container
      Parameters:
      x - 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(RunContainer runContainer)
      Specified by:
      contains in class Container

    • contains

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

    • contains

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

    • ensureCapacity

      protected void ensureCapacity(int minNbRuns)

    • 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

    • getLength

      public short getLength(int index)
      Gets the length of the run at the index.
      Parameters:
      index - the index of the run.
      Returns:
      the length of the run at the index.
      Throws:
      ArrayIndexOutOfBoundsException - if index is negative or larger than the index of the last run.

    • getLengthAsInt

      public int getLengthAsInt(int index)

    • 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

    • getValue

      public short getValue(int index)
      Gets the value of the first element of the run at the index.
      Parameters:
      index - the index of the run.
      Returns:
      the value of the first element of the run at the index.
      Throws:
      ArrayIndexOutOfBoundsException - if index is negative or larger than the index of the last run.

    • getValueAsInt

      public int getValueAsInt(int index)

    • iaddUnsafe

      public RunContainer iaddUnsafe(int begin, int end, int searchBeginRunIndex)

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

    • iand

      public Container iand(BitmapContainer 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

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

    • iandNot

      public Container iandNot(BitmapContainer 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

    • 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 rangeStart, int rangeEnd)
      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:
      rangeStart - beginning of range (inclusive); 0 is beginning of this container.
      rangeEnd - ending of range (exclusive)
      Returns:
      (partially) complemented container

    • ior

      public Container ior(ArrayContainer 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

    • ior

      public Container ior(BitmapContainer 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

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

    • ixor

      public Container ixor(BitmapContainer 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

    • 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

    • not

      public Container not(int rangeStart, int rangeEnd)
      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:
      rangeStart - beginning of range (inclusive); 0 is beginning of this container.
      rangeEnd - ending of range (exclusive)
      Returns:
      (partially) complemented container

    • numberOfRuns

      public int numberOfRuns()

    • or

      public Container or(ArrayContainer 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

    • or

      public Container or(BitmapContainer 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

    • 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

    • 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

    • unset

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

    • iunset

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

    • runOptimize

      public Container runOptimize()
      Convert to Array or Bitmap container if the serialized form would be shorter. Exactly the same functionality as toEfficientContainer.
      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 RunContainer 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.

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

    • xor

      public Container xor(BitmapContainer 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

    • 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