Class NullAwareCharSegmentedSortedArray
java.lang.Object
io.deephaven.engine.table.impl.ssa.NullAwareCharSegmentedSortedArray
- All Implemented Interfaces:
SegmentedSortedArray
,LongSizedDataStructure
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 char values, and then on the corresponding
row key.
-
Nested Class Summary
-
Field Summary
Fields inherited from interface io.deephaven.engine.table.impl.ssa.SegmentedSortedArray
SEGMENTED_SORTED_ARRAY_VALIDATION
-
Constructor Summary
ConstructorDescriptionNullAwareCharSegmentedSortedArray
(int leafSize) Create a NullAwareCharSegmentedSortedArray with the given leafSize. -
Method Summary
Modifier and TypeMethodDescriptionvoid
applyShift
(Chunk<? extends Any> stampChunk, LongChunk<? extends RowKeys> keyChunk, long shiftDelta) void
applyShiftReverse
(Chunk<? extends Any> stampChunk, LongChunk<? extends RowKeys> keyChunk, long shiftDelta) void
forAllKeys
(LongConsumer longConsumer) Call the longConsumer for each of the long row keys in this SegmentedSortedArray.long
getFirst()
long
getLast()
int
void
Insert new valuesToInsert into this SSA.<T extends Any>
intinsertAndGetNextValue
(Chunk<T> valuesToInsert, LongChunk<? extends RowKeys> rowKeysToInsert, WritableChunk<T> nextValue) boolean
iterator
(boolean disallowExactMatch, boolean isRightSide) Create an iterator for this ssa.void
Remove valuesToRemove from this SSA.void
removeAndGetPrior
(Chunk<? extends Any> stampChunk, LongChunk<? extends RowKeys> rowKeysToRemove, WritableLongChunk<? extends RowKeys> priorRedirections) Remove the values and indices referenced in stampChunk and indicesToRemove.long
size()
The size of this data structure.void
validate()
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
Methods inherited from interface io.deephaven.util.datastructures.LongSizedDataStructure
intSize, intSize
-
Constructor Details
-
NullAwareCharSegmentedSortedArray
public NullAwareCharSegmentedSortedArray(int leafSize) Create a NullAwareCharSegmentedSortedArray 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 interfaceSegmentedSortedArray
- Parameters:
valuesToInsert
- the valuesToInsert to insertrowKeysToInsert
- the corresponding indicesToInsert
-
insertAndGetNextValue
public <T extends Any> int insertAndGetNextValue(Chunk<T> valuesToInsert, LongChunk<? extends RowKeys> rowKeysToInsert, WritableChunk<T> nextValue) - Specified by:
insertAndGetNextValue
in interfaceSegmentedSortedArray
-
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 interfaceSegmentedSortedArray
- Parameters:
valuesToRemove
- the valuesToRemove to removerowKeysToRemove
- 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 interfaceSegmentedSortedArray
- Parameters:
stampChunk
- the values to removerowKeysToRemove
- 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 interfaceSegmentedSortedArray
-
applyShiftReverse
public void applyShiftReverse(Chunk<? extends Any> stampChunk, LongChunk<? extends RowKeys> keyChunk, long shiftDelta) - Specified by:
applyShiftReverse
in interfaceSegmentedSortedArray
-
validate
-
forAllKeys
Description copied from interface:SegmentedSortedArray
Call the longConsumer for each of the long row keys in this SegmentedSortedArray.- Specified by:
forAllKeys
in interfaceSegmentedSortedArray
- 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 interfaceLongSizedDataStructure
- Returns:
- The size
-
iterator
public NullAwareCharSegmentedSortedArray.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 advanceisRightSide
- 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 interfaceSegmentedSortedArray
-
isReversed
public boolean isReversed()- Specified by:
isReversed
in interfaceSegmentedSortedArray
-
getFirst
public long getFirst()- Specified by:
getFirst
in interfaceSegmentedSortedArray
- Returns:
- the first row key in this SSA, RowSet.NULL_ROW_KEY when empty.
-
getLast
public long getLast()- Specified by:
getLast
in interfaceSegmentedSortedArray
- Returns:
- the last row key in this SSA, RowSet.NULL_ROW_KEY when empty.
-
makeChecker
- Specified by:
makeChecker
in interfaceSegmentedSortedArray
-