trie

Documentation

Overview

Package trie implements a string prefix trie.

Index

• type Branches
• type Node
• type SyncTrie
  • func NewSyncTrie[V any]() *SyncTrie[V]
  • func (self *SyncTrie[V]) Delete(key string) (value V, deleted bool)
  • func (self *SyncTrie[V]) Enum(f func(key string, value V) bool)
  • func (self *SyncTrie[V]) EnumKeys(f func(key string) bool)
  • func (self *SyncTrie[V]) EnumValues(f func(value V) bool)
  • func (self *SyncTrie[V]) Exists(key string) (exists bool)
  • func (self *SyncTrie[V]) Get(key string) (value V, found bool)
  • func (self *SyncTrie[V]) HasPrefixes(key string) (truth bool)
  • func (self *SyncTrie[V]) HasSuffixes(key string) (truth bool)
  • func (self *SyncTrie[V]) Prefixes(key string) (out []string)
  • func (self *SyncTrie[V]) Print(w io.Writer)
  • func (self *SyncTrie[V]) Put(key string, value V) (old V, replaced bool)
  • func (self *SyncTrie[V]) Suffixes(key string) (out []string)
• type Trie
  • func New[V any]() *Trie[V]
  • func (self *Trie[V]) Delete(key string) (value V, deleted bool)
  • func (self *Trie[V]) Enum(f func(key string, value V) bool)
  • func (self *Trie[V]) EnumKeys(f func(key string) bool)
  • func (self *Trie[V]) EnumValues(f func(value V) bool)
  • func (self *Trie[V]) Exists(key string) (exists bool)
  • func (self *Trie[V]) Get(key string) (value V, found bool)
  • func (self *Trie[V]) HasPrefixes(key string) bool
  • func (self *Trie[V]) HasSuffixes(key string) bool
  • func (self *Trie[V]) Prefixes(key string) (out []string)
  • func (self *Trie[V]) Print(w io.Writer)
  • func (self *Trie[V]) Put(key string, value V) (old V, replaced bool)
  • func (self *Trie[V]) Suffixes(key string) (out []string)

Types

type Branches

type Branches[V any] []*Node[V]

Branches is a slice of node branches. Each unique starting utf8 code point is in its own slice.

type Node

type Node[V any] struct {
	Prefix   []rune
	Value    V
	HasValue bool
	Branches[V]
}

Node represents a node in the tree.

type SyncTrie

type SyncTrie[V any] struct {
	// contains filtered or unexported fields
}

SyncTrie is the concurrency safe version of Trie.

func NewSyncTrie

func NewSyncTrie[V any]() *SyncTrie[V]

NewSyncTrie returns a new SyncTrie.

func (*SyncTrie[V]) Delete

func (self *SyncTrie[V]) Delete(key string) (value V, deleted bool)

Delete deletes an entry by key. It returns true if entry was found and deleted and false if not found.

After an entry has been deleted its parent nodes are traversed back towards root and deleted if they have no other child branches. This means that a single Delete operation may remove additional unused nodes. It can also happen that no nodes get deleted in case the node that contains the value has child branches of its own.

It does not merge nodes that have single branches which results in tree fragmentation after delete operations.

func (*SyncTrie[V]) Enum

func (self *SyncTrie[V]) Enum(f func(key string, value V) bool)

Enum enumerates all key-value pairs in the Trie.

It calls the provided function 'f' for each key-value pair in the Trie. The enumeration stops if 'f' returns false.

func (*SyncTrie[V]) EnumKeys

func (self *SyncTrie[V]) EnumKeys(f func(key string) bool)

EnumKeys enumerates all keys in the Trie.

It calls the provided function 'f' for each key in the Trie. The enumeration stops if 'f' returns false.

func (*SyncTrie[V]) EnumValues

func (self *SyncTrie[V]) EnumValues(f func(value V) bool)

EnumValues enumerates all values in the Trie.

It calls the provided function 'f' for each value in the Trie. The enumeration stops if 'f' returns false.

func (*SyncTrie[V]) Exists

func (self *SyncTrie[V]) Exists(key string) (exists bool)

Exists returns true if key exists.

func (*SyncTrie[V]) Get

func (self *SyncTrie[V]) Get(key string) (value V, found bool)

Get returns the value at key and true if it exists or a zero value of V and false if not found.

Key must not be empty. If it is Get returns a zero value and false.

func (*SyncTrie[V]) HasPrefixes

func (self *SyncTrie[V]) HasPrefixes(key string) (truth bool)

HasPrefixes returns true if key has any prefixes.

func (*SyncTrie[V]) HasSuffixes

func (self *SyncTrie[V]) HasSuffixes(key string) (truth bool)

HasSuffixes returns true if key has any prefixes.

func (*SyncTrie[V]) Prefixes

func (self *SyncTrie[V]) Prefixes(key string) (out []string)

Prefixes returns a list of set keys which are a prefix of key.

func (*SyncTrie[V]) Print

func (self *SyncTrie[V]) Print(w io.Writer)

Print writes self to writer w as a multiline string representing the tree structure.

It is formatted as one node per line where child nodes are indented with two spaces each level and line is in format: <indent><prefix>[,value]

func (*SyncTrie[V]) Put

func (self *SyncTrie[V]) Put(key string, value V) (old V, replaced bool)

Put inserts value under key.

If a value already exists at key it is returned with true, otherwise a zero value of V is returned and false.

Key must not be empty. If it is no value is inserted and a zero value of V and false is returned.

func (*SyncTrie[V]) Suffixes

func (self *SyncTrie[V]) Suffixes(key string) (out []string)

Suffixes returns a list of set keys which are suffixes of key argument.

type Trie

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

Trie implements a prefix tree of generic values keyed by a string key.

It has fast lookups and can retrieve keys which are a prefix or suffix of some key.

Implemented as a tree of Node where each node stores branches in a slice where each indice starts with a unique rune and is sorted alphabetically. A binary search is used on branch lookups, rest of key is scanned sequentially.

Puts require 2 allocations when allocating a new Node in the structure. Gets are fast, require no allocations.

func New

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

New returns a new Trie.

func (*Trie[V]) Delete

func (self *Trie[V]) Delete(key string) (value V, deleted bool)

Delete deletes an entry by key. It returns true if entry was found and deleted and false if not found.

After an entry has been deleted its parent nodes are traversed back towards root and deleted if they have no other child branches. This means that a single Delete operation may remove additional unused nodes. It can also happen that no nodes get deleted in case the node that contains the value has child branches of its own.

It merges nodes that have single branches along the parent path to avoid fragmentation.

func (*Trie[V]) Enum

func (self *Trie[V]) Enum(f func(key string, value V) bool)

Enum enumerates all key-value pairs in the Trie.

It calls the provided function 'f' for each key-value pair in the Trie. The enumeration stops if 'f' returns false.

func (*Trie[V]) EnumKeys

func (self *Trie[V]) EnumKeys(f func(key string) bool)

EnumKeys enumerates all keys in the Trie.

It calls the provided function 'f' for each key in the Trie. The enumeration stops if 'f' returns false.

func (*Trie[V]) EnumValues

func (self *Trie[V]) EnumValues(f func(value V) bool)

EnumValues enumerates all values in the Trie.

It calls the provided function 'f' for each value in the Trie. The enumeration stops if 'f' returns false.

func (*Trie[V]) Exists

func (self *Trie[V]) Exists(key string) (exists bool)

Exists returns true if key exists.

func (*Trie[V]) Get

func (self *Trie[V]) Get(key string) (value V, found bool)

Get returns the value at key and true if key exists or a zero value of V and false if not found.

Key must not be empty. If it is Get returns a zero value and false.

func (*Trie[V]) HasPrefixes

func (self *Trie[V]) HasPrefixes(key string) bool

HasPrefixes returns true if key has any prefixes.

func (*Trie[V]) HasSuffixes

func (self *Trie[V]) HasSuffixes(key string) bool

Suffixes returns a list of set keys which are suffixes of key argument.

func (*Trie[V]) Prefixes

func (self *Trie[V]) Prefixes(key string) (out []string)

Prefixes returns a list of set keys which are a prefix of key. For example, if trie has following keys:

• foo
• foobar
• foobarbaz

Prefixes then returns ["foo", "foobar"] for key "foobarbaz".

func (*Trie[V]) Print

func (self *Trie[V]) Print(w io.Writer)

Print writes self to writer w as a multiline string representing the tree structure.

It is formatted as one node per line where child nodes are indented with two spaces each level and line is in format: <indent><prefix>[,value]

func (*Trie[V]) Put

func (self *Trie[V]) Put(key string, value V) (old V, replaced bool)

Put inserts value keyed by key.

If an entry under key already exists its value is replaced with value argument and the old value is returned with replaced being true. Otherwise a zero value of V is returned and false.

Key must not be empty. If it is, no value is inserted and a zero value of V and false is returned.

func (*Trie[V]) Suffixes

func (self *Trie[V]) Suffixes(key string) (out []string)

Suffixes returns a list of set keys which are a suffix of key.

For example, if trie has following keys:

• foo
• foobar
• foobarbaz

suffixes then returns ["foobar", "foobarbaz"] for key "foo".