Package com.ibm.icu.util
Class StringTrieBuilder.Node
- java.lang.Object
-
- com.ibm.icu.util.StringTrieBuilder.Node
-
- Direct Known Subclasses:
StringTrieBuilder.BranchNode
,StringTrieBuilder.ValueNode
- Enclosing class:
- StringTrieBuilder
private abstract static class StringTrieBuilder.Node extends java.lang.Object
-
-
Field Summary
Fields Modifier and Type Field Description protected int
offset
-
Constructor Summary
Constructors Constructor Description Node()
-
Method Summary
All Methods Instance Methods Abstract Methods Concrete Methods Modifier and Type Method Description StringTrieBuilder.Node
add(StringTrieBuilder builder, java.lang.CharSequence s, int start, int sValue)
Recursive method for adding a new (string, value) pair.boolean
equals(java.lang.Object other)
int
getOffset()
abstract int
hashCode()
int
markRightEdgesFirst(int edgeNumber)
Traverses the Node graph and numbers branch edges, with rightmost edges first.StringTrieBuilder.Node
register(StringTrieBuilder builder)
Recursive method for registering unique nodes, after all (string, value) pairs have been added.abstract void
write(StringTrieBuilder builder)
void
writeUnlessInsideRightEdge(int firstRight, int lastRight, StringTrieBuilder builder)
-
-
-
Method Detail
-
hashCode
public abstract int hashCode()
- Overrides:
hashCode
in classjava.lang.Object
-
equals
public boolean equals(java.lang.Object other)
- Overrides:
equals
in classjava.lang.Object
-
add
public StringTrieBuilder.Node add(StringTrieBuilder builder, java.lang.CharSequence s, int start, int sValue)
Recursive method for adding a new (string, value) pair. Matches the remaining part of s from start, and adds a new node where there is a mismatch.- Returns:
- this or a replacement Node
-
register
public StringTrieBuilder.Node register(StringTrieBuilder builder)
Recursive method for registering unique nodes, after all (string, value) pairs have been added. Final-value nodes are pre-registered while add()ing (string, value) pairs. Other nodes created while add()ing registerNode() themselves later and might replace themselves with new types of nodes for write()ing.- Returns:
- The registered version of this node which implements write().
-
markRightEdgesFirst
public int markRightEdgesFirst(int edgeNumber)
Traverses the Node graph and numbers branch edges, with rightmost edges first. This is to avoid writing a duplicate node twice. Branch nodes in this trie data structure are not symmetric. Most branch edges "jump" to other nodes but the rightmost branch edges just continue without a jump. Therefore, write() must write the rightmost branch edge last (trie units are written backwards), and must write it at that point even if it is a duplicate of a node previously written elsewhere. This function visits and marks right branch edges first. Edges are numbered with increasingly negative values because we share the offset field which gets positive values when nodes are written. A branch edge also remembers the first number for any of its edges. When a further-left branch edge has a number in the range of the rightmost edge's numbers, then it will be written as part of the required right edge and we can avoid writing it first. After root.markRightEdgesFirst(-1) the offsets of all nodes are negative edge numbers.- Parameters:
edgeNumber
- The first edge number for this node and its sub-nodes.- Returns:
- An edge number that is at least the maximum-negative of the input edge number and the numbers of this node and all of its sub-nodes.
-
write
public abstract void write(StringTrieBuilder builder)
-
writeUnlessInsideRightEdge
public final void writeUnlessInsideRightEdge(int firstRight, int lastRight, StringTrieBuilder builder)
-
getOffset
public final int getOffset()
-
-