14
export class DynamicProgrammingDiffing implements IDiffAlgorithm {
15
compute(sequence1: ISequence, sequence2: ISequence, timeout: ITimeout = InfiniteTimeout.instance, equalityScore?: (offset1: number, offset2: number) => number): DiffAlgorithmResult {
17
return DiffAlgorithmResult.trivial(sequence1, sequence2);
18
}
20
>
/**
21
>
* lcsLengths.get(i, j): Length of the longest common subsequence of sequence1.substring(0, i + 1) and sequence2.substring(0, j + 1).
22
>
*/
23
>
const lcsLengths = new Array2D<number>(sequence1.length, sequence2.length);
24
>
const directions = new Array2D<number>(sequence1.length, sequence2.length);
25
>
const lengths = new Array2D<number>(sequence1.length, sequence2.length);
26
>
27
>
// ==== Initializing lcsLengths ====
28
>
for (let s1 = 0; s1 < sequence1.length; s1++) {
29
>
for (let s2 = 0; s2 < sequence2.length; s2++) {
30
>
if (!timeout.isValid()) {
31
return DiffAlgorithmResult.trivialTimedOut(sequence1, sequence2);
32
}
34
>
const horizontalLen = s1 === 0 ? 0 : lcsLengths.get(s1 - 1, s2);
35
>
const verticalLen = s2 === 0 ? 0 : lcsLengths.get(s1, s2 - 1);
36
>
37
>
let extendedSeqScore: number;
38
>
if (sequence1.getElement(s1) === sequence2.getElement(s2)) {
39
>
if (s1 === 0 || s2 === 0) {
40
>
extendedSeqScore = 0;
41
>
} else {
42
>
extendedSeqScore = lcsLengths.get(s1 - 1, s2 - 1);
43
>
}
44
>
if (s1 > 0 && s2 > 0 && directions.get(s1 - 1, s2 - 1) === 3) {
45
>
// Prefer consecutive diagonals
46
>
extendedSeqScore += lengths.get(s1 - 1, s2 - 1);
47
>
}
48
>
extendedSeqScore += (equalityScore ? equalityScore(s1, s2) : 1);
49
>
} else {
50
>
extendedSeqScore = -1;
51
>
}
52
>
53
>
const newValue = Math.max(horizontalLen, verticalLen, extendedSeqScore);
54
>
55
>
if (newValue === extendedSeqScore) {
56
>
// Prefer diagonals
57
>
const prevLen = s1 > 0 && s2 > 0 ? lengths.get(s1 - 1, s2 - 1) : 0;
58
>
lengths.set(s1, s2, prevLen + 1);
59
>
directions.set(s1, s2, 3);
60
>
} else if (newValue === horizontalLen) {
61
>
lengths.set(s1, s2, 0);
62
>
directions.set(s1, s2, 1);
63
>
} else if (newValue === verticalLen) {
64
lengths.set(s1, s2, 0);
65
directions.set(s1, s2, 2);
66
}
68
>
lcsLengths.set(s1, s2, newValue);
69
>
}
70
>
}
71
>
72
>
// ==== Backtracking ====
73
>
const result: SequenceDiff[] = [];
74
>
let lastAligningPosS1: number = sequence1.length;
75
>
let lastAligningPosS2: number = sequence2.length;
76
>
77
>
function reportDecreasingAligningPositions(s1: number, s2: number): void {
78
>
if (s1 + 1 !== lastAligningPosS1 || s2 + 1 !== lastAligningPosS2) {
79
result.push(new SequenceDiff(
80
new OffsetRange(s1 + 1, lastAligningPosS1),