Documentation ¶
Overview ¶
Package critbit implements Crit-Bit tree for byte sequences.
Crit-Bit tree [1] is fast, memory efficient and a variant of PATRICIA trie. This implementation can be used for byte sequences if it includes a null byte or not. This is based on [2] and extends it to support a null byte in a byte sequence.
[1]: http://cr.yp.to/critbit.html (definition) [2]: https://github.com/agl/critbit (C implementation and document)
Index ¶
- type Tree
- func (t *Tree) Clear() bool
- func (t *Tree) Delete(k []byte) (interface{}, bool)
- func (t *Tree) Get(k []byte) (interface{}, bool)
- func (t *Tree) Insert(k []byte, v interface{}) (interface{}, bool)
- func (t *Tree) Len() int
- func (t *Tree) LongestPrefix(prefix []byte) ([]byte, interface{}, bool)
- func (t *Tree) Maximum() ([]byte, interface{}, bool)
- func (t *Tree) Minimum() ([]byte, interface{}, bool)
- func (t *Tree) Walk(fn WalkFn)
- func (t *Tree) WalkPath(path []byte, fn WalkFn)
- func (t *Tree) WalkPrefix(prefix []byte, fn WalkFn)
- type WalkFn
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 critbit tree.
func (*Tree) Clear ¶
Clear removes all elements in the tree. If it removes something, it returns true while the tree is empty and there is nothing to remove, it returns false.
func (*Tree) Delete ¶
Delete removes a given key and its value from the tree. If it succeeded, it returns the key's previous value and true while if not, it returns nil and false. On an empty tree, it always fails.
func (*Tree) Get ¶
Get searches a given key from the tree. If the key exists in the tree, it returns its value and true. If not, it returns nil and false.
func (*Tree) Insert ¶
Insert adds or updates a given key to the tree and returns its previous value and if anything was set or not. If there is the key in the tree, it adds the key and the value to the tree and returns nil and true when it succeeded while if not, it updates the key's value and returns its previous value and true when it succeeded.
func (*Tree) LongestPrefix ¶
LongestPrefix searches the longest key which is included in a given key and returns the found key and its value. For example, if there are "f", "fo", "foobar" in the tree and "foo" is given, it returns "fo". If it found such a key, it returns true as the bool value while if not, it returns false as it.
func (*Tree) Maximum ¶
Maximum searches a key from the tree in lexicographic order and returns the last one and its value. If it found such a key, it also returns true as the bool value while if not, it returns false as it.
func (*Tree) Minimum ¶
Minimum searches a key from the tree in lexicographic order and returns the first one and its value. If it found such a key, it also returns true as the bool value while if not, it returns false as it.
func (*Tree) Walk ¶
Walk walks whole the tree and call a given function with each element's key and value. If the function returns true, the walk is terminated at there.
func (*Tree) WalkPath ¶
WalkPath walks the tree from the root up to a given key and call a given function with each element's key and value. For example, the tree has "f", "fo", "foob", "foobar" and "foo" is given, it visits "f" and "fo" elements. If the function returns true, the walk is terminated at there.
func (*Tree) WalkPrefix ¶
WalkPrefix walks the tree under a given prefix and call a given function with each element's key and value. For example, the tree has "f", "fo", "foob", "foobar" and "foo" is given, it visits "foob" and "foobar" elements. If the function returns true, the walk is terminated at there.