regexptree

package
v0.0.0-...-d31700d Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Mar 28, 2022 License: MIT Imports: 6 Imported by: 0

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

Examples

Constants

This section is empty.

Variables

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

Functions

This section is empty.

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

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.