radix

README

Radix

This package provides a generic implementation of a radix tree.

Installing

go get gitlab.com/romalor/radix@v1

Documentation

Overview

package radix represents an implementation of a PATRICA tree.

Index

• func All[K cmp.Ordered, V any](t *Tree[K, V]) iter.Seq2[[]K, V]
• func Keys[K cmp.Ordered, V any](t *Tree[K, V]) iter.Seq[[]K]
• func Values[K cmp.Ordered, V any](t *Tree[K, V]) iter.Seq[V]
• func Zero[T any]() T
• type Tree
  • func Collect[K cmp.Ordered, V any](seq iter.Seq2[[]K, V]) *Tree[K, V]
  • func New[K cmp.Ordered, V any]() *Tree[K, V]
  • func (t *Tree[K, V]) Delete(key []K)
  • func (t *Tree[K, V]) Get(key []K) (V, bool)
  • func (t *Tree[K, V]) Insert(key []K, value V)
  • func (t *Tree[K, V]) Len() int
  • func (t *Tree[K, V]) Max() []K
  • func (t *Tree[K, V]) Print()
  • func (t *Tree[K, V]) Search(key []K) (V, bool)

Functions

func All

func All[K cmp.Ordered, V any](t *Tree[K, V]) iter.Seq2[[]K, V]

All returns an iterator over the key-value pairs in t. Iteration order is always guaranteed to be in the ascending order of the keys in t.

func Keys

func Keys[K cmp.Ordered, V any](t *Tree[K, V]) iter.Seq[[]K]

Keys returns an iterator over the keys stored in t. Iteration order is always guaranteed to be in ascending order.

func Values

func Values[K cmp.Ordered, V any](t *Tree[K, V]) iter.Seq[V]

Values returns an iterator over the values stored in t. Iteration order is always guaranteed to based on the ascending order of the keys in t.

func Zero

func Zero[T any]() T

Zero returns the zero value for T.

Types

type Tree

type Tree[K cmp.Ordered, V any] struct {
	// contains filtered or unexported fields
}

Tree represents a radix tree.

func Collect

func Collect[K cmp.Ordered, V any](seq iter.Seq2[[]K, V]) *Tree[K, V]

Collect collects key-value pairs from seq to populate a new tree and returns it.

func New

func New[K cmp.Ordered, V any]() *Tree[K, V]

New creates a new radix tree.

func (*Tree[K, V]) Delete

func (t *Tree[K, V]) Delete(key []K)

Delete removes a node from the tree. Not concurrency safe.

func (*Tree[K, V]) Get

func (t *Tree[K, V]) Get(key []K) (V, bool)

Get retrieves a value by its key.

func (*Tree[K, V]) Insert

func (t *Tree[K, V]) Insert(key []K, value V)

Insert adds a key-value pair to the tree. Not concurrency safe.

func (*Tree[K, V]) Len

func (t *Tree[K, V]) Len() int

Len returns the number of keys stored in the tree.

func (*Tree[K, V]) Max

func (t *Tree[K, V]) Max() []K

Max returns the longest key stored in the tree.

The precedence of Max is in descending order. If two keys are of equal length, max will return the last one found.

Example:

"apple"
"bands" <- Returned from max.

If the tree is empty, Max returns an empty slice.

func (*Tree[K, V]) Print

func (t *Tree[K, V]) Print()

Print recursively prints the contents of the tree.

func (*Tree[K, V]) Search

func (t *Tree[K, V]) Search(key []K) (V, bool)

Search returns the longest prefix match for a key.