pathtree: github.com/robfig/pathtree Index | Files

package pathtree

import "github.com/robfig/pathtree"

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

Package Files

tree.go

type Leaf Uses

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 Uses

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

func New Uses

func New() *Node

New returns a new path tree.

func (*Node) Add Uses

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 Uses

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.

Package pathtree imports 2 packages (graph) and is imported by 150 packages. Updated 2016-07-15. Refresh now. Tools for package owners.