cedar

README

cedar

Package cedar implementes double-array trie, base on cedar-go.

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/go-ego/cedar

Usage

package main

import (
	"fmt"

	"github.com/go-ego/cedar"
)

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

License

Under the GPL-3.0 License.

Documentation

Overview

Package cedar 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

package main

import (
	"fmt"

	"github.com/go-ego/cedar"
)

var trie *cedar.Cedar

func main() {
	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)

package main

import (
	"fmt"

	"github.com/go-ego/cedar"
)

var trie *cedar.Cedar

func main() {
	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)

package main

import (
	"fmt"

	"github.com/go-ego/cedar"
)

var trie *cedar.Cedar

func main() {
	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)

package main

import (
	"github.com/go-ego/cedar"
)

var trie *cedar.Cedar

func main() {
	trie.SaveToFile("cedar.gob", "gob")
	trie.SaveToFile("cedar.json", "json")

	trie.LoadFromFile("cedar.gob", "gob")
	trie.LoadFromFile("cedar.json", "json")
}

Index

• Constants
• Variables
• type Cedar
  • func New() *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, 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, 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

• Package
• Package (PrefixMatch)
• Package (PrefixPredict)
• Package (SaveAndLoad)

Constants

const (
	// ValueLimit limit value
	ValueLimit = int(^uint(0) >> 1)
)

Variables

var (
	// ErrInvalidDataType invalid data type error
	ErrInvalidDataType = errors.New("cedar: invalid datatype")
	// ErrInvalidValue invalid value error
	ErrInvalidValue = errors.New("cedar: invalid value")
	// ErrInvalidKey invalid key error
	ErrInvalidKey = errors.New("cedar: invalid key")

	// ErrNoPath no path error
	ErrNoPath = errors.New("cedar: no path")
	// ErrNoValue no value error
	ErrNoValue = errors.New("cedar: no value")
)

Types

type Cedar

type Cedar struct {
	Array  []node
	Ninfos []ninfo
	Blocks []block
	Reject [257]int

	BheadF, BheadC, BheadO int

	Capacity int
	Size     int
	Ordered  bool
	MaxTrial int
}

Cedar cedar struct

func New

func New() *Cedar

New new Cedar

func (*Cedar) Delete

func (da *Cedar) Delete(key []byte) error

Delete removes a key-value pair from the cedar. It will return ErrNoPath, if the key has not been added.

func (*Cedar) Get

func (da *Cedar) Get(key []byte) (value int, err error)

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

func (da *Cedar) Insert(key []byte, value int) error

Insert adds a key-value pair into the cedar. It will return ErrInvalidValue, if value < 0 or >= ValueLimit.

func (*Cedar) Jump

func (da *Cedar) Jump(path []byte, from int) (to int, err error)

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

func (da *Cedar) Key(id int) (key []byte, err error)

Key returns the key of the node with the given `id`. It will return ErrNoPath, if the node does not exist.

func (*Cedar) Load

func (da *Cedar) Load(in io.Reader, dataType string) error

Load loads the cedar from an io.Writer, where dataType is either "json" or "gob".

func (*Cedar) LoadFromFile

func (da *Cedar) LoadFromFile(fileName, dataType string) error

LoadFromFile loads the cedar from a file, where dataType is either "json" or "gob".

func (*Cedar) PrefixMatch

func (da *Cedar) PrefixMatch(key []byte, num int) (ids []int)

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

func (da *Cedar) PrefixPredict(key []byte, num int) (ids []int)

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

func (da *Cedar) Save(out io.Writer, dataType string) error

Save saves the cedar to an io.Writer, where dataType is either "json" or "gob".

func (*Cedar) SaveToFile

func (da *Cedar) SaveToFile(fileName, dataType string) error

SaveToFile saves the cedar to a file, where dataType is either "json" or "gob".

func (*Cedar) Status

func (da *Cedar) Status() (keys, nodes, size, capacity int)

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.

func (*Cedar) Update

func (da *Cedar) Update(key []byte, value int) error

Update increases the value associated with the `key`. The `key` will be inserted if it is not in the cedar. It will return ErrInvalidValue, if the updated value < 0 or >= ValueLimit.

func (*Cedar) Value

func (da *Cedar) Value(id int) (value int, err error)

Value returns the value of the node with the given `id`. It will return ErrNoValue, if the node does not have a value.