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

Class TreeIndex

java.lang.Object
com.illumon.iris.db.v2.utils.OrderedKeysAsChunkImpl
com.illumon.iris.db.v2.utils.SortedIndex
com.illumon.iris.db.v2.utils.TreeIndex
All Implemented Interfaces:
com.fishlib.base.log.LogOutputAppendable, LongSizedDataStructure, Index, OrderedKeys, ReadOnlyIndex, SafeCloseable, Externalizable, Serializable, AutoCloseable, Iterable<Long>
public class TreeIndex extends SortedIndex implements Externalizable
See Also:

  • Constructor Details

    • TreeIndex

      public TreeIndex()

    • TreeIndex

      public TreeIndex(TreeIndexImpl impl)

  • Method Details

    • getImpl

      public final TreeIndexImpl getImpl()

    • makeEmptyRsp

      public static TreeIndex makeEmptyRsp()

    • makeEmptySr

      public static TreeIndex makeEmptySr()

    • makeSingleRange

      public static TreeIndex makeSingleRange(long start, long end)

    • trace

      public static void trace(String msg)

    • close

      public void close()
      Description copied from interface: OrderedKeys

      Free any resources associated with this object.

      Using any OrderedKeys methods after close() is an error and may produce exceptions or undefined results.

      Specified by:
      close in interface AutoCloseable
      Specified by:
      close in interface OrderedKeys
      Specified by:
      close in interface ReadOnlyIndex
      Specified by:
      close in interface SafeCloseable
      Overrides:
      close in class OrderedKeysAsChunkImpl

    • refCount

      @VisibleForTesting public int refCount()
      Specified by:
      refCount in interface ReadOnlyIndex

    • insert

      public void insert(long key)
      Description copied from interface: Index
      Add a single key to this index if it's not already present.
      Specified by:
      insert in interface Index
      Parameters:
      key - The key to add

    • insertRange

      public void insertRange(long startKey, long endKey)
      Description copied from interface: Index
      Add all keys in a closed range to this index if they are not already present.
      Specified by:
      insertRange in interface Index
      Parameters:
      startKey - The first key to add
      endKey - The last key to add (inclusive)

    • insert

      public void insert(LongChunk<Attributes.OrderedKeyIndices> keys, int offset, int length)
      Description copied from interface: Index
      Add all of the (ordered) keys in a slice of keys to this index if they are not already present.
      Specified by:
      insert in interface Index
      Parameters:
      keys - The LongChunk of Attributes.OrderedKeyIndices to insert
      offset - The offset in keys to begin inserting keys from
      length - The number of keys to insert

    • insert

      public void insert(ReadOnlyIndex added)
      Description copied from interface: Index
      Add all of the keys in added to this index if they are not already present.
      Specified by:
      insert in interface Index
      Overrides:
      insert in class SortedIndex
      Parameters:
      added - The index to add

    • remove

      public void remove(long key)
      Description copied from interface: Index
      Remove a single key from this index if it's present.
      Specified by:
      remove in interface Index
      Parameters:
      key - The key to remove

    • removeRange

      public void removeRange(long startKey, long endKey)
      Description copied from interface: Index
      Remove all keys in a closed range from this index if they are present.
      Specified by:
      removeRange in interface Index
      Parameters:
      startKey - The first key to remove
      endKey - The last key to remove (inclusive)

    • remove

      public void remove(LongChunk<Attributes.OrderedKeyIndices> keys, int offset, int length)
      Description copied from interface: Index
      Remove all of the (ordered) keys in a slice of keys from this index if they are present.
      Specified by:
      remove in interface Index
      Parameters:
      keys - The LongChunk of Attributes.OrderedKeyIndices to remove
      offset - The offset in keys to begin removing keys from
      length - The number of keys to remove

    • remove

      public void remove(ReadOnlyIndex removed)
      Description copied from interface: Index
      Remove all of the keys in removed that are present in this index.
      Specified by:
      remove in interface Index
      Overrides:
      remove in class SortedIndex
      Parameters:
      removed - The index to remove

    • lastKey

      public long lastKey()
      Description copied from interface: OrderedKeys
      Get the last key in this OrderedKeys.
      Specified by:
      lastKey in interface OrderedKeys
      Specified by:
      lastKey in interface ReadOnlyIndex
      Specified by:
      lastKey in class OrderedKeysAsChunkImpl
      Returns:
      The last key, or ReadOnlyIndex.NULL_KEY if there is none.

    • firstKey

      public long firstKey()
      Description copied from interface: ReadOnlyIndex
      Get the first key in this Index.
      Specified by:
      firstKey in interface OrderedKeys
      Specified by:
      firstKey in interface ReadOnlyIndex
      Returns:
      The first key, or ReadOnlyIndex.NULL_KEY if there is none.

    • clear

      public void clear()
      Specified by:
      clear in interface Index

    • forEachLong

      public boolean forEachLong(LongAbortableConsumer lc)
      Description copied from interface: ReadOnlyIndex
      Provide each value contained in this index, in increased sorted order to the consumer. If the consumer returns false for a key, stops after that key (does not provide any keys after that key).
      Specified by:
      forEachLong in interface OrderedKeys
      Specified by:
      forEachLong in interface ReadOnlyIndex
      Parameters:
      lc - the consumer.
      Returns:
      false if the consumer returned false at some point, true if the consumer always returned true and all values in the index were consumed.

    • forEachLongRange

      public boolean forEachLongRange(LongRangeAbortableConsumer lrac)
      Description copied from interface: OrderedKeys
      For as long as the consumer wants more ranges, call accept on the consumer with the individual key ranges in this OrderedKeys, in increasing order.
      Specified by:
      forEachLongRange in interface OrderedKeys
      Parameters:
      lrac - a consumer to feed the individual key values to.
      Returns:
      false if the consumer provided ever returned false, true otherwise.

    • subindexByPos

      public Index subindexByPos(long startPos, long endPos)
      Description copied from interface: ReadOnlyIndex
      Get a subset of this index within this range of positions
      Specified by:
      subindexByPos in interface ReadOnlyIndex
      Parameters:
      startPos - The first position to included in the output (inclusive)
      endPos - The last position to included in the output (exclusive)
      Returns:
      A new index, containing only positions >= startPos and < endPos

    • subindexByKey

      public Index subindexByKey(long startKey, long endKey)
      Description copied from interface: ReadOnlyIndex
      Get a subset of this index within this range of keys.
      Specified by:
      subindexByKey in interface ReadOnlyIndex
      Parameters:
      startKey - The first key to include in the output.
      endKey - The last key (inclusive) to include in the output.
      Returns:
      A new index, containing only values >= startKey and <= endKey.

    • get

      public long get(long pos)
      Description copied from interface: ReadOnlyIndex
      Returns the key at the given rank position.
      Specified by:
      get in interface ReadOnlyIndex
      Parameters:
      pos - a position in this index between 0 and size() - 1
      Returns:
      the key at that rank.

    • getKeysForPositions

      public void getKeysForPositions(PrimitiveIterator.OfLong positions, LongConsumer outputKeys)
      Description copied from interface: ReadOnlyIndex
      Returns the sequence of (increasing) keys corresponding to the positions provided as input.
      Specified by:
      getKeysForPositions in interface ReadOnlyIndex
      Parameters:
      positions - an iterator providing index positions in increasing order.
      outputKeys - a consumer of corresponding keys for the positions provided as input.

    • getPrev

      public long getPrev(long pos)
      Specified by:
      getPrev in interface ReadOnlyIndex

    • sizePrev

      public long sizePrev()
      Specified by:
      sizePrev in interface ReadOnlyIndex

    • getPrevIndex

      public Index getPrevIndex()
      Specified by:
      getPrevIndex in interface ReadOnlyIndex

    • initializePreviousValue

      public void initializePreviousValue()
      Description copied from interface: Index
      Initializes our previous value from the current value. This call is used by operations that manipulate an Index while constructing it, but need to set the state at the end of the initial operation to the current state. Calling this in other circumstances will yield undefined results.
      Specified by:
      initializePreviousValue in interface Index

    • find

      public long find(long key)
      Description copied from interface: ReadOnlyIndex
      Returns the position in [0..(size-1)] where the key is found. If not found, then return (-(position it would be) - 1), a la Array.binarySearch.
      Specified by:
      find in interface ReadOnlyIndex
      Parameters:
      key - the key to search for
      Returns:
      a position from [0..(size-1)] if the key was found. If the key was not found, then (-position - 1) as in Array.binarySearch.

    • invert

      public Index invert(ReadOnlyIndex keys, long maximumPosition)
      Description copied from class: SortedIndex
      The only used implementation of invert is in the TreeIndex, really the guts of it are in BspNodeIndex. This version is inefficient as it simply performs O(keys) find operations; which is O(keys * lg size), because there is no memory about what you've already found. It serves as a reasonable reference for what the invert operation is "meant" to do. Note maximumPosition is inclusive.
      Specified by:
      invert in interface ReadOnlyIndex
      Overrides:
      invert in class SortedIndex
      Parameters:
      keys - the keys to find positions for
      maximumPosition - the largest position for which we will find a key
      Returns:
      a new Index containing the positions of the keys in this index

    • findPrev

      public long findPrev(long key)
      Description copied from interface: ReadOnlyIndex
      Returns the position in [0..(size-1)] where the key is found in the previous index. If not found, then return (-(position it would be) - 1), as in Array.binarySearch.
      Specified by:
      findPrev in interface ReadOnlyIndex
      Parameters:
      key - the key to search for
      Returns:
      a position from [0..(size-1)] if the key was found. If the key was not found, then (-position - 1) as in Array.binarySearch.

    • firstKeyPrev

      public long firstKeyPrev()
      Specified by:
      firstKeyPrev in interface ReadOnlyIndex

    • lastKeyPrev

      public long lastKeyPrev()
      Specified by:
      lastKeyPrev in interface ReadOnlyIndex

    • searchIterator

      public ReadOnlyIndex.SearchIterator searchIterator()
      Specified by:
      searchIterator in interface ReadOnlyIndex

    • iterator

      @NotNull public ReadOnlyIndex.Iterator iterator()
      Specified by:
      iterator in interface Iterable<Long>
      Specified by:
      iterator in interface ReadOnlyIndex

    • reverseIterator

      public ReadOnlyIndex.SearchIterator reverseIterator()
      Specified by:
      reverseIterator in interface ReadOnlyIndex

    • rangeIterator

      public ReadOnlyIndex.RangeIterator rangeIterator()
      Specified by:
      rangeIterator in interface ReadOnlyIndex

    • size

      public long size()
      Description copied from interface: ReadOnlyIndex
      How many keys are in this index.
      Specified by:
      size in interface LongSizedDataStructure
      Specified by:
      size in interface OrderedKeys
      Specified by:
      size in interface ReadOnlyIndex
      Returns:
      the number of keys in this index.

    • empty

      public boolean empty()
      Description copied from interface: ReadOnlyIndex
      Queries whether this index is empty (i.e. has no keys).
      Specified by:
      empty in interface ReadOnlyIndex
      Returns:
      true if the size() of this Index is zero, false if the size is greater than zero

    • containsRange

      public boolean containsRange(long start, long end)
      Description copied from interface: ReadOnlyIndex
      Queries whether this index contains every element in the range provided.
      Specified by:
      containsRange in interface ReadOnlyIndex
      Parameters:
      start - Start of the range, inclusive.
      end - End of the range, inclusive.
      Returns:
      true if this index contains every element x in start <= x <= end.

    • compact

      public void compact()
      Description copied from interface: Index
      May reclaim some unused memory.
      Specified by:
      compact in interface Index

    • update

      public void update(ReadOnlyIndex added, ReadOnlyIndex removed)
      Description copied from interface: Index
      Simultaneously adds the keys from the first index and removes the keys from the second one. API assumption: the intersection of added and removed is empty.
      Specified by:
      update in interface Index

    • retain

      public void retain(@NotNull ReadOnlyIndex toIntersect)
      Description copied from interface: Index
      Modifies the index by removing any keys not in the indexToIntersect argument.
      Specified by:
      retain in interface Index
      Parameters:
      toIntersect - an index with the keys to retain; any other keys not in indexToIntersect will be removed.

    • retainRange

      public void retainRange(long startKey, long endKey)
      Description copied from interface: Index
      Modifies the index by keeping only keys in the interval [start, end]
      Specified by:
      retainRange in interface Index
      Parameters:
      startKey - beginning of interval of keys to keep.
      endKey - end of interval of keys to keep (inclusive).

    • intersect

      @NotNull public Index intersect(@NotNull ReadOnlyIndex range)
      Description copied from interface: ReadOnlyIndex
      Returns a new index representing the intersection of the current index with the input index
      Specified by:
      intersect in interface ReadOnlyIndex

    • overlaps

      public boolean overlaps(@NotNull ReadOnlyIndex range)
      Description copied from interface: ReadOnlyIndex
      Returns true if an index has any overlap.
      Specified by:
      overlaps in interface ReadOnlyIndex

    • overlapsRange

      public boolean overlapsRange(long start, long end)
      Description copied from interface: ReadOnlyIndex
      Returns true if this index has any overlap with the provided range.
      Specified by:
      overlapsRange in interface ReadOnlyIndex
      Parameters:
      start - Start of range, inclusive.
      end - End of range, inclusive.
      Returns:
      true if any value x in start <= x <= end is contained in this index.

    • subsetOf

      public boolean subsetOf(@NotNull ReadOnlyIndex range)
      Description copied from interface: ReadOnlyIndex
      Returns true if this index is a (possibly improper) subset of other.
      Specified by:
      subsetOf in interface ReadOnlyIndex
      Returns:
      true if every element of this exists within other

    • minus

      public Index minus(ReadOnlyIndex set)
      Description copied from interface: ReadOnlyIndex
      Returns a new index representing the keys of the current set not present inside indexToRemove This operation is equivalent to set difference. This index is not modified.
      Specified by:
      minus in interface ReadOnlyIndex

    • union

      public Index union(ReadOnlyIndex set)
      Description copied from interface: ReadOnlyIndex
      Returns a new index representing the keys present in both this index and the argument index.
      Specified by:
      union in interface ReadOnlyIndex
      Parameters:
      set - an index whose keys will be joined with our own to produce a new index.
      Returns:
      a new index with the union of the keys in both this index and indexToAdd.

    • makeRandomBuilder

      public static Index.RandomBuilder makeRandomBuilder()

    • makeSequentialBuilder

      public static Index.SequentialBuilder makeSequentialBuilder()

    • makeCurrentRandomBuilder

      public static Index.RandomBuilder makeCurrentRandomBuilder()

    • makeCurrentSequentialBuilder

      public static Index.SequentialBuilder makeCurrentSequentialBuilder()

    • getEmptyIndex

      public static SortedIndex getEmptyIndex()

    • toString

      public String toString()
      Overrides:
      toString in class SortedIndex

    • toString

      public String toString(int maxNodes)

    • shift

      public Index shift(long shiftAmount)
      Description copied from interface: ReadOnlyIndex
      Returns a new index representing the keys in this index shifted by the amount indicated.
      Specified by:
      shift in interface ReadOnlyIndex
      Parameters:
      shiftAmount - the amount to shift the keys in the index
      Returns:
      a new index with the keys shifted by shiftAmount

    • shiftInPlace

      public void shiftInPlace(long shiftAmount)
      Specified by:
      shiftInPlace in interface Index

    • insertWithShift

      public void insertWithShift(long shiftAmount, ReadOnlyIndex other)
      Description copied from interface: Index
      For each key in the provided index, shift it by shiftAmount and insert it in the current index.
      Specified by:
      insertWithShift in interface Index
      Parameters:
      shiftAmount - the amount to add to each key in the index argument before insertion.
      other - the index with the keys to shift and insert.

    • validate

      public void validate(String failMsg)
      Specified by:
      validate in interface ReadOnlyIndex

    • clone

      public Index clone()
      Description copied from interface: ReadOnlyIndex
      Create a copy of this index.
      Specified by:
      clone in interface ReadOnlyIndex
      Overrides:
      clone in class SortedIndex
      Returns:
      a copy of this index

    • add

      public static void add(TreeIndexImpl.RandomBuilder builder, TreeIndex idx, boolean acquire)

    • append

      public com.fishlib.base.log.LogOutput append(com.fishlib.base.log.LogOutput logOutput)
      Specified by:
      append in interface com.fishlib.base.log.LogOutputAppendable

    • writeExternal

      public void writeExternal(@NotNull ObjectOutput out) throws IOException
      Specified by:
      writeExternal in interface Externalizable
      Throws:
      IOException

    • writeImpl

      public void writeImpl(ObjectOutput out) throws IOException
      Throws:
      IOException

    • readExternal

      public void readExternal(@NotNull ObjectInput in) throws IOException, ClassNotFoundException
      Specified by:
      readExternal in interface Externalizable
      Throws:
      IOException
      ClassNotFoundException

    • getAverageRunLengthEstimate

      public long getAverageRunLengthEstimate()
      Description copied from interface: OrderedKeys

      Get an estimate of the average (mean) length of runs of adjacent keys in this OrderedKeys.

      Implementations should strive to keep this method efficient (O(1) preferred) at the expense of accuracy.

      Empty OrderedKeys should return an arbitrary valid value, usually 1.

      Specified by:
      getAverageRunLengthEstimate in interface OrderedKeys
      Returns:
      An estimate of the average run length in this OrderedKeys, in [1, size()]

    • getOrderedKeysIterator

      public OrderedKeys.Iterator getOrderedKeysIterator()
      Description copied from interface: OrderedKeys
      Get an OrderedKeys.Iterator over this OrderedKeys.
      Specified by:
      getOrderedKeysIterator in interface OrderedKeys
      Returns:
      A new iterator, positioned at the first key

    • getOrderedKeysByKeyRange

      public OrderedKeys getOrderedKeysByKeyRange(long startKeyInclusive, long endKeyInclusive)
      Description copied from interface: OrderedKeys

      Get an ordered subset of the keys in this OrderedKeys for a key range. The returned set will be the intersection of the keys in this with the keys in the closed interval [startKeyInclusive, endKeyInclusive]. The returned reference is owned by the caller, who should call close() when it is done with it.

      Specified by:
      getOrderedKeysByKeyRange in interface OrderedKeys
      Parameters:
      startKeyInclusive - The minimum key to include
      endKeyInclusive - The maximum key to include
      Returns:
      The subset as an OrderedKeys, which may be this

    • getOrderedKeysByPosition

      public OrderedKeys getOrderedKeysByPosition(long start, long len)
      Description copied from interface: OrderedKeys

      Get an ordered subset of the keys in this OrderedKeys for a position range. The result will contain the set of keys in this that lie at positions in the half-open range [startPositionInclusive, startPositionInclusive + length). The returned reference is owned by the caller, who should call close() when it is done with it.

      Specified by:
      getOrderedKeysByPosition in interface OrderedKeys
      Parameters:
      start - The position of the first key to include
      len - The number of keys to include
      Returns:
      The subset as an OrderedKeys, which may be this

    • asIndex

      public Index asIndex()
      Description copied from interface: OrderedKeys
      Get an Index representation of this OrderedKeys.
      Specified by:
      asIndex in interface OrderedKeys
      Returns:
      An Index representation for the same keys in the same order

    • fillKeyIndicesChunk

      public void fillKeyIndicesChunk(WritableLongChunk<? extends Attributes.KeyIndices> chunkToFill)
      Description copied from interface: OrderedKeys

      Fill the supplied WritableLongChunk with individual keys from this OrderedKeys.

      The chunk's capacity is assumed to be big enough.

      Specified by:
      fillKeyIndicesChunk in interface OrderedKeys
      Parameters:
      chunkToFill - A chunk to fill with individual keys

    • fillKeyRangesChunk

      public void fillKeyRangesChunk(WritableLongChunk<Attributes.OrderedKeyRanges> chunkToFill)
      Description copied from interface: OrderedKeys

      Fill the supplied WritableLongChunk with key ranges from this OrderedKeys.

      The chunk's capacity is assumed to be big enough.

      Specified by:
      fillKeyRangesChunk in interface OrderedKeys
      Parameters:
      chunkToFill - A chunk to fill with key ranges

    • rangesCountUpperBound

      public long rangesCountUpperBound()
      Specified by:
      rangesCountUpperBound in class OrderedKeysAsChunkImpl

    • strid

      default String strid()
      Override to improve index debug-tracing messages.