Something went wrong. Try again.
xcvr tui
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234package main
import ()
type EditType = int
const ( EditAdd EditType = iota EditKeep EditDel EditNil)
type Edit struct { EditType EditType Utf16Text []uint16}
type Editstring struct { EditType EditType Text string}
type EditSegment struct { weight int aidx int bidx int parent *EditSegment}
type coordinate struct { a int b int}
type SegmentHeap struct { segments []*EditSegment searched map[coordinate]bool}
func NewSegmentHeap() SegmentHeap { segments := make([]*EditSegment, 0, 10) searched := make(map[coordinate]bool) return SegmentHeap{segments, searched}}
func (h *SegmentHeap) Add(seg *EditSegment) { searched := h.searched[coordinate{seg.aidx, seg.bidx}] if searched { return } h.segments = append(h.segments, seg) h.searched[coordinate{seg.aidx, seg.bidx}] = true h.siftUp(len(h.segments) - 1)}
func (h *SegmentHeap) PopFront() *EditSegment { if len(h.segments) == 0 { return nil } front := h.segments[0] if len(h.segments) == 1 { h.segments = nil return front } h.segments[0] = h.segments[len(h.segments)-1] h.segments = h.segments[:len(h.segments)-1] h.siftDown(0) return front}
func (h *SegmentHeap) siftUp(idx int) { if idx == 0 { return } loweridx := idx upperidx := (idx - 1) / 2 lower := h.segments[loweridx] upper := h.segments[upperidx] if lower.lighter(upper) { h.segments[upperidx] = lower h.segments[loweridx] = upper h.siftUp(upperidx) }}
func (h *SegmentHeap) siftDown(idx int) { upperidx := idx var swap *EditSegment loweridx := idx*2 + 1 lower2idx := idx*2 + 2 if loweridx < len(h.segments) && h.segments[loweridx].lighter(h.segments[upperidx]) { swap = h.segments[upperidx] h.segments[upperidx] = h.segments[loweridx] h.segments[loweridx] = swap h.siftDown(loweridx) return } if lower2idx < len(h.segments) && h.segments[lower2idx].lighter(h.segments[upperidx]) { swap = h.segments[upperidx] h.segments[upperidx] = h.segments[lower2idx] h.segments[lower2idx] = swap h.siftDown(lower2idx) return }
}
func (seg *EditSegment) lighter(A *EditSegment) bool { if seg.weight < A.weight { return true } else if seg.weight > A.weight { return false } else { return seg.aidx+seg.bidx > A.aidx+A.bidx }}
// Diff calculates the diff between wordA and wordB as a miniaml slice of// edits that you have to make to wordA so that you end up with wordBfunc Diff(wordA []uint16, wordB []uint16) []Edit { heap := NewSegmentHeap() head := EditSegment{0, 0, 0, nil} heap.Add(&head) segment := heap.PopFront() for !(segment.aidx == len(wordA) && segment.bidx == len(wordB)) { if segment.aidx != len(wordA) && segment.bidx != len(wordB) && wordA[segment.aidx] == wordB[segment.bidx] { newSegment := EditSegment{segment.weight, segment.aidx + 1, segment.bidx + 1, segment} heap.Add(&newSegment) } if segment.aidx != len(wordA) { newSegment := EditSegment{segment.weight + 1, segment.aidx + 1, segment.bidx, segment} heap.Add(&newSegment) } if segment.bidx != len(wordB) { newSegment := EditSegment{segment.weight + 1, segment.aidx, segment.bidx + 1, segment} heap.Add(&newSegment) } segment = heap.PopFront() } prevSegment := segment.parent edits := make([]Edit, 0) currentEdit := Edit{EditNil, nil} for prevSegment != nil { diffA := prevSegment.aidx != segment.aidx diffB := prevSegment.bidx != segment.bidx var et EditType var char uint16 if diffA && diffB { et = EditKeep char = wordA[prevSegment.aidx] } else if diffA { et = EditDel char = wordA[prevSegment.aidx] } else if diffB { et = EditAdd char = wordB[prevSegment.bidx] } else { et = EditNil } if currentEdit.EditType != et { if currentEdit.EditType != EditNil { edits = append([]Edit{currentEdit}, edits...) } currentEdit = Edit{et, []uint16{char}} } else { currentEdit.Utf16Text = append([]uint16{char}, currentEdit.Utf16Text...) } segment = prevSegment prevSegment = segment.parent } edits = append([]Edit{currentEdit}, edits...) return edits}
func Diffs(wordA string, wordB string) []Editstring { heap := NewSegmentHeap() head := EditSegment{0, 0, 0, nil} heap.Add(&head) segment := heap.PopFront() for !(segment.aidx == len(wordA) && segment.bidx == len(wordB)) { if segment.aidx != len(wordA) && segment.bidx != len(wordB) && wordA[segment.aidx] == wordB[segment.bidx] { newSegment := EditSegment{segment.weight, segment.aidx + 1, segment.bidx + 1, segment} heap.Add(&newSegment) } if segment.aidx != len(wordA) { newSegment := EditSegment{segment.weight + 1, segment.aidx + 1, segment.bidx, segment} heap.Add(&newSegment) } if segment.bidx != len(wordB) { newSegment := EditSegment{segment.weight + 1, segment.aidx, segment.bidx + 1, segment} heap.Add(&newSegment) } segment = heap.PopFront() } prevSegment := segment.parent edits := make([]Editstring, 0) currentEdit := Editstring{EditNil, ""} for prevSegment != nil { diffA := prevSegment.aidx != segment.aidx diffB := prevSegment.bidx != segment.bidx var et EditType var char string if diffA && diffB { et = EditKeep char = string(wordA[prevSegment.aidx]) } else if diffA { et = EditDel char = string(wordA[prevSegment.aidx]) } else if diffB { et = EditAdd char = string(wordB[prevSegment.bidx]) } else { et = EditNil } if currentEdit.EditType != et { if currentEdit.EditType != EditNil { edits = append([]Editstring{currentEdit}, edits...) } currentEdit = Editstring{et, char} } else { currentEdit.Text = char + currentEdit.Text } segment = prevSegment prevSegment = segment.parent } edits = append([]Editstring{currentEdit}, edits...) return edits}