Class SegmentTree
java.lang.Object
com.vladsch.flexmark.util.sequence.builder.tree.SegmentTree
- Direct Known Subclasses:
SegmentOffsetTree
Binary search tree of sequence segments
-
Nested Class Summary
Nested Classes -
Field Summary
FieldsModifier and TypeFieldDescriptionstatic final int
static final int
protected final byte[]
protected final int[]
-
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionvoid
addSegments
(@NotNull IBasedSegmentBuilder<?> builder, int startIndex, int endIndex, int startOffset, int endOffset, int startPos, int endPos) Add segments of subsequence of this tree to buildervoid
addSegments
(@NotNull IBasedSegmentBuilder<?> builder, @NotNull SegmentTreeRange treeRange) Add segments selected by given treeRangeint
aggrLength
(int pos) static int
aggrLength
(int pos, int[] treeData) static @NotNull SegmentTree
build
(@NotNull BasedSegmentBuilder builder) static @NotNull SegmentTree
build
(@NotNull Iterable<Seg> segments, @NotNull CharSequence allText) static @NotNull SegmentTree.SegmentTreeData
buildTreeData
(@NotNull Iterable<Seg> segments, @NotNull CharSequence allText, boolean buildIndexData) Build binary tree search dataint
byteOffset
(int pos) static int
byteOffset
(int pos, int[] treeData) int
byteOffsetData
(int pos) static int
byteOffsetData
(int pos, int[] treeData) static @Nullable Segment
findSegment
(int index, int[] treeData, int startPos, int endPos, byte[] segmentBytes, @NotNull BasedSequence baseSeq) @Nullable Segment
findSegment
(int index, int startPos, int endPos, @NotNull BasedSequence baseSeq, @Nullable Segment hint) @Nullable Segment
findSegment
(int index, @NotNull BasedSequence baseSeq, @Nullable Segment hint) @Nullable SegmentTreePos
findSegmentPos
(int index) static @Nullable SegmentTreePos
findSegmentPos
(int index, int[] treeData, int startPos, int endPos) @Nullable SegmentTreePos
findSegmentPos
(int index, int startPos, int endPos) static int
getAnchorOffset
(int byteOffsetData) static int
getByteOffset
(int byteOffsetData) static @NotNull CharSequence
getCharSequence
(@NotNull Segment segment, int startIndex, int endIndex, int startPos, int endPos) Get char sequence of segment corresponding to sub-sequence in segment treestatic @Nullable Segment
getPrevAnchor
(int pos, int[] treeData, byte[] segmentBytes, @NotNull BasedSequence baseSeq) @Nullable Segment
getPrevAnchor
(int pos, @NotNull BasedSequence baseSeq) static @NotNull Segment
getSegment
(int pos, int[] treeData, byte[] segmentBytes, @NotNull BasedSequence baseSeq) @NotNull Segment
getSegment
(int byteOffset, int pos, int startIndex, @NotNull BasedSequence baseSeq) @NotNull Segment
getSegment
(int pos, @NotNull BasedSequence baseSeq) byte[]
@NotNull SegmentOffsetTree
getSegmentOffsetTree
(@NotNull BasedSequence baseSeq) Build an offset segment tree from this index segment tree@NotNull SegmentTreeRange
getSegmentRange
(int startIndex, int endIndex, int startPos, int endPos, @NotNull BasedSequence baseSequence, @Nullable Segment hint) int
getTextEndOffset
(Segment segment, @NotNull BasedSequence baseSequence) int
getTextStartOffset
(Segment segment, @NotNull BasedSequence baseSequence) int[]
boolean
hasPreviousAnchor
(int pos) static boolean
hasPreviousAnchor
(int pos, int[] treeData) int
previousAnchorOffset
(int pos) static int
previousAnchorOffset
(int pos, int[] treeData) static void
setTreeData
(int pos, int[] treeData, int agrrLength, int byteOffset, int prevAnchorOffset) int
size()
@NotNull String
toString()
@NotNull String
toString
(@NotNull BasedSequence baseSeq)
-
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
-
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
-
getTextStartOffset
-
addSegments
public void addSegments(@NotNull @NotNull IBasedSegmentBuilder<?> builder, @NotNull @NotNull SegmentTreeRange treeRange) Add segments selected by given treeRange- Parameters:
builder
- based segment buildertreeRange
- 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 segmentsstartIndex
- start index of sub-sequence of segment treeendIndex
- end index of sub-sequence of segment treestartOffset
- start offset of the subsequence to use as start anchorendOffset
- end offset of the subsequence to use as end anchorstartPos
- start pos of sub-sequence segments in treeendPos
- 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
- segmentstartIndex
- start index of sub-sequence of segment treeendIndex
- end index of sub-sequence of segment treestartPos
- start pos of sub-sequence segments in treeendPos
- 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
-
getSegment
-
getPrevAnchor
-
toString
-
toString
-
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
-
buildTreeData
@NotNull public static @NotNull SegmentTree.SegmentTreeData buildTreeData(@NotNull @NotNull Iterable<Seg> segments, @NotNull @NotNull CharSequence allText, boolean buildIndexData) Build binary tree search dataIndex 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 treeallText
- all out of base textbuildIndexData
- 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 treeEfficiently 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
-