Documentation
¶
Overview ¶
Package gtrie provides a trie implementation based on a minimal acyclic finite-state automaton.
Index ¶
- func Size(node *Node) int
- type Node
- func (n *Node) Accepts(suffix string) bool
- func (n *Node) ChildKeys() []string
- func (z *Node) DecodeMsg(dc *msgp.Reader) (err error)
- func (z *Node) EncodeMsg(en *msgp.Writer) (err error)
- func (n *Node) GetChild(letter rune) (child *Node)
- func (n *Node) HasChild(letter rune) bool
- func (n *Node) HasChildren() bool
- func (n *Node) HasPrefix(prefix string) (*Node, error)
- func (z *Node) MarshalMsg(b []byte) (o []byte, err error)
- func (z *Node) Msgsize() (s int)
- func (z *Node) UnmarshalMsg(bts []byte) (o []byte, err error)
- type NodeId
- type Transition
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
Types ¶
type Node ¶
type Node struct {
Id NodeId
Terminal bool
Transitions []Transition
}
Represents a node in the acyclic finite-state automaton.
func Create ¶
Creates an acyclic finite-state automaton from a sorted list of words and returns the root node. Words can contain any unicode chararcters. An error will be returned if the list of words is not lexicographically sorted.
func (*Node) Accepts ¶
Whether the node recognizes the given suffix. A suffix is accepted if there exists a path from the current node to a final node labeled with the suffix elements.
func (*Node) GetChild ¶
Retrieves the child for the given letter. Returns nil if there is no child for this letter.
func (*Node) HasPrefix ¶
Whether the given prefix is found in the tree. Most useful reading off the root node.
func (*Node) MarshalMsg ¶
MarshalMsg implements msgp.Marshaler
type NodeId ¶
type NodeId int
func (NodeId) MarshalMsg ¶
MarshalMsg implements msgp.Marshaler
type Transition ¶
Represents a transition in the acyclic finite-state automaton. Each transition has one label and leads to one node.
func (*Transition) DecodeMsg ¶
func (z *Transition) DecodeMsg(dc *msgp.Reader) (err error)
DecodeMsg implements msgp.Decodable
func (*Transition) EncodeMsg ¶
func (z *Transition) EncodeMsg(en *msgp.Writer) (err error)
EncodeMsg implements msgp.Encodable
func (*Transition) MarshalMsg ¶
func (z *Transition) MarshalMsg(b []byte) (o []byte, err error)
MarshalMsg implements msgp.Marshaler
func (*Transition) Msgsize ¶
func (z *Transition) Msgsize() (s int)
func (*Transition) UnmarshalMsg ¶
func (z *Transition) UnmarshalMsg(bts []byte) (o []byte, err error)
UnmarshalMsg implements msgp.Unmarshaler
Source Files