trie

Documentation

Overview

Package trie provides a character-based prefix trie data structure for storing arbitrary payloads in an efficiently retrievable manner.

Index

• type Trie
  • func New() *Trie
  • func (t *Trie) FindPrefixes(key string, f Visitor)
  • func (t *Trie) FindSuffixes(key string, f Visitor)
  • func (t *Trie) SetValue(key string, value any)
  • func (t *Trie) Size() int
• type Visitor

Types

type Trie

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

Trie stores data at given strings in tree structure, for linear-time retrieval. Call New() to obtain a valid Trie.

func New

func New() *Trie

New creates a new instance of the Trie interface.

func (*Trie) FindPrefixes

func (t *Trie) FindPrefixes(key string, f Visitor)

FindPrefixes invokes the Visitor with all key-value pairs where the key is a prefix of `key`, including exact matches. It does this in increasing order of key length, and terminates early if Visitor returns false.

func (*Trie) FindSuffixes

func (t *Trie) FindSuffixes(key string, f Visitor)

FindSuffixes invokes the Visitor with all key-value pairs where the key is prefixed by `key`, including exact matches. It does this in an unspecified order, and terminates early if the Visitor returns false.

Invoking FindSuffixes with the empty string as a key will iterate over all values.

func (*Trie) SetValue

func (t *Trie) SetValue(key string, value any)

SetValue associates the specified key with the given value, replacing any existing value.

func (*Trie) Size

func (t *Trie) Size() int

Size returns the total number of values in the Trie.

type Visitor

type Visitor func(prefix string, value any) bool

Visitor accepts a prefix string and an associated value, and returns true iff searching should continue deeper into the Trie. It is used by FindMatching().