Package com.illumon.iris.db.v2.ssa

Class DoubleReverseSegmentedSortedArray

java.lang.Object

com.illumon.iris.db.v2.ssa.DoubleReverseSegmentedSortedArray

All Implemented Interfaces:

LongSizedDataStructure, SegmentedSortedArray

public final class DoubleReverseSegmentedSortedArray
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 index 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 double values, and then on the corresponding index key.

Field Summary

Fields inherited from interface com.illumon.iris.db.v2.ssa.SegmentedSortedArray

SEGMENTED_SORTED_ARRAY_VALIDATION

Constructor Summary

Constructors

Constructor	Description
DoubleReverseSegmentedSortedArray(int leafSize)	Create a DoubleReverseSegmentedSortedArray with the given leafSize.

Method Summary

Modifier and Type	Method	Description
void	applyShift(Chunk<? extends Attributes.Any> stampChunk, LongChunk<? extends Attributes.KeyIndices> keyChunk, long shiftDelta)
void	applyShiftReverse(Chunk<? extends Attributes.Any> stampChunk, LongChunk<? extends Attributes.KeyIndices> keyChunk, long shiftDelta)
void	forAllKeys(LongConsumer longConsumer)	Call the longConsumer for each of the long index keys in this SegmentedSortedArray.
long	getFirst()
long	getLast()
int	getNodeSize()
void	insert(Chunk<? extends Attributes.Any> valuesToInsert, LongChunk<? extends Attributes.KeyIndices> indicesToInsert)	Insert new valuesToInsert into this SSA.
<T extends Attributes.Any> int	insertAndGetNextValue(Chunk<T> valuesToInsert, LongChunk<? extends Attributes.KeyIndices> indicesToInsert, WritableChunk<T> nextValue)
boolean	isReversed()
SsaChecker	makeChecker()
void	remove(Chunk<? extends Attributes.Any> valuesToRemove, LongChunk<? extends Attributes.KeyIndices> indicesToRemove)	Remove valuesToRemove from this SSA.
void	removeAndGetPrior(Chunk<? extends Attributes.Any> stampChunk, LongChunk<? extends Attributes.KeyIndices> indicesToRemove, WritableLongChunk<? extends Attributes.KeyIndices> 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 com.illumon.iris.db.util.LongSizedDataStructure

intSize, intSize

Constructor Details

DoubleReverseSegmentedSortedArray

public DoubleReverseSegmentedSortedArray(int leafSize)

Create a DoubleReverseSegmentedSortedArray with the given leafSize.

Parameters:

leafSize - the maximumSize for any leaf

Method Details

insert

public void insert(Chunk<? extends Attributes.Any> valuesToInsert,
 LongChunk<? extends Attributes.KeyIndices> indicesToInsert)

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

indicesToInsert - the corresponding indicesToInsert

insertAndGetNextValue

public <T extends Attributes.Any> int insertAndGetNextValue(Chunk<T> valuesToInsert,
 LongChunk<? extends Attributes.KeyIndices> indicesToInsert,
 WritableChunk<T> nextValue)

Specified by:

insertAndGetNextValue in interface SegmentedSortedArray

remove

public void remove(Chunk<? extends Attributes.Any> valuesToRemove,
 LongChunk<? extends Attributes.KeyIndices> indicesToRemove)

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

indicesToRemove - the corresponding indices

removeAndGetPrior

public void removeAndGetPrior(Chunk<? extends Attributes.Any> stampChunk,
 LongChunk<? extends Attributes.KeyIndices> indicesToRemove,
 WritableLongChunk<? extends Attributes.KeyIndices> 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

indicesToRemove - the indices (parallel to the values)

priorRedirections - the output prior redirections (parallel to valeus/indices)

applyShift

public void applyShift(Chunk<? extends Attributes.Any> stampChunk,
 LongChunk<? extends Attributes.KeyIndices> keyChunk,
 long shiftDelta)

Specified by:

applyShift in interface SegmentedSortedArray

applyShiftReverse

public void applyShiftReverse(Chunk<? extends Attributes.Any> stampChunk,
 LongChunk<? extends Attributes.KeyIndices> 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 index 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

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 index in this SSA, Index.NULL_KEY when empty.

getLast

public long getLast()

Specified by:

getLast in interface SegmentedSortedArray

Returns:

the last index in this SSA, Index.NULL_KEY when empty.

makeChecker

public SsaChecker makeChecker()

Specified by:

makeChecker in interface SegmentedSortedArray