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
|
package slice
import "reflect"
type Slice []interface{}
type Del int
type Ins struct {
Idx int
Value []interface{}
}
type Delta struct {
Del []Del
Ins []Ins
}
func Patch(source Slice, delta Delta) (target Slice) {
// apply Del part from patch to source into temp
size := len(source) - len(delta.Del)
temp := make(Slice, size)
fill := 0
prev := 0
for _, del := range delta.Del {
di := int(del)
copy(temp[fill:], source[prev:di])
fill += di - prev
prev = di + 1
}
copy(temp[fill:], source[prev:])
// apply Ins part from patch to temp into target
for _, ins := range delta.Ins {
size += len(ins.Value)
}
target = make(Slice, size)
fill = 0
prev = 0
tpos := 0
for _, ins := range delta.Ins {
offset := ins.Idx - prev
copy(target[fill:], temp[tpos:tpos+offset])
fill += offset
tpos += offset
copy(target[fill:], ins.Value)
fill += len(ins.Value)
prev = ins.Idx + len(ins.Value)
}
return
}
func Diff(source Slice, target Slice) (delta Delta) {
var si, ti int
var found bool
for ; si < len(source); si++ {
for i := ti; i < len(target); i++ {
found = reflect.DeepEqual(target[i], source[si])
if found {
if i != ti {
delta.Ins = append(delta.Ins, Ins{ti, target[ti:i]})
}
ti = i + 1
break
}
}
if !found {
delta.Del = append(delta.Del, Del(si))
}
}
if ti < len(target) {
delta.Ins = append(delta.Ins, Ins{ti, target[ti:]})
}
return
}
|
