prefix

Documentation

Overview

Package prefix holds a prefix tree for strings. The term word is used to refer to values which are present in the tree. Gram is used to refer to any sequence that exists in the tree. For instance is the word 'test' is inserted then the tree contains the gram 'tes' but it will not be a word.

Index

• type Node
• type Nodes
  • func (ns Nodes) AllWords() Nodes
  • func (ns Nodes) Strings() list.Wrapper[string]
• type Prefix
  • func New() *Prefix
  • func (p *Prefix) Containing(gram string) Nodes
  • func (p *Prefix) Find(gram string) Node
  • func (p *Prefix) Purge()
  • func (p *Prefix) Remove(word string)
  • func (p *Prefix) Upsert(word string) (n Node, insert bool)
• type Suggestion
  • func (s Suggestion) Words(prefix string) []string

Types

type Node

type Node interface {
	// Child looks up the child node by rune
	Child(rune) Node
	// Children returns all the child runes
	Children() []rune
	// ChildrenCount returns the number of children
	ChildrenCount() int
	// IsWord returns true if this Node was inserted as word into the tree
	IsWord() bool
	// Gram returns the string this node represents
	Gram() string
	Suggest(max int) []Suggestion
	// AllWords returns all child nodes (including self) that are a word.
	AllWords() Nodes
}

Node in a prefix tree.

type Nodes

type Nodes []Node

Nodes is a slice of Nodes

func (Nodes) AllWords

func (ns Nodes) AllWords() Nodes

func (Nodes) Strings

func (ns Nodes) Strings() list.Wrapper[string]

Strings returns a list.Wrapper for getting the strings from nodes.

type Prefix

type Prefix struct {
	// contains filtered or unexported fields
}

Prefix is the root of a prefix tree

func New

func New() *Prefix

New Prefix tree.

func (*Prefix) Containing

func (p *Prefix) Containing(gram string) Nodes

Containing returns all nodes in the tree containing the specified gram, even if they do not begin with the specified gram.

func (*Prefix) Find

func (p *Prefix) Find(gram string) Node

Find a node by it's gram. If there are no prefixes starting with the gram, nil is returned.

func (*Prefix) Purge

func (p *Prefix) Purge()

func (*Prefix) Remove

func (p *Prefix) Remove(word string)

func (*Prefix) Upsert

func (p *Prefix) Upsert(word string) (n Node, insert bool)

Upsert a word into the prefix tree returning the Node for that word and a bool indicating if an insert happened.

type Suggestion

type Suggestion struct {
	Word      string
	Terminals []int
}

func (Suggestion) Words

func (s Suggestion) Words(prefix string) []string