patricia

README

patricia (PATRICIA tree)

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 errouneously implemented a radix tree, and not exactly a PATRICIA tree, which is a binary version of the radix tree. If you're looking for a radix tree implementation, try this package instead.

About

This package is an implementation of a PATRICIA tree (or binary radix tree) in Go (or Golang).

Usage

Full documentation here.
HEAD holds the most recent features.

Contribution

How to help:

• Pull Requests
• Issues
• Opinions

Documentation

Overview

Package patricia is an implementation of a PATRICIA 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/patricia"
)

func main() {
	// Example from https://upload.wikimedia.org/wikipedia/commons/a/ae/Patricia_trie.svg.
	t := patricia.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)

	n := t.Get("romanus")

	fmt.Println(n.Value)
}

Output:
2

Index

• type Node
  • func (n *Node) Depth() int
  • func (n *Node) IsLeaf() bool
• type SortingTechnique
• type Tree
  • func New(name string) *Tree
  • func (t *Tree) Add(s string, v interface{})
  • func (t *Tree) Del(s string)
  • func (t *Tree) Get(s string) *Node
  • func (t *Tree) Size() uint

Examples

• Package

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 PATRICIA 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.

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 PATRICIA Tree.

func New

func New(name string) *Tree

New creates a named PATRICIA 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) Del

func (t *Tree) Del(s string)

Del deletes a node.

func (*Tree) Get

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

Get retrieves a node.

func (*Tree) Size

func (t *Tree) Size() uint

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