Package dk.brics.automaton
Class StringUnionOperations
- java.lang.Object
-
- dk.brics.automaton.StringUnionOperations
-
public final class StringUnionOperations extends java.lang.Object
Operations for building minimal deterministic automata from sets of strings. The algorithm requires sorted input data, but is very fast (nearly linear with the input size).
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description (package private) static class
StringUnionOperations.State
State withchar
labels on transitions.
-
Field Summary
Fields Modifier and Type Field Description static java.util.Comparator<java.lang.CharSequence>
LEXICOGRAPHIC_ORDER
Lexicographic order of input sequences.private java.lang.StringBuilder
previous
Previous sequence added to the automaton inadd(CharSequence)
.private java.util.HashMap<StringUnionOperations.State,StringUnionOperations.State>
register
"register" for state interning.private StringUnionOperations.State
root
Root automaton state.
-
Constructor Summary
Constructors Constructor Description StringUnionOperations()
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description void
add(java.lang.CharSequence current)
Add another character sequence to this automaton.private void
addSuffix(StringUnionOperations.State state, java.lang.CharSequence current, int fromIndex)
Add a suffix ofcurrent
starting atfromIndex
(inclusive) to statestate
.static State
build(java.lang.CharSequence[] input)
Build a minimal, deterministic automaton from a sorted list of strings.StringUnionOperations.State
complete()
Finalize the automaton and return the root state.private static State
convert(StringUnionOperations.State s, java.util.IdentityHashMap<StringUnionOperations.State,State> visited)
Internal recursive traversal for conversion.private void
replaceOrRegister(StringUnionOperations.State state)
Replace last child ofstate
with an already registered state or register the last child state.private boolean
setPrevious(java.lang.CharSequence current)
Copycurrent
into an internal buffer.
-
-
-
Field Detail
-
LEXICOGRAPHIC_ORDER
public static final java.util.Comparator<java.lang.CharSequence> LEXICOGRAPHIC_ORDER
Lexicographic order of input sequences.
-
register
private java.util.HashMap<StringUnionOperations.State,StringUnionOperations.State> register
"register" for state interning.
-
root
private StringUnionOperations.State root
Root automaton state.
-
previous
private java.lang.StringBuilder previous
Previous sequence added to the automaton inadd(CharSequence)
.
-
-
Method Detail
-
add
public void add(java.lang.CharSequence current)
Add another character sequence to this automaton. The sequence must be lexicographically larger or equal compared to any previous sequences added to this automaton (the input must be sorted).
-
complete
public StringUnionOperations.State complete()
Finalize the automaton and return the root state. No more strings can be added to the builder after this call.- Returns:
- Root automaton state.
-
convert
private static State convert(StringUnionOperations.State s, java.util.IdentityHashMap<StringUnionOperations.State,State> visited)
Internal recursive traversal for conversion.
-
build
public static State build(java.lang.CharSequence[] input)
Build a minimal, deterministic automaton from a sorted list of strings.
-
setPrevious
private boolean setPrevious(java.lang.CharSequence current)
Copycurrent
into an internal buffer.
-
replaceOrRegister
private void replaceOrRegister(StringUnionOperations.State state)
Replace last child ofstate
with an already registered state or register the last child state.
-
addSuffix
private void addSuffix(StringUnionOperations.State state, java.lang.CharSequence current, int fromIndex)
Add a suffix ofcurrent
starting atfromIndex
(inclusive) to statestate
.
-
-