1  'use strict';
  2  
  3  Object.defineProperty(exports, '__esModule', {
  4    value: true
  5  });
  6  exports.default = void 0;
  7  
  8  /**
  9   * Copyright (c) Facebook, Inc. and its affiliates. All Rights Reserved.
 10   *
 11   * This source code is licensed under the MIT license found in the
 12   * LICENSE file in the root directory of this source tree.
 13   *
 14   */
 15  // This diff-sequences package implements the linear space variation in
 16  // An O(ND) Difference Algorithm and Its Variations by Eugene W. Myers
 17  // Relationship in notation between Myers paper and this package:
 18  // A is a
 19  // N is aLength, aEnd - aStart, and so on
 20  // x is aIndex, aFirst, aLast, and so on
 21  // B is b
 22  // M is bLength, bEnd - bStart, and so on
 23  // y is bIndex, bFirst, bLast, and so on
 24  // Δ = N - M is negative of baDeltaLength = bLength - aLength
 25  // D is d
 26  // k is kF
 27  // k + Δ is kF = kR - baDeltaLength
 28  // V is aIndexesF or aIndexesR (see comment below about Indexes type)
 29  // index intervals [1, N] and [1, M] are [0, aLength) and [0, bLength)
 30  // starting point in forward direction (0, 0) is (-1, -1)
 31  // starting point in reverse direction (N + 1, M + 1) is (aLength, bLength)
 32  // The “edit graph” for sequences a and b corresponds to items:
 33  // in a on the horizontal axis
 34  // in b on the vertical axis
 35  //
 36  // Given a-coordinate of a point in a diagonal, you can compute b-coordinate.
 37  //
 38  // Forward diagonals kF:
 39  // zero diagonal intersects top left corner
 40  // positive diagonals intersect top edge
 41  // negative diagonals insersect left edge
 42  //
 43  // Reverse diagonals kR:
 44  // zero diagonal intersects bottom right corner
 45  // positive diagonals intersect right edge
 46  // negative diagonals intersect bottom edge
 47  // The graph contains a directed acyclic graph of edges:
 48  // horizontal: delete an item from a
 49  // vertical: insert an item from b
 50  // diagonal: common item in a and b
 51  //
 52  // The algorithm solves dual problems in the graph analogy:
 53  // Find longest common subsequence: path with maximum number of diagonal edges
 54  // Find shortest edit script: path with minimum number of non-diagonal edges
 55  // Input callback function compares items at indexes in the sequences.
 56  // Output callback function receives the number of adjacent items
 57  // and starting indexes of each common subsequence.
 58  // Either original functions or wrapped to swap indexes if graph is transposed.
 59  // Indexes in sequence a of last point of forward or reverse paths in graph.
 60  // Myers algorithm indexes by diagonal k which for negative is bad deopt in V8.
 61  // This package indexes by iF and iR which are greater than or equal to zero.
 62  // and also updates the index arrays in place to cut memory in half.
 63  // kF = 2 * iF - d
 64  // kR = d - 2 * iR
 65  // Division of index intervals in sequences a and b at the middle change.
 66  // Invariant: intervals do not have common items at the start or end.
 67  const pkg = 'diff-sequences'; // for error messages
 68  
 69  const NOT_YET_SET = 0; // small int instead of undefined to avoid deopt in V8
 70  // Return the number of common items that follow in forward direction.
 71  // The length of what Myers paper calls a “snake” in a forward path.
 72  
 73  const countCommonItemsF = (aIndex, aEnd, bIndex, bEnd, isCommon) => {
 74    let nCommon = 0;
 75  
 76    while (aIndex < aEnd && bIndex < bEnd && isCommon(aIndex, bIndex)) {
 77      aIndex += 1;
 78      bIndex += 1;
 79      nCommon += 1;
 80    }
 81  
 82    return nCommon;
 83  }; // Return the number of common items that precede in reverse direction.
 84  // The length of what Myers paper calls a “snake” in a reverse path.
 85  
 86  const countCommonItemsR = (aStart, aIndex, bStart, bIndex, isCommon) => {
 87    let nCommon = 0;
 88  
 89    while (aStart <= aIndex && bStart <= bIndex && isCommon(aIndex, bIndex)) {
 90      aIndex -= 1;
 91      bIndex -= 1;
 92      nCommon += 1;
 93    }
 94  
 95    return nCommon;
 96  }; // A simple function to extend forward paths from (d - 1) to d changes
 97  // when forward and reverse paths cannot yet overlap.
 98  
 99  const extendPathsF = (d, aEnd, bEnd, bF, isCommon, aIndexesF, iMaxF) => {
100    // Unroll the first iteration.
101    let iF = 0;
102    let kF = -d; // kF = 2 * iF - d
103  
104    let aFirst = aIndexesF[iF]; // in first iteration always insert
105  
106    let aIndexPrev1 = aFirst; // prev value of [iF - 1] in next iteration
107  
108    aIndexesF[iF] += countCommonItemsF(
109      aFirst + 1,
110      aEnd,
111      bF + aFirst - kF + 1,
112      bEnd,
113      isCommon
114    ); // Optimization: skip diagonals in which paths cannot ever overlap.
115  
116    const nF = d < iMaxF ? d : iMaxF; // The diagonals kF are odd when d is odd and even when d is even.
117  
118    for (iF += 1, kF += 2; iF <= nF; iF += 1, kF += 2) {
119      // To get first point of path segment, move one change in forward direction
120      // from last point of previous path segment in an adjacent diagonal.
121      // In last possible iteration when iF === d and kF === d always delete.
122      if (iF !== d && aIndexPrev1 < aIndexesF[iF]) {
123        aFirst = aIndexesF[iF]; // vertical to insert from b
124      } else {
125        aFirst = aIndexPrev1 + 1; // horizontal to delete from a
126  
127        if (aEnd <= aFirst) {
128          // Optimization: delete moved past right of graph.
129          return iF - 1;
130        }
131      } // To get last point of path segment, move along diagonal of common items.
132  
133      aIndexPrev1 = aIndexesF[iF];
134      aIndexesF[iF] =
135        aFirst +
136        countCommonItemsF(aFirst + 1, aEnd, bF + aFirst - kF + 1, bEnd, isCommon);
137    }
138  
139    return iMaxF;
140  }; // A simple function to extend reverse paths from (d - 1) to d changes
141  // when reverse and forward paths cannot yet overlap.
142  
143  const extendPathsR = (d, aStart, bStart, bR, isCommon, aIndexesR, iMaxR) => {
144    // Unroll the first iteration.
145    let iR = 0;
146    let kR = d; // kR = d - 2 * iR
147  
148    let aFirst = aIndexesR[iR]; // in first iteration always insert
149  
150    let aIndexPrev1 = aFirst; // prev value of [iR - 1] in next iteration
151  
152    aIndexesR[iR] -= countCommonItemsR(
153      aStart,
154      aFirst - 1,
155      bStart,
156      bR + aFirst - kR - 1,
157      isCommon
158    ); // Optimization: skip diagonals in which paths cannot ever overlap.
159  
160    const nR = d < iMaxR ? d : iMaxR; // The diagonals kR are odd when d is odd and even when d is even.
161  
162    for (iR += 1, kR -= 2; iR <= nR; iR += 1, kR -= 2) {
163      // To get first point of path segment, move one change in reverse direction
164      // from last point of previous path segment in an adjacent diagonal.
165      // In last possible iteration when iR === d and kR === -d always delete.
166      if (iR !== d && aIndexesR[iR] < aIndexPrev1) {
167        aFirst = aIndexesR[iR]; // vertical to insert from b
168      } else {
169        aFirst = aIndexPrev1 - 1; // horizontal to delete from a
170  
171        if (aFirst < aStart) {
172          // Optimization: delete moved past left of graph.
173          return iR - 1;
174        }
175      } // To get last point of path segment, move along diagonal of common items.
176  
177      aIndexPrev1 = aIndexesR[iR];
178      aIndexesR[iR] =
179        aFirst -
180        countCommonItemsR(
181          aStart,
182          aFirst - 1,
183          bStart,
184          bR + aFirst - kR - 1,
185          isCommon
186        );
187    }
188  
189    return iMaxR;
190  }; // A complete function to extend forward paths from (d - 1) to d changes.
191  // Return true if a path overlaps reverse path of (d - 1) changes in its diagonal.
192  
193  const extendOverlappablePathsF = (
194    d,
195    aStart,
196    aEnd,
197    bStart,
198    bEnd,
199    isCommon,
200    aIndexesF,
201    iMaxF,
202    aIndexesR,
203    iMaxR,
204    division
205  ) => {
206    const bF = bStart - aStart; // bIndex = bF + aIndex - kF
207  
208    const aLength = aEnd - aStart;
209    const bLength = bEnd - bStart;
210    const baDeltaLength = bLength - aLength; // kF = kR - baDeltaLength
211    // Range of diagonals in which forward and reverse paths might overlap.
212  
213    const kMinOverlapF = -baDeltaLength - (d - 1); // -(d - 1) <= kR
214  
215    const kMaxOverlapF = -baDeltaLength + (d - 1); // kR <= (d - 1)
216  
217    let aIndexPrev1 = NOT_YET_SET; // prev value of [iF - 1] in next iteration
218    // Optimization: skip diagonals in which paths cannot ever overlap.
219  
220    const nF = d < iMaxF ? d : iMaxF; // The diagonals kF = 2 * iF - d are odd when d is odd and even when d is even.
221  
222    for (let iF = 0, kF = -d; iF <= nF; iF += 1, kF += 2) {
223      // To get first point of path segment, move one change in forward direction
224      // from last point of previous path segment in an adjacent diagonal.
225      // In first iteration when iF === 0 and kF === -d always insert.
226      // In last possible iteration when iF === d and kF === d always delete.
227      const insert = iF === 0 || (iF !== d && aIndexPrev1 < aIndexesF[iF]);
228      const aLastPrev = insert ? aIndexesF[iF] : aIndexPrev1;
229      const aFirst = insert
230        ? aLastPrev // vertical to insert from b
231        : aLastPrev + 1; // horizontal to delete from a
232      // To get last point of path segment, move along diagonal of common items.
233  
234      const bFirst = bF + aFirst - kF;
235      const nCommonF = countCommonItemsF(
236        aFirst + 1,
237        aEnd,
238        bFirst + 1,
239        bEnd,
240        isCommon
241      );
242      const aLast = aFirst + nCommonF;
243      aIndexPrev1 = aIndexesF[iF];
244      aIndexesF[iF] = aLast;
245  
246      if (kMinOverlapF <= kF && kF <= kMaxOverlapF) {
247        // Solve for iR of reverse path with (d - 1) changes in diagonal kF:
248        // kR = kF + baDeltaLength
249        // kR = (d - 1) - 2 * iR
250        const iR = (d - 1 - (kF + baDeltaLength)) / 2; // If this forward path overlaps the reverse path in this diagonal,
251        // then this is the middle change of the index intervals.
252  
253        if (iR <= iMaxR && aIndexesR[iR] - 1 <= aLast) {
254          // Unlike the Myers algorithm which finds only the middle “snake”
255          // this package can find two common subsequences per division.
256          // Last point of previous path segment is on an adjacent diagonal.
257          const bLastPrev = bF + aLastPrev - (insert ? kF + 1 : kF - 1); // Because of invariant that intervals preceding the middle change
258          // cannot have common items at the end,
259          // move in reverse direction along a diagonal of common items.
260  
261          const nCommonR = countCommonItemsR(
262            aStart,
263            aLastPrev,
264            bStart,
265            bLastPrev,
266            isCommon
267          );
268          const aIndexPrevFirst = aLastPrev - nCommonR;
269          const bIndexPrevFirst = bLastPrev - nCommonR;
270          const aEndPreceding = aIndexPrevFirst + 1;
271          const bEndPreceding = bIndexPrevFirst + 1;
272          division.nChangePreceding = d - 1;
273  
274          if (d - 1 === aEndPreceding + bEndPreceding - aStart - bStart) {
275            // Optimization: number of preceding changes in forward direction
276            // is equal to number of items in preceding interval,
277            // therefore it cannot contain any common items.
278            division.aEndPreceding = aStart;
279            division.bEndPreceding = bStart;
280          } else {
281            division.aEndPreceding = aEndPreceding;
282            division.bEndPreceding = bEndPreceding;
283          }
284  
285          division.nCommonPreceding = nCommonR;
286  
287          if (nCommonR !== 0) {
288            division.aCommonPreceding = aEndPreceding;
289            division.bCommonPreceding = bEndPreceding;
290          }
291  
292          division.nCommonFollowing = nCommonF;
293  
294          if (nCommonF !== 0) {
295            division.aCommonFollowing = aFirst + 1;
296            division.bCommonFollowing = bFirst + 1;
297          }
298  
299          const aStartFollowing = aLast + 1;
300          const bStartFollowing = bFirst + nCommonF + 1;
301          division.nChangeFollowing = d - 1;
302  
303          if (d - 1 === aEnd + bEnd - aStartFollowing - bStartFollowing) {
304            // Optimization: number of changes in reverse direction
305            // is equal to number of items in following interval,
306            // therefore it cannot contain any common items.
307            division.aStartFollowing = aEnd;
308            division.bStartFollowing = bEnd;
309          } else {
310            division.aStartFollowing = aStartFollowing;
311            division.bStartFollowing = bStartFollowing;
312          }
313  
314          return true;
315        }
316      }
317    }
318  
319    return false;
320  }; // A complete function to extend reverse paths from (d - 1) to d changes.
321  // Return true if a path overlaps forward path of d changes in its diagonal.
322  
323  const extendOverlappablePathsR = (
324    d,
325    aStart,
326    aEnd,
327    bStart,
328    bEnd,
329    isCommon,
330    aIndexesF,
331    iMaxF,
332    aIndexesR,
333    iMaxR,
334    division
335  ) => {
336    const bR = bEnd - aEnd; // bIndex = bR + aIndex - kR
337  
338    const aLength = aEnd - aStart;
339    const bLength = bEnd - bStart;
340    const baDeltaLength = bLength - aLength; // kR = kF + baDeltaLength
341    // Range of diagonals in which forward and reverse paths might overlap.
342  
343    const kMinOverlapR = baDeltaLength - d; // -d <= kF
344  
345    const kMaxOverlapR = baDeltaLength + d; // kF <= d
346  
347    let aIndexPrev1 = NOT_YET_SET; // prev value of [iR - 1] in next iteration
348    // Optimization: skip diagonals in which paths cannot ever overlap.
349  
350    const nR = d < iMaxR ? d : iMaxR; // The diagonals kR = d - 2 * iR are odd when d is odd and even when d is even.
351  
352    for (let iR = 0, kR = d; iR <= nR; iR += 1, kR -= 2) {
353      // To get first point of path segment, move one change in reverse direction
354      // from last point of previous path segment in an adjacent diagonal.
355      // In first iteration when iR === 0 and kR === d always insert.
356      // In last possible iteration when iR === d and kR === -d always delete.
357      const insert = iR === 0 || (iR !== d && aIndexesR[iR] < aIndexPrev1);
358      const aLastPrev = insert ? aIndexesR[iR] : aIndexPrev1;
359      const aFirst = insert
360        ? aLastPrev // vertical to insert from b
361        : aLastPrev - 1; // horizontal to delete from a
362      // To get last point of path segment, move along diagonal of common items.
363  
364      const bFirst = bR + aFirst - kR;
365      const nCommonR = countCommonItemsR(
366        aStart,
367        aFirst - 1,
368        bStart,
369        bFirst - 1,
370        isCommon
371      );
372      const aLast = aFirst - nCommonR;
373      aIndexPrev1 = aIndexesR[iR];
374      aIndexesR[iR] = aLast;
375  
376      if (kMinOverlapR <= kR && kR <= kMaxOverlapR) {
377        // Solve for iF of forward path with d changes in diagonal kR:
378        // kF = kR - baDeltaLength
379        // kF = 2 * iF - d
380        const iF = (d + (kR - baDeltaLength)) / 2; // If this reverse path overlaps the forward path in this diagonal,
381        // then this is a middle change of the index intervals.
382  
383        if (iF <= iMaxF && aLast - 1 <= aIndexesF[iF]) {
384          const bLast = bFirst - nCommonR;
385          division.nChangePreceding = d;
386  
387          if (d === aLast + bLast - aStart - bStart) {
388            // Optimization: number of changes in reverse direction
389            // is equal to number of items in preceding interval,
390            // therefore it cannot contain any common items.
391            division.aEndPreceding = aStart;
392            division.bEndPreceding = bStart;
393          } else {
394            division.aEndPreceding = aLast;
395            division.bEndPreceding = bLast;
396          }
397  
398          division.nCommonPreceding = nCommonR;
399  
400          if (nCommonR !== 0) {
401            // The last point of reverse path segment is start of common subsequence.
402            division.aCommonPreceding = aLast;
403            division.bCommonPreceding = bLast;
404          }
405  
406          division.nChangeFollowing = d - 1;
407  
408          if (d === 1) {
409            // There is no previous path segment.
410            division.nCommonFollowing = 0;
411            division.aStartFollowing = aEnd;
412            division.bStartFollowing = bEnd;
413          } else {
414            // Unlike the Myers algorithm which finds only the middle “snake”
415            // this package can find two common subsequences per division.
416            // Last point of previous path segment is on an adjacent diagonal.
417            const bLastPrev = bR + aLastPrev - (insert ? kR - 1 : kR + 1); // Because of invariant that intervals following the middle change
418            // cannot have common items at the start,
419            // move in forward direction along a diagonal of common items.
420  
421            const nCommonF = countCommonItemsF(
422              aLastPrev,
423              aEnd,
424              bLastPrev,
425              bEnd,
426              isCommon
427            );
428            division.nCommonFollowing = nCommonF;
429  
430            if (nCommonF !== 0) {
431              // The last point of reverse path segment is start of common subsequence.
432              division.aCommonFollowing = aLastPrev;
433              division.bCommonFollowing = bLastPrev;
434            }
435  
436            const aStartFollowing = aLastPrev + nCommonF; // aFirstPrev
437  
438            const bStartFollowing = bLastPrev + nCommonF; // bFirstPrev
439  
440            if (d - 1 === aEnd + bEnd - aStartFollowing - bStartFollowing) {
441              // Optimization: number of changes in forward direction
442              // is equal to number of items in following interval,
443              // therefore it cannot contain any common items.
444              division.aStartFollowing = aEnd;
445              division.bStartFollowing = bEnd;
446            } else {
447              division.aStartFollowing = aStartFollowing;
448              division.bStartFollowing = bStartFollowing;
449            }
450          }
451  
452          return true;
453        }
454      }
455    }
456  
457    return false;
458  }; // Given index intervals and input function to compare items at indexes,
459  // divide at the middle change.
460  //
461  // DO NOT CALL if start === end, because interval cannot contain common items
462  // and because this function will throw the “no overlap” error.
463  
464  const divide = (
465    nChange,
466    aStart,
467    aEnd,
468    bStart,
469    bEnd,
470    isCommon,
471    aIndexesF,
472    aIndexesR,
473    division // output
474  ) => {
475    const bF = bStart - aStart; // bIndex = bF + aIndex - kF
476  
477    const bR = bEnd - aEnd; // bIndex = bR + aIndex - kR
478  
479    const aLength = aEnd - aStart;
480    const bLength = bEnd - bStart; // Because graph has square or portrait orientation,
481    // length difference is minimum number of items to insert from b.
482    // Corresponding forward and reverse diagonals in graph
483    // depend on length difference of the sequences:
484    // kF = kR - baDeltaLength
485    // kR = kF + baDeltaLength
486  
487    const baDeltaLength = bLength - aLength; // Optimization: max diagonal in graph intersects corner of shorter side.
488  
489    let iMaxF = aLength;
490    let iMaxR = aLength; // Initialize no changes yet in forward or reverse direction:
491  
492    aIndexesF[0] = aStart - 1; // at open start of interval, outside closed start
493  
494    aIndexesR[0] = aEnd; // at open end of interval
495  
496    if (baDeltaLength % 2 === 0) {
497      // The number of changes in paths is 2 * d if length difference is even.
498      const dMin = (nChange || baDeltaLength) / 2;
499      const dMax = (aLength + bLength) / 2;
500  
501      for (let d = 1; d <= dMax; d += 1) {
502        iMaxF = extendPathsF(d, aEnd, bEnd, bF, isCommon, aIndexesF, iMaxF);
503  
504        if (d < dMin) {
505          iMaxR = extendPathsR(d, aStart, bStart, bR, isCommon, aIndexesR, iMaxR);
506        } else if (
507          // If a reverse path overlaps a forward path in the same diagonal,
508          // return a division of the index intervals at the middle change.
509          extendOverlappablePathsR(
510            d,
511            aStart,
512            aEnd,
513            bStart,
514            bEnd,
515            isCommon,
516            aIndexesF,
517            iMaxF,
518            aIndexesR,
519            iMaxR,
520            division
521          )
522        ) {
523          return;
524        }
525      }
526    } else {
527      // The number of changes in paths is 2 * d - 1 if length difference is odd.
528      const dMin = ((nChange || baDeltaLength) + 1) / 2;
529      const dMax = (aLength + bLength + 1) / 2; // Unroll first half iteration so loop extends the relevant pairs of paths.
530      // Because of invariant that intervals have no common items at start or end,
531      // and limitation not to call divide with empty intervals,
532      // therefore it cannot be called if a forward path with one change
533      // would overlap a reverse path with no changes, even if dMin === 1.
534  
535      let d = 1;
536      iMaxF = extendPathsF(d, aEnd, bEnd, bF, isCommon, aIndexesF, iMaxF);
537  
538      for (d += 1; d <= dMax; d += 1) {
539        iMaxR = extendPathsR(
540          d - 1,
541          aStart,
542          bStart,
543          bR,
544          isCommon,
545          aIndexesR,
546          iMaxR
547        );
548  
549        if (d < dMin) {
550          iMaxF = extendPathsF(d, aEnd, bEnd, bF, isCommon, aIndexesF, iMaxF);
551        } else if (
552          // If a forward path overlaps a reverse path in the same diagonal,
553          // return a division of the index intervals at the middle change.
554          extendOverlappablePathsF(
555            d,
556            aStart,
557            aEnd,
558            bStart,
559            bEnd,
560            isCommon,
561            aIndexesF,
562            iMaxF,
563            aIndexesR,
564            iMaxR,
565            division
566          )
567        ) {
568          return;
569        }
570      }
571    }
572    /* istanbul ignore next */
573  
574    throw new Error(
575      `${pkg}: no overlap aStart=${aStart} aEnd=${aEnd} bStart=${bStart} bEnd=${bEnd}`
576    );
577  }; // Given index intervals and input function to compare items at indexes,
578  // return by output function the number of adjacent items and starting indexes
579  // of each common subsequence. Divide and conquer with only linear space.
580  //
581  // The index intervals are half open [start, end) like array slice method.
582  // DO NOT CALL if start === end, because interval cannot contain common items
583  // and because divide function will throw the “no overlap” error.
584  
585  const findSubsequences = (
586    nChange,
587    aStart,
588    aEnd,
589    bStart,
590    bEnd,
591    transposed,
592    callbacks,
593    aIndexesF,
594    aIndexesR,
595    division // temporary memory, not input nor output
596  ) => {
597    if (bEnd - bStart < aEnd - aStart) {
598      // Transpose graph so it has portrait instead of landscape orientation.
599      // Always compare shorter to longer sequence for consistency and optimization.
600      transposed = !transposed;
601  
602      if (transposed && callbacks.length === 1) {
603        // Lazily wrap callback functions to swap args if graph is transposed.
604        const {foundSubsequence, isCommon} = callbacks[0];
605        callbacks[1] = {
606          foundSubsequence: (nCommon, bCommon, aCommon) => {
607            foundSubsequence(nCommon, aCommon, bCommon);
608          },
609          isCommon: (bIndex, aIndex) => isCommon(aIndex, bIndex)
610        };
611      }
612  
613      const tStart = aStart;
614      const tEnd = aEnd;
615      aStart = bStart;
616      aEnd = bEnd;
617      bStart = tStart;
618      bEnd = tEnd;
619    }
620  
621    const {foundSubsequence, isCommon} = callbacks[transposed ? 1 : 0]; // Divide the index intervals at the middle change.
622  
623    divide(
624      nChange,
625      aStart,
626      aEnd,
627      bStart,
628      bEnd,
629      isCommon,
630      aIndexesF,
631      aIndexesR,
632      division
633    );
634    const {
635      nChangePreceding,
636      aEndPreceding,
637      bEndPreceding,
638      nCommonPreceding,
639      aCommonPreceding,
640      bCommonPreceding,
641      nCommonFollowing,
642      aCommonFollowing,
643      bCommonFollowing,
644      nChangeFollowing,
645      aStartFollowing,
646      bStartFollowing
647    } = division; // Unless either index interval is empty, they might contain common items.
648  
649    if (aStart < aEndPreceding && bStart < bEndPreceding) {
650      // Recursely find and return common subsequences preceding the division.
651      findSubsequences(
652        nChangePreceding,
653        aStart,
654        aEndPreceding,
655        bStart,
656        bEndPreceding,
657        transposed,
658        callbacks,
659        aIndexesF,
660        aIndexesR,
661        division
662      );
663    } // Return common subsequences that are adjacent to the middle change.
664  
665    if (nCommonPreceding !== 0) {
666      foundSubsequence(nCommonPreceding, aCommonPreceding, bCommonPreceding);
667    }
668  
669    if (nCommonFollowing !== 0) {
670      foundSubsequence(nCommonFollowing, aCommonFollowing, bCommonFollowing);
671    } // Unless either index interval is empty, they might contain common items.
672  
673    if (aStartFollowing < aEnd && bStartFollowing < bEnd) {
674      // Recursely find and return common subsequences following the division.
675      findSubsequences(
676        nChangeFollowing,
677        aStartFollowing,
678        aEnd,
679        bStartFollowing,
680        bEnd,
681        transposed,
682        callbacks,
683        aIndexesF,
684        aIndexesR,
685        division
686      );
687    }
688  };
689  
690  const validateLength = (name, arg) => {
691    if (typeof arg !== 'number') {
692      throw new TypeError(`${pkg}: ${name} typeof ${typeof arg} is not a number`);
693    }
694  
695    if (!Number.isSafeInteger(arg)) {
696      throw new RangeError(`${pkg}: ${name} value ${arg} is not a safe integer`);
697    }
698  
699    if (arg < 0) {
700      throw new RangeError(`${pkg}: ${name} value ${arg} is a negative integer`);
701    }
702  };
703  
704  const validateCallback = (name, arg) => {
705    const type = typeof arg;
706  
707    if (type !== 'function') {
708      throw new TypeError(`${pkg}: ${name} typeof ${type} is not a function`);
709    }
710  }; // Compare items in two sequences to find a longest common subsequence.
711  // Given lengths of sequences and input function to compare items at indexes,
712  // return by output function the number of adjacent items and starting indexes
713  // of each common subsequence.
714  
715  var _default = (aLength, bLength, isCommon, foundSubsequence) => {
716    validateLength('aLength', aLength);
717    validateLength('bLength', bLength);
718    validateCallback('isCommon', isCommon);
719    validateCallback('foundSubsequence', foundSubsequence); // Count common items from the start in the forward direction.
720  
721    const nCommonF = countCommonItemsF(0, aLength, 0, bLength, isCommon);
722  
723    if (nCommonF !== 0) {
724      foundSubsequence(nCommonF, 0, 0);
725    } // Unless both sequences consist of common items only,
726    // find common items in the half-trimmed index intervals.
727  
728    if (aLength !== nCommonF || bLength !== nCommonF) {
729      // Invariant: intervals do not have common items at the start.
730      // The start of an index interval is closed like array slice method.
731      const aStart = nCommonF;
732      const bStart = nCommonF; // Count common items from the end in the reverse direction.
733  
734      const nCommonR = countCommonItemsR(
735        aStart,
736        aLength - 1,
737        bStart,
738        bLength - 1,
739        isCommon
740      ); // Invariant: intervals do not have common items at the end.
741      // The end of an index interval is open like array slice method.
742  
743      const aEnd = aLength - nCommonR;
744      const bEnd = bLength - nCommonR; // Unless one sequence consists of common items only,
745      // therefore the other trimmed index interval consists of changes only,
746      // find common items in the trimmed index intervals.
747  
748      const nCommonFR = nCommonF + nCommonR;
749  
750      if (aLength !== nCommonFR && bLength !== nCommonFR) {
751        const nChange = 0; // number of change items is not yet known
752  
753        const transposed = false; // call the original unwrapped functions
754  
755        const callbacks = [
756          {
757            foundSubsequence,
758            isCommon
759          }
760        ]; // Indexes in sequence a of last points in furthest reaching paths
761        // from outside the start at top left in the forward direction:
762  
763        const aIndexesF = [NOT_YET_SET]; // from the end at bottom right in the reverse direction:
764  
765        const aIndexesR = [NOT_YET_SET]; // Initialize one object as output of all calls to divide function.
766  
767        const division = {
768          aCommonFollowing: NOT_YET_SET,
769          aCommonPreceding: NOT_YET_SET,
770          aEndPreceding: NOT_YET_SET,
771          aStartFollowing: NOT_YET_SET,
772          bCommonFollowing: NOT_YET_SET,
773          bCommonPreceding: NOT_YET_SET,
774          bEndPreceding: NOT_YET_SET,
775          bStartFollowing: NOT_YET_SET,
776          nChangeFollowing: NOT_YET_SET,
777          nChangePreceding: NOT_YET_SET,
778          nCommonFollowing: NOT_YET_SET,
779          nCommonPreceding: NOT_YET_SET
780        }; // Find and return common subsequences in the trimmed index intervals.
781  
782        findSubsequences(
783          nChange,
784          aStart,
785          aEnd,
786          bStart,
787          bEnd,
788          transposed,
789          callbacks,
790          aIndexesF,
791          aIndexesR,
792          division
793        );
794      }
795  
796      if (nCommonR !== 0) {
797        foundSubsequence(nCommonR, aEnd, bEnd);
798      }
799    }
800  };
801  
802  exports.default = _default;