Documentation
¶
Overview ¶
Package prefixtrie implements a compressed (radix) trie that finds the keys a string starts with in one O(len(s)) walk, however many keys there are. A trie of reversed keys (see Reverse) finds the keys a string ends with.
Index ¶
- func Reverse(s string) string
- type Entry
- type Trie
- func (p *Trie[V]) Compact()
- func (p *Trie[V]) Entries() []Entry[V]
- func (p *Trie[V]) HasPrefixOf(s string) bool
- func (p *Trie[V]) HasSuffixOf(s string) bool
- func (p *Trie[V]) Insert(key string) *V
- func (p *Trie[V]) PrefixesOf(s string, visit func(*V) error) error
- func (p *Trie[V]) SuffixesOf(s string, visit func(*V) error) error
- func (p *Trie[V]) Values(visit func(*V) error) error
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
Types ¶
type Trie ¶
type Trie[V any] struct { // contains filtered or unexported fields }
Trie maps string keys to values of type V. The zero value is an empty trie.
func (*Trie[V]) Compact ¶
func (p *Trie[V]) Compact()
Compact releases the edge slices' spare capacity, often more than half of it. Call it once nothing more will be inserted.
func (*Trie[V]) Entries ¶
Entries returns the trie's keys in lexicographic order. It allocates a string per key, so is meant for debugging and tests.
func (*Trie[V]) HasPrefixOf ¶
HasPrefixOf reports whether s starts with any key in the trie.
func (*Trie[V]) HasSuffixOf ¶
HasSuffixOf reports whether s ends with any key, in a trie of reversed keys.
func (*Trie[V]) PrefixesOf ¶
PrefixesOf calls visit with the value of every key s starts with, shortest first, stopping at the first error.
func (*Trie[V]) SuffixesOf ¶
SuffixesOf is PrefixesOf for the end of s, in a trie of reversed keys.
Source Files