Package com.illumon.iris.db.v2.utils.sortedranges

Class SortedRanges

java.lang.Object
com.illumon.iris.db.v2.utils.RefCountedCow<SortedRanges>
com.illumon.iris.db.v2.utils.sortedranges.SortedRanges
All Implemented Interfaces:
TreeIndexImpl
Direct Known Subclasses:
SortedRangesTyped
public abstract class SortedRanges extends RefCountedCow<SortedRanges> implements TreeIndexImpl

  • Field Details

    • INITIAL_SIZE

      protected static final int INITIAL_SIZE

    • DEBUG

      public static final boolean DEBUG

    • LONG_DENSE_MAX_CAPACITY

      public static final int LONG_DENSE_MAX_CAPACITY

    • LONG_SPARSE_MAX_CAPACITY

      public static final int LONG_SPARSE_MAX_CAPACITY

    • INT_DENSE_MAX_CAPACITY

      public static final int INT_DENSE_MAX_CAPACITY

    • INT_SPARSE_MAX_CAPACITY

      public static final int INT_SPARSE_MAX_CAPACITY

    • SHORT_MAX_CAPACITY

      public static final int SHORT_MAX_CAPACITY

    • ELEMENTS_PER_BLOCK_DENSE_THRESHOLD

      public static final int ELEMENTS_PER_BLOCK_DENSE_THRESHOLD

    • MAX_CAPACITY

      public static final int MAX_CAPACITY

    • LONG_EXTENT

      protected static final int LONG_EXTENT

    • INT_EXTENT

      protected static final int INT_EXTENT

    • SHORT_EXTENT

      protected static final int SHORT_EXTENT

    • POOL_ARRAYS

      protected static final boolean POOL_ARRAYS

    • USE_RANGES_ARRAY

      public static final boolean USE_RANGES_ARRAY

    • cardinality

      protected long cardinality

    • count

      protected int count

  • Constructor Details

    • SortedRanges

      protected SortedRanges()

  • Method Details

    • deepCopy

      public abstract SortedRanges deepCopy()
      Description copied from class: RefCountedCow
      Get a deep copy of the current object, not shared with anybody. Note this is not thread safe.
      Specified by:
      deepCopy in class RefCountedCow<SortedRanges>
      Returns:
      A full, deep copy of this object with a reference count of 1 (not shared).

    • self

      public final SortedRanges self()
      Description copied from class: RefCountedCow
      Derived classes should implement self() by simply "return this" of the right type. This method exists only as an implementation artifact for a type safe implementation of the curiously recurring generic pattern.
      Specified by:
      self in class RefCountedCow<SortedRanges>
      Returns:
      this object, with the right, most derived type.

    • arraySizeRoundingInt

      public static int arraySizeRoundingInt(int sizeToRound)

    • arraySizeRoundingShort

      public static int arraySizeRoundingShort(int sizeToRound)

    • makeSingleRange

      public static SortedRanges makeSingleRange(long start, long end)

    • makeSingleElement

      public static SortedRanges makeSingleElement(long v)

    • makeEmpty

      public static SortedRanges makeEmpty()

    • tryMakeForKnownRangeFinalCapacityLowerBound

      public static SortedRanges tryMakeForKnownRangeFinalCapacityLowerBound(int initialCapacity, int finalCapacityLowerBound, long first, long last, boolean isDense)

    • makeForKnownRange

      public static SortedRanges makeForKnownRange(long first, long last, boolean isDense)

    • tryMakeForKnownRangeUnknownMaxCapacity

      public static SortedRanges tryMakeForKnownRangeUnknownMaxCapacity(int initialCapacity, long first, long last, boolean isDense)

    • tryMakeForKnownRangeKnownCount

      public static SortedRanges tryMakeForKnownRangeKnownCount(int count, long first, long last)

    • isEmpty

      public final boolean isEmpty()

    • clear

      public final void clear()

    • first

      public final long first()

    • last

      public final long last()

    • hasMoreThanOneRange

      public final boolean hasMoreThanOneRange()

    • validate

      public final void validate()

    • offsetToDebugString

      protected void offsetToDebugString(StringBuilder sb)

    • toDebugString

      protected String toDebugString()

    • dataToDebugString

      protected void dataToDebugString(StringBuilder sb)

    • toString

      public final String toString()
      Overrides:
      toString in class Object

    • contains

      public final boolean contains(long v)

    • containsRange

      public final boolean containsRange(long start, long end)

    • find

      public final long find(long v)

    • get

      public final long get(long targetPos)

    • applyShift

      public abstract SortedRanges applyShift(long shift)

    • applyShiftOnNew

      public abstract SortedRanges applyShiftOnNew(long shift)

    • add

      public final SortedRanges add(long v)

    • addUnsafe

      public final SortedRanges addUnsafe(long v)

    • addRange

      public final SortedRanges addRange(long start, long end)

    • addRangeUnsafe

      public final SortedRanges addRangeUnsafe(long start, long end)

    • append

      public final SortedRanges append(long v)

    • appendUnsafe

      public final SortedRanges appendUnsafe(long v)

    • appendRange

      public final SortedRanges appendRange(long start, long end)

    • appendRangeUnsafe

      public final SortedRanges appendRangeUnsafe(long start, long end)

    • remove

      public final SortedRanges remove(long v)

    • removeRange

      public final SortedRanges removeRange(long start, long end)

    • forEachLongRange

      public final boolean forEachLongRange(LongRangeAbortableConsumer lrac)

    • forEachLong

      public final boolean forEachLong(LongAbortableConsumer lac)

    • getIterator

      public final ReadOnlyIndex.Iterator getIterator()

    • getRangeIterator

      public ReadOnlyIndex.RangeIterator getRangeIterator()

    • getSearchIterator

      public final ReadOnlyIndex.SearchIterator getSearchIterator()

    • getReverseIterator

      public final ReadOnlyIndex.SearchIterator getReverseIterator()

    • getCardinality

      public final long getCardinality()

    • getKeysForPositions

      public final void getKeysForPositions(PrimitiveIterator.OfLong inputPositions, LongConsumer outputKeys)

    • subRangesByPos

      public final SortedRanges subRangesByPos(long startPosIn, long endPosIn)

    • subRangesByKey

      public final SortedRanges subRangesByKey(long start, long end)

    • overlapsRange

      public final boolean overlapsRange(long start, long end)

    • overlaps

      public final boolean overlaps(ReadOnlyIndex.RangeIterator rangeIter)

    • retainRange

      public final SortedRanges retainRange(long start, long end)

    • isDenseShort

      public static boolean isDenseShort(short[] data, int count)

    • isDenseLongSample

      protected static boolean isDenseLongSample(long v0, long v1, int count)

    • isDenseInt

      public static boolean isDenseInt(int[] data, int count)

    • isDenseLong

      public static boolean isDenseLong(long[] data, int count)

    • isDense

      public abstract boolean isDense()

    • isSparse

      public final boolean isSparse()

    • intersectOnNewImpl

      public final TreeIndexImpl intersectOnNewImpl(TreeIndexImpl other)

    • count

      public final int count()

    • subsetOf

      public final boolean subsetOf(ReadOnlyIndex.RangeIterator ritOther)

    • unionOnNew

      public static TreeIndexImpl unionOnNew(SortedRanges sar, SortedRanges otherSar)

    • unionOnNewLegacy

      public static SortedRanges unionOnNewLegacy(SortedRanges sar, SortedRanges otherSar)

    • insertImpl

      public final TreeIndexImpl insertImpl(SortedRanges other)

    • mergeAppend

      public final SortedRanges mergeAppend(SortedRanges other, boolean writeCheck)

    • insertImpl

      public final TreeIndexImpl insertImpl(SortedRanges other, boolean writeCheck)

    • invertRangeOnNew

      public final TreeIndexImpl invertRangeOnNew(long start, long end, long maxPosition)

    • invertOnNew

      public final boolean invertOnNew(ReadOnlyIndex.RangeIterator rit, TreeIndexImplSequentialBuilder builder, long maxPosition)

    • getOrderedKeysByPosition

      public final OrderedKeys getOrderedKeysByPosition(long pos, long length)

    • getOrderedKeysByPositionWithStart

      public final OrderedKeys getOrderedKeysByPositionWithStart(long iStartPos, int istart, long startPosForOK, long lengthForOK)

    • getOrderedKeysByKeyRange

      public final OrderedKeys getOrderedKeysByKeyRange(long start, long end)

    • getOrderedKeysIterator

      public final OrderedKeys.Iterator getOrderedKeysIterator()

    • getAverageRunLengthEstimate

      public final long getAverageRunLengthEstimate()

    • shortArrayCapacityForLastIndex

      protected static int shortArrayCapacityForLastIndex(int lastIndex)

    • intArrayCapacityForLastIndex

      protected static int intArrayCapacityForLastIndex(int lastIndex, boolean isDense)

    • longArrayCapacityForLastIndex

      protected static int longArrayCapacityForLastIndex(int lastIndex, boolean isDense)

    • fits

      public abstract boolean fits(long value)

    • fits

      public abstract boolean fits(long start, long end)

    • fitsForAppend

      public abstract boolean fitsForAppend(long end)

    • makeMyTypeAndOffset

      protected abstract SortedRanges makeMyTypeAndOffset(int initialCapacity)

    • growOnNew

      protected abstract SortedRanges growOnNew(int capacity)

    • packedValuesPerCacheLine

      protected abstract int packedValuesPerCacheLine()

    • packedGet

      protected abstract long packedGet(int i)

    • absPackedGet

      protected final long absPackedGet(int i)

    • packedSet

      protected abstract void packedSet(int i, long packedValue)

    • pack

      protected abstract long pack(long unpackedValue)

    • unpackedGet

      protected abstract long unpackedGet(int i)

    • absUnpackedGet

      protected abstract long absUnpackedGet(int i)

    • unpackedSet

      protected abstract void unpackedSet(int i, long unpackedValue)

    • unpack

      protected abstract long unpack(long packedValue)

    • dataLength

      protected abstract int dataLength()

    • ensureCanAppend

      protected abstract SortedRanges ensureCanAppend(int newLastPosition, long unpackedNewLastKey, boolean writeCheck)

    • moveData

      protected abstract void moveData(int srcPos, int dstPos, int len)

    • copyData

      protected abstract void copyData(int newCapacity)

    • addInternal

      protected abstract SortedRanges addInternal(long v, boolean writeCheck)

    • addRangeInternal

      protected abstract SortedRanges addRangeInternal(long start, long end, boolean writeCheck)

    • appendInternal

      protected abstract SortedRanges appendInternal(long v, boolean writeCheck)

    • appendRangeInternal

      protected abstract SortedRanges appendRangeInternal(long start, long end, boolean writeCheck)

    • removeInternal

      protected abstract SortedRanges removeInternal(long v)

    • removeRangeInternal

      protected abstract SortedRanges removeRangeInternal(long start, long end)

    • tryPackFor

      protected abstract SortedRanges tryPackFor(long first, long last, int maxPos, boolean isDense)

    • tryPackWithNewLast

      protected final SortedRanges tryPackWithNewLast(long newLastKey, int maxPos, boolean isDense)

    • tryPack

      protected abstract SortedRanges tryPack()

    • bytesAllocated

      public abstract int bytesAllocated()

    • bytesUsed

      public abstract int bytesUsed()

    • tryCompactUnsafe

      public abstract SortedRanges tryCompactUnsafe(int k)
      Parameters:
      k - if k == 0, compact if count < capacity. k > 0, compact if (capacity - count > (capacity >> k).

    • tryCompact

      public final SortedRanges tryCompact(int k)

    • isLongAllocationSize

      protected static boolean isLongAllocationSize(int length)

    • isIntAllocationSize

      protected static boolean isIntAllocationSize(int length)

    • isShortAllocationSize

      protected static boolean isShortAllocationSize(int length)

    • checkSizeAndMoveData

      protected abstract SortedRanges checkSizeAndMoveData(int srcPos, int dstPos, int len, long first, boolean writeCheck)

    • close

      protected final void close(int pos)

    • close2

      protected final void close2(int pos)

    • addPacked

      protected static SortedRanges addPacked(SortedRanges sar, long packedValue, long value, boolean writeCheck)

    • addPackedWithStart

      protected static SortedRanges addPackedWithStart(SortedRanges sar, int iStart, long packedValue, long value, org.apache.commons.lang3.mutable.MutableInt iStartOut, boolean writeCheck)

    • addRangePacked

      protected static SortedRanges addRangePacked(SortedRanges sar, long packedStart, long packedEnd, long start, long end, boolean writeCheck)

    • addRangePackedWithStart

      protected static SortedRanges addRangePackedWithStart(SortedRanges sar, int iStart, long packedStart, long packedEnd, long start, long end, long deltaCard, org.apache.commons.lang3.mutable.MutableInt iStartOut, boolean writeCheck)

    • appendPacked

      protected static SortedRanges appendPacked(SortedRanges sar, long packedValue, long value, boolean writeCheck)

    • appendRangeUnpacked

      protected static SortedRanges appendRangeUnpacked(SortedRanges sar, long start, long end, boolean writeCheck)

    • appendRangePacked

      protected static SortedRanges appendRangePacked(SortedRanges sar, long packedStart, long packedEnd, long start, long end, boolean writeCheck)

    • removePacked

      protected static SortedRanges removePacked(SortedRanges sar, long packedValue, long value)

    • removeRangePacked

      protected static SortedRanges removeRangePacked(SortedRanges sar, long packedStart, long packedEnd, long start, long end)

    • removeRangePackedWithStart

      protected static SortedRanges removeRangePackedWithStart(SortedRanges sar, int iStart, long packedStart, long packedEnd, long start, long end, org.apache.commons.lang3.mutable.MutableInt iStartOut, boolean writeCheck)

    • validate

      protected final void validate(long iv1, long iv2)

    • validate

      protected final void validate(String strArg, long iv1, long iv2)

    • ixCowRef

      public final SortedRanges ixCowRef()
      Specified by:
      ixCowRef in interface TreeIndexImpl

    • ixRelease

      public final void ixRelease()
      Specified by:
      ixRelease in interface TreeIndexImpl

    • ixRefCount

      public final int ixRefCount()
      Specified by:
      ixRefCount in interface TreeIndexImpl

    • ixInsert

      public final TreeIndexImpl ixInsert(long key)
      Specified by:
      ixInsert in interface TreeIndexImpl

    • ixInsertRange

      public final TreeIndexImpl ixInsertRange(long startKey, long endKey)
      Specified by:
      ixInsertRange in interface TreeIndexImpl

    • ixInsertSecondHalf

      public final TreeIndexImpl ixInsertSecondHalf(LongChunk<Attributes.OrderedKeyIndices> keys, int offset, int length)
      Specified by:
      ixInsertSecondHalf in interface TreeIndexImpl

    • ixRemoveSecondHalf

      public final TreeIndexImpl ixRemoveSecondHalf(LongChunk<Attributes.OrderedKeyIndices> keys, int offset, int length)
      Specified by:
      ixRemoveSecondHalf in interface TreeIndexImpl

    • ixAppendRange

      public final TreeIndexImpl ixAppendRange(long startKey, long endKey)
      Specified by:
      ixAppendRange in interface TreeIndexImpl

    • ixRemove

      public final TreeIndexImpl ixRemove(long key)
      Specified by:
      ixRemove in interface TreeIndexImpl

    • ixLastKey

      public final long ixLastKey()
      Specified by:
      ixLastKey in interface TreeIndexImpl

    • ixFirstKey

      public final long ixFirstKey()
      Specified by:
      ixFirstKey in interface TreeIndexImpl

    • ixForEachLong

      public final boolean ixForEachLong(LongAbortableConsumer lc)
      Specified by:
      ixForEachLong in interface TreeIndexImpl

    • ixForEachLongRange

      public final boolean ixForEachLongRange(LongRangeAbortableConsumer lrac)
      Specified by:
      ixForEachLongRange in interface TreeIndexImpl

    • ixSubindexByPosOnNew

      public final TreeIndexImpl ixSubindexByPosOnNew(long startPos, long endPosExclusive)
      Specified by:
      ixSubindexByPosOnNew in interface TreeIndexImpl

    • ixSubindexByKeyOnNew

      public final TreeIndexImpl ixSubindexByKeyOnNew(long startKey, long endKey)
      Specified by:
      ixSubindexByKeyOnNew in interface TreeIndexImpl

    • ixGet

      public final long ixGet(long pos)
      Specified by:
      ixGet in interface TreeIndexImpl

    • ixGetKeysForPositions

      public final void ixGetKeysForPositions(PrimitiveIterator.OfLong inputPositions, LongConsumer outputKeys)
      Specified by:
      ixGetKeysForPositions in interface TreeIndexImpl

    • ixFind

      public final long ixFind(long key)
      Specified by:
      ixFind in interface TreeIndexImpl

    • ixIterator

      public final ReadOnlyIndex.Iterator ixIterator()
      Specified by:
      ixIterator in interface TreeIndexImpl

    • ixSearchIterator

      public final ReadOnlyIndex.SearchIterator ixSearchIterator()
      Specified by:
      ixSearchIterator in interface TreeIndexImpl

    • ixReverseIterator

      public final ReadOnlyIndex.SearchIterator ixReverseIterator()
      Specified by:
      ixReverseIterator in interface TreeIndexImpl

    • ixRangeIterator

      public final ReadOnlyIndex.RangeIterator ixRangeIterator()
      Specified by:
      ixRangeIterator in interface TreeIndexImpl

    • ixCardinality

      public final long ixCardinality()
      Specified by:
      ixCardinality in interface TreeIndexImpl

    • ixIsEmpty

      public final boolean ixIsEmpty()
      Specified by:
      ixIsEmpty in interface TreeIndexImpl

    • ixUpdate

      public final TreeIndexImpl ixUpdate(TreeIndexImpl added, TreeIndexImpl removed)
      Specified by:
      ixUpdate in interface TreeIndexImpl

    • ixRemove

      public final TreeIndexImpl ixRemove(TreeIndexImpl removed)
      Specified by:
      ixRemove in interface TreeIndexImpl

    • remove

      public final TreeIndexImpl remove(TreeIndexImpl removed)

    • ixRemoveRange

      public final TreeIndexImpl ixRemoveRange(long startKey, long endKey)
      Specified by:
      ixRemoveRange in interface TreeIndexImpl

    • ixRetain

      public final TreeIndexImpl ixRetain(TreeIndexImpl toIntersect)
      Specified by:
      ixRetain in interface TreeIndexImpl

    • ixRetainRange

      public final TreeIndexImpl ixRetainRange(long start, long end)
      Specified by:
      ixRetainRange in interface TreeIndexImpl

    • ixIntersectOnNew

      public final TreeIndexImpl ixIntersectOnNew(TreeIndexImpl toIntersect)
      Specified by:
      ixIntersectOnNew in interface TreeIndexImpl

    • intersectOnNew

      public final TreeIndexImpl intersectOnNew(TreeIndexImpl toIntersect)

    • ixContainsRange

      public final boolean ixContainsRange(long start, long end)
      Specified by:
      ixContainsRange in interface TreeIndexImpl

    • ixOverlaps

      public final boolean ixOverlaps(TreeIndexImpl impl)
      Specified by:
      ixOverlaps in interface TreeIndexImpl

    • ixOverlapsRange

      public final boolean ixOverlapsRange(long start, long end)
      Specified by:
      ixOverlapsRange in interface TreeIndexImpl

    • ixSubsetOf

      public final boolean ixSubsetOf(TreeIndexImpl other)
      Specified by:
      ixSubsetOf in interface TreeIndexImpl

    • ixMinusOnNew

      public final TreeIndexImpl ixMinusOnNew(TreeIndexImpl other)
      Specified by:
      ixMinusOnNew in interface TreeIndexImpl

    • ixUnionOnNew

      public final TreeIndexImpl ixUnionOnNew(TreeIndexImpl other)
      Specified by:
      ixUnionOnNew in interface TreeIndexImpl

    • ixShiftOnNew

      public final TreeIndexImpl ixShiftOnNew(long shiftAmount)
      Specified by:
      ixShiftOnNew in interface TreeIndexImpl

    • ixShiftInPlace

      public final TreeIndexImpl ixShiftInPlace(long shiftAmount)
      Specified by:
      ixShiftInPlace in interface TreeIndexImpl

    • ixInsertWithShift

      public final TreeIndexImpl ixInsertWithShift(long shiftAmount, TreeIndexImpl other)
      Specified by:
      ixInsertWithShift in interface TreeIndexImpl

    • ixInsert

      public final TreeIndexImpl ixInsert(TreeIndexImpl added)
      Specified by:
      ixInsert in interface TreeIndexImpl

    • ixGetOrderedKeysByPosition

      public final OrderedKeys ixGetOrderedKeysByPosition(long startPositionInclusive, long length)
      Specified by:
      ixGetOrderedKeysByPosition in interface TreeIndexImpl

    • ixGetOrderedKeysByKeyRange

      public final OrderedKeys ixGetOrderedKeysByKeyRange(long startKeyInclusive, long endKeyInclusive)
      Specified by:
      ixGetOrderedKeysByKeyRange in interface TreeIndexImpl

    • ixGetOrderedKeysIterator

      public final OrderedKeys.Iterator ixGetOrderedKeysIterator()
      Specified by:
      ixGetOrderedKeysIterator in interface TreeIndexImpl

    • ixRangesCountUpperBound

      public final long ixRangesCountUpperBound()
      Specified by:
      ixRangesCountUpperBound in interface TreeIndexImpl

    • ixGetAverageRunLengthEstimate

      public final long ixGetAverageRunLengthEstimate()
      Specified by:
      ixGetAverageRunLengthEstimate in interface TreeIndexImpl

    • ixToRspOnNew

      public final RspBitmap ixToRspOnNew()
      Specified by:
      ixToRspOnNew in interface TreeIndexImpl

    • toRsp

      public final RspBitmap toRsp()

    • ixInvertOnNew

      public final TreeIndexImpl ixInvertOnNew(TreeIndexImpl keys, long maxPosition)
      Description copied from interface: TreeIndexImpl
      Invert the given index.
      Specified by:
      ixInvertOnNew in interface TreeIndexImpl
      Parameters:
      keys - Index of keys to invert
      maxPosition - the largest position to add to indexBuilder, inclusive
      Returns:
      the inverse of index

    • ixCompact

      public final TreeIndexImpl ixCompact()
      Specified by:
      ixCompact in interface TreeIndexImpl

    • ixValidate

      public final void ixValidate(String failMsg)
      Specified by:
      ixValidate in interface TreeIndexImpl