forest

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

• Ternary Search Trees

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 NewTernarySearchTree[K constraints.Ordered, V any]() *TernarySearchTree[K, V]
  • 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

• TernarySearchTree

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
}