pathtree

Documentation

Overview

pathtree implements a tree for fast path lookup.

Restrictions

• Paths must be a '/'-separated list of strings, like a URL or Unix filesystem.
• All paths must begin with a '/'.
• Path elements may not contain a '/'.
• Path elements beginning with a ':' or '*' will be interpreted as wildcards.
• Trailing slashes are inconsequential.

Wildcards

Wildcards are named path elements that may match any strings in that location. Two different kinds of wildcards are permitted:

• :var - names beginning with ':' will match any single path element.
• *var - names beginning with '*' will match one or more path elements. (however, no path elements may come after a star wildcard)

Extensions

Single element wildcards in the last path element can optionally end with an extension. This allows for routes like '/users/:id.json', which will not conflict with '/users/:id'.

Algorithm

Paths are mapped to the tree in the following way:

• Each '/' is a Node in the tree. The root node is the leading '/'.
• Each Node has edges to other nodes. The edges are named according to the possible path elements at that depth in the path.
• Any Node may have an associated Leaf. Leafs are terminals containing the data associated with the path as traversed from the root to that Node.

Edges are implemented as a map from the path element name to the next node in the path.

Index

• type Leaf
• type Node
  • func New() *Node
  • func (n *Node) Add(key string, val interface{}) error
  • func (n *Node) Find(key string) (leaf *Leaf, expansions []string)

Types

type Leaf

type Leaf struct {
	Value     interface{} // the value associated with this node
	Wildcards []string    // the wildcard names, in order they appear in the path
	// contains filtered or unexported fields
}

type Node

type Node struct {
	// contains filtered or unexported fields
}

func New

func New() *Node

New returns a new path tree.

func (*Node) Add

func (n *Node) Add(key string, val interface{}) error

Add a path and its associated value to the tree.

• key must begin with "/"
• key must not duplicate any existing key.

Returns an error if those conditions do not hold.

func (*Node) Find

func (n *Node) Find(key string) (leaf *Leaf, expansions []string)

Find a given path. Any wildcards traversed along the way are expanded and returned, along with the value.