forked from alecthomas/gometalinter
/
dupl.go
98 lines (83 loc) · 1.74 KB
/
dupl.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
package suffixtree
import "sort"
type Match struct {
Ps []Pos
Len Pos
}
type posList struct {
positions []Pos
}
func newPosList() *posList {
return &posList{make([]Pos, 0)}
}
func (p *posList) append(p2 *posList) {
p.positions = append(p.positions, p2.positions...)
}
func (p *posList) add(pos Pos) {
p.positions = append(p.positions, pos)
}
type contextList struct {
lists map[int]*posList
}
func newContextList() *contextList {
return &contextList{make(map[int]*posList)}
}
func (c *contextList) getAll() []Pos {
keys := make([]int, 0, len(c.lists))
for k := range c.lists {
keys = append(keys, k)
}
sort.Ints(keys)
var ps []Pos
for _, k := range keys {
ps = append(ps, c.lists[k].positions...)
}
return ps
}
func (c *contextList) append(c2 *contextList) {
for lc, pl := range c2.lists {
if _, ok := c.lists[lc]; ok {
c.lists[lc].append(pl)
} else {
c.lists[lc] = pl
}
}
}
// FindDuplOver find pairs of maximal duplicities over a threshold
// length.
func (t *STree) FindDuplOver(threshold int) <-chan Match {
auxTran := newTran(0, 0, t.root)
ch := make(chan Match)
go func() {
walkTrans(auxTran, 0, threshold, ch)
close(ch)
}()
return ch
}
func walkTrans(parent *tran, length, threshold int, ch chan<- Match) *contextList {
s := parent.state
cl := newContextList()
if len(s.trans) == 0 {
pl := newPosList()
start := parent.end + 1 - Pos(length)
pl.add(start)
ch := 0
if start > 0 {
ch = s.tree.data[start-1].Val()
}
cl.lists[ch] = pl
return cl
}
for _, t := range s.trans {
ln := length + t.len()
cl2 := walkTrans(t, ln, threshold, ch)
if ln >= threshold {
cl.append(cl2)
}
}
if length >= threshold && len(cl.lists) > 1 {
m := Match{cl.getAll(), Pos(length)}
ch <- m
}
return cl
}