Package io.deephaven.engine.table.impl.ssms

Class DoubleSegmentedSortedMultiset

java.lang.Object
io.deephaven.engine.table.impl.ssms.DoubleSegmentedSortedMultiset
All Implemented Interfaces:
SegmentedSortedMultiSet<Double>, LongSizedDataStructure, DoubleVector, Vector<DoubleVector>, Serializable, Comparable<DoubleVector>, Iterable<Double>
public final class DoubleSegmentedSortedMultiset extends Object implements SegmentedSortedMultiSet<Double>, DoubleVector
See Also:

  • Constructor Details

    • DoubleSegmentedSortedMultiset

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

  • Method Details

    • insert

      public boolean insert(WritableChunk<? extends Values> valuesToInsert, WritableIntChunk<ChunkLengths> counts)
      Description copied from interface: SegmentedSortedMultiSet
      Insert new valuesToInsert into this SSMS. The valuesToInsert to insert must be sorted, without duplicates. The valuesToInsert and counts chunks will be modified during this call, and the resulting chunks are undefined.
      Specified by:
      insert in interface SegmentedSortedMultiSet<Double>
      Parameters:
      valuesToInsert - the valuesToInsert to insert
      counts - the number of times each value occurs
      Returns:
      true if any new values were inserted

    • insert

      public boolean insert(WritableChunk<? extends Values> valuesToInsert, WritableIntChunk<ChunkLengths> counts, int offset, int length)
      Description copied from interface: SegmentedSortedMultiSet
      Insert the length new valuesToInsert beginning at offset into this SSMS. The valuesToInsert to insert must be sorted, without duplicates, within the specified range. The valuesToInsert and counts chunks will be modified within the specified range during this call, and the resulting values within the range are undefined.
      Specified by:
      insert in interface SegmentedSortedMultiSet<Double>
      Parameters:
      valuesToInsert - the valuesToInsert to insert
      counts - the number of times each value occurs
      offset - the first position in valuesToInsert and counts to insert
      length - the number of positions in valuesToInsert and counts to insert
      Returns:
      true if any new values were inserted

    • insert

      public boolean insert(WritableDoubleChunk<? extends Values> valuesToInsert, WritableIntChunk<ChunkLengths> counts, int offset, int length)
      Insert the length values beginning at offset; accepts an already-typed chunk so callers that repeatedly insert from the same backing chunk can cast it once rather than per call.

    • insert

      public boolean insert(double value, long count)
      Insert count copies of a single value, returning whether a new distinct value was added (as opposed to merging into an existing one). This does the work of insert(WritableDoubleChunk, WritableIntChunk, int, int) for one value without requiring the caller to wrap it in a chunk, so seeding a freshly created set is allocation-free. Values at the boundaries reuse appendMaximum(double, long)/prependMinimum(double, long) (which handle leaf splitting); interior values are placed directly, splitting the target leaf only when it is full.

    • remove

      public boolean remove(SegmentedSortedMultiSet.RemoveContext removeContext, WritableChunk<? extends Values> valuesToRemove, WritableIntChunk<ChunkLengths> counts)
      Remove valuesToRemove from this SSA. The valuesToRemove to remove must be sorted.
      Specified by:
      remove in interface SegmentedSortedMultiSet<Double>
      Parameters:
      removeContext - removalContext
      valuesToRemove - the valuesToRemove to remove
      Returns:
      true if any values were removed.

    • remove

      public boolean remove(SegmentedSortedMultiSet.RemoveContext removeContext, WritableChunk<? extends Values> valuesToRemove, WritableIntChunk<ChunkLengths> counts, int offset, int length)
      Description copied from interface: SegmentedSortedMultiSet
      Remove the length valuesToRemove beginning at offset from this SSMS. The valuesToRemove to remove must be sorted within the specified range.
      Specified by:
      remove in interface SegmentedSortedMultiSet<Double>
      Parameters:
      removeContext - removalContext
      valuesToRemove - the valuesToRemove to remove
      offset - the first position in valuesToRemove and lengths to remove
      length - the number of positions in valuesToRemove and lengths to remove
      Returns:
      true if any values were removed.

    • remove

      public boolean remove(SegmentedSortedMultiSet.RemoveContext removeContext, WritableDoubleChunk<? extends Values> valuesToRemove, WritableIntChunk<ChunkLengths> counts, int offset, int length)
      Remove the length values beginning at offset; accepts an already-typed chunk so callers that repeatedly remove from the same backing chunk can cast it once rather than per call.

    • remove

      public boolean remove(double value, long count)
      Remove count copies of a single value, which must currently be present, returning whether the distinct value was fully removed (its count reached zero). This does the work of remove(RemoveContext, WritableDoubleChunk, WritableIntChunk, int, int) for one value without requiring the caller to wrap it in a chunk. Empty leaves are dropped and the set collapses back toward the directory and singleton representations, but non-empty leaves are not opportunistically merged.

    • validate

      @VisibleForTesting public void validate()

    • totalSize

      public long totalSize()
      Specified by:
      totalSize in interface SegmentedSortedMultiSet<Double>
      Returns:
      the total size of the set in elements (i.e. if A exists twice, 2 is returned not one)

    • getNodeSize

      public int getNodeSize()
      Specified by:
      getNodeSize in interface SegmentedSortedMultiSet<Double>

    • getMin

      public Double getMin()
      Specified by:
      getMin in interface SegmentedSortedMultiSet<Double>

    • getMax

      public Double getMax()
      Specified by:
      getMax in interface SegmentedSortedMultiSet<Double>

    • getMinDouble

      public double getMinDouble()

    • getMinCount

      public long getMinCount()
      Specified by:
      getMinCount in interface SegmentedSortedMultiSet<Double>
      Returns:
      the number of times the minimum value exists in this SSM.

    • getMaxDouble

      public double getMaxDouble()

    • getMaxCount

      public long getMaxCount()
      Specified by:
      getMaxCount in interface SegmentedSortedMultiSet<Double>
      Returns:
      the number of times the maximum value exists in this SSM.

    • moveFrontToBack

      public void moveFrontToBack(SegmentedSortedMultiSet untypedDestination, long count)
      Description copied from interface: SegmentedSortedMultiSet
      Remove count elements from the front of this SSM and add them to the back of the destination SSM.

      The minimum element of this SSM must be greater than or equal to the maximum of destination.

      Specified by:
      moveFrontToBack in interface SegmentedSortedMultiSet<Double>
      Parameters:
      untypedDestination - the SegmentedSortedMultiSet to append count elements to
      count - how many elements to move to the destination

    • moveBackToFront

      public void moveBackToFront(SegmentedSortedMultiSet untypedDestination, long count)
      Description copied from interface: SegmentedSortedMultiSet
      Remove count elements from the back of this SSM and add them to the front of the destination SSM.

      The minimum element of this SSM must be less than or equal to the maximum of destination.

      Specified by:
      moveBackToFront in interface SegmentedSortedMultiSet<Double>
      Parameters:
      untypedDestination - the SegmentedSortedMultiSet to prepend count elements to
      count - how many elements to move to the destination

    • keyChunk

      public WritableDoubleChunk<?> keyChunk()
      Specified by:
      keyChunk in interface SegmentedSortedMultiSet<Double>

    • fillKeyChunk

      public void fillKeyChunk(WritableChunk<?> keyChunk, int offset)
      Specified by:
      fillKeyChunk in interface SegmentedSortedMultiSet<Double>

    • countChunk

      public WritableLongChunk<?> countChunk()
      Specified by:
      countChunk in interface SegmentedSortedMultiSet<Double>

    • setTrackDeltas

      public void setTrackDeltas(boolean shouldTrackDeltas)
      Specified by:
      setTrackDeltas in interface SegmentedSortedMultiSet<Double>

    • clearDeltas

      public void clearDeltas()
      Specified by:
      clearDeltas in interface SegmentedSortedMultiSet<Double>

    • getAddedSize

      public int getAddedSize()
      Specified by:
      getAddedSize in interface SegmentedSortedMultiSet<Double>

    • getRemovedSize

      public int getRemovedSize()
      Specified by:
      getRemovedSize in interface SegmentedSortedMultiSet<Double>

    • fillRemovedChunk

      public void fillRemovedChunk(WritableDoubleChunk<? extends Values> chunk, int position)

    • fillAddedChunk

      public void fillAddedChunk(WritableDoubleChunk<? extends Values> chunk, int position)

    • getPrevValues

      public DoubleVector getPrevValues()

    • get

      public double get(long index)
      Description copied from interface: DoubleVector
      Get the element of this DoubleVector at offset index. If index is not within range [0, size()), will return the null double.
      Specified by:
      get in interface DoubleVector
      Parameters:
      index - An offset into this DoubleVector
      Returns:
      The element at the specified offset, or the null double

    • iterator

      public ValueIteratorOfDouble iterator(long fromIndexInclusive, long toIndexExclusive)
      Returns an iterator over a slice of this vector, with equivalent semantics to subVector(fromIndexInclusive, toIndexExclusive).iterator().

      The inherited implementation is positional, and get(long) rescans the leaf directory on every element, making a traversal O(size * leafCount). Walking the leaves instead makes it O(size), which matters because the iterator-based hashCode() and equals(Object) run per row per cycle when an SSM-valued column is used as an aggregation key.

      Specified by:
      iterator in interface DoubleVector
      Parameters:
      fromIndexInclusive - The first position to include
      toIndexExclusive - The first position after fromIndexInclusive to not include
      Returns:
      An iterator over the requested slice

    • subVector

      public DoubleVector subVector(long fromIndexInclusive, long toIndexExclusive)
      Description copied from interface: Vector
      Get a Vector that represents a slice of this Vector.
      Specified by:
      subVector in interface DoubleVector
      Specified by:
      subVector in interface Vector<DoubleVector>
      Parameters:
      fromIndexInclusive - The first offset into this Vector to include in the result; if negative, the result will have a range of null values at offsets in [0, -fromIndexInclusive)
      toIndexExclusive - The first offset into this Vector to not include in the result; if larger than size(), the result will have a range of null values at the corresponding offsets
      Returns:
      The sub-Vector specified by [fromIndexInclusive, toIndexExclusive)

    • subVectorByPositions

      public DoubleVector subVectorByPositions(long[] positions)
      Description copied from interface: Vector
      Get a Vector that represents a set of offset positions in this Vector.
      Specified by:
      subVectorByPositions in interface DoubleVector
      Specified by:
      subVectorByPositions in interface Vector<DoubleVector>
      Parameters:
      positions - The offsets to include; if not within [0, size()), the corresponding offset in the result will contain the appropriate null value
      Returns:
      The sub-Vector specified by positions

    • toArray

      public double[] toArray()
      Description copied from interface: Vector
      Get an array representation of the elements of this Vector. Callers must not mutate the result, as implementations may choose to return their backing array in some cases.
      Specified by:
      toArray in interface DoubleVector
      Specified by:
      toArray in interface Vector<DoubleVector>
      Returns:
      An array representation of the elements of this Vector that must not be mutated

    • copyToArray

      public double[] copyToArray()
      Description copied from interface: Vector
      Get an array representation of the elements of this Vector. Callers may freely mutate the result, as it is guaranteed to be freshly-allocated and belongs to the caller upon return.
      Specified by:
      copyToArray in interface DoubleVector
      Specified by:
      copyToArray in interface Vector<DoubleVector>
      Returns:
      An array representation of the elements of this Vector that may be freely mutated

    • size

      public long size()
      Description copied from interface: LongSizedDataStructure
      The size of this data structure.
      Specified by:
      size in interface LongSizedDataStructure
      Specified by:
      size in interface SegmentedSortedMultiSet<Double>
      Returns:
      the size of the set (i.e. the number of unique elements).

    • getDirect

      public DoubleVector getDirect()
      Specified by:
      getDirect in interface DoubleVector
      Specified by:
      getDirect in interface Vector<DoubleVector>
      Returns:
      A version of this Vector that is flattened out to only reference memory

    • equals

      public boolean equals(Object o)

      Equal to any DoubleVector holding the same values, including another SSM: an SSM is a DoubleVector, so it takes the same element-wise path rather than a structural comparison of leaf layouts. Two SSMs can hold identical values in different layouts -- leaves need not be full, and the node sizes need not agree -- so layout is not a sound basis for equality.

      Nothing else is equal, exactly as DoubleVector.equals(DoubleVector, Object) requires: a Vector that stores its elements some other way cannot be accepted without breaking the hashCode() contract, and would not be reciprocated in any case, since that Vector's own equals rejects a DoubleVector.

      Overrides:
      equals in class Object

    • hashCode

      public int hashCode()

      equals(Object) accepts any Vector with matching contents, so this must produce exactly the hash DoubleVector.hashCode(DoubleVector) would: the same seed, the same multiplier, and the same per-element DoubleComparisons.hashCode(double). That per-element hash is also why equals(Object) must compare elements with DoubleComparisons.eq(double, double) rather than ==.

      Walking the leaves here rather than delegating to the helper avoids an iterator per call, which is worth roughly 2x once the values span more than one leaf. Since that duplicates the helper's formula, TestDoubleSegmentedSortedMultiset#testHashCodeMatchesVectorHelper pins the two against each other across every representation so they cannot drift apart.

      Overrides:
      hashCode in class Object

    • toString

      public String toString()
      Overrides:
      toString in class Object