README
¶
Critbit
Critbit is a Go package which implements a critbit tree. A critbit tree is useful for quickly finding a string within a tree of strings. It naturally stores strings in sorted order, so they can be also trivially be retrieved from the tree in sorted order.
See the on-line Go doc for this package at:
https://godoc.org/github.com/gilramir/critbit
The implementation is novel in that it uses two arrays to maintain all nodes, instead of relying on pointers. Aspects of this implementation were influenced by:
https://github.com/mb0/critbit
and
https://github.com/glk/critbit
Example
package main
import (
"fmt"
"github.com/gilramir/critbit"
)
func main() {
tree := critbit.New(0)
ok, err = tree.Insert("gamma", 300)
ok, err = tree.Insert("beta", 200)
ok, err = tree.Insert("alpha", 100)
for kv := range tree.GetKeyValueTuples() {
fmt.Printf("%s = %d\n", kv.Key, kv.Value.(int))
}
}
Methods
- Delete - delete a key
- Dump - print the trie's representation to stdout, for debugging
- Get - get a key's value
- GetHasPrefix - find the first key that starts with a prefix, and return the KeyValueTuple
- GetKeyValueTuples - get all key/value tuples
- GetKeyValueTupleChan - get a channel to read all key/value tuples
- Insert - insert a new key/value, without updating an existing key
- IterateItems - returns an iterator over all key/value pairs, in order
- Keys - get all keys
- Length - get the number of keys
- Louds - get the LOUDS representation of the trie
- SaveDot - output the tree in graphviz/dot format
- Split - split a trie into 2 even tries
- SplitAt - split a trie into 2 tries of any size
- Update - update an existing key's value, without inserting a new key
- Upsert - insert a new key/value, but if it exists already, update the existing key's value
Documentation
¶
Overview ¶
Package critbit provides an implementation of a Critbit tree that stores nodes in arrays rather than allocating them individually and relying on pointers.
Index ¶
- Constants
- type Critbit
- func (tree *Critbit[T]) Delete(key string) bool
- func (tree *Critbit[T]) Dump()
- func (tree *Critbit[T]) Get(key string) (T, bool)
- func (tree *Critbit[T]) GetHasPrefix(key string) *KeyValueTuple[T]
- func (tree *Critbit[T]) GetKeyValueTupleChan() (chan *KeyValueTuple[T], context.CancelFunc)
- func (tree *Critbit[T]) GetKeyValueTuples() []*KeyValueTuple[T]
- func (tree *Critbit[T]) Insert(key string, value T) (bool, error)
- func (tree *Critbit[T]) IterateItems() iter.Seq2[string, T]
- func (tree *Critbit[T]) Keys() []string
- func (tree *Critbit[T]) Length() int
- func (tree *Critbit[T]) Louds() LOUDS
- func (tree *Critbit[T]) SaveDot(filename string) error
- func (tree *Critbit[T]) Split() (*Critbit[T], *Critbit[T])
- func (tree *Critbit[T]) SplitAt(leftNumKeys int) (*Critbit[T], *Critbit[T])
- func (tree *Critbit[T]) Update(key string, value T) bool
- func (tree *Critbit[T]) Upsert(key string, value T) error
- type KeyValueTuple
- type LOUDS
Constants ¶
const ( // A uint16 value is used to store the offset within a string, // so the maximum allowed string length is 65,536. MaxStringLength = 65536 )
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Critbit ¶
type Critbit[T any] struct { // contains filtered or unexported fields }
A Critbit represents one Critbit tree.
func New ¶
New allocates a new Critbit tree and returns a pointer to it. The capacityStrings argument allows smart allocation of the internal arrays, if you happen to know that a tree will contain a certain amount of strings. This is for efficiency only; capacityStrings does not impose any limit on the number of strings.
func (*Critbit[T]) Delete ¶
Delete removes the key from the tree. The boolean return value indicates if the key was in the tree.
func (*Critbit[T]) Dump ¶
func (tree *Critbit[T]) Dump()
Dump prints the structure of the entire tree to stdout.
func (*Critbit[T]) Get ¶
Get finds the key and returns its value. The boolean indicates if it was found or not.
func (*Critbit[T]) GetHasPrefix ¶
func (tree *Critbit[T]) GetHasPrefix(key string) *KeyValueTuple[T]
Returns the first key that starts with a string, and returns the KeyValueTuple, or nil
func (*Critbit[T]) GetKeyValueTupleChan ¶
func (tree *Critbit[T]) GetKeyValueTupleChan() (chan *KeyValueTuple[T], context.CancelFunc)
GetKeyValueTuplesCHan returns a channel that can be read from which contains each key-value pair, in sorted order by the keys. It also returns a cancel function which you need to call when you're done reading.
func (*Critbit[T]) GetKeyValueTuples ¶
func (tree *Critbit[T]) GetKeyValueTuples() []*KeyValueTuple[T]
Returns all the KeyValueTuples in key-sorted order.
func (*Critbit[T]) Insert ¶
Insert inserts a key/value pair into the tree. It returns a boolean indicating if the key was inserted. If the key already exists, in the tree, the value will not be changed, and false will be returned. An error value is also returned. An error will occur if the tree is full, or if the string is too long to be inserted. If an error is returned, the boolean value returned will be false.
func (*Critbit[T]) IterateItems ¶
Returns an iterator overy (key, value)
func (*Critbit[T]) Keys ¶
Keys returns a string slice containing all the keys in the tree. The keys are in sorted order.
func (*Critbit[T]) Length ¶
Length returns the number of keys currently stored in the tree. More space for keys may have been allocated, if keys were deleted and no other keys were inserted.
func (*Critbit[T]) Louds ¶
LoudsSlice returns a slice of bytes, all of which are either 1 or 0, which represent the tree structure in the LOUDS (level-order unary degree separation) representation, a succinct representation of the tree. Given N nodes (internal nodes + external refs), 2N+1 bytes will be returned in the slice. See https://memoria-framework.dev/docs/data-zoo/louds-tree/ for an introduction to LOUDS.
func (*Critbit[T]) SaveDot ¶
SaveDot save the tree structure to a graphviz/dot file with the given name. You can run 'dot' on the file to see the graphical representation of the tree.
func (*Critbit[T]) Split ¶
Split splits a tree into two trees, each having one half of the key-value pairs. If there is an odd number of keys, the right tree (the second returned tree) will have the extra key-value pair.
func (*Critbit[T]) SplitAt ¶
Split splits a tree into two arbitrarily sized trees. The leftNumKeys arguments indicates how many treees the left tree (the first returned tree) should have. The right tree (the second returned tree) will have the rest.
func (*Critbit[T]) Update ¶
Update changes the value for the given key. If the key is not stored in the tree, the returned bool value is false.
type KeyValueTuple ¶
A KeyValueTuple is returned during an iteration.
Source Files