trie

Documentation

Index

• Constants
• Variables
• func GetParam(w http.ResponseWriter, key string) string
• func SetParam(w http.ResponseWriter, key, value string) bool
• type InsertOption
  • func WithData(data interface{}) InsertOption
  • func WithProxyFactory(proxy gateway.ProxyFactory) InsertOption
  • func WithTag(tag string) InsertOption
• type Node
  • func NewNode() *Node
  • func (n *Node) IsEnd() bool
  • func (n *Node) Keys(sorter NodeKeysSorter) (list []string)
  • func (n *Node) Parent() *Node
  • func (n *Node) String() string
• type NodeKeysSorter
• type ParamEntry
  • func GetParams(w http.ResponseWriter) []ParamEntry
• type ParamStore
• type ParamsSetter
• type Trie
  • func NewTrie() *Trie
  • func (t *Trie) Autocomplete(prefix string, sorter NodeKeysSorter) (list []string)
  • func (t *Trie) HasPrefix(prefix string) bool
  • func (t *Trie) Insert(pattern string, options ...InsertOption)
  • func (t *Trie) Parents(prefix string) (parents []*Node)
  • func (t *Trie) Search(q string, params ParamsSetter) *Node
  • func (t *Trie) SearchPrefix(prefix string) *Node
• type Writer
  • func (pw *Writer) Get(key string) string
  • func (pw *Writer) GetAll() []ParamEntry
  • func (pw *Writer) Set(key, value string)

Constants

const (
	// ParamStart is the character, as a string, which a path pattern starts to define its named parameter.
	ParamStart = ":"
	// WildcardParamStart is the character, as a string, which a path pattern starts to define its named parameter for wildcards.
	// It allows everything else after that path prefix
	// but the Trie checks for static paths and named parameters before that in order to support everything that other implementations do not,
	// and if nothing else found then it tries to find the closest wildcard path(super and unique).
	WildcardParamStart = "*"
)

Variables

var DefaultKeysSorter = func(list []string) func(i, j int) bool {
	return func(i, j int) bool {
		return len(strings.Split(list[i], pathSep)) < len(strings.Split(list[j], pathSep))
	}
}

DefaultKeysSorter sorts as: first the "key (the path)" with the lowest number of slashes.

Functions

func GetParam

func GetParam(w http.ResponseWriter, key string) string

GetParam returns the path parameter value based on its key, i.e "/hello/:name", the parameter key is the "name". For example if a route with pattern of "/hello/:name" is inserted to the `Trie` or handlded by the `Mux` and the path "/hello/kataras" is requested through the `Mux#ServeHTTP -> Trie#search` then the `GetParam("name")` will return the value of "kataras". If not associated value with that key is found then it will return an empty string.

The function will do its job only if the given "w" http.ResponseWriter interface is a `ParamStore`.

func SetParam

func SetParam(w http.ResponseWriter, key, value string) bool

SetParam sets manually a parameter to the "w" http.ResponseWriter which should be a ResponseWriter. This is not commonly used by the end-developers, unless sharing values(string messages only) between handlers is absolutely necessary.

Types

type InsertOption

type InsertOption func(*Node)

InsertOption is just a function which accepts a pointer to a Node which can alt its `Handler`, `Tag` and `Data` fields.

See `WithHandler`, `WithTag` and `WithData`.

func WithData

func WithData(data interface{}) InsertOption

WithData sets the node's optionally `Data` field.

func WithProxyFactory

func WithProxyFactory(proxy gateway.ProxyFactory) InsertOption

WithProxyFactory sets the node's `Handler` field (useful for HTTP).

func WithTag

func WithTag(tag string) InsertOption

WithTag sets the node's `Tag` field (may be useful for HTTP).

type Node

type Node struct {

	// insert main data relative to http and a tag for things like route names.
	Proxy gateway.ProxyFactory
	Tag   string

	// other insert data.
	Data interface{}
	// contains filtered or unexported fields
}

Node is the trie's node which path patterns with their data like an HTTP handler are saved to. See `Trie` too.

func NewNode

func NewNode() *Node

NewNode returns a new, empty, Node.

func (*Node) IsEnd

func (n *Node) IsEnd() bool

IsEnd returns true if this Node is a final path, has a key.

func (*Node) Keys

func (n *Node) Keys(sorter NodeKeysSorter) (list []string)

Keys returns this node's key (if it's a final path segment) and its children's node's key. The "sorter" can be optionally used to sort the result.

func (*Node) Parent

func (n *Node) Parent() *Node

Parent returns the parent of that node, can return nil if this is the root node.

func (*Node) String

func (n *Node) String() string

String returns the key, which is the path pattern for the HTTP Mux.

type NodeKeysSorter

type NodeKeysSorter = func(list []string) func(i, j int) bool

NodeKeysSorter is the type definition for the sorting logic that caller can pass on `GetKeys` and `Autocomplete`.

type ParamEntry

type ParamEntry struct {
	Key   string
	Value string
}

ParamEntry holds the Key and the Value of a named path parameter.

func GetParams

func GetParams(w http.ResponseWriter) []ParamEntry

GetParams returns all the available parameters based on the "w" http.ResponseWriter which should be a ParamStore.

The function will do its job only if the given "w" http.ResponseWriter interface is a `ParamStore`.

type ParamStore

type ParamStore interface {
	Set(key string, value string)
	Get(key string) string
	GetAll() []ParamEntry
}

ParamStore should be completed by http.ResponseWriter to support dynamic path parameters. See the `Writer` type for more. This interface can be implemented by custom response writers. Example of implementation: to change where and how the parameters are stored and retrieved.

type ParamsSetter

type ParamsSetter interface {
	Set(string, interface{})
}

ParamsSetter is the interface which should be implemented by the params writer for `search` in order to store the found named path parameters, if any.

type Trie

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

Trie contains the main logic for adding and searching nodes for path segments. It supports wildcard and named path parameters. Trie supports very coblex and useful path patterns for routes. The Trie checks for static paths(path without : or *) and named parameters before that in order to support everything that other implementations do not, and if nothing else found then it tries to find the closest wildcard path(super and unique).

func NewTrie

func NewTrie() *Trie

NewTrie returns a new, empty Trie. It is only useful for end-developers that want to design their own mux/router based on my trie implementation.

See `Trie`

func (*Trie) Autocomplete

func (t *Trie) Autocomplete(prefix string, sorter NodeKeysSorter) (list []string)

Autocomplete returns the keys that starts with "prefix", this is useful for custom search-engines built on top of my trie implementation.

func (*Trie) HasPrefix

func (t *Trie) HasPrefix(prefix string) bool

HasPrefix returns true if "prefix" is found inside the registered nodes.

func (*Trie) Insert

func (t *Trie) Insert(pattern string, options ...InsertOption)

Insert adds a node to the trie.

func (*Trie) Parents

func (t *Trie) Parents(prefix string) (parents []*Node)

Parents returns the list of nodes that a node with "prefix" key belongs to.

func (*Trie) Search

func (t *Trie) Search(q string, params ParamsSetter) *Node

Search is the most important part of the Trie. It will try to find the responsible node for a specific query (or a request path for HTTP endpoints).

Search supports searching for static paths(path without : or *) and paths that contain named parameters or wildcards. Priority as: 1. static paths 2. named parameters with ":" 3. wildcards 4. closest wildcard if not found, if any 5. root wildcard

func (*Trie) SearchPrefix

func (t *Trie) SearchPrefix(prefix string) *Node

SearchPrefix returns the last node which holds the key which starts with "prefix".

type Writer

type Writer struct {
	http.ResponseWriter
	// contains filtered or unexported fields
}

Writer is the muxie's specific ResponseWriter to hold the path parameters. Usage: use this to cast a handler's `http.ResponseWriter` and pass it as an embedded parameter to custom response writer that will be passed to the next handler in the chain.

func (*Writer) Get

func (pw *Writer) Get(key string) string

Get returns the value of the associated parameter based on its key/name.

func (*Writer) GetAll

func (pw *Writer) GetAll() []ParamEntry

GetAll returns all the path parameters keys-values.

func (*Writer) Set

func (pw *Writer) Set(key, value string)

Set implements the `ParamsSetter` which `Trie#search` needs to store the parameters, if any. These are decoupled because end-developers may want to use the trie to design a new Mux of their own or to store different kind of data inside it.