trout
2015-03-16
Child:bf38b050b6c4
trout/trie.go
First pass at a router library. First pass at a router library and, incidentally, implementing a trie. I could probably optimise the search for the right branch somehow, but I honestly just can't be bothered right now. I also haven't tested this at all or even tried to run it, so who knows if my code even works. But it compiles, go vet and golint have found nothing to complain about, it has documentation, and it's properly formatted. So it's already better than most software out there. </ba dump tiss>
1 package trout
3 import (
4 "net/http"
5 "sort"
6 "sync"
7 )
9 type trie struct {
10 branch *branch
11 sync.RWMutex
12 }
14 func (t *trie) match(input []string) ([]int, bool) {
15 if t.branch == nil {
16 t.branch = &branch{}
17 }
18 b := t.branch
19 path := []int{}
20 offset := 0
21 num := len(input)
22 for i := 0; i < num; i++ {
23 // if we're on a nil branch, we're at the end of our line
24 if b == nil {
25 return path, false
26 }
27 offset = pickNextBranch(b, offset, input[i])
28 if offset == -1 {
29 if len(path) == 0 {
30 // can't find it, bail
31 return path, false
32 }
33 // no match, backup
34 path, offset = backup(path)
35 offset = offset + 1 // we want the next index from the previously matched one
36 b = b.parent // we need to be picking a branch from our parent, again
37 i = i - 2 // back up to the choice before the one that got us here
38 } else {
39 path = append(path, offset)
40 b = b.children[offset]
41 offset = 0
42 }
43 }
44 return path, true
45 }
47 type branch struct {
48 parent *branch
49 children []*branch
50 key string
51 isParam bool
52 methods map[string]http.Handler
53 }
55 func (b *branch) Less(i, j int) bool {
56 if b.children[i].key == b.children[j].key {
57 return b.children[j].isParam && !b.children[i].isParam
58 }
59 return b.children[i].key < b.children[j].key
60 }
62 func (b *branch) Len() int {
63 return len(b.children)
64 }
66 func (b *branch) Swap(i, j int) {
67 b.children[i], b.children[j] = b.children[j], b.children[i]
68 }
70 func (b *branch) addChild(key string, param bool) *branch {
71 child := &branch{key: key, parent: b, isParam: param}
72 if b.children == nil {
73 b.children = []*branch{child}
74 return child
75 }
76 b.children = append(b.children, child)
77 sort.Sort(b)
78 return child
79 }
81 func (b *branch) check(input string) bool {
82 if b.isParam && b.key != "" {
83 return true
84 }
85 if b.key == input {
86 return true
87 }
88 return false
89 }
91 func (b *branch) setHandler(method string, handler http.Handler) {
92 b.methods[method] = handler
93 }
95 func pickNextBranch(b *branch, offset int, input string) int {
96 count := len(b.children)
97 for i := offset; i < count; i++ {
98 if b.children[i].check(input) {
99 return i
100 }
101 }
102 return -1
103 }
105 func backup(path []int) ([]int, int) {
106 last := len(path) - 1
107 pos := path[last]
108 path = path[:last]
109 return path, pos
110 }