trie

README

trie

Generic prefix tree for golang

example

    import (
        "fmt"
        "log"

        "github.com/s0rg/trie"
    )

    func main() {
        t := trie.New[int]()

        t.Add("bar", 1)
        t.Add("baz", 2)
        t.Add("bat", 3)

        val, ok := t.Find("bar")
        if !ok {
            log.Fatal("not found")
        }

        fmt.Println(val) // will print 1
    }

Documentation

Index

• type Trie
  • func New[T any]() *Trie[T]
  • func (t *Trie[T]) Add(key string, value T)
  • func (t *Trie[T]) Common(prefix string, minLength int) (rv []string)
  • func (t *Trie[T]) Del(key string) (ok bool)
  • func (t *Trie[T]) Find(key string) (value T, ok bool)
  • func (t *Trie[T]) Iter(prefix string, walker func(key string, value T))
  • func (t *Trie[T]) String() string
  • func (t *Trie[T]) Suggest(prefix string) (rv []string, ok bool)

Types

type Trie

type Trie[T any] struct {
	// contains filtered or unexported fields
}

Trie represents generic prefix-tree.

func New

func New[T any]() *Trie[T]

New creates empty Trie.

func (*Trie[T]) Add

func (t *Trie[T]) Add(key string, value T)

Add inserts new key/value pair.

func (*Trie[T]) Common

func (t *Trie[T]) Common(prefix string, minLength int) (rv []string)

Common returns slice of common keys with at least `minLength` of their length Pass prefix="" to find all commons whithin given length Resulting slice is sorted by overall matching keys count, key with most goes first.

func (*Trie[T]) Del

func (t *Trie[T]) Del(key string) (ok bool)

Del removes node by key.

func (*Trie[T]) Find

func (t *Trie[T]) Find(key string) (value T, ok bool)

Find does tree-lookup in order to find value associated with given key.

func (*Trie[T]) Iter

func (t *Trie[T]) Iter(prefix string, walker func(key string, value T))

Iter iterates over trie by prefix using dfs. Pass prefix="" to iterate over whole trie.

func (*Trie[T]) String

func (t *Trie[T]) String() string

String implements fmt.Stringer interface.

func (*Trie[T]) Suggest

func (t *Trie[T]) Suggest(prefix string) (rv []string, ok bool)

Suggest returns slice of existing keys with matching prefix.