gtrie

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 Create(words []string) (automaton *Node, err error)
  • 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
  • func (z *NodeId) DecodeMsg(dc *msgp.Reader) (err error)
  • func (z NodeId) EncodeMsg(en *msgp.Writer) (err error)
  • func (z NodeId) MarshalMsg(b []byte) (o []byte, err error)
  • func (z NodeId) Msgsize() (s int)
  • func (z *NodeId) UnmarshalMsg(bts []byte) (o []byte, err error)
• type Transition
  • func (z *Transition) DecodeMsg(dc *msgp.Reader) (err error)
  • func (z *Transition) EncodeMsg(en *msgp.Writer) (err error)
  • func (z *Transition) MarshalMsg(b []byte) (o []byte, err error)
  • func (z *Transition) Msgsize() (s int)
  • func (z *Transition) UnmarshalMsg(bts []byte) (o []byte, err error)

Functions

func Size

func Size(node *Node) int

Gets the number of nodes in the given automaton.

Types

type Node

type Node struct {
	Id          NodeId
	Terminal    bool
	Transitions []Transition
}

Represents a node in the acyclic finite-state automaton.

func Create

func Create(words []string) (automaton *Node, err error)

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

func (n *Node) Accepts(suffix string) bool

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) ChildKeys

func (n *Node) ChildKeys() []string

func (*Node) DecodeMsg

func (z *Node) DecodeMsg(dc *msgp.Reader) (err error)

DecodeMsg implements msgp.Decodable

func (*Node) EncodeMsg

func (z *Node) EncodeMsg(en *msgp.Writer) (err error)

EncodeMsg implements msgp.Encodable

func (*Node) GetChild

func (n *Node) GetChild(letter rune) (child *Node)

Retrieves the child for the given letter. Returns nil if there is no child for this letter.

func (*Node) HasChild

func (n *Node) HasChild(letter rune) bool

Checks whether the node has a child for the given letter.

func (*Node) HasChildren

func (n *Node) HasChildren() bool

Checks whether the node has children.

func (*Node) HasPrefix

func (n *Node) HasPrefix(prefix string) (*Node, error)

Whether the given prefix is found in the tree. Most useful reading off the root node.

func (*Node) MarshalMsg

func (z *Node) MarshalMsg(b []byte) (o []byte, err error)

MarshalMsg implements msgp.Marshaler

func (*Node) Msgsize

func (z *Node) Msgsize() (s int)

func (*Node) UnmarshalMsg

func (z *Node) UnmarshalMsg(bts []byte) (o []byte, err error)

UnmarshalMsg implements msgp.Unmarshaler

type NodeId

type NodeId int

func (*NodeId) DecodeMsg

func (z *NodeId) DecodeMsg(dc *msgp.Reader) (err error)

DecodeMsg implements msgp.Decodable

func (NodeId) EncodeMsg

func (z NodeId) EncodeMsg(en *msgp.Writer) (err error)

EncodeMsg implements msgp.Encodable

func (NodeId) MarshalMsg

func (z NodeId) MarshalMsg(b []byte) (o []byte, err error)

MarshalMsg implements msgp.Marshaler

func (NodeId) Msgsize

func (z NodeId) Msgsize() (s int)

func (*NodeId) UnmarshalMsg

func (z *NodeId) UnmarshalMsg(bts []byte) (o []byte, err error)

UnmarshalMsg implements msgp.Unmarshaler

type Transition

type Transition struct {
	Child *Node
	Label rune
}

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