Documentation ¶
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Cell ¶ added in v0.5.0
type Cell uint64
Cell represents a states / transitions in the table.
Cells are 64 bit unsigned integers with the following layout: 23 bit unused | 1 bit data marker | 8 bit character | 32 bit data
func MkCell ¶ added in v0.7.0
MkCell creates a new cell. If isdata is true, a state-cell is created. Otherwise a transition-cell with the given character and target state is created. TODO: Check if it is correct to set c for data/state-cells.
func (Cell) Data ¶ added in v0.5.0
Data returns the target state of a transition-cell or the target info string of a state-cell (if not 0).
type CompactedTrieBuilder ¶ added in v0.2.0
type CompactedTrieBuilder struct {
// contains filtered or unexported fields
}
Builder for compacted tries.
func NewCompactedTrieBuilder ¶ added in v0.2.0
func NewCompactedTrieBuilder(opts ...CompactedTrieBuilderOption) *CompactedTrieBuilder
NewCompactedTrieBuilder creates a new builder that builds a compacted trie.
func (*CompactedTrieBuilder) Add ¶ added in v0.2.0
func (b *CompactedTrieBuilder) Add(wf, v string) error
Add adds a key-value pair to the builder. The resulting automaton then associates key wf with value v.
func (*CompactedTrieBuilder) AddToAlphabet ¶ added in v0.2.0
func (b *CompactedTrieBuilder) AddToAlphabet(chars string)
AddToAlphabet adds all characters (bytes) in str to the builder's internal alphabet.
All characters of keys added to the builder must be added to the alphabet before being added to the builder. The zero character \0 has special meaning and cannot be added to the builder's alphabet.
func (*CompactedTrieBuilder) Build ¶ added in v0.2.0
func (b *CompactedTrieBuilder) Build() (*FSA, error)
Build finishes the building process and returns the CFSA.
func (*CompactedTrieBuilder) Statistics ¶ added in v0.2.0
func (b *CompactedTrieBuilder) Statistics() Statistics
Statistics returns a Statistics struct.
type CompactedTrieBuilderOption ¶ added in v0.2.0
type CompactedTrieBuilderOption func(*CompactedTrieBuilder)
CompactedTrieBuilderOptions defines options
func CompactedTrieWithSeperator ¶ added in v0.2.0
func CompactedTrieWithSeperator(enable bool) CompactedTrieBuilderOption
CompactedTrieWithSeperator enables/disables special handling of ` ` characters in the input strings. If this option is enabled and such a seperator is encountered in an input string, the resulting automaton accepts one or more sequences of ` ` within the accepted strings.
type DFAState ¶ added in v0.4.0
type DFAState interface { Final() (string, bool) // Return if the state is final and additional data if the state is final. Target(byte) DFAState // Target for the given transition or nil for nonexistent transitions. LinkTo(byte, DFAState) // Link this state to a target state. }
DFAState represents a state in a DFA. They can be used to construct a FSA instance.
Final states should return their rewrite data in the implementation of the Final() method. If a node has no target transition, nil should be returned.
type DFAStateFactory ¶ added in v0.8.0
type DFAStateFactory interface {
New(final bool, data string) DFAState // Create a new (non-) final state.
}
DFAStateFactory is used to create DFANodes. If `final` is true, data denotes the new state's final data, otherwise data should be ignored.
type FSA ¶
type FSA struct { Infos []byte // Holds the rewrite strings (null-terminated). Cells []Cell // Cells of the automaton. Codec [nchars]byte // Codec maps -> external bytes to internal bytes. }
func NewFSAFromDFA ¶ added in v0.7.0
NewFSAFromDFA creates a new fsa from a DFA with the given initial state. The function returns an error if the given nodes do not represent a valid DFA.
func (*FSA) Delta ¶
Delta executes a transition from s using c and returns the target state. If no transition can be executed, 0 is returned.
type NDFAState ¶ added in v0.4.0
type NDFAState interface { Final() (string, bool) // Return if the state is final and additional final data if final. Targets(c byte) []NDFAState // Targets for the given transitions. ID() uint64 // The unique id for this node. }
NDFAState represents a state in a NDFA. They can be used to construct an deterministic automaton and from there be converted into a DFA instance.
Final states should return their rewrite data in the implementation of the Final() method. If a node has no target transition, nil (or an empty array) should be returned. Each distinct NDFAState must return a unique id with it's ID() method.