README
¶
Provides the radix package that implements a radix tree.
The package only provides a single Tree implementation, optimized for sparse nodes.
As a radix tree, it provides the following:
- O(k) operations. In many cases, this can be faster than a hash table since the hash function is an O(k) operation, and hash tables have very poor cache locality.
- Minimum / Maximum value lookups
- Ordered iteration
For an immutable variant, see go-immutable-radix.
Documentation
The full documentation is available on Godoc.
Example
Below is a simple example of usage
// Create a tree
r := radix.New[int]()
r.Insert("foo", 1)
r.Insert("bar", 2)
r.Insert("foobar", 2)
// Find the longest prefix match
m, _, _ := r.LongestPrefix("foozip")
if m != "foo" {
panic("should be foo")
}
Documentation
¶
Index ¶
- type Tree
- func (t *Tree[T]) Delete(s string) (T, bool)
- func (t *Tree[T]) DeletePrefix(s string) int
- func (t *Tree[T]) Get(s string) (T, bool)
- func (t *Tree[T]) Insert(s string, v T) (T, bool)
- func (t *Tree[T]) Len() int
- func (t *Tree[T]) LongestPrefix(s string) (string, T, bool)
- func (t *Tree[T]) Maximum() (string, T, bool)
- func (t *Tree[T]) Minimum() (string, T, bool)
- func (t *Tree[T]) ToMap() map[string]T
- func (t *Tree[T]) Walk(h WalkHandler[T]) error
- func (t *Tree[T]) WalkPath(path string, h WalkHandler[T]) error
- func (t *Tree[T]) WalkPrefix(prefix string, h WalkHandler[T]) error
- type WalkFlag
- type WalkFn
- type WalkHandler
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Tree ¶
type Tree[T any] struct { // contains filtered or unexported fields }
Tree implements a radix tree. This can be treated as a Dictionary abstract data type. The main advantage over a standard hash map is prefix-based lookups and ordered iteration,
func NewFromMap ¶
NewFromMap returns a new tree containing the keys from an existing map
func (*Tree[T]) Delete ¶
Delete is used to delete a key, returning the previous value and if it was deleted
func (*Tree[T]) DeletePrefix ¶
DeletePrefix is used to delete the subtree under a prefix Returns how many nodes were deleted Use this to delete large subtrees efficiently
func (*Tree[T]) Insert ¶
Insert is used to add a newentry or update an existing entry. Returns true if an existing record is updated.
func (*Tree[T]) LongestPrefix ¶
LongestPrefix is like Get, but instead of an exact match, it will return the longest prefix match.
func (*Tree[T]) WalkPath ¶
func (t *Tree[T]) WalkPath(path string, h WalkHandler[T]) error
WalkPath is used to walk the tree, but only visiting nodes from the root down to a given leaf. Where WalkPrefix walks all the entries *under* the given prefix, this walks the entries *above* the given prefix.
func (*Tree[T]) WalkPrefix ¶
func (t *Tree[T]) WalkPrefix(prefix string, h WalkHandler[T]) error
WalkPrefix is used to walk the tree under a prefix
type WalkFlag ¶
type WalkFlag uint32
WalkFlag is a bitmask return value for Walk functions.
func (WalkFlag) ShouldSet ¶ added in v1.1.1
ShouldSet returns true if the walk function wants to set a new value.
func (WalkFlag) ShouldSkip ¶ added in v1.1.2
ShouldSkip returns true if the walk should skip this node.
func (WalkFlag) ShouldStop ¶ added in v1.1.1
ShouldStop returns true if the walk should terminate.
Source Files