radix

Documentation

Overview

Package radix implements a generic radix tree. This is based primarily on this original implementation in this project:

https://github.com/armon/go-radix

The original was not generic, but this one is. I also cut out some extraneous operations I didn't feel I needed.

Index

• type Tree
  • func New[T any]() Tree[T]
  • func (tree *Tree[T]) Delete(s string) (T, bool)
  • func (tree *Tree[T]) DeletePrefix(s string) int
  • func (tree *Tree[T]) Get(s string) (T, bool)
  • func (tree *Tree[T]) Insert(s string, v T) (T, bool)
  • func (tree *Tree[T]) Len() int
  • func (tree *Tree[T]) LongestPrefix(s string) (string, T, bool)
  • func (tree *Tree[T]) Maximum() (string, T, bool)
  • func (tree *Tree[T]) Minimum() (string, T, bool)
  • func (tree *Tree[T]) Walk(fn WalkFunc[T])
  • func (tree *Tree[T]) WalkPath(path string, fn WalkFunc[T])
  • func (tree *Tree[T]) WalkPrefix(prefix string, fn WalkFunc[T])
• type WalkFunc

Types

type Tree

type Tree[T any] struct {
	// contains filtered or unexported fields
}

Tree implements a radix tree. It's a map-like structure that lets you efficiently find exact instances of keys as well as anything matching prefixes.

func New

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

New returns an empty radix Tree.

func (*Tree[T]) Delete

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

Delete is used to remove a node from the tree, returning the previous value and if it was deleted.

func (*Tree[T]) DeletePrefix

func (tree *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 (tree *Tree[T]) Get(s string) (T, bool)

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

func (*Tree[T]) Insert

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

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

func (*Tree[T]) Len

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

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

func (*Tree[T]) LongestPrefix

func (tree *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 (tree *Tree[T]) Maximum() (string, T, bool)

Maximum is used to return the maximum value in the tree.

func (*Tree[T]) Minimum

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

Minimum is used to return the minimum value in the tree.

func (*Tree[T]) Walk

func (tree *Tree[T]) Walk(fn WalkFunc[T])

Walk visits every not in the tree, invoking your callback function for each one.

func (*Tree[T]) WalkPath

func (tree *Tree[T]) WalkPath(path string, fn WalkFunc[T])

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 (tree *Tree[T]) WalkPrefix(prefix string, fn WalkFunc[T])

WalkPrefix is used to visit just the nodes whose key starts with the given prefix.

type WalkFunc

type WalkFunc[T any] func(s string, v T) bool

WalkFunc is used when walking the tree. Takes a key and value, returning if iteration should be terminated.