Package io.deephaven.engine.table.impl.ssa

Class ByteReverseSegmentedSortedArray

java.lang.Object
io.deephaven.engine.table.impl.ssa.ByteReverseSegmentedSortedArray
All Implemented Interfaces:
SegmentedSortedArray, LongSizedDataStructure
public final class ByteReverseSegmentedSortedArray extends Object implements SegmentedSortedArray
For keeping track of incremental states of sorted values, we would ideally like to hold them in an Array or a Chunk; with parallel row keys. However, if we just put them in an array we can not insert or remove values without unnecessarily shifting everything. The segmented array allows us to either insert or remove elements and only shift values in a "leaf" block and possibly a "directory" block. It can be thought of as similar to a single-level b+ tree with only keys. We must be totally ordered, which is accomplished by sorting on the byte values, and then on the corresponding row key.

  • Constructor Details

    • ByteReverseSegmentedSortedArray

      public ByteReverseSegmentedSortedArray(int leafSize)
      Create a ByteReverseSegmentedSortedArray with the given leafSize.
      Parameters:
      leafSize - the maximumSize for any leaf

  • Method Details

    • insert

      public void insert(Chunk<? extends Any> valuesToInsert, LongChunk<? extends RowKeys> rowKeysToInsert)
      Description copied from interface: SegmentedSortedArray
      Insert new valuesToInsert into this SSA. The valuesToInsert to insert must be sorted.
      Specified by:
      insert in interface SegmentedSortedArray
      Parameters:
      valuesToInsert - the valuesToInsert to insert
      rowKeysToInsert - the corresponding indicesToInsert

    • insertAndGetNextValue

      public <T extends Any> int insertAndGetNextValue(Chunk<T> valuesToInsert, LongChunk<? extends RowKeys> rowKeysToInsert, WritableChunk<T> nextValue)
      Specified by:
      insertAndGetNextValue in interface SegmentedSortedArray

    • remove

      public void remove(Chunk<? extends Any> valuesToRemove, LongChunk<? extends RowKeys> rowKeysToRemove)
      Description copied from interface: SegmentedSortedArray
      Remove valuesToRemove from this SSA. The valuesToRemove to remove must be sorted.
      Specified by:
      remove in interface SegmentedSortedArray
      Parameters:
      valuesToRemove - the valuesToRemove to remove
      rowKeysToRemove - the corresponding indices

    • removeAndGetPrior

      public void removeAndGetPrior(Chunk<? extends Any> stampChunk, LongChunk<? extends RowKeys> rowKeysToRemove, WritableLongChunk<? extends RowKeys> priorRedirections)
      Description copied from interface: SegmentedSortedArray
      Remove the values and indices referenced in stampChunk and indicesToRemove. Fill priorRedirections with the redirection value immediately preceding the removed value.
      Specified by:
      removeAndGetPrior in interface SegmentedSortedArray
      Parameters:
      stampChunk - the values to remove
      rowKeysToRemove - the indices (parallel to the values)
      priorRedirections - the output prior redirections (parallel to valeus/indices)

    • applyShift

      public void applyShift(Chunk<? extends Any> stampChunk, LongChunk<? extends RowKeys> keyChunk, long shiftDelta)
      Specified by:
      applyShift in interface SegmentedSortedArray

    • applyShiftReverse

      public void applyShiftReverse(Chunk<? extends Any> stampChunk, LongChunk<? extends RowKeys> keyChunk, long shiftDelta)
      Specified by:
      applyShiftReverse in interface SegmentedSortedArray

    • validate

      @VisibleForTesting public void validate()

    • forAllKeys

      public void forAllKeys(LongConsumer longConsumer)
      Description copied from interface: SegmentedSortedArray
      Call the longConsumer for each of the long row keys in this SegmentedSortedArray.
      Specified by:
      forAllKeys in interface SegmentedSortedArray
      Parameters:
      longConsumer - the long consumer to call

    • size

      public long size()
      Description copied from interface: LongSizedDataStructure
      The size of this data structure.
      Specified by:
      size in interface LongSizedDataStructure
      Returns:
      The size

    • iterator

      public ByteReverseSegmentedSortedArray.Iterator iterator(boolean disallowExactMatch, boolean isRightSide)
      Create an iterator for this ssa.
      Parameters:
      disallowExactMatch - if true, then we are operating as a right side that does not allow equal matches, but only lt matches when calling advance
      isRightSide - if true, then we ignore eqaual values; which is suitable for right side processing. We also start off with the first value. When false, we do not advance while equal, and we start off one before the first value (so that next must be called)
      Returns:
      an iterator for this SSA

    • getNodeSize

      public int getNodeSize()
      Specified by:
      getNodeSize in interface SegmentedSortedArray

    • isReversed

      public boolean isReversed()
      Specified by:
      isReversed in interface SegmentedSortedArray

    • getFirst

      public long getFirst()
      Specified by:
      getFirst in interface SegmentedSortedArray
      Returns:
      the first row key in this SSA, RowSet.NULL_ROW_KEY when empty.

    • getLast

      public long getLast()
      Specified by:
      getLast in interface SegmentedSortedArray
      Returns:
      the last row key in this SSA, RowSet.NULL_ROW_KEY when empty.

    • makeChecker

      public SsaChecker makeChecker()
      Specified by:
      makeChecker in interface SegmentedSortedArray