package radix

import "github.com/gohugoio/go-radix"

Index ¶

• type Tree
• func New[T any]() *Tree[T]
• func NewFromMap[T any](m map[string]T) *Tree[T]
• 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
• func (w WalkFlag) ShouldSet() bool
• func (w WalkFlag) ShouldSkip() bool
• func (w WalkFlag) ShouldStop() bool
• type WalkFn
• func (wf WalkFn[T]) Check(s string) (WalkFlag, error)
• func (wf WalkFn[T]) Handle(s string, v T) (WalkFlag, T, error)
• type WalkHandler

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 New ¶

func New[T any]() *Tree[T]

New returns an empty Tree

func NewFromMap ¶

func NewFromMap[T any](m map[string]T) *Tree[T]

NewFromMap returns a new tree containing the keys from an existing map

func (*Tree[T]) Delete ¶

func (t *Tree[T]) Delete(s string) (T, bool)

Delete is used to delete a key, returning the previous value and if it was deleted

func (*Tree[T]) DeletePrefix ¶

func (t *Tree[T]) DeletePrefix(s string) int

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]) Get ¶

func (t *Tree[T]) Get(s string) (T, bool)

Get is used to lookup a specific key, returning the value and if it was found

func (*Tree[T]) Insert ¶

func (t *Tree[T]) Insert(s string, v T) (T, bool)

Insert is used to add a newentry or update an existing entry. Returns true if an existing record is updated.

func (*Tree[T]) Len ¶

func (t *Tree[T]) Len() int

Len is used to return the number of elements in the tree

func (*Tree[T]) LongestPrefix ¶

func (t *Tree[T]) LongestPrefix(s string) (string, T, bool)

LongestPrefix is like Get, but instead of an exact match, it will return the longest prefix match.

func (*Tree[T]) Maximum ¶

func (t *Tree[T]) Maximum() (string, T, bool)

Maximum is used to return the maximum value in the tree

func (*Tree[T]) Minimum ¶

func (t *Tree[T]) Minimum() (string, T, bool)

Minimum is used to return the minimum value in the tree

func (*Tree[T]) ToMap ¶

func (t *Tree[T]) ToMap() map[string]T

ToMap is used to walk the tree and convert it into a map

func (*Tree[T]) Walk ¶

func (t *Tree[T]) Walk(h WalkHandler[T]) error

Walk is used to walk the tree

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.

const (
	WalkContinue WalkFlag = 0
	WalkSkip     WalkFlag = 1 << 0
	WalkStop     WalkFlag = 1 << 1
	WalkSet      WalkFlag = 1 << 2
)

func (WalkFlag) ShouldSet ¶

func (w WalkFlag) ShouldSet() bool

ShouldSet returns true if the walk function wants to set a new value.

func (WalkFlag) ShouldSkip ¶

func (w WalkFlag) ShouldSkip() bool

ShouldSkip returns true if the walk should skip this node.

func (WalkFlag) ShouldStop ¶

func (w WalkFlag) ShouldStop() bool

ShouldStop returns true if the walk should terminate.

type WalkFn ¶

type WalkFn[T any] func(s string, v T) (WalkFlag, T, error)

WalkFn is used when walking the tree. Takes a key and value, returning a WalkFlag to indicate how to proceed and possibly a new value to set.

func (WalkFn[T]) Check ¶

func (wf WalkFn[T]) Check(s string) (WalkFlag, error)

func (WalkFn[T]) Handle ¶

func (wf WalkFn[T]) Handle(s string, v T) (WalkFlag, T, error)

type WalkHandler ¶

type WalkHandler[T any] interface {
	Check(s string) (WalkFlag, error)
	Handle(s string, v T) (WalkFlag, T, error)
}

WalkHandler is the handler passed to Walk functions. When split into two steps, this allows us to walk the keys withut reading the values.

Source Files ¶

radix.go