moth11.net
xcvr tui
1package main
2
3import ()
4
5type EditType = int
6
7const (
8 EditAdd EditType = iota
9 EditKeep
10 EditDel
11 EditNil
12)
13
14type Edit struct {
15 EditType EditType
16 Utf16Text []uint16
17}
18
19type Editstring struct {
20 EditType EditType
21 Text string
22}
23
24type EditSegment struct {
25 weight int
26 aidx int
27 bidx int
28 parent *EditSegment
29}
30
31type coordinate struct {
32 a int
33 b int
34}
35
36type SegmentHeap struct {
37 segments []*EditSegment
38 searched map[coordinate]bool
39}
40
41func NewSegmentHeap() SegmentHeap {
42 segments := make([]*EditSegment, 0, 10)
43 searched := make(map[coordinate]bool)
44 return SegmentHeap{segments, searched}
45}
46
47func (h *SegmentHeap) Add(seg *EditSegment) {
48 searched := h.searched[coordinate{seg.aidx, seg.bidx}]
49 if searched {
50 return
51 }
52 h.segments = append(h.segments, seg)
53 h.searched[coordinate{seg.aidx, seg.bidx}] = true
54 h.siftUp(len(h.segments) - 1)
55}
56
57func (h *SegmentHeap) PopFront() *EditSegment {
58 if len(h.segments) == 0 {
59 return nil
60 }
61 front := h.segments[0]
62 if len(h.segments) == 1 {
63 h.segments = nil
64 return front
65 }
66 h.segments[0] = h.segments[len(h.segments)-1]
67 h.segments = h.segments[:len(h.segments)-1]
68 h.siftDown(0)
69 return front
70}
71
72func (h *SegmentHeap) siftUp(idx int) {
73 if idx == 0 {
74 return
75 }
76 loweridx := idx
77 upperidx := (idx - 1) / 2
78 lower := h.segments[loweridx]
79 upper := h.segments[upperidx]
80 if lower.lighter(upper) {
81 h.segments[upperidx] = lower
82 h.segments[loweridx] = upper
83 h.siftUp(upperidx)
84 }
85}
86
87func (h *SegmentHeap) siftDown(idx int) {
88 upperidx := idx
89 var swap *EditSegment
90 loweridx := idx*2 + 1
91 lower2idx := idx*2 + 2
92 if loweridx < len(h.segments) && h.segments[loweridx].lighter(h.segments[upperidx]) {
93 swap = h.segments[upperidx]
94 h.segments[upperidx] = h.segments[loweridx]
95 h.segments[loweridx] = swap
96 h.siftDown(loweridx)
97 return
98 }
99 if lower2idx < len(h.segments) && h.segments[lower2idx].lighter(h.segments[upperidx]) {
100 swap = h.segments[upperidx]
101 h.segments[upperidx] = h.segments[lower2idx]
102 h.segments[lower2idx] = swap
103 h.siftDown(lower2idx)
104 return
105 }
106
107}
108
109func (seg *EditSegment) lighter(A *EditSegment) bool {
110 if seg.weight < A.weight {
111 return true
112 } else if seg.weight > A.weight {
113 return false
114 } else {
115 return seg.aidx+seg.bidx > A.aidx+A.bidx
116 }
117}
118
119// Diff calculates the diff between wordA and wordB as a miniaml slice of
120// edits that you have to make to wordA so that you end up with wordB
121func Diff(wordA []uint16, wordB []uint16) []Edit {
122 heap := NewSegmentHeap()
123 head := EditSegment{0, 0, 0, nil}
124 heap.Add(&head)
125 segment := heap.PopFront()
126 for !(segment.aidx == len(wordA) && segment.bidx == len(wordB)) {
127 if segment.aidx != len(wordA) &&
128 segment.bidx != len(wordB) &&
129 wordA[segment.aidx] == wordB[segment.bidx] {
130 newSegment := EditSegment{segment.weight, segment.aidx + 1, segment.bidx + 1, segment}
131 heap.Add(&newSegment)
132 }
133 if segment.aidx != len(wordA) {
134 newSegment := EditSegment{segment.weight + 1, segment.aidx + 1, segment.bidx, segment}
135 heap.Add(&newSegment)
136 }
137 if segment.bidx != len(wordB) {
138 newSegment := EditSegment{segment.weight + 1, segment.aidx, segment.bidx + 1, segment}
139 heap.Add(&newSegment)
140 }
141 segment = heap.PopFront()
142 }
143 prevSegment := segment.parent
144 edits := make([]Edit, 0)
145 currentEdit := Edit{EditNil, nil}
146 for prevSegment != nil {
147 diffA := prevSegment.aidx != segment.aidx
148 diffB := prevSegment.bidx != segment.bidx
149 var et EditType
150 var char uint16
151 if diffA && diffB {
152 et = EditKeep
153 char = wordA[prevSegment.aidx]
154 } else if diffA {
155 et = EditDel
156 char = wordA[prevSegment.aidx]
157 } else if diffB {
158 et = EditAdd
159 char = wordB[prevSegment.bidx]
160 } else {
161 et = EditNil
162 }
163 if currentEdit.EditType != et {
164 if currentEdit.EditType != EditNil {
165 edits = append([]Edit{currentEdit}, edits...)
166 }
167 currentEdit = Edit{et, []uint16{char}}
168 } else {
169 currentEdit.Utf16Text = append([]uint16{char}, currentEdit.Utf16Text...)
170 }
171 segment = prevSegment
172 prevSegment = segment.parent
173 }
174 edits = append([]Edit{currentEdit}, edits...)
175 return edits
176}
177
178func Diffs(wordA string, wordB string) []Editstring {
179 heap := NewSegmentHeap()
180 head := EditSegment{0, 0, 0, nil}
181 heap.Add(&head)
182 segment := heap.PopFront()
183 for !(segment.aidx == len(wordA) && segment.bidx == len(wordB)) {
184 if segment.aidx != len(wordA) &&
185 segment.bidx != len(wordB) &&
186 wordA[segment.aidx] == wordB[segment.bidx] {
187 newSegment := EditSegment{segment.weight, segment.aidx + 1, segment.bidx + 1, segment}
188 heap.Add(&newSegment)
189 }
190 if segment.aidx != len(wordA) {
191 newSegment := EditSegment{segment.weight + 1, segment.aidx + 1, segment.bidx, segment}
192 heap.Add(&newSegment)
193 }
194 if segment.bidx != len(wordB) {
195 newSegment := EditSegment{segment.weight + 1, segment.aidx, segment.bidx + 1, segment}
196 heap.Add(&newSegment)
197 }
198 segment = heap.PopFront()
199 }
200 prevSegment := segment.parent
201 edits := make([]Editstring, 0)
202 currentEdit := Editstring{EditNil, ""}
203 for prevSegment != nil {
204 diffA := prevSegment.aidx != segment.aidx
205 diffB := prevSegment.bidx != segment.bidx
206 var et EditType
207 var char string
208 if diffA && diffB {
209 et = EditKeep
210 char = string(wordA[prevSegment.aidx])
211 } else if diffA {
212 et = EditDel
213 char = string(wordA[prevSegment.aidx])
214 } else if diffB {
215 et = EditAdd
216 char = string(wordB[prevSegment.bidx])
217 } else {
218 et = EditNil
219 }
220 if currentEdit.EditType != et {
221 if currentEdit.EditType != EditNil {
222 edits = append([]Editstring{currentEdit}, edits...)
223 }
224 currentEdit = Editstring{et, char}
225 } else {
226 currentEdit.Text = char + currentEdit.Text
227 }
228 segment = prevSegment
229 prevSegment = segment.parent
230 }
231 edits = append([]Editstring{currentEdit}, edits...)
232 return edits
233}