1package diff23import "sort"45// minSimilar is how alike two sheets' cells must be, as the share of6// cells they hold the same, for a sheet gone under one name and a sheet7// come under another to count as one sheet renamed.8const minSimilar = 0.5910// pairing says which sheets of two workbooks are the same sheet: by11// index in a and in b.12type pairing struct {13 pairs [][2]int // matched, in a's order14 onlyA []int // a's sheets without a match: removed15 onlyB []int // b's sheets without a match: added16}1718// matchSheets pairs a's sheets with b's: first by name, ignoring case,19// then each sheet left in a with the most alike left in b, when they20// share at least half their cells (a rename, perhaps with edits).21func matchSheets(a, b *rawBook) pairing {22 var p pairing23 usedB := make([]bool, len(b.sheets))24 var leftA []int25 for i, s := range a.sheets {26 j := b.sheetIndex(s.name)27 if j < 0 || usedB[j] {28 leftA = append(leftA, i)29 continue30 }31 usedB[j] = true32 p.pairs = append(p.pairs, [2]int{i, j})33 }34 type candidate struct {35 i, j int36 score float6437 }38 var cands []candidate39 for _, i := range leftA {40 for j := range b.sheets {41 if !usedB[j] {42 if sc := similarity(a.sheets[i], b.sheets[j]); sc >= minSimilar {43 cands = append(cands, candidate{i, j, sc})44 }45 }46 }47 }48 sort.SliceStable(cands, func(x, y int) bool { return cands[x].score > cands[y].score })49 usedA := map[int]bool{}50 for _, c := range cands {51 if !usedA[c.i] && !usedB[c.j] {52 usedA[c.i], usedB[c.j] = true, true53 p.pairs = append(p.pairs, [2]int{c.i, c.j})54 }55 }56 sort.Slice(p.pairs, func(x, y int) bool { return p.pairs[x][0] < p.pairs[y][0] })57 for _, i := range leftA {58 if !usedA[i] {59 p.onlyA = append(p.onlyA, i)60 }61 }62 for j := range b.sheets {63 if !usedB[j] {64 p.onlyB = append(p.onlyB, j)65 }66 }67 return p68}6970// similarity is the share of cells two sheets hold the same, 1 for two71// empty sheets.72func similarity(a, b *rawSheet) float64 {73 n := max(len(a.cells), len(b.cells))74 if n == 0 {75 return 176 }77 same := 078 for k, v := range a.cells {79 if equal(v, b.cells[k]) {80 same++81 }82 }83 return float64(same) / float64(n)84}8586// sameSheet reports whether two sheets are alike in every field, their87// names included.88func sameSheet(a, b *rawSheet) bool {89 if a.name != b.name || len(a.cells) != len(b.cells) || len(a.fields) != len(b.fields) {90 return false91 }92 for k, v := range a.cells {93 if !equal(v, b.cells[k]) {94 return false95 }96 }97 for k, v := range a.fields {98 if !equal(v, b.fields[k]) {99 return false100 }101 }102 return true103}