radix

README

radix (radix tree)

Example
. (14 nodes)
└── 7↑ r → <nil>
    ├── 4↑ ub → <nil>
    │   ├── 2↑ ic → <nil>
    │   │   ├── 1↑ undus 🍂 → 7
    │   │   └── 1↑ on 🍂 → 6
    │   └── 2↑ e → <nil>
    │       ├── 1↑ r 🍂 → 5
    │       └── 1↑ ns 🍂 → 4
    └── 3↑ om → <nil>
        ├── 2↑ an → <nil>
        │   ├── 1↑ us 🍂 → 2
        │   └── 1↑ e 🍂 → 1
        └── 1↑ ulus 🍂 → 3

Important

• Until version 1.0 is released, anything can change, including names of methods or even their existence.
• Until version 0.3.0, this package was named patricia, despite implementing a radix tree. If you're looking for a PATRICIA tree implementation, try this package instead.

About

This package is an implementation of a radix tree in Go (or Golang).
Some of its features are based on this awesome package.

Features

• No memory allocation for default search.
• Priority sort.
• Named parameter matching.

Usage

Full documentation here.
HEAD holds the most recent features.

Contribution

How to help:

• Pull Requests
• Issues
• Opinions

Documentation

Overview

Package radix is an implementation of a radix tree.

It has the three basic operations (insertion, lookup and deletion) plus some additional methods, notably one that allows a dynamic lookup based on delimiters, which works similar to a named parameter functionality in HTTP routers.

Example

package main

import (
	"fmt"

	"github.com/gbrlsnchs/radix"
)

func main() {
	// Example from https://upload.wikimedia.org/wikipedia/commons/a/ae/Patricia_trie.svg.
	t := radix.New("Example")

	t.Add("romane", 1)
	t.Add("romanus", 2)
	t.Add("romulus", 3)
	t.Add("rubens", 4)
	t.Add("ruber", 5)
	t.Add("rubicon", 6)
	t.Add("rubicundus", 7)
	t.Sort(radix.AscLabelSort)

	err := t.Debug()

	if err != nil {
		// ...
	}

	t.Sort(radix.DescLabelSort)

	err = t.Debug()

	if err != nil {
		// ...
	}

	t.Sort(radix.PrioritySort)

	err = t.Debug()

	if err != nil {
		// ...
	}

	n := t.Get("romanus")

	fmt.Println(n.Value)
}

Output:

2

Example (Named)

package main

import (
	"fmt"

	"github.com/gbrlsnchs/radix"
)

func main() {
	t := radix.New("Named Edge Example")

	t.Add("foo@bar!@baz", "foobar")

	err := t.Debug()

	if err != nil {
		// ...
	}

	_, params := t.GetByRune("foo123!456", '@', '!')

	fmt.Println(params["bar"])
	fmt.Println(params["baz"])
}

Output:

123
456

Index

• type Node
  • func (n *Node) Depth() int
  • func (n *Node) IsLeaf() bool
  • func (n *Node) Len() int
  • func (n *Node) Less(i, j int) bool
  • func (n *Node) Priority() int
  • func (n *Node) Swap(i, j int)
• type SortingTechnique
• type Tree
  • func New(name string) *Tree
  • func (t *Tree) Add(s string, v interface{})
  • func (t *Tree) Debug() error
  • func (t *Tree) Del(s string)
  • func (t *Tree) Get(s string) *Node
  • func (t *Tree) GetByRune(s string, ph, delim rune) (*Node, map[string]string)
  • func (t *Tree) Print() error
  • func (t *Tree) Size() uint
  • func (t *Tree) Sort(st SortingTechnique)
  • func (t *Tree) String(debug bool) (string, error)

Examples

• Package
• Package (Named)

Types

type Node

type Node struct {
	// Value is a value of any type held by a node.
	Value interface{}
	// contains filtered or unexported fields
}

Node is a node of a radix tree.

func (*Node) Depth

func (n *Node) Depth() int

Depth returns the node's depth.

func (*Node) IsLeaf

func (n *Node) IsLeaf() bool

IsLeaf returns whether the node is a leaf.

func (*Node) Len

func (n *Node) Len() int

Len returns the number of edges the node has.

func (*Node) Less

func (n *Node) Less(i, j int) bool

Less compares two nodes for sorting based on their priority.

func (*Node) Priority

func (n *Node) Priority() int

Priority returns the node's priority.

func (*Node) Swap

func (n *Node) Swap(i, j int)

Swap swaps two edges from the node.

type SortingTechnique

type SortingTechnique uint8

SortingTechnique is the technique used to sort the tree.

const (
	// AscLabelSort is the value for sorting
	// the tree's edges by label in ascending order.
	AscLabelSort SortingTechnique = iota
	// DescLabelSort is the value for sorting
	// the tree's edges by label in descending order.
	DescLabelSort
	// PrioritySort is the value for sorting
	// the tree's edges by the priority of their nodes.
	PrioritySort
)

type Tree

type Tree struct {
	// Safe tells whether the tree's operations
	// should be thread-safe. By default, the tree's
	// not thread-safe.
	Safe bool
	// contains filtered or unexported fields
}

Tree is a radix tree.

func New

func New(name string) *Tree

New creates a named radix tree with a single node (its root).

func (*Tree) Add

func (t *Tree) Add(s string, v interface{})

Add adds a new node to the tree.

func (*Tree) Debug

func (t *Tree) Debug() error

Debug prints the tree's structure plus its metadata.

func (*Tree) Del

func (t *Tree) Del(s string)

Del deletes a node.

If a parent node that holds no value ends up holding only one edge after a deletion of one of its edges, it gets merged with the remaining edge.

func (*Tree) Get

func (t *Tree) Get(s string) *Node

Get retrieves a node.

func (*Tree) GetByRune

func (t *Tree) GetByRune(s string, ph, delim rune) (*Node, map[string]string)

GetByRune dynamically retrieves a node based on a placeholder and a delimiter. It also returns a map of "named parameters".

func (*Tree) Print

func (t *Tree) Print() error

Print prints the tree's structure.

func (*Tree) Size

func (t *Tree) Size() uint

Size returns the total numbers of nodes the tree has, including the root.

func (*Tree) Sort

func (t *Tree) Sort(st SortingTechnique)

Sort sorts the tree nodes and its children recursively according to their priority counter.

func (*Tree) String

func (t *Tree) String(debug bool) (string, error)

String returns a string representation of the tree structure.