README
¶
cedar-go 
Package cedar-go implementes double-array trie.
It is a Golang port of cedar which is written in C++ by Naoki Yoshinaga. cedar-go currently implements the reduced verion of cedar.
This package is not thread safe if there is one goroutine doing insertions or deletions.
Install
go get github.com/adamzy/cedar-go
Usage
package main
import (
"fmt"
"github.com/adamzy/cedar-go"
)
func main() {
// create a new cedar trie.
trie := cedar.New()
// a helper function to print the id-key-value triple given trie node id
printIdKeyValue := func(id int) {
// the key of node `id`.
key, _ := trie.Key(id)
// the value of node `id`.
value, _ := trie.Value(id)
fmt.Printf("%d\t%s:%v\n", id, key, value)
}
// Insert key-value pairs.
// The order of insertion is not important.
trie.Insert([]byte("How many"), 0)
trie.Insert([]byte("How many loved"), 1)
trie.Insert([]byte("How many loved your moments"), 2)
trie.Insert([]byte("How many loved your moments of glad grace"), 3)
trie.Insert([]byte("姑苏"), 4)
trie.Insert([]byte("姑苏城外"), 5)
trie.Insert([]byte("姑苏城外寒山寺"), 6)
// Get the associated value of a key directly.
value, _ := trie.Get([]byte("How many loved your moments of glad grace"))
fmt.Println(value)
// Or, jump to the node first,
id, _ := trie.Jump([]byte("How many loved your moments"), 0)
// then get the key and the value
printIdKeyValue(id)
fmt.Println("\nPrefixMatch\nid\tkey:value")
for _, id := range trie.PrefixMatch([]byte("How many loved your moments of glad grace"), 0) {
printIdKeyValue(id)
}
fmt.Println("\nPrefixPredict\nid\tkey:value")
for _, id := range trie.PrefixPredict([]byte("姑苏"), 0) {
printIdKeyValue(id)
}
}
will produce
3
281 How many loved your moments:2
PrefixMatch
id key:value
262 How many:0
268 How many loved:1
281 How many loved your moments:2
296 How many loved your moments of glad grace:3
PrefixPredict
id key:value
303 姑苏:4
309 姑苏城外:5
318 姑苏城外寒山寺:6
Documentation
¶
Overview ¶
Package cedar-go implements double-array trie.
It is a golang port of cedar (http://www.tkl.iis.u-tokyo.ac.jp/~ynaga/cedar) which is written in C++ by Naoki Yoshinaga. Currently cedar-go implements the `reduced` verion of cedar. This package is not thread safe if there is one goroutine doing insertions or deletions.
Note ¶
key must be `[]byte` without zero items, while value must be integer in the range [0, 2<<63-2] or [0, 2<<31-2] depends on the platform.
Example ¶
trie = cedar.New()
// Insert key-value pairs.
// The order of insertion is not important.
trie.Insert([]byte("How many"), 0)
trie.Insert([]byte("How many loved"), 1)
trie.Insert([]byte("How many loved your moments"), 2)
trie.Insert([]byte("How many loved your moments of glad grace"), 3)
trie.Insert([]byte("姑苏"), 4)
trie.Insert([]byte("姑苏城外"), 5)
trie.Insert([]byte("姑苏城外寒山寺"), 6)
// Get the associated value of a key directly.
value, _ := trie.Get([]byte("How many loved your moments of glad grace"))
fmt.Println(value)
// Or, use `jump` to get the id of the trie node fist,
id, _ := trie.Jump([]byte("How many loved your moments"), 0)
// then get the key and the value.
key, _ := trie.Key(id)
value, _ = trie.Value(id)
fmt.Printf("%d\t%s:%v\n", id, key, value)
Output: 3 281 How many loved your moments:2
Example (PrefixMatch) ¶
fmt.Println("id\tkey:value")
for _, id := range trie.PrefixMatch([]byte("How many loved your moments of glad grace"), 0) {
key, _ := trie.Key(id)
value, _ := trie.Value(id)
fmt.Printf("%d\t%s:%v\n", id, key, value)
}
Output: id key:value 262 How many:0 268 How many loved:1 281 How many loved your moments:2 296 How many loved your moments of glad grace:3
Example (PrefixPredict) ¶
fmt.Println("id\tkey:value")
for _, id := range trie.PrefixPredict([]byte("姑苏"), 0) {
key, _ := trie.Key(id)
value, _ := trie.Value(id)
fmt.Printf("%d\t%s:%v\n", id, key, value)
}
Output: id key:value 303 姑苏:4 309 姑苏城外:5 318 姑苏城外寒山寺:6
Example (SaveAndLoad) ¶
trie.SaveToFile("cedar.gob", "gob")
trie.SaveToFile("cedar.json", "json")
trie.LoadFromFile("cedar.gob", "gob")
trie.LoadFromFile("cedar.json", "json")
Output:
Index ¶
- Constants
- Variables
- type Cedar
- func (da *Cedar) Delete(key []byte) error
- func (da *Cedar) Get(key []byte) (value int, err error)
- func (da *Cedar) Insert(key []byte, value int) error
- func (da *Cedar) Jump(path []byte, from int) (to int, err error)
- func (da *Cedar) Key(id int) (key []byte, err error)
- func (da *Cedar) Load(in io.Reader, dataType string) error
- func (da *Cedar) LoadFromFile(fileName string, dataType string) error
- func (da *Cedar) PrefixMatch(key []byte, num int) (ids []int)
- func (da *Cedar) PrefixPredict(key []byte, num int) (ids []int)
- func (da *Cedar) Save(out io.Writer, dataType string) error
- func (da *Cedar) SaveToFile(fileName string, dataType string) error
- func (da *Cedar) Status() (keys, nodes, size, capacity int)
- func (da *Cedar) Update(key []byte, value int) error
- func (da *Cedar) Value(id int) (value int, err error)
Examples ¶
Constants ¶
const ValueLimit = int(^uint(0) >> 1)
Variables ¶
Functions ¶
This section is empty.
Types ¶
type Cedar ¶
type Cedar struct {
// contains filtered or unexported fields
}
func (*Cedar) Delete ¶
Delete removes a key-value pair from the cedar. It will return ErrNoPath, if the key has not been added.
func (*Cedar) Get ¶
Get returns the value associated with the given `key`. It is equivalent to
id, err1 = Jump(key) value, err2 = Value(id)
Thus, it may return ErrNoPath or ErrNoValue,
func (*Cedar) Insert ¶
Insert adds a key-value pair into the cedar. It will return ErrInvalidValue, if value < 0 or >= ValueLimit.
func (*Cedar) Jump ¶
Jump travels from a node `from` to another node `to` by following the path `path`. For example, if the following keys were inserted:
id key 19 abc 23 ab 37 abcd
then
Jump([]byte("ab"), 0) = 23, nil // reach "ab" from root
Jump([]byte("c"), 23) = 19, nil // reach "abc" from "ab"
Jump([]byte("cd"), 23) = 37, nil // reach "abcd" from "ab"
func (*Cedar) Key ¶
Key returns the key of the node with the given `id`. It will return ErrNoPath, if the node does not exist.
func (*Cedar) Load ¶
Load loads the cedar from an io.Writer, where dataType is either "json" or "gob".
func (*Cedar) LoadFromFile ¶
LoadFromFile loads the cedar from a file, where dataType is either "json" or "gob".
func (*Cedar) PrefixMatch ¶
PrefixMatch returns a list of at most `num` nodes which match the prefix of the key. If `num` is 0, it returns all matches. For example, if the following keys were inserted:
id key 19 abc 23 ab 37 abcd
then
PrefixMatch([]byte("abc"), 1) = [ 23 ] // match ["ab"]
PrefixMatch([]byte("abcd"), 0) = [ 23, 19, 37] // match ["ab", "abc", "abcd"]
func (*Cedar) PrefixPredict ¶
PrefixPredict returns a list of at most `num` nodes which has the key as their prefix. These nodes are ordered by their keys. If `num` is 0, it returns all matches. For example, if the following keys were inserted:
id key 19 abc 23 ab 37 abcd
then
PrefixPredict([]byte("ab"), 2) = [ 23, 19 ] // predict ["ab", "abc"]
PrefixPredict([]byte("ab"), 0) = [ 23, 19, 37 ] // predict ["ab", "abc", "abcd"]
func (*Cedar) Save ¶
Save saves the cedar to an io.Writer, where dataType is either "json" or "gob".
func (*Cedar) SaveToFile ¶
SaveToFile saves the cedar to a file, where dataType is either "json" or "gob".
func (*Cedar) Status ¶
Status reports the following statistics of the cedar:
keys: number of keys that are in the cedar, nodes: number of trie nodes (slots in the base array) has been taken, size: the size of the base array used by the cedar, capacity: the capicity of the base array used by the cedar.
Source Files