Class SegmentTree

java.lang.Object
com.vladsch.flexmark.util.sequence.builder.tree.SegmentTree
Direct Known Subclasses:
SegmentOffsetTree
public class SegmentTree extends Object
Binary search tree of sequence segments

  • Field Details

    • MAX_VALUE

      public static final int MAX_VALUE
      See Also:

    • F_ANCHOR_FLAGS

      public static final int F_ANCHOR_FLAGS
      See Also:

    • treeData

      protected final int[] treeData

    • segmentBytes

      protected final byte[] segmentBytes

  • Constructor Details

    • SegmentTree

      protected SegmentTree(int[] treeData, byte[] segmentBytes)

  • Method Details

    • getTreeData

      public int[] getTreeData()

    • getSegmentBytes

      public byte[] getSegmentBytes()

    • size

      public int size()

    • aggrLength

      public int aggrLength(int pos)

    • byteOffsetData

      public int byteOffsetData(int pos)

    • byteOffset

      public int byteOffset(int pos)

    • getByteOffset

      public static int getByteOffset(int byteOffsetData)

    • getAnchorOffset

      public static int getAnchorOffset(int byteOffsetData)

    • hasPreviousAnchor

      public boolean hasPreviousAnchor(int pos)

    • previousAnchorOffset

      public int previousAnchorOffset(int pos)

    • findSegmentPos

      @Nullable public @Nullable SegmentTreePos findSegmentPos(int index)

    • getSegment

      @NotNull public @NotNull Segment getSegment(int byteOffset, int pos, int startIndex, @NotNull @NotNull BasedSequence baseSeq)

    • findSegment

      @Nullable public @Nullable Segment findSegment(int index, @NotNull @NotNull BasedSequence baseSeq, @Nullable @Nullable Segment hint)

    • findSegment

      @Nullable public @Nullable Segment findSegment(int index, int startPos, int endPos, @NotNull @NotNull BasedSequence baseSeq, @Nullable @Nullable Segment hint)

    • getSegmentRange

      @NotNull public @NotNull SegmentTreeRange getSegmentRange(int startIndex, int endIndex, int startPos, int endPos, @NotNull @NotNull BasedSequence baseSequence, @Nullable @Nullable Segment hint)

    • getTextEndOffset

      public int getTextEndOffset(Segment segment, @NotNull @NotNull BasedSequence baseSequence)

    • getTextStartOffset

      public int getTextStartOffset(Segment segment, @NotNull @NotNull BasedSequence baseSequence)

    • addSegments

      public void addSegments(@NotNull @NotNull IBasedSegmentBuilder<?> builder, @NotNull @NotNull SegmentTreeRange treeRange)
      Add segments selected by given treeRange
      Parameters:
      builder - based segment builder
      treeRange - treeRange for which to add segments

    • addSegments

      public void addSegments(@NotNull @NotNull IBasedSegmentBuilder<?> builder, int startIndex, int endIndex, int startOffset, int endOffset, int startPos, int endPos)
      Add segments of subsequence of this tree to builder
      Parameters:
      builder - builder to which to add the segments
      startIndex - start index of sub-sequence of segment tree
      endIndex - end index of sub-sequence of segment tree
      startOffset - start offset of the subsequence to use as start anchor
      endOffset - end offset of the subsequence to use as end anchor
      startPos - start pos of sub-sequence segments in tree
      endPos - end pos of sub-sequence segments in tree

    • getCharSequence

      @NotNull public static @NotNull CharSequence getCharSequence(@NotNull @NotNull Segment segment, int startIndex, int endIndex, int startPos, int endPos)
      Get char sequence of segment corresponding to sub-sequence in segment tree
      Parameters:
      segment - segment
      startIndex - start index of sub-sequence of segment tree
      endIndex - end index of sub-sequence of segment tree
      startPos - start pos of sub-sequence segments in tree
      endPos - end pos of sub-sequence segments in tree
      Returns:
      subsequence of segment corresponding to part of it which is in the sub-sequence of the tree

    • findSegmentPos

      @Nullable public @Nullable SegmentTreePos findSegmentPos(int index, int startPos, int endPos)

    • getSegment

      @NotNull public @NotNull Segment getSegment(int pos, @NotNull @NotNull BasedSequence baseSeq)

    • getPrevAnchor

      @Nullable public @Nullable Segment getPrevAnchor(int pos, @NotNull @NotNull BasedSequence baseSeq)

    • toString

      @NotNull public @NotNull String toString(@NotNull @NotNull BasedSequence baseSeq)

    • toString

      @NotNull public @NotNull String toString()
      Overrides:
      toString in class Object

    • aggrLength

      public static int aggrLength(int pos, int[] treeData)

    • byteOffsetData

      public static int byteOffsetData(int pos, int[] treeData)

    • byteOffset

      public static int byteOffset(int pos, int[] treeData)

    • setTreeData

      public static void setTreeData(int pos, int[] treeData, int agrrLength, int byteOffset, int prevAnchorOffset)

    • hasPreviousAnchor

      public static boolean hasPreviousAnchor(int pos, int[] treeData)

    • previousAnchorOffset

      public static int previousAnchorOffset(int pos, int[] treeData)

    • findSegmentPos

      @Nullable public static @Nullable SegmentTreePos findSegmentPos(int index, int[] treeData, int startPos, int endPos)

    • findSegment

      @Nullable public static @Nullable Segment findSegment(int index, int[] treeData, int startPos, int endPos, byte[] segmentBytes, @NotNull @NotNull BasedSequence baseSeq)

    • getSegment

      @NotNull public static @NotNull Segment getSegment(int pos, int[] treeData, byte[] segmentBytes, @NotNull @NotNull BasedSequence baseSeq)

    • getPrevAnchor

      @Nullable public static @Nullable Segment getPrevAnchor(int pos, int[] treeData, byte[] segmentBytes, @NotNull @NotNull BasedSequence baseSeq)

    • build

      @NotNull public static @NotNull SegmentTree build(@NotNull @NotNull Iterable<Seg> segments, @NotNull @NotNull CharSequence allText)

    • build

      @NotNull public static @NotNull SegmentTree build(@NotNull @NotNull BasedSegmentBuilder builder)

    • buildTreeData

      @NotNull public static @NotNull SegmentTree.SegmentTreeData buildTreeData(@NotNull @NotNull Iterable<Seg> segments, @NotNull @NotNull CharSequence allText, boolean buildIndexData)
      Build binary tree search data

      Index data has aggregated lengths with BASE and TEXT segments in the data, Offset data has segment start offset with BASE and ANCHOR segments in the data since TEXT segments have no offset they are skipped

      The offset data can be used to pass as treeData to findSegmentPos(int, int[], int, int) with desired offset instead of index to find a segment which can contain the desired offset, with some post processing logic to handle offset segments which are not in the data

      Parameters:
      segments - segments of the tree
      allText - all out of base text
      buildIndexData - true to build index search data, false to build base offset tree data
      Returns:
      segment tree instance with the data

    • getSegmentOffsetTree

      @NotNull public @NotNull SegmentOffsetTree getSegmentOffsetTree(@NotNull @NotNull BasedSequence baseSeq)
      Build an offset segment tree from this index segment tree

      Efficiently reuses segmentBytes and only computes offset treeData for BASE and ANCHOR segments

      Parameters:
      baseSeq - base sequence for the sequence for this segment tree
      Returns:
      SegmentOffsetTree for this segment tree