regexptree

README

regexp_tree

a regular expression prefix tree.

Usage

package main

import (
	"fmt"
	"gitee.com/go-better/dev/regexp_tree"
)

func main() {
	root, err := regexp_tree.New("/", 1)
	if err != nil {
		fmt.Println(err)
		return
	}
	root.Add("/users", 2)
	root.Add(`/users/(\d+)`, 3)

	fmt.Println(root.Lookup("/"))
	fmt.Println(root.Lookup("/users"))
	fmt.Println(root.Lookup("/users/1013"))
	fmt.Println(root.Lookup("/users/a013"))

	// Output:
	// 1 []
	// 2 []
	// 3 [1013]
	// <nil> []
}

Documentation

Overview

Example (LiteralCommonPrefix_differentSuffix)

common, a, b, err := literalCommonPrefix(`/users\.html`, `/users\.htm`)
fmt.Printf("%s, %s, %s, %v", common, a, b, err)

Output:

/users\.htm, l, , <nil>

Example (LiteralCommonPrefix_error1)

common, a, b, err := literalCommonPrefix(`(`, `/`)
fmt.Printf("%s, %s, %s, %v", common, a, b, err)

Output:

, , , error parsing regexp: missing closing ): `(`

Example (LiteralCommonPrefix_error2)

common, a, b, err := literalCommonPrefix(`/`, `)`)
fmt.Printf("%s, %s, %s, %v", common, a, b, err)

Output:

, , , error parsing regexp: unexpected ): `)`

Example (NewRegex_simple)

r, err := newRegex("/")
fmt.Printf("%+v %v\n", r, err)
r, err = newRegex(`/index\.html`)
fmt.Printf("%+v %v\n", r, err)
r, err = newRegex(`/index.html`)
fmt.Printf("%+v %v\n", r, err)
r, err = newRegex(`(`)
fmt.Printf("%+v %v\n", r, err)

Output:

{ static: / } <nil>
{ static: /index.html } <nil>
{ dynamic: ^/index.html } <nil>
{  } error parsing regexp: missing closing ): `(`

Example (Regex_commonPrefix_dynamic)

r, _ := newRegex("/([a-z]+)")
common, a, b, err := r.commonPrefix("/")
fmt.Printf("%s, %s, %s, %v\n", common, a, b, err)
r, _ = newRegex("users/([0-9]+)")
common, a, b, err = r.commonPrefix("members")
fmt.Printf("%s, %s, %s, %v\n", common, a, b, err)
r, _ = newRegex("/([a-z]+)")
common, a, b, err = r.commonPrefix("/([a-z]+)/members")
fmt.Printf("%s, %s, %s, %v\n", common, a, b, err)
r, _ = newRegex("users/([0-9]+)")
common, a, b, err = r.commonPrefix("users/([a-z]+)")
fmt.Printf("%s, %s, %s, %v\n", common, a, b, err)
r, _ = newRegex(`user\.s/([0-9]+)`)
common, a, b, err = r.commonPrefix(`user\.s/managers`)
fmt.Printf("%s, %s, %s, %v\n", common, a, b, err)

Output:

/, ([a-z]+), , <nil>
, users/([0-9]+), members, <nil>
/([a-z]+), , /members, <nil>
users/, ([0-9]+), ([a-z]+), <nil>
user\.s/, ([0-9]+), managers, <nil>

Example (Regex_commonPrefix_static)

r, _ := newRegex("/")
common, a, b, err := r.commonPrefix("/")
fmt.Printf("%s, %s, %s, %v\n", common, a, b, err)
r, _ = newRegex("users")
common, a, b, err = r.commonPrefix("members")
fmt.Printf("%s, %s, %s, %v\n", common, a, b, err)
r, _ = newRegex("/users")
common, a, b, err = r.commonPrefix("/")
fmt.Printf("%s, %s, %s, %v\n", common, a, b, err)
r, _ = newRegex("users")
common, a, b, err = r.commonPrefix("([0-9]+)")
fmt.Printf("%s, %s, %s, %v\n", common, a, b, err)
r, _ = newRegex("/")
common, a, b, err = r.commonPrefix("/users")
fmt.Printf("%s, %s, %s, %v\n", common, a, b, err)
r, _ = newRegex("users/managers")
common, a, b, err = r.commonPrefix("users/([0-9]+)")
fmt.Printf("%s, %s, %s, %v\n", common, a, b, err)

Output:

/, , , <nil>
, users, members, <nil>
/, users, , <nil>
, users, ([0-9]+), <nil>
/, , users, <nil>
users/, managers, ([0-9]+), <nil>

Example (RegexpCommonPrefix_differentSuffix1)

common, a, b, err := regexpCommonPrefix(`/user_([0-9]+)/xyz`, `/user_([0-9]+)/def`)
fmt.Printf("%s, %s, %s, %v", common, a, b, err)

Output:

/user_([0-9]+)/, xyz, def, <nil>

Example (RegexpCommonPrefix_differentSuffix2)

common, a, b, err := regexpCommonPrefix("users/([0-9]+)", "users/managers")
fmt.Printf("%s, %s, %s, %v", common, a, b, err)

Output:

users/, ([0-9]+), managers, <nil>

Example (RegexpCommonPrefix_differentSuffix3)

common, a, b, err := regexpCommonPrefix(
	"/([a-z]+)/members/([0-9]+)", "/([a-z]+)/managers/([0-9]+)",
)
fmt.Printf("%s, %s, %s, %v", common, a, b, err)

Output:

/([a-z]+)/m, embers/([0-9]+), anagers/([0-9]+), <nil>

Example (RegexpCommonPrefix_empty1)

common, a, b, err := regexpCommonPrefix(`user_(\d+)/xyz`, `manager_(\d+)/def`)
fmt.Printf("%s, %s, %s, %v", common, a, b, err)

Output:

, user_([0-9]+)/xyz, manager_([0-9]+)/def, <nil>

Example (RegexpCommonPrefix_empty2)

common, a, b, err := regexpCommonPrefix(`(\d+)/xyz`, `(\w+)/def`)
fmt.Printf("%s, %s, %s, %v", common, a, b, err)

Output:

, ([0-9]+)/xyz, ([0-9A-Z_a-z]+)/def, <nil>

Example (RegexpCommonPrefix_empty3)

common, a, b, err := regexpCommonPrefix(`(\d+)`, `(\w+)`)
fmt.Printf("%s, %s, %s, %v", common, a, b, err)

Output:

, ([0-9]+), ([0-9A-Z_a-z]+), <nil>

Example (RegexpCommonPrefix_error1)

common, a, b, err := regexpCommonPrefix("(", "/")
fmt.Printf("%s, %s, %s, %v", common, a, b, err)

Output:

, , , error parsing regexp: missing closing ): `(`

Example (RegexpCommonPrefix_error2)

common, a, b, err := regexpCommonPrefix("/", ")")
fmt.Printf("%s, %s, %s, %v", common, a, b, err)

Output:

, , , error parsing regexp: unexpected ): `)`

Example (RegexpCommonPrefix_leftLonger1)

common, a, b, err := regexpCommonPrefix(`/(\d+)`, `/`)
fmt.Printf("%s, %s, %s, %v", common, a, b, err)

Output:

/, ([0-9]+), , <nil>

Example (RegexpCommonPrefix_leftLonger2)

common, a, b, err := regexpCommonPrefix(`/users/(\d+)`, `/users/`)
fmt.Printf("%s, %s, %s, %v", common, a, b, err)

Output:

/users/, ([0-9]+), , <nil>

Example (RegexpCommonPrefix_leftLonger3)

common, a, b, err := regexpCommonPrefix(`/users/(\w+)/(\d+)`, `/users/(\w+)`)
fmt.Printf("%s, %s, %s, %v", common, a, b, err)

Output:

/users/([0-9A-Z_a-z]+), /([0-9]+), , <nil>

Example (RegexpCommonPrefix_rightLonger1)

common, a, b, err := regexpCommonPrefix(`/`, `/(\d+)`)
fmt.Printf("%s, %s, %s, %v", common, a, b, err)

Output:

/, , ([0-9]+), <nil>

Example (RegexpCommonPrefix_rightLonger2)

common, a, b, err := regexpCommonPrefix(`/users/`, `/users/(\d+)`)
fmt.Printf("%s, %s, %s, %v", common, a, b, err)

Output:

/users/, , ([0-9]+), <nil>

Example (RegexpCommonPrefix_same1)

common, a, b, err := regexpCommonPrefix(`/(\d+)`, `/([0-9]+)`)
fmt.Printf("%s, %s, %s, %v", common, a, b, err)

Output:

/([0-9]+), , , <nil>

Example (RegexpCommonPrefix_same2)

common, a, b, err := regexpCommonPrefix(`/user_(\d+)`, `/user_(\d+)`)
fmt.Printf("%s, %s, %s, %v", common, a, b, err)

Output:

/user_([0-9]+), , , <nil>

Example (StringCommonPrefix_differentSuffix)

common, a, b := stringCommonPrefix("/users/list", "/users/root")
fmt.Printf("%s, %s, %s,", common, a, b)

Output:

/users/, list, root,

Example (StringCommonPrefix_empty1)

common, a, b := stringCommonPrefix("users", "managers")
fmt.Printf("%s, %s, %s,", common, a, b)

Output:

, users, managers,

Example (StringCommonPrefix_leftLonger1)

common, a, b := stringCommonPrefix("/users", "/")
fmt.Printf("%s, %s, %s,", common, a, b)

Output:

/, users, ,

Example (StringCommonPrefix_leftLonger2)

common, a, b := stringCommonPrefix("/users/root", "/users")
fmt.Printf("%s, %s, %s,", common, a, b)

Output:

/users, /root, ,

Example (StringCommonPrefix_rightLonger1)

common, a, b := stringCommonPrefix("/", "/users")
fmt.Printf("%s, %s, %s,", common, a, b)

Output:

/, , users,

Example (StringCommonPrefix_rightLonger2)

common, a, b := stringCommonPrefix("/users", "/users/root")
fmt.Printf("%s, %s, %s,", common, a, b)

Output:

/users, , /root,

Example (StringCommonPrefix_same1)

common, a, b := stringCommonPrefix("/", "/")
fmt.Printf("%s, %s, %s,", common, a, b)

Output:

/, , ,

Example (StringCommonPrefix_same2)

common, a, b := stringCommonPrefix("/users", "/users")
fmt.Printf("%s, %s, %s,", common, a, b)

Output:

/users, , ,

Example (Usage)

root, err := New("/", 1)
if err != nil {
	fmt.Println(err)
	return
}
root.Add("/users", 2)
root.Add(`/users/(\d+)`, 3)

fmt.Println(root.Lookup("/"))
fmt.Println(root.Lookup("/users"))
fmt.Println(root.Lookup("/users/1013"))
fmt.Println(root.Lookup("/users/a013"))

Output:

1 []
2 []
3 [1013]
<nil> []

Index

• Variables
• type Node
  • func New(path string, data interface{}) (*Node, error)
  • func (n *Node) Add(path string, data interface{}) error
  • func (n *Node) Lookup(path string) (interface{}, []string)
  • func (n *Node) String() string
  • func (n *Node) StringIndent(indent string) string

Examples

• Package (LiteralCommonPrefix_differentSuffix)
• Package (LiteralCommonPrefix_error1)
• Package (LiteralCommonPrefix_error2)
• Package (NewRegex_simple)
• Package (Regex_commonPrefix_dynamic)
• Package (Regex_commonPrefix_static)
• Package (RegexpCommonPrefix_differentSuffix1)
• Package (RegexpCommonPrefix_differentSuffix2)
• Package (RegexpCommonPrefix_differentSuffix3)
• Package (RegexpCommonPrefix_empty1)
• Package (RegexpCommonPrefix_empty2)
• Package (RegexpCommonPrefix_empty3)
• Package (RegexpCommonPrefix_error1)
• Package (RegexpCommonPrefix_error2)
• Package (RegexpCommonPrefix_leftLonger1)
• Package (RegexpCommonPrefix_leftLonger2)
• Package (RegexpCommonPrefix_leftLonger3)
• Package (RegexpCommonPrefix_rightLonger1)
• Package (RegexpCommonPrefix_rightLonger2)
• Package (RegexpCommonPrefix_same1)
• Package (RegexpCommonPrefix_same2)
• Package (StringCommonPrefix_differentSuffix)
• Package (StringCommonPrefix_empty1)
• Package (StringCommonPrefix_leftLonger1)
• Package (StringCommonPrefix_leftLonger2)
• Package (StringCommonPrefix_rightLonger1)
• Package (StringCommonPrefix_rightLonger2)
• Package (StringCommonPrefix_same1)
• Package (StringCommonPrefix_same2)
• Package (Usage)
• New
• Node (AddToChildren_dynamic1)
• Node (AddToChildren_static1)
• Node (AddToChildren_static2)
• Node (AddToChildren_static3)
• Node (Split_dynamic1)
• Node (Split_dynamic2)
• Node (Split_dynamic3)
• Node (Split_dynamic4)
• Node (Split_static1)
• Node (Split_static2)
• Node.Add (Conflict1)
• Node.Add (Conflict2)
• Node.Add (Conflict3)
• Node.Add (Conflict4)
• Node.Add (Conflict5)
• Node.Add (Simple1)
• Node.Add (Simple2)
• Node.Lookup
• Node.Lookup (Loopback)

Variables

var (
	ErrorDataIsNil      = errors.New("data is nil")
	ErrorNoCommonPrefix = errors.New("no common prefix")
	ErrorAlreadyExists  = errors.New("path already exists")
)

Types

type Node

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

Example (AddToChildren_dynamic1)

n, _ := New("/u", 0)
n.children = []*Node{
	{regex: regex{static: "sers"}},
	{regex: regex{dynamic: regexp.MustCompile("^/")}},
}
n.addToChildren("[0-9]+", 1)
fmt.Println(n)

Output:

{ static: /u, data: 0, children: [
  { static: sers }
  { dynamic: ^/ }
  { dynamic: ^[0-9]+, data: 1 }
] }

Example (AddToChildren_static1)

n, _ := New("/", 0)
fmt.Println(n.addToChildren(`(`, 1))
n.addToChildren("users", 1)
fmt.Println(n)
fmt.Println(n.addToChildren(`(`, 1))

Output:

error parsing regexp: missing closing ): `(`
{ static: /, data: 0, children: [
  { static: users, data: 1 }
] }
error parsing regexp: missing closing ): `(`

Example (AddToChildren_static2)

n, _ := New("/u", 0)
n.children = []*Node{
	{regex: regex{dynamic: regexp.MustCompile("^/")}},
}
n.addToChildren("sers", 1)
fmt.Println(n)

Output:

{ static: /u, data: 0, children: [
  { static: sers, data: 1 }
  { dynamic: ^/ }
] }

Example (AddToChildren_static3)

n, _ := New("/u", 0)
n.children = []*Node{
	{regex: regex{static: "nix"}},
	{regex: regex{dynamic: regexp.MustCompile("^/1")}},
	{regex: regex{dynamic: regexp.MustCompile("^/2")}},
}
n.addToChildren("sers", 1)
fmt.Println(n)

Output:

{ static: /u, data: 0, children: [
  { static: nix }
  { static: sers, data: 1 }
  { dynamic: ^/1 }
  { dynamic: ^/2 }
] }

Example (Split_dynamic1)

n, _ := New("/[a-z]+", 0)
n.split("/", "[a-z]+")
fmt.Println(n)

Output:

{ static: /, children: [
  { dynamic: ^[a-z]+, data: 0 }
] }

Example (Split_dynamic2)

n, _ := New(`/users/[0-9]+`, 0)
n.split("/u", "sers/[0-9]+")
fmt.Println(n)

Output:

{ static: /u, children: [
  { dynamic: ^sers/[0-9]+, data: 0 }
] }

Example (Split_dynamic3)

n, _ := New(`/([a-z]+)/([0-9]+)`, 0)
n.split("/([a-z]+)/", "([0-9]+)")
fmt.Println(n)

Output:

{ dynamic: ^/([a-z]+)/, children: [
  { dynamic: ^([0-9]+), data: 0 }
] }

Example (Split_dynamic4)

n, _ := New("/users/[0-9]+", 0)
n.split("/users/", "[0-9]+")
fmt.Println(n)

Output:

{ static: /users/, children: [
  { dynamic: ^[0-9]+, data: 0 }
] }

Example (Split_static1)

n, _ := New("/users", 0)
n.split("/", "users")
fmt.Println(n)
fmt.Println(n.split(`(`, "/"))
fmt.Println(n.split(`/`, ")"))

Output:

{ static: /, children: [
  { static: users, data: 0 }
] }
error parsing regexp: missing closing ): `(`
error parsing regexp: unexpected ): `)`

Example (Split_static2)

n, _ := New("/users/managers", 0)
n.split("/users/", "managers")
fmt.Println(n)

Output:

{ static: /users/, children: [
  { static: managers, data: 0 }
] }

func New

func New(path string, data interface{}) (*Node, error)

Example

fmt.Println(New("/", 1))
fmt.Println(New("/users", 2))
fmt.Println(New("/[a-z]+", 3))
fmt.Println(New("/users/[0-9]+", 4))
fmt.Println(New(`/users/\d+`, 5))
fmt.Println(New(`(`, 6))

Output:

{ static: /, data: 1 } <nil>
{ static: /users, data: 2 } <nil>
{ dynamic: ^/[a-z]+, data: 3 } <nil>
{ dynamic: ^/users/[0-9]+, data: 4 } <nil>
{ dynamic: ^/users/\d+, data: 5 } <nil>
<nil> error parsing regexp: missing closing ): `(`

func (*Node) Add

func (n *Node) Add(path string, data interface{}) error

Example (Conflict1)

root, _ := New("/", 0)
fmt.Println(root.Add("/", 1))

Output:

path already exists

Example (Conflict2)

root, _ := New("/users", 0)
fmt.Println(root.Add("/users", 1))

Output:

path already exists

Example (Conflict3)

root, _ := New("/users", 0)
root.Add("/", 1)
fmt.Println(root.Add("/users", 2))

Output:

path already exists

Example (Conflict4)

root, _ := New("/users/active", 0)
root.Add("/", 1)
root.Add("/users", 2)
fmt.Println(root.Add("/users/active", 3))

Output:

path already exists

Example (Conflict5)

root, _ := New("/users/([0-9]+)", 0)
root.Add("/", 1)
root.Add("/users", 2)
fmt.Println(root.Add("/users/([0-9]+)", 3))

Output:

path already exists

Example (Simple1)

root, _ := New("/", 0)
fmt.Println(root.Add("(", 3))
root.Add("/users", 1)
root.Add(`/users/(\d+)`, 2)
fmt.Println(root)

Output:

error parsing regexp: missing closing ): `(`
{ static: /, data: 0, children: [
  { static: users, data: 1, children: [
    { dynamic: ^/([0-9]+), data: 2 }
  ] }
] }

Example (Simple2)

root, _ := New("/", 0)
root.Add("/users", 1)
root.Add("/users/([0-9]+)", 2)
root.Add("/unix/([a-z]+)", 3)
root.Add("/users/root", 4)
root.Add("/([0-9]+)", 5)
fmt.Println(root)

Output:

{ static: /, data: 0, children: [
  { static: u, children: [
    { static: sers, data: 1, children: [
      { static: /, children: [
        { static: root, data: 4 }
        { dynamic: ^([0-9]+), data: 2 }
      ] }
    ] }
    { dynamic: ^nix/([a-z]+), data: 3 }
  ] }
  { dynamic: ^([0-9]+), data: 5 }
] }

func (*Node) Lookup

func (n *Node) Lookup(path string) (interface{}, []string)

Example

root, _ := New("/", 0)
root.Add("/users", 1)
root.Add("/users/123/([0-9]+)", 22)
root.Add("/users/([0-9]+)", 2)
root.Add("/unix/([a-z]+)/([0-9.]+)", 3)
root.Add("/users/root", 4)
root.Add("/([0-9]+)", 5)
fmt.Println(root.Lookup("/"))
fmt.Println(root.Lookup("/users"))
fmt.Println(root.Lookup("/users/123"))
fmt.Println(root.Lookup("/users/123/456"))
fmt.Println(root.Lookup("/unix/linux/4.4.0"))
fmt.Println(root.Lookup("/users/root"))
fmt.Println(root.Lookup("/987"))
fmt.Println(root.Lookup("404"))
fmt.Println(root.Lookup("/users404"))
fmt.Println(root.Lookup("/unix/linux/4.4.0a"))

Output:

0 []
1 []
2 [123]
22 [456]
3 [linux 4.4.0]
4 []
5 [987]
<nil> []
<nil> []
<nil> []

Example (Loopback)

root, _ := New("/", 0)
root.Add(`/(\w+)`, 1)
root.Add(`/(\w+)/abc`, 2)
root.Add(`/([a-z]+)/def`, 3)

fmt.Println(root.Lookup("/"))
fmt.Println(root.Lookup("/users"))
fmt.Println(root.Lookup("/users/abc"))
fmt.Println(root.Lookup("/users/def"))

Output:

0 []
1 [users]
2 [users]
3 [users]

func (*Node) String

func (n *Node) String() string

func (*Node) StringIndent

func (n *Node) StringIndent(indent string) string