README
¶
prefixtree
The prefixtree package implements a simple prefix trie data structure. The tree enables rapid searching for strings that uniquely match a given prefix. The implementation allows the user to associate data with each string, so it can act as a sort of flexible key-value store where searches succeed with the shortest unambiguous key prefix.
Example: Building a prefix tree
The following code adds strings and associated data (in this case an integer) to a prefix tree.
tree := prefixtree.New()
tree.Add("apple", 10)
tree.Add("orange", 20)
tree.Add("apple pie", 30)
tree.Add("lemon", 40)
tree.Add("lemon meringue pie", 50)
Example: Searching the prefix tree
The following code searches the prefix tree generated by the previous example and outputs the results.
fmt.Printf("%-18s %-8s %s\n", "prefix", "value", "error")
fmt.Printf("%-18s %-8s %s\n", "------", "-----", "-----")
for _, prefix := range []string{
"a",
"appl",
"apple",
"apple p",
"apple pie",
"apple pies",
"o",
"oran",
"orange",
"oranges",
"l",
"lemo",
"lemon",
"lemon m",
"lemon meringue",
"pear",
} {
value, err := tree.Find(prefix)
fmt.Printf("%-18s %-8v %v\n", prefix, value, err)
}
Output:
prefix value error
------ ----- -----
a <nil> prefixtree: prefix ambiguous
appl <nil> prefixtree: prefix ambiguous
apple 10 <nil>
apple p 30 <nil>
apple pie 30 <nil>
apple pies <nil> prefixtree: prefix not found
o 20 <nil>
orang 20 <nil>
orange 20 <nil>
oranges <nil> prefixtree: prefix not found
l <nil> prefixtree: prefix ambiguous
lemo <nil> prefixtree: prefix ambiguous
lemon 40 <nil>
lemon m 50 <nil>
lemon meringue 50 <nil>
pear <nil> prefixtree: prefix not found
Documentation
¶
Overview ¶
Package prefixtree implements a prefix tree (technically, a trie). A prefix tree enables rapid searching for key strings that uniquely match a given prefix. This implementation allows the user to associate value data with each key string, so it can act as a sort of flexible key-value store.
Index ¶
- Variables
- type KeyValue
- type Tree
- func (t *Tree) Add(key string, value any)
- func (t *Tree) Find(prefix string) (value any, err error)deprecated
- func (t *Tree) FindAll(prefix string) (values []any)deprecated
- func (t *Tree) FindKey(prefix string) (key string, err error)
- func (t *Tree) FindKeyValue(prefix string) (kv KeyValue, err error)
- func (t *Tree) FindKeyValues(prefix string) (values []KeyValue)
- func (t *Tree) FindKeys(prefix string) (keys []string)
- func (t *Tree) FindValue(prefix string) (value any, err error)
- func (t *Tree) FindValues(prefix string) (values []any)
- func (t *Tree) Output()
Examples ¶
Constants ¶
This section is empty.
Variables ¶
var ( // ErrPrefixNotFound is returned by Find if the prefix being searched for // matches zero strings in the prefix tree. ErrPrefixNotFound = errors.New("prefixtree: prefix not found") // ErrPrefixAmbiguous is returned by Find if the prefix being // searched for matches more than one string in the prefix tree. ErrPrefixAmbiguous = errors.New("prefixtree: prefix ambiguous") )
Functions ¶
This section is empty.
Types ¶
type Tree ¶
type Tree struct {
// contains filtered or unexported fields
}
A Tree represents a prefix tree containing strings and their associated value data. The tree is implemented as a trie and can be searched efficiently for unique prefix matches.
Example (Usage) ¶
Build a prefix tree and search it for various prefix matches.
package main
import (
"fmt"
"github.com/beevik/prefixtree"
)
func main() {
// Create the tree. Add 5 strings, each with an associated
// integer.
tree := prefixtree.New()
for i, s := range []string{
"apple",
"orange",
"apple pie",
"lemon meringue",
"lemon",
} {
tree.Add(s, i)
}
// Attempt to find various prefixes in the tree, and output
// the result.
fmt.Printf("%-18s %-8s %s\n", "prefix", "value", "error")
fmt.Printf("%-18s %-8s %s\n", "------", "-----", "-----")
for _, s := range []string{
"a",
"appl",
"apple",
"apple p",
"apple pie",
"apple pies",
"o",
"orang",
"orange",
"oranges",
"lemo",
"lemon",
"lemon m",
"lemon meringue",
"lemon meringues",
} {
value, err := tree.Find(s)
fmt.Printf("%-18s %-8v %v\n", s, value, err)
}
}
Output: prefix value error ------ ----- ----- a <nil> prefixtree: prefix ambiguous appl <nil> prefixtree: prefix ambiguous apple 0 <nil> apple p 2 <nil> apple pie 2 <nil> apple pies <nil> prefixtree: prefix not found o 1 <nil> orang 1 <nil> orange 1 <nil> oranges <nil> prefixtree: prefix not found lemo <nil> prefixtree: prefix ambiguous lemon 4 <nil> lemon m 3 <nil> lemon meringue 3 <nil> lemon meringues <nil> prefixtree: prefix not found
func (*Tree) FindKey ¶ added in v0.3.0
FindKey searches the prefix tree for a key string that uniquely matches the prefix. If found, the full matching key is returned. If not found, ErrPrefixNotFound is returned. If the prefix matches more than one key in the tree, ErrPrefixAmbiguous is returned.
func (*Tree) FindKeyValue ¶ added in v0.3.0
FindKeyValue searches the prefix tree for a key string that uniquely matches the prefix. If found, the full matching key and its associated value is returned. If not found, ErrPrefixNotFound is returned. If the prefix matches more than one key in the tree, ErrPrefixAmbiguous is returned.
func (*Tree) FindKeyValues ¶ added in v0.3.0
FindKeyValues searches the prefix tree for all key strings prefixed by the provided prefix. All discovered keys and their values are returned.
func (*Tree) FindKeys ¶ added in v0.3.0
FindKeys searches the prefix tree for all key strings prefixed by the provided prefix and returns them.
func (*Tree) FindValue ¶ added in v0.3.0
FindValue searches the prefix tree for a key string that uniquely matches the prefix. If found, the value associated with the key is returned. If not found, ErrPrefixNotFound is returned. If the prefix matches more than one key in the tree, ErrPrefixAmbiguous is returned.
func (*Tree) FindValues ¶ added in v0.3.0
FindValues searches the prefix tree for all key strings prefixed by the provided prefix. All associated values are returned.
Source Files