routree

go, telephony, routing, prefix-tree, lpm, generics, high-performance

r := Router[string]{}
for i, pattern := range map[int]string{
	0: ".*",
	1: "7495123.*",
	2: "7(49[5|9]).......*",
	3: "7(49[5|9])......*",
	4: "7(49[5|9]).......",
	5: "1(72[0-3|4-7|8|9],5[5|7].)......*",
	6: "7495#123.*",
} {
	patterns, err := ParsePattern(pattern)
	if err != nil {
		return
	}
	r.Add(patterns, fmt.Sprintf("%d:%q", i, pattern))
}
for _, number := range []string{
	"74951234567",
	"74981234567",
	"74991234567",
	"749512345678",
	"7495#1234567",
	"17211234567",
	"15555555555",
} {
	phone, err := ParsePhone(number)
	if err != nil {
		return
	}
	fmt.Printf("%-12s -> %v\n", number, r.Match(phone))
}
m := make(map[int]bool)
fmt.Println("┬")
r.Dump(func(u Digit, v []string, l int, e bool) {
    m[l] = e
    var p strings.Builder
    for i := 0; i < l; i++ {
        if m[i] {
            p.WriteString("    ")
        } else {
            p.WriteString("│   ")
        }
    }
    if e {
        p.WriteString("└── [")
    } else {
        p.WriteString("├── [")
    }
    p.Write(bytes.Replace(u.Split(), []byte{'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'}, []byte{'.'}, 1))
    p.WriteByte(']')
    if len(v) != 0 {
        p.WriteString(" = [")
        p.WriteString(strings.Join(v, " "))
        p.WriteByte(']')
    }
    fmt.Println(p.String())
})
// Output:
// 74951234567  -> [1:"7495123.*" 4:"7(49[5|9])......." 2:"7(49[5|9]).......*" 3:"7(49[5|9])......*" 0:".*"]
// 74981234567  -> [0:".*"]
// 74991234567  -> [4:"7(49[5|9])......." 2:"7(49[5|9]).......*" 3:"7(49[5|9])......*" 0:".*"]
// 749512345678 -> [1:"7495123.*" 2:"7(49[5|9]).......*" 3:"7(49[5|9])......*" 0:".*"]
// 7495#1234567 -> [6:"7495#123.*"]
// 17211234567  -> [5:"1(72[0-3|4-7|8|9],5[5|7].)......*" 0:".*"]
// 15555555555  -> [5:"1(72[0-3|4-7|8|9],5[5|7].)......*" 0:".*"]
// ┬
// ├── [1]
// │   ├── [5]
// │   │   └── [57]
// │   │       └── [.]
// │   │           └── [.]
// │   │               └── [.]
// │   │                   └── [.]
// │   │                       └── [.]
// │   │                           └── [.]
// │   │                               └── [.*] = [5:"1(72[0-3|4-7|8|9],5[5|7].)......*"]
// │   └── [7]
// │       └── [2]
// │           └── [.]
// │               └── [.]
// │                   └── [.]
// │                       └── [.]
// │                           └── [.]
// │                               └── [.]
// │                                   └── [.*] = [5:"1(72[0-3|4-7|8|9],5[5|7].)......*"]
// ├── [7]
// │   └── [4]
// │       └── [9]
// │           ├── [5]
// │           │   └── [1]
// │           │       └── [2]
// │           │           └── [3]
// │           │               └── [.*] = [1:"7495123.*"]
// │           ├── [59]
// │           │   └── [.]
// │           │       └── [.]
// │           │           └── [.]
// │           │               └── [.]
// │           │                   └── [.]
// │           │                       ├── [.]
// │           │                       │   ├── [.] = [4:"7(49[5|9])......."]
// │           │                       │   └── [.*] = [2:"7(49[5|9]).......*"]
// │           │                       └── [.*] = [3:"7(49[5|9])......*"]
// │           └── [5#]
// │               └── [1]
// │                   └── [2]
// │                       └── [3]
// │                           └── [.*] = [6:"7495#123.*"]
// └── [.*] = [0:".*"]

---

goos: linux
goarch: amd64
pkg: github.com/pshvedko/routree
cpu: 11th Gen Intel(R) Core(TM) i7-11700F @ 2.50GHz
BenchmarkRouter_Add-16                  10406216               111.4 ns/op             0 B/op          0 allocs/op
BenchmarkRouter_Match-16                 4009887               272.9 ns/op            80 B/op         10 allocs/op
BenchmarkRouter_MatchFunc-16            22134595                52.94 ns/op            0 B/op          0 allocs/op
BenchmarkRouter_Match_Random-16          2247616               522.9 ns/op           174 B/op         17 allocs/op
PASS