trie

README

Trie.go

Usage

tree := trie.New()
// Put(pattern string, value interface())
tree.Put("/", "root")
tree.Put("/<id:int>", "name pattern")

// Has(pattern string) bool
duplicated := tree.Has("/")

// Match(key string) bool, result
ok, result := tree.Match("/")
// ok is true
// result.Params is nil
// result.Value.(string) is "root"

ok, result = tree.Match("/123")
// ok is true
// result.Params is {"id": 123}
// result.Value.(string) is "name pattern"

ok, result = tree.Match("/hi")
// ok is false

ok, node := tree.GetNode("/<id:int>")
if ok {
	node.Data["put_data"] = "hello"
}

Examples

A HTTP router base on it.

package main

import (
	"fmt"
	"net/http"
	"os"

	"github.com/importcjj/trie-go/router"
)

func Helloworld(ctx *router.Context) {
	ctx.WriteString("hello, world!")
}

func ParamHandler(ctx *router.Context) {
	username := ctx.ParamString("username")
	text := fmt.Sprintf("hi, %s", username)
	ctx.WriteString(text)
}

var PageResource = &router.Handler{
	OnGet: func(ctx *router.Context) {
		filepath := ctx.ParamString("filepath")
		text := fmt.Sprintf("Get page %s", filepath)
		ctx.WriteString(text)
	},

	OnPost: func(ctx *router.Context) {
		filepath := ctx.ParamString("filepath")
		text := fmt.Sprintf("Post page %s", filepath)
		ctx.WriteString(text)
	},
}

// BasicAuth is a Midwares
func BasicAuth(ctx *router.Context) {
	fmt.Fprintln(os.Stderr, ctx.Request.URL, "Call Basic Auth.")
}

// BeforeMetric mark a time point when the request start.
func BeforeMetric(ctx *router.Context) {
	// just a example, so use the params map to
	// record the time.
	ctx.Params["time"] = time.Now().Format("Mon Jan 2 15:04:05 -0700 MST 2006")
}

// AfterMetric log the time spent to handle the requeset.
func AfterMetric(ctx *router.Context) {
	start, _ := time.Parse("Mon Jan 2 15:04:05 -0700 MST 2006", ctx.Params["time"])
	dur := time.Since(start)
	fmt.Fprintf(os.Stderr, "%s spent", dur.String())
}

var r = router.New()

func init() {
	r.Get("/hello/world", Helloworld)
	r.Get("/hi/<username:str>", ParamHandler)
	// restful api style, this pattern can match such as
	// "/page/hi.html" "/page/static/inde.html" eta.
	r.Router("/page/<filepath:*>", PageResource)

	r.Before("/", BasicAuth, BeforeMetric)
	r.After("/", AfterMetric)
}

func main() {
	server := &http.Server{
		Addr:    ":8080",
		Handler: r,
	}
	server.ListenAndServe()
}

Documentation

Index

• Constants
• Variables
• func RegisterPattern(name string, pattern string) error
• type Node
  • func NewNode(str ...string) *Node
• type Pattern
  • func NewPattern(str string) *Pattern
  • func (pattern *Pattern) EqualToStr(str string) bool
  • func (pattern *Pattern) Match(str string) (bool, map[string]string)
  • func (pattern *Pattern) MatchEverything() bool
• type PatternStore
  • func NewPatternStore() *PatternStore
  • func (store *PatternStore) GetPattern(name string) string
  • func (store *PatternStore) Register(name string, pattern string) error
• type Result
  • func NewResult() *Result
• type Trie
  • func New() *Trie
  • func (trie *Trie) GetNode(v string) (ok bool, node *Node)
  • func (trie *Trie) Has(pattern string) bool
  • func (trie *Trie) Match(v string) (bool, *Result)
  • func (trie *Trie) Put(pattern string, value interface{}) error
  • func (trie *Trie) SetDelimeter(delimeter string)

Constants

const (
	DefaultPatternDelimeter = ":"
)

consts

Variables

var (
	ErrDuplicatedPatternName = errors.New("trie.go: the pattern name already exists")
)

Errors

Functions

func RegisterPattern

func RegisterPattern(name string, pattern string) error

RegisterPattern allow you add a customize pattern to the defaultPatternStore.

Types

type Node

type Node struct {
	Pattern  *Pattern
	Value    interface{}
	Data     map[string]interface{}
	Children map[string]*Node
	// contains filtered or unexported fields
}

Node is the tree node of the Trie.

func NewNode

func NewNode(str ...string) *Node

NewNode returns a new Node object.

type Pattern

type Pattern struct {
	IsRegexpPattern bool
	// contains filtered or unexported fields
}

Pattern of trie node.

func NewPattern

func NewPattern(str string) *Pattern

NewPattern returns a new Pattern object.

func (*Pattern) EqualToStr

func (pattern *Pattern) EqualToStr(str string) bool

EqualToStr returns true if the pattern's regexpStr just equal to self's patternStr

func (*Pattern) Match

func (pattern *Pattern) Match(str string) (bool, map[string]string)

Match matches the given string with self's regexpStr, if pattern matched, it will return true and the params it found. Otherwise, just returns false and nil.

func (*Pattern) MatchEverything

func (pattern *Pattern) MatchEverything() bool

MatchEverything returns true, if the pattern is the `*` pattern.

type PatternStore

type PatternStore struct {
	Patterns       map[string]string
	DefaultPattern func() string
}

PatternStore is a pattern register.

func NewPatternStore

func NewPatternStore() *PatternStore

NewPatternStore returns a new PatternStore object.

func (*PatternStore) GetPattern

func (store *PatternStore) GetPattern(name string) string

GetPattern returns a pattern which is bound to name. If there is none, returns the default pattern. In the Default Pattern Store, it just returns then `str` pattern.

func (*PatternStore) Register

func (store *PatternStore) Register(name string, pattern string) error

Register can adds a new customize pattern to the pattern store.

type Result

type Result struct {
	Params    map[string]string
	Value     interface{}
	ChainData []map[string]interface{}
}

Result is return by Match and GetNode.

func NewResult

func NewResult() *Result

NewResult returns a new Result object.

type Trie

type Trie struct {
	Delimeter string
	Root      *Node
}

Trie is a tree

func New

func New() *Trie

New returns a new Trie object.

func (*Trie) GetNode

func (trie *Trie) GetNode(v string) (ok bool, node *Node)

GetNode allows you use the origin pattern string which was used in Put to get the node which points it.

func (*Trie) Has

func (trie *Trie) Has(pattern string) bool

Has returns true if the pattern is duplicated in the trie tree. Otherwise, returns false.

func (*Trie) Match

func (trie *Trie) Match(v string) (bool, *Result)

Match try to match the key with a pattern, if successful, it will return true and the value which was put with the matched pattern. If the pattern is't a certain string, this function will also return the params matched by this pattern.

func (*Trie) Put

func (trie *Trie) Put(pattern string, value interface{}) error

Put add a new pattern to the trie tree.

func (*Trie) SetDelimeter

func (trie *Trie) SetDelimeter(delimeter string)

SetDelimeter sets the delimeter of the trie object.