Repository Public
1// ORIX Docs2// File: Packages/ORIXDocsKit/Sources/DocReview/SequenceDiff.swift3// Description: Longest common subsequence of two integer sequences: unique-line (patience) anchors, then linear-space Myers with a cost cap.4//5// Author: Simon-Pierre Boucher6// Contact: contact@spboucher.ai7import Foundation89/// LCS over interned symbols. Memory is O(n + m): the Myers search keeps two diagonal vectors and recurses on the middle snake10/// (Myers 1986, section 4b), never a full edit graph.11enum SequenceDiff {12 /// Matched index pairs `(i, j)` with `a[i] == b[j]`, strictly increasing in both coordinates.13 /// - Parameters:14 /// - anchors: first pin the symbols that occur exactly once on each side (patience diff), then run Myers between the pins.15 /// This keeps far-apart identical blocks aligned even when the documents differ a lot.16 /// - maxCost: when a Myers sub-problem needs more than this many edit steps the search stops and the sub-problem is17 /// reported as having nothing in common (the caller pairs its content by similarity instead).18 static func lcs(_ a: [Int], _ b: [Int], anchors: Bool, maxCost: Int = 2048) -> [(Int, Int)] {19 var engine = Engine(a: a, b: b, cap: maxCost)20 var lo = 021 let limit = min(a.count, b.count)22 while lo < limit && a[lo] == b[lo] { engine.out.append((lo, lo)); lo += 1 }23 var suffix = 024 while suffix < limit - lo && a[a.count - 1 - suffix] == b[b.count - 1 - suffix] { suffix += 1 }25 let aHi = a.count - suffix, bHi = b.count - suffix26 if lo < aHi && lo < bHi {27 if anchors {28 var pa = lo, pb = lo29 for (i, j) in uniqueAnchors(a, b, lo, aHi, lo, bHi) {30 engine.diff(pa, i, pb, j)31 engine.out.append((i, j))32 pa = i + 1; pb = j + 133 }34 engine.diff(pa, aHi, pb, bHi)35 } else {36 engine.diff(lo, aHi, lo, bHi)37 }38 }39 for k in 0..<suffix { engine.out.append((aHi + k, bHi + k)) }40 return engine.out41 }4243 /// Symbols occurring exactly once in each range, reduced to the longest chain that is increasing on both sides.44 private static func uniqueAnchors(_ a: [Int], _ b: [Int], _ aLo: Int, _ aHi: Int, _ bLo: Int, _ bHi: Int) -> [(Int, Int)] {45 var countA: [Int: Int] = [:], posB: [Int: Int] = [:], countB: [Int: Int] = [:]46 countA.reserveCapacity(aHi - aLo); countB.reserveCapacity(bHi - bLo)47 for i in aLo..<aHi { countA[a[i], default: 0] += 1 }48 for j in bLo..<bHi { countB[b[j], default: 0] += 1; posB[b[j]] = j }49 var cand: [(Int, Int)] = []50 for i in aLo..<aHi where countA[a[i]] == 1 && countB[a[i]] == 1 { cand.append((i, posB[a[i]]!)) }51 guard !cand.isEmpty else { return [] }52 // Longest increasing subsequence on the b coordinate (patience sorting with back pointers).53 var tails: [Int] = [] // index into cand of the last element of the best chain of each length54 var prev = Array(repeating: -1, count: cand.count)55 for (ci, c) in cand.enumerated() {56 var l = 0, h = tails.count57 while l < h {58 let mid = (l + h) / 259 if cand[tails[mid]].1 < c.1 { l = mid + 1 } else { h = mid }60 }61 if l > 0 { prev[ci] = tails[l - 1] }62 if l == tails.count { tails.append(ci) } else { tails[l] = ci }63 }64 var chain: [(Int, Int)] = []65 var cur = tails.last ?? -166 while cur >= 0 { chain.append(cand[cur]); cur = prev[cur] }67 return chain.reversed()68 }6970 private struct Engine {71 let a: [Int], b: [Int]72 let cap: Int73 var out: [(Int, Int)] = []74 var vf: [Int], vb: [Int]7576 init(a: [Int], b: [Int], cap: Int) {77 self.a = a; self.b = b; self.cap = cap78 let size = a.count + b.count + 879 vf = Array(repeating: -1, count: size)80 vb = Array(repeating: -1, count: size)81 out.reserveCapacity(min(a.count, b.count))82 }8384 mutating func diff(_ aLo0: Int, _ aHi0: Int, _ bLo0: Int, _ bHi0: Int) {85 var aLo = aLo0, bLo = bLo086 while aLo < aHi0 && bLo < bHi0 && a[aLo] == b[bLo] { out.append((aLo, bLo)); aLo += 1; bLo += 1 }87 var suffix = 088 while aLo < aHi0 - suffix && bLo < bHi0 - suffix && a[aHi0 - 1 - suffix] == b[bHi0 - 1 - suffix] { suffix += 1 }89 let aHi = aHi0 - suffix, bHi = bHi0 - suffix90 if aLo < aHi && bLo < bHi, let s = middleSnake(aLo, aHi, bLo, bHi) {91 diff(aLo, s.0, bLo, s.1)92 var k = 093 while s.0 + k < s.2 { out.append((s.0 + k, s.1 + k)); k += 1 }94 diff(s.2, aHi, s.3, bHi)95 }96 for k in 0..<suffix { out.append((aHi + k, bHi + k)) }97 }9899 /// The middle snake of the shortest edit path, as `(x0, y0, x1, y1)` in absolute coordinates; nil when the cost cap is hit.100 /// Points outside the grid are marked unreachable (-1) so a returned snake always lies inside the sub-problem.101 private mutating func middleSnake(_ aLo: Int, _ aHi: Int, _ bLo: Int, _ bHi: Int) -> (Int, Int, Int, Int)? {102 let n = aHi - aLo, m = bHi - bLo103 let delta = n - m104 let maxD = (n + m + 1) / 2105 let off = maxD + 2106 let odd = delta % 2 != 0107 for d in 0...maxD {108 if d > cap { return nil }109 var k = -d110 while k <= d {111 var x = -1112 if d == 0 { x = 0 } else {113 if k > -d { let p = vf[off + k - 1]; if p >= 0 && p + 1 <= n { x = p + 1 } }114 if k < d { let p = vf[off + k + 1]; if p >= 0 && p - k <= m && p > x { x = p } }115 }116 if x < 0 { vf[off + k] = -1; k += 2; continue }117 var y = x - k118 let x0 = x, y0 = y119 while x < n && y < m && a[aLo + x] == b[bLo + y] { x += 1; y += 1 }120 vf[off + k] = x121 if odd {122 let kb = delta - k123 if kb >= -(d - 1) && kb <= d - 1 {124 let r = vb[off + kb]125 if r >= 0 && x + r >= n { return (aLo + x0, bLo + y0, aLo + x, bLo + y) }126 }127 }128 k += 2129 }130 k = -d131 while k <= d {132 var x = -1133 if d == 0 { x = 0 } else {134 if k > -d { let p = vb[off + k - 1]; if p >= 0 && p + 1 <= n { x = p + 1 } }135 if k < d { let p = vb[off + k + 1]; if p >= 0 && p - k <= m && p > x { x = p } }136 }137 if x < 0 { vb[off + k] = -1; k += 2; continue }138 var y = x - k139 let x0 = x, y0 = y140 while x < n && y < m && a[aHi - 1 - x] == b[bHi - 1 - y] { x += 1; y += 1 }141 vb[off + k] = x142 if !odd {143 let kf = delta - k144 if kf >= -d && kf <= d {145 let f = vf[off + kf]146 if f >= 0 && x + f >= n { return (aHi - x, bHi - y, aHi - x0, bHi - y0) }147 }148 }149 k += 2150 }151 }152 return nil153 }154 }155}156