583
*/
584
private ComputeRecursionPoint(originalStart: number, originalEnd: number, modifiedStart: number, modifiedEnd: number, midOriginalArr: number[], midModifiedArr: number[], quitEarlyArr: boolean[]) {
585
>
let originalIndex = 0, modifiedIndex = 0;
diff.ts
586
>
let diagonalForwardStart = 0, diagonalForwardEnd = 0;
587
>
let diagonalReverseStart = 0, diagonalReverseEnd = 0;
588
>
589
>
// To traverse the edit graph and produce the proper LCS, our actual
590
>
// start position is just outside the given boundary
591
>
originalStart--;
592
>
modifiedStart--;
593
>
594
>
// We set these up to make the compiler happy, but they will
595
>
// be replaced before we return with the actual recursion point
596
>
midOriginalArr[0] = 0;
597
>
midModifiedArr[0] = 0;
598
>
599
>
// Clear out the history
600
>
this.m_forwardHistory = [];
601
>
this.m_reverseHistory = [];
602
>
603
>
// Each cell in the two arrays corresponds to a diagonal in the edit graph.
604
>
// The integer value in the cell represents the originalIndex of the furthest
605
>
// reaching point found so far that ends in that diagonal.
606
>
// The modifiedIndex can be computed mathematically from the originalIndex and the diagonal number.
607
>
const maxDifferences = (originalEnd - originalStart) + (modifiedEnd - modifiedStart);
608
>
const numDiagonals = maxDifferences + 1;
609
>
const forwardPoints = new Int32Array(numDiagonals);
610
>
const reversePoints = new Int32Array(numDiagonals);
611
>
// diagonalForwardBase: Index into forwardPoints of the diagonal which passes through (originalStart, modifiedStart)
612
>
// diagonalReverseBase: Index into reversePoints of the diagonal which passes through (originalEnd, modifiedEnd)
613
>
const diagonalForwardBase = (modifiedEnd - modifiedStart);
614
>
const diagonalReverseBase = (originalEnd - originalStart);
615
>
// diagonalForwardOffset: Geometric offset which allows modifiedIndex to be computed from originalIndex and the
616
>
// diagonal number (relative to diagonalForwardBase)
617
>
// diagonalReverseOffset: Geometric offset which allows modifiedIndex to be computed from originalIndex and the
618
>
// diagonal number (relative to diagonalReverseBase)
619
>
const diagonalForwardOffset = (originalStart - modifiedStart);
620
>
const diagonalReverseOffset = (originalEnd - modifiedEnd);
621
>
622
>
// delta: The difference between the end diagonal and the start diagonal. This is used to relate diagonal numbers
623
>
// relative to the start diagonal with diagonal numbers relative to the end diagonal.
624
>
// The Even/Oddn-ness of this delta is important for determining when we should check for overlap
625
>
const delta = diagonalReverseBase - diagonalForwardBase;
626
>
const deltaIsEven = (delta % 2 === 0);
627
>
628
>
// Here we set up the start and end points as the furthest points found so far
629
>
// in both the forward and reverse directions, respectively
630
>
forwardPoints[diagonalForwardBase] = originalStart;
631
>
reversePoints[diagonalReverseBase] = originalEnd;
632
>
633
>
// Remember if we quit early, and thus need to do a best-effort result instead of a real result.
634
>
quitEarlyArr[0] = false;
635
>
636
>
637
>
638
>
// A couple of points:
639
>
// --With this method, we iterate on the number of differences between the two sequences.
640
>
// The more differences there actually are, the longer this will take.
641
>
// --Also, as the number of differences increases, we have to search on diagonals further
642
>
// away from the reference diagonal (which is diagonalForwardBase for forward, diagonalReverseBase for reverse).
643
>
// --We extend on even diagonals (relative to the reference diagonal) only when numDifferences
644
>
// is even and odd diagonals only when numDifferences is odd.
645
>
for (let numDifferences = 1; numDifferences <= (maxDifferences / 2) + 1; numDifferences++) {
646
>
let furthestOriginalIndex = 0;
647
>
let furthestModifiedIndex = 0;
648
>
649
>
// Run the algorithm in the forward direction
650
>
diagonalForwardStart = this.ClipDiagonalBound(diagonalForwardBase - numDifferences, numDifferences, diagonalForwardBase, numDiagonals);
651
>
diagonalForwardEnd = this.ClipDiagonalBound(diagonalForwardBase + numDifferences, numDifferences, diagonalForwardBase, numDiagonals);
652
>
for (let diagonal = diagonalForwardStart; diagonal <= diagonalForwardEnd; diagonal += 2) {
653
>
// STEP 1: We extend the furthest reaching point in the present diagonal
654
>
// by looking at the diagonals above and below and picking the one whose point
655
>
// is further away from the start point (originalStart, modifiedStart)
656
>
if (diagonal === diagonalForwardStart || (diagonal < diagonalForwardEnd && forwardPoints[diagonal - 1] < forwardPoints[diagonal + 1])) {
657
>
originalIndex = forwardPoints[diagonal + 1];
658
>
} else {
659
>
originalIndex = forwardPoints[diagonal - 1] + 1;
660
>
}
661
>
modifiedIndex = originalIndex - (diagonal - diagonalForwardBase) - diagonalForwardOffset;
662
>
663
>
// Save the current originalIndex so we can test for false overlap in step 3
664
>
const tempOriginalIndex = originalIndex;
665
>
666
>
// STEP 2: We can continue to extend the furthest reaching point in the present diagonal
667
>
// so long as the elements are equal.
668
>
while (originalIndex < originalEnd && modifiedIndex < modifiedEnd && this.ElementsAreEqual(originalIndex + 1, modifiedIndex + 1)) {
669
originalIndex++;
670
modifiedIndex++;
671
}
672
>
forwardPoints[diagonal] = originalIndex;
diff.ts
673
>
674
>
if (originalIndex + modifiedIndex > furthestOriginalIndex + furthestModifiedIndex) {
675
furthestOriginalIndex = originalIndex;
676
furthestModifiedIndex = modifiedIndex;
677
}
679
>
// STEP 3: If delta is odd (overlap first happens on forward when delta is odd)
680
>
// and diagonal is in the range of reverse diagonals computed for numDifferences-1
681
>
// (the previous iteration; we haven't computed reverse diagonals for numDifferences yet)
682
>
// then check for overlap.
683
>
if (!deltaIsEven && Math.abs(diagonal - diagonalReverseBase) <= (numDifferences - 1)) {
684
if (originalIndex >= reversePoints[diagonal]) {
685
midOriginalArr[0] = originalIndex;