-
-
Notifications
You must be signed in to change notification settings - Fork 53
/
feature.go
109 lines (96 loc) · 1.96 KB
/
feature.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
package filter
import (
"fmt"
"io"
"strings"
)
type (
// Feature represents a feature.
Feature = string
// Features represents a vector of features.
Features = []string
)
// Any represents an arbitrary feature.
const Any Feature = "\x00"
type filterEdge struct {
val Feature
to *filterNode
}
type filterNode struct {
fanout []*filterEdge
}
func (n filterNode) isLeaf() bool {
return n.fanout == nil
}
func (n filterNode) has(s Feature) int {
for i, v := range n.fanout {
if v.val == Any || v.val == s {
return i
}
}
return -1
}
// FeaturesFilter represents a filter that filters a vector of features.
type FeaturesFilter struct {
root filterNode
}
// NewFeaturesFilter returns a features filter.
func NewFeaturesFilter(fs ...Features) *FeaturesFilter {
var ret FeaturesFilter
for _, v := range fs {
ret.add(v)
}
return &ret
}
func (f *FeaturesFilter) add(fs Features) {
n := &f.root
for i, v := range fs {
tail := i == len(fs)-1
if k := n.has(v); k >= 0 {
n = n.fanout[k].to
if n.isLeaf() {
break // a stronger condition exists.
} else if tail {
n.fanout = nil // clear week conditions.
break
}
continue
}
edge := filterEdge{
val: v,
}
n.fanout = append(n.fanout, &edge)
edge.to = &filterNode{}
n = edge.to
}
}
// Match returns true if a filter matches given features.
func (f FeaturesFilter) Match(fs Features) bool {
n := &f.root
for _, v := range fs {
if k := n.has(v); k >= 0 {
n = n.fanout[k].to
if n.isLeaf() {
return true
}
continue
}
return false
}
return false
}
// String implements string interface.
func (f FeaturesFilter) String() string {
var buf strings.Builder
filterString(&buf, 0, &f.root)
return buf.String()
}
func filterString(w io.Writer, indent int, n *filterNode) {
const space = ` `
for _, edge := range n.fanout {
_, _ = fmt.Fprintf(w, "%s%s\n", strings.Repeat(space, indent), edge.val)
if edge.to != nil {
filterString(w, indent+1, edge.to)
}
}
}