prefixtree

package

v1.2.0 Latest Latest Go to latest Published: Mar 17, 2025 License: MIT Imports: 3 Imported by: 0

Details

Package prefixtree provides a basic prefix tree implementation.

Add, Has, HasPrefix, Delete and DeletePrefix are linear in query length, regardless of the size of the tree. All operations are non-recursive.

This section is empty.

This section is empty.

This section is empty.

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

A Tree is a prefix tree.

A zero value tree is invalid; use New to create a new instance.

func New() *Tree

New returns an empty tree.

func (t *Tree) Add(x []byte)

Add inserts x to the tree. If a was already added, the tree is unchanged.

func (t *Tree) Delete(x []byte) bool

Delete removes x from the tree, if possible. Returns the result of Has(a) before deletion.

func (t *Tree) DeletePrefix(x []byte)

DeletePrefix removes prefix x from the tree. All sequences that have x as their prefix are removed. Other sequences are unchanged.

func (t *Tree) FindPrefixes(x []byte) [][]byte

FindPrefixes returns all the elements in the tree that are prefixes of x, ordered by length.

func (t *Tree) Has(x []byte) bool

Has returns whether x was added to the tree.

func (t *Tree) HasPrefix(x []byte) bool

HasPrefix returns whether x is a prefix of an element in the tree.

func (t *Tree) Iter() iter.Seq[[]byte]

Iter iterates over the elements of t, in no particular order. The tree should not be modified during iteration.

func (t *Tree) IterPrefix(x []byte) iter.Seq[[]byte]

IterPrefix iterates the elements in the tree that have x as their prefix. Calling IterPrefix with a zero-length slice is equivalent to Iter().