Class SegmentTree
- java.lang.Object
-
- com.vladsch.flexmark.util.sequence.builder.tree.SegmentTree
-
- Direct Known Subclasses:
SegmentOffsetTree
public class SegmentTree extends java.lang.Object
Binary search tree of sequence segments
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description protected static class
SegmentTree.SegmentTreeData
-
Field Summary
Fields Modifier and Type Field Description static int
F_ANCHOR_FLAGS
static int
MAX_VALUE
protected byte[]
segmentBytes
protected int[]
treeData
-
Constructor Summary
Constructors Modifier Constructor Description protected
SegmentTree(int[] treeData, byte[] segmentBytes)
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description void
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 java.lang.Iterable<Seg> segments, @NotNull java.lang.CharSequence allText)
static @NotNull SegmentTree.SegmentTreeData
buildTreeData(@NotNull java.lang.Iterable<Seg> segments, @NotNull java.lang.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 java.lang.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[]
getSegmentBytes()
@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[]
getTreeData()
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 java.lang.String
toString()
@NotNull java.lang.String
toString(@NotNull BasedSequence baseSeq)
-
-
-
Field Detail
-
MAX_VALUE
public static final int MAX_VALUE
- See Also:
- Constant Field Values
-
F_ANCHOR_FLAGS
public static final int F_ANCHOR_FLAGS
- See Also:
- Constant Field Values
-
treeData
protected final int[] treeData
-
segmentBytes
protected final byte[] segmentBytes
-
-
Method Detail
-
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 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 java.lang.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
@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 java.lang.String toString(@NotNull @NotNull BasedSequence baseSeq)
-
toString
@NotNull public @NotNull java.lang.String toString()
- Overrides:
toString
in classjava.lang.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 java.lang.Iterable<Seg> segments, @NotNull @NotNull java.lang.CharSequence allText)
-
build
@NotNull public static @NotNull SegmentTree build(@NotNull @NotNull BasedSegmentBuilder builder)
-
buildTreeData
@NotNull public static @NotNull SegmentTree.SegmentTreeData buildTreeData(@NotNull @NotNull java.lang.Iterable<Seg> segments, @NotNull @NotNull java.lang.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
-
-