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) 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.FindValue(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.