README
¶
go-suffix-tree
This "suffix" package implements a suffix tree.
As a suffix tree, it allows to lookup a key in O(k) operations. In some cases(for example, some scenes in our production), this can be faster than a hash table because the hash function is an O(n) operation, with poor cache locality.
Plus suffix tree is more memory-effective than a hash table.
Example
A simple use case:
import (
suffix "github.com/spacewander/go-suffix-tree"
)
var (
TubeNameTree *suffix.Tree
TubeNames = []string{
// ...
}
)
func init() {
tree := suffix.NewTree()
for _, s := range TubeNames {
tree.Insert([]byte(s), &s)
}
TubeNameTree = tree
}
func getTubeName(name []byte) *string {
res, found := TubeNameTree.Get(name)
if found {
return res.(*string)
}
return nil
}
For more usage, see the godoc.
Documentation
¶
Index ¶
- type Tree
- func (tree *Tree) Get(key []byte) (value interface{}, found bool)
- func (tree *Tree) Insert(key []byte, value interface{}) (oldValue interface{}, ok bool)
- func (tree *Tree) Len() int
- func (tree *Tree) LongestSuffix(key []byte) (matchedKey []byte, value interface{}, found bool)
- func (tree *Tree) Remove(key []byte) (oldValue interface{}, found bool)
- func (tree *Tree) Walk(f func(key []byte, value interface{}) bool)
- func (tree *Tree) WalkSuffix(suffix []byte, f func(key []byte, value interface{}) bool)
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Tree ¶
type Tree struct {
// contains filtered or unexported fields
}
Tree represents a suffix tree.
func (*Tree) Get ¶
Get returns the value of given key and a boolean to indicate whether the value is found.
Example ¶
tree := NewTree()
tree.Insert([]byte("sth"), "sth")
value, found := tree.Get([]byte("sth"))
if found {
fmt.Println(value.(string))
}
Output: sth
func (*Tree) Insert ¶
Insert suffix tree with given key and value. Return the previous value and a boolean to indicate whether the insertion is successful.
Example ¶
tree := NewTree()
tree.Insert([]byte("sth"), "sth")
oldValue, ok := tree.Insert([]byte("sth"), "else")
// Always ok
if ok {
fmt.Println(oldValue.(string))
}
value, found := tree.Get([]byte("sth"))
if found {
fmt.Println(value.(string))
}
Output: sth else
func (*Tree) LongestSuffix ¶
LongestSuffix is mostly like Get. It returns the key which is the longest suffix of the given key, and the value referred by this key. Plus a boolean to indicate whether the key/value, is found.
Example ¶
tree := NewTree()
tree.Insert([]byte("table"), "table")
tree.Insert([]byte("able"), "able")
tree.Insert([]byte("present"), "present")
key, value, found := tree.LongestSuffix([]byte("presentable"))
if found {
fmt.Println("Matched key:", string(key))
fmt.Println(value.(string))
}
Output: Matched key: table table
func (*Tree) Remove ¶
Remove returns the value of given key and a boolean to indicate whethe the value is found. Then the value will be removed.
Example ¶
tree := NewTree()
tree.Insert([]byte("sth"), "sth")
oldValue, found := tree.Remove([]byte("sth"))
if found {
fmt.Println(oldValue.(string))
}
_, found = tree.Get([]byte("sth"))
if !found {
fmt.Println("Already removed")
}
Output: sth Already removed
func (*Tree) Walk ¶
Walk through the tree, call function with key and value. Once the function returns true, it will stop walking. The travelling order is DFS, in the same suffix level the shortest key comes first.
Example ¶
tree := NewTree()
tree.Insert([]byte("able"), 1)
tree.Insert([]byte("table"), 2)
tree.Insert([]byte("presentable"), 3)
tree.Walk(func(key []byte, _ interface{}) (stop bool) {
fmt.Println(string(key))
return false
})
fmt.Println("Walk and stop in the middle:")
tree.Walk(func(key []byte, _ interface{}) (stop bool) {
fmt.Println(string(key))
return string(key) == "able"
})
Output: able table presentable Walk and stop in the middle: able
func (*Tree) WalkSuffix ¶
WalkSuffix travels through nodes which have given suffix, calls function with key and value. Once the function returns true, it will stop walking. The travelling order is DFS, in the same suffix level the shortest key comes first.
Example ¶
tree := NewTree()
tree.Insert([]byte("able"), 1)
tree.Insert([]byte("table"), 2)
tree.Insert([]byte("presentable"), 3)
tree.Insert([]byte("present"), 4)
tree.WalkSuffix([]byte("table"), func(key []byte, _ interface{}) (stop bool) {
fmt.Println(string(key))
return false
})
fmt.Println("Walk and stop in the middle:")
tree.WalkSuffix([]byte("table"), func(key []byte, _ interface{}) (stop bool) {
fmt.Println(string(key))
return string(key) == "table"
})
Output: table presentable Walk and stop in the middle: table
Source Files