README
¶
forest-go
Tree structure implementations in golang
Ternary Search Tree
Features
- insertion
- deletion
- exact matching
- prefix matching
- applying a user-defined function to each entry
References
Documentation
¶
Index ¶
- func ApplyToTernarySearchTree[K constraints.Ordered, V any, R any](t *TernarySearchTree[K, V], prefix []K, callback func([]K, V) R) []R
- type TernarySearchTree
- func (t *TernarySearchTree[K, V]) Delete(key []K) (value V, found bool)
- func (t *TernarySearchTree[K, V]) Entries(prefix []K) []*TernarySearchTreeEntry[K, V]
- func (t *TernarySearchTree[K, V]) Insert(key []K, value V) error
- func (t *TernarySearchTree[K, V]) Keys(prefix []K) [][]K
- func (t *TernarySearchTree[K, V]) Search(key []K) (value V, found bool)
- func (t *TernarySearchTree[K, V]) Values(prefix []K) []V
- type TernarySearchTreeEntry
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func ApplyToTernarySearchTree ¶
func ApplyToTernarySearchTree[K constraints.Ordered, V any, R any](t *TernarySearchTree[K, V], prefix []K, callback func([]K, V) R) []R
ApplyToTernarySearchTree applies a user-defined function to each entry whose key has a specified prefix.
Types ¶
type TernarySearchTree ¶
type TernarySearchTree[K constraints.Ordered, V any] struct { // contains filtered or unexported fields }
Example ¶
keys := [][]rune{
[]rune("hello"),
[]rune("world"),
[]rune("heaven"),
[]rune("hell"),
[]rune("healthy"),
}
tst := NewTernarySearchTree[rune, int]()
for i, key := range keys {
err := tst.Insert(key, i+1)
if err != nil {
fmt.Println(err)
return
}
}
fmt.Println("All entries:")
for _, entry := range tst.Entries(nil) {
fmt.Println(string(entry.Key), entry.Value)
}
fmt.Println("Entries with prefix `hea`:")
for _, entry := range tst.Entries([]rune("hea")) {
fmt.Println(string(entry.Key), entry.Value)
}
fmt.Println("Entries with prefix `hell`:")
for _, entry := range tst.Entries([]rune("hell")) {
fmt.Println(string(entry.Key), entry.Value)
}
Output: All entries: healthy 5 heaven 3 hell 4 hello 1 world 2 Entries with prefix `hea`: healthy 5 heaven 3 Entries with prefix `hell`: hell 4 hello 1
func NewTernarySearchTree ¶
func NewTernarySearchTree[K constraints.Ordered, V any]() *TernarySearchTree[K, V]
NewTernarySearchTree returns a new ternary search tree that can contain entries mapping `[]K` to `V`.
func (*TernarySearchTree[K, V]) Delete ¶
func (t *TernarySearchTree[K, V]) Delete(key []K) (value V, found bool)
Delete deletes an entry and returns its value.
func (*TernarySearchTree[K, V]) Entries ¶
func (t *TernarySearchTree[K, V]) Entries(prefix []K) []*TernarySearchTreeEntry[K, V]
Entries returns entries. When a prefix isn't empty, this function returns entries whose key has the prefix.
func (*TernarySearchTree[K, V]) Insert ¶
func (t *TernarySearchTree[K, V]) Insert(key []K, value V) error
Insert inserts an entry. When the key already exists, this function return an error.
func (*TernarySearchTree[K, V]) Keys ¶
func (t *TernarySearchTree[K, V]) Keys(prefix []K) [][]K
Keys returns keys. When a prefix isn't empty, this function returns keys having the prefix.
func (*TernarySearchTree[K, V]) Search ¶
func (t *TernarySearchTree[K, V]) Search(key []K) (value V, found bool)
Search earches for an entry having a key that exactly matches a specified key and returns its value.
func (*TernarySearchTree[K, V]) Values ¶
func (t *TernarySearchTree[K, V]) Values(prefix []K) []V
Values returns values. When a prefix isn't empty, this function returns values whose key has the prefix.
type TernarySearchTreeEntry ¶
type TernarySearchTreeEntry[K constraints.Ordered, V any] struct { Key []K Value V }
Source Files