README
¶
automaton
Documentation
¶
Index ¶
- Constants
- func GetSingletonAutomaton(a *Automaton) ([]int, error)
- func IsEmptyAutomaton(a *Automaton) bool
- func IsFiniteAutomaton(a *Automaton) *atomic.Bool
- func IsTotalAutomaton(a *Automaton) bool
- func IsTotalAutomatonRange(a *Automaton, minAlphabet, maxAlphabet int) bool
- func Run(a *Automaton, s string) bool
- type Automata
- func (*Automata) MakeAnyBinary() (*Automaton, error)
- func (r *Automata) MakeAnyChar() (*Automaton, error)
- func (*Automata) MakeAnyString() (*Automaton, error)
- func (r *Automata) MakeBinary(term []byte) (*Automaton, error)
- func (r *Automata) MakeBinaryInterval(min []byte, minInclusive bool, max []byte, maxInclusive bool) (*Automaton, error)
- func (r *Automata) MakeChar(c int32) (*Automaton, error)
- func (r *Automata) MakeCharRange(min, max int32) (*Automaton, error)
- func (r *Automata) MakeDecimalInterval(min, max, digits int) (*Automaton, error)
- func (*Automata) MakeEmpty() *Automaton
- func (*Automata) MakeEmptyString() *Automaton
- func (*Automata) MakeNonEmptyBinary() (*Automaton, error)
- func (r *Automata) MakeString(s string) (*Automaton, error)
- type Automaton
- func (a *Automaton) AddEpsilon(source, dest int)
- func (a *Automaton) AddTransition(source, dest, min, max int) error
- func (a *Automaton) AddTransitionLabel(source, dest, label int) error
- func (a *Automaton) Copy(other *Automaton)
- func (a *Automaton) CreateState() int
- func (a *Automaton) FinishState()
- func (a *Automaton) GetNextTransition(t *Transition)
- func (a *Automaton) GetNumStates() int
- func (a *Automaton) GetNumTransitions() int
- func (a *Automaton) GetNumTransitionsWithState(state int) int
- func (a *Automaton) GetStartPoints() []int
- func (a *Automaton) InitTransition(state int, t *Transition) int
- func (a *Automaton) IsAccept(state int) bool
- func (a *Automaton) IsDeterministic() bool
- func (a *Automaton) NewByteRunAutomaton() *ByteRunAutomaton
- func (a *Automaton) Next(transition *Transition, label int) int
- func (a *Automaton) SetAccept(state int, accept bool)
- func (a *Automaton) Step(state, label int) int
- type Builder
- func (r *Builder) AddEpsilon(source, dest int)
- func (r *Builder) AddTransition(source, dest, min, max int)
- func (r *Builder) AddTransitionLabel(source, dest, label int)
- func (r *Builder) Copy(other *Automaton)
- func (r *Builder) CopyStates(other *Automaton)
- func (r *Builder) CreateState() int
- func (r *Builder) Finish() *Automaton
- func (r *Builder) GetNumStates() int
- func (r *Builder) IsAccept(state int) bool
- func (r *Builder) SetAccept(state int, accept bool)
- type ByteRunAutomaton
- type CompiledAutomaton
- type Entry
- type FrozenIntSet
- type HashMap
- type Hashable
- type IntPair
- type IntSet
- type Kind
- type MockIntSet
- type OptionsHashMap
- type PointTransitionSet
- type PointTransitions
- type Provider
- type RegExp
- type RegExpOption
- type RunAutomaton
- type StateList
- type StateListNode
- type StateSet
- type ToAutomatonOptions
- type Transition
- type TransitionList
Constants ¶
const ( // Golden ratio bit mixers. PHI_C32 = uint32(0x9e3779b9) PHI_C64 = uint64(0x9e3779b97f4a7c15) )
const ( AUTOMATON_TYPE_NONE = iota // Automaton that accepts no strings. AUTOMATON_TYPE_ALL // Automaton that accepts all possible strings. AUTOMATON_TYPE_SINGLE // Automaton that accepts only a single fixed string. AUTOMATON_TYPE_NORMAL // Catch-all for any other automata. )
const ( REGEXP_UNION = Kind(iota) // The union of two expressions REGEXP_CONCATENATION // A sequence of two expressions REGEXP_INTERSECTION // The intersection of two expressions REGEXP_OPTIONAL // An optional expression REGEXP_REPEAT // An expression that repeats REGEXP_REPEAT_MIN // An expression that repeats a minimum number of times REGEXP_REPEAT_MINMAX // An expression that repeats a minimum and maximum number of times REGEXP_COMPLEMENT // The complement of an expression REGEXP_CHAR // A Character REGEXP_CHAR_RANGE // A Character range REGEXP_ANYCHAR // Any Character allowed REGEXP_EMPTY // An empty expression REGEXP_STRING // A string expression REGEXP_ANYSTRING // Any string allowed REGEXP_AUTOMATON // An Automaton expression REGEXP_INTERVAL // An Interval expression )
const ( INTERSECTION = 0x0001 COMPLEMENT = 0x0002 EMPTY = 0x0004 ANYSTRING = 0x0008 AUTOMATON = 0x0010 INTERVAL = 0x0020 ALL = 0xff NONE = 0x0000 ASCII_CASE_INSENSITIVE = 0x0100 )
const (
DEFAULT_DETERMINIZE_WORK_LIMIT = 10000
)
Variables ¶
This section is empty.
Functions ¶
func GetSingletonAutomaton ¶
func IsEmptyAutomaton ¶
IsEmptyAutomaton Returns true if the given automaton accepts no strings.
func IsFiniteAutomaton ¶
func IsTotalAutomaton ¶
IsTotalAutomaton Returns true if the given automaton accepts all strings. The automaton must be minimized.
func IsTotalAutomatonRange ¶
IsTotalAutomatonRange Returns true if the given automaton accepts all strings for the specified min/max range of the alphabet. The automaton must be minimized.
Types ¶
type Automata ¶
type Automata struct {
}
func (*Automata) MakeAnyBinary ¶
func (*Automata) MakeAnyChar ¶
func (*Automata) MakeAnyString ¶
MakeAnyString Returns a new (deterministic) automaton that accepts all strings.
func (*Automata) MakeBinaryInterval ¶
func (*Automata) MakeCharRange ¶
func (*Automata) MakeDecimalInterval ¶
func (*Automata) MakeEmpty ¶
MakeEmpty Returns a new (deterministic) automaton with the empty language.
func (*Automata) MakeEmptyString ¶
MakeEmptyString Returns a new (deterministic) automaton that accepts only the empty string.
func (*Automata) MakeNonEmptyBinary ¶
type Automaton ¶
type Automaton struct {
// contains filtered or unexported fields
}
Automaton Represents an automaton and all its states and transitions. States are integers and must be created using createState. Mark a state as an accept state using setAccept. Add transitions using addTransition. Each state must have all of its transitions added at once; if this is too restrictive then use Automaton.Builder instead. State 0 is always the initial state. Once a state is finished, either because you've starting adding transitions to another state or you call FinishState, then that states transitions are sorted (first by min, then max, then dest) and reduced (transitions with adjacent labels going to the same dest are combined).
func DeterminizeAutomaton ¶
DeterminizeAutomaton Determinizes the given automaton. Worst case complexity: exponential in number of states. Params: workLimit – Maximum amount of "work" that the powerset construction will spend before throwing
TooComplexToDeterminizeException. Higher numbers allow this operation to consume more memory and CPU but allow more complex automatons. Use DEFAULT_DETERMINIZE_WORK_LIMIT as a decent default if you don't otherwise know what to specify.
Throws: TooComplexToDeterminizeException – if determinizing requires more than workLimit "effort"
func Minimize ¶
Minimize Minimizes (and determinizes if not already deterministic) the given automaton using Hopcroft's algorithm.
func NewAutomaton ¶
func NewAutomaton() *Automaton
func NewAutomatonV1 ¶
func (*Automaton) AddEpsilon ¶
AddEpsilon Add a [virtual] epsilon transition between source and dest. Dest state must already have all transitions added because this method simply copies those same transitions over to source.
func (*Automaton) AddTransition ¶
AddTransition Add a new transition with the specified source, dest, min, max.
func (*Automaton) AddTransitionLabel ¶
AddTransitionLabel Add a new transition with min = max = label.
func (*Automaton) Copy ¶
Copy Copies over all states/transitions from other. The states numbers are sequentially assigned (appended).
func (*Automaton) CreateState ¶
CreateState Create a new state.
func (*Automaton) FinishState ¶
func (a *Automaton) FinishState()
FinishState Finishes the current state; call this once you are done adding transitions for a state. This is automatically called if you start adding transitions to a new source state, but for the last state you add you need to this method yourself.
func (*Automaton) GetNextTransition ¶
func (a *Automaton) GetNextTransition(t *Transition)
GetNextTransition Iterate to the next transition after the provided one
func (*Automaton) GetNumStates ¶
GetNumStates How many states this automaton has.
func (*Automaton) GetNumTransitions ¶
GetNumTransitions How many transitions this automaton has.
func (*Automaton) GetNumTransitionsWithState ¶
GetNumTransitionsWithState How many transitions this state has.
func (*Automaton) GetStartPoints ¶
GetStartPoints Returns sorted array of all interval start points.
func (*Automaton) InitTransition ¶
func (a *Automaton) InitTransition(state int, t *Transition) int
InitTransition Initialize the provided Transition to iterate through all transitions leaving the specified state. You must call GetNextTransition to get each transition. Returns the number of transitions leaving this state.
func (*Automaton) IsDeterministic ¶
IsDeterministic Returns true if this automaton is deterministic (for ever state there is only one transition for each label).
func (*Automaton) NewByteRunAutomaton ¶
func (a *Automaton) NewByteRunAutomaton() *ByteRunAutomaton
func (*Automaton) Next ¶
func (a *Automaton) Next(transition *Transition, label int) int
Next Looks for the next transition that matches the provided label, assuming determinism. This method is similar to step(int, int) but is used more efficiently when iterating over multiple transitions from the same source state. It keeps the latest reached transition index in transition.transitionUpto so the next call to this method can continue from there instead of restarting from the first transition.
transition: The transition to start the lookup from (inclusive, using its Transition.source and Transition.transitionUpto). It is updated with the matched transition; or with Transition.dest = -1 if no match.
label: The codepoint to look up.
Returns: The destination state; or -1 if no matching outgoing transition.
type Builder ¶
type Builder struct {
// contains filtered or unexported fields
}
Builder Records new states and transitions and then finish creates the Automaton. Use this when you cannot create the Automaton directly because it's too restrictive to have to add all transitions leaving each state at once.
func NewBuilder ¶
func NewBuilder() *Builder
func NewBuilderV1 ¶
func (*Builder) AddEpsilon ¶
func (*Builder) AddTransition ¶
func (*Builder) AddTransitionLabel ¶
func (*Builder) CopyStates ¶
CopyStates Copies over all states from other.
func (*Builder) CreateState ¶
func (*Builder) GetNumStates ¶
type ByteRunAutomaton ¶
type ByteRunAutomaton struct {
*RunAutomaton
}
ByteRunAutomaton Automaton representation for matching UTF-8 byte[].
func NewByteRunAutomaton ¶
func NewByteRunAutomaton(a *Automaton, isBinary bool, determinizeWorkLimit int) *ByteRunAutomaton
func (*ByteRunAutomaton) Run ¶
func (r *ByteRunAutomaton) Run(s []byte) bool
Run Returns true if the given byte array is accepted by this automaton
type CompiledAutomaton ¶
type CompiledAutomaton struct {
// contains filtered or unexported fields
}
CompiledAutomaton Immutable class holding compiled details for a given Automaton. The Automaton is deterministic, must not have dead states but is not necessarily minimal.
func NewCompiledAutomaton ¶
func NewCompiledAutomaton(automaton *Automaton, finite *atomic.Bool, simplify bool, determinizeWorkLimit int, isBinary bool) (*CompiledAutomaton, error)
NewCompiledAutomaton Create this. If finite is null, we use Operations.isFinite to determine whether it is finite. If simplify is true, we run possibly expensive operations to determine if the automaton is one the cases in CompiledAutomaton.AUTOMATON_TYPE. If simplify requires determinizing the automaton then at most determinizeWorkLimit effort will be spent. Any more than that will cause a TooComplexToDeterminizeException.
func (*CompiledAutomaton) RunAutomaton ¶
func (r *CompiledAutomaton) RunAutomaton() *ByteRunAutomaton
func (*CompiledAutomaton) Term ¶
func (r *CompiledAutomaton) Term() []byte
func (*CompiledAutomaton) Type ¶
func (r *CompiledAutomaton) Type() int
type FrozenIntSet ¶
type FrozenIntSet struct {
// contains filtered or unexported fields
}
func NewFrozenIntSet ¶
func NewFrozenIntSet(values []int, hashCode uint64, state int) *FrozenIntSet
func (*FrozenIntSet) Equals ¶
func (f *FrozenIntSet) Equals(other Hashable) bool
func (*FrozenIntSet) GetArray ¶
func (f *FrozenIntSet) GetArray() []int
func (*FrozenIntSet) Hash ¶
func (f *FrozenIntSet) Hash() uint64
func (*FrozenIntSet) Size ¶
func (f *FrozenIntSet) Size() int
type HashMap ¶
type HashMap[T any] struct { // contains filtered or unexported fields }
HashMap 自定义哈希表结构
func NewHashMap ¶
func NewHashMap[T any](options ...OptionsHashMap) *HashMap[T]
NewHashMap 创建哈希表 参数：capacity 初始容量（自动调整为2的幂）
type MockIntSet ¶
type MockIntSet struct {
}
func (MockIntSet) Equals ¶
func (m MockIntSet) Equals(other Hashable) bool
func (MockIntSet) GetArray ¶
func (m MockIntSet) GetArray() []int
func (MockIntSet) Hash ¶
func (m MockIntSet) Hash() uint64
func (MockIntSet) Size ¶
func (m MockIntSet) Size() int
type OptionsHashMap ¶
type OptionsHashMap func(hashMap *optionsHashMap)
func WithCapacity ¶
func WithCapacity(capacity int) OptionsHashMap
func WithLoadFactory ¶
func WithLoadFactory(loadFactory float64) OptionsHashMap
type PointTransitionSet ¶
type PointTransitionSet struct {
// contains filtered or unexported fields
}
func NewPointTransitionSet ¶
func NewPointTransitionSet() *PointTransitionSet
func (*PointTransitionSet) Add ¶
func (s *PointTransitionSet) Add(t *Transition)
func (*PointTransitionSet) Reset ¶
func (s *PointTransitionSet) Reset()
func (*PointTransitionSet) Sort ¶
func (s *PointTransitionSet) Sort()
type PointTransitions ¶
type PointTransitions struct {
// contains filtered or unexported fields
}
func NewPointTransitions ¶
func NewPointTransitions() *PointTransitions
type RegExp ¶
type RegExp struct {
// contains filtered or unexported fields
}
func (*RegExp) ToAutomaton ¶
type RegExpOption ¶
type RegExpOption func(*regExpOption)
func WithMatchFlags ¶
func WithMatchFlags(matchFlags int) RegExpOption
func WithSyntaxFlags ¶
func WithSyntaxFlags(syntaxFlags int) RegExpOption
type RunAutomaton ¶
type RunAutomaton struct {
// contains filtered or unexported fields
}
RunAutomaton Finite-state automaton with fast run operation. The initial state is always 0.
func NewRunAutomaton ¶
func NewRunAutomaton(a *Automaton, alphabetSize, determinizeWorkLimit int) *RunAutomaton
func (*RunAutomaton) GetCharClass ¶
func (r *RunAutomaton) GetCharClass(c int) int
GetCharClass Gets character class of given codepoint
func (*RunAutomaton) GetSize ¶
func (r *RunAutomaton) GetSize() int
GetSize Returns number of states in automaton.
func (*RunAutomaton) IsAccept ¶
func (r *RunAutomaton) IsAccept(state int) bool
IsAccept Returns acceptance status for given state.
func (*RunAutomaton) Step ¶
func (r *RunAutomaton) Step(state int, c int) int
Step Returns the state obtained by reading the given char from the given state. Returns -1 if not obtaining any such state. (If the original Automaton had no dead states, -1 is returned here if and only if a dead state is entered in an equivalent automaton with a total transition function.)
type StateListNode ¶
type StateListNode struct {
}
type StateSet ¶
type StateSet struct {
// contains filtered or unexported fields
}
func NewStateSet ¶
func NewStateSet() *StateSet
func (*StateSet) Freeze ¶
func (s *StateSet) Freeze(state int) *FrozenIntSet
type ToAutomatonOptions ¶
type ToAutomatonOptions func(*toAutomatonOptions)
func WithAutomata ¶
func WithAutomata(automata map[string]*Automaton) ToAutomatonOptions
func WithAutomatonProvider ¶
func WithAutomatonProvider(automatonProvider Provider) ToAutomatonOptions
type Transition ¶
type Transition struct {
// Source state.
Source int
// Destination state.
Dest int
// Minimum accepted label (inclusive).
Min int
// Maximum accepted label (inclusive).
Max int
// Remembers where we are in the iteration; init to -1 to provoke exception if nextTransition is
// called without first initTransition.
TransitionUpto int
}
Transition Holds one transition from an Automaton. This is typically used temporarily when iterating through transitions by invoking Automaton.initTransition and Automaton.getNextTransition.
func NewTransition ¶
func NewTransition() *Transition
type TransitionList ¶
type TransitionList struct {
// contains filtered or unexported fields
}
func NewTransitionList ¶
func NewTransitionList() *TransitionList
func (*TransitionList) Add ¶
func (t *TransitionList) Add(item *Transition)
Source Files