123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802 |
- 'use strict';
- Object.defineProperty(exports, '__esModule', {
- value: true
- });
- exports.default = void 0;
- const pkg = 'diff-sequences';
- const NOT_YET_SET = 0;
- const countCommonItemsF = (aIndex, aEnd, bIndex, bEnd, isCommon) => {
- let nCommon = 0;
- while (aIndex < aEnd && bIndex < bEnd && isCommon(aIndex, bIndex)) {
- aIndex += 1;
- bIndex += 1;
- nCommon += 1;
- }
- return nCommon;
- };
- const countCommonItemsR = (aStart, aIndex, bStart, bIndex, isCommon) => {
- let nCommon = 0;
- while (aStart <= aIndex && bStart <= bIndex && isCommon(aIndex, bIndex)) {
- aIndex -= 1;
- bIndex -= 1;
- nCommon += 1;
- }
- return nCommon;
- };
- const extendPathsF = (d, aEnd, bEnd, bF, isCommon, aIndexesF, iMaxF) => {
-
- let iF = 0;
- let kF = -d;
- let aFirst = aIndexesF[iF];
- let aIndexPrev1 = aFirst;
- aIndexesF[iF] += countCommonItemsF(
- aFirst + 1,
- aEnd,
- bF + aFirst - kF + 1,
- bEnd,
- isCommon
- );
- const nF = d < iMaxF ? d : iMaxF;
- for (iF += 1, kF += 2; iF <= nF; iF += 1, kF += 2) {
-
-
-
- if (iF !== d && aIndexPrev1 < aIndexesF[iF]) {
- aFirst = aIndexesF[iF];
- } else {
- aFirst = aIndexPrev1 + 1;
- if (aEnd <= aFirst) {
-
- return iF - 1;
- }
- }
- aIndexPrev1 = aIndexesF[iF];
- aIndexesF[iF] =
- aFirst +
- countCommonItemsF(aFirst + 1, aEnd, bF + aFirst - kF + 1, bEnd, isCommon);
- }
- return iMaxF;
- };
- const extendPathsR = (d, aStart, bStart, bR, isCommon, aIndexesR, iMaxR) => {
-
- let iR = 0;
- let kR = d;
- let aFirst = aIndexesR[iR];
- let aIndexPrev1 = aFirst;
- aIndexesR[iR] -= countCommonItemsR(
- aStart,
- aFirst - 1,
- bStart,
- bR + aFirst - kR - 1,
- isCommon
- );
- const nR = d < iMaxR ? d : iMaxR;
- for (iR += 1, kR -= 2; iR <= nR; iR += 1, kR -= 2) {
-
-
-
- if (iR !== d && aIndexesR[iR] < aIndexPrev1) {
- aFirst = aIndexesR[iR];
- } else {
- aFirst = aIndexPrev1 - 1;
- if (aFirst < aStart) {
-
- return iR - 1;
- }
- }
- aIndexPrev1 = aIndexesR[iR];
- aIndexesR[iR] =
- aFirst -
- countCommonItemsR(
- aStart,
- aFirst - 1,
- bStart,
- bR + aFirst - kR - 1,
- isCommon
- );
- }
- return iMaxR;
- };
- const extendOverlappablePathsF = (
- d,
- aStart,
- aEnd,
- bStart,
- bEnd,
- isCommon,
- aIndexesF,
- iMaxF,
- aIndexesR,
- iMaxR,
- division
- ) => {
- const bF = bStart - aStart;
- const aLength = aEnd - aStart;
- const bLength = bEnd - bStart;
- const baDeltaLength = bLength - aLength;
-
- const kMinOverlapF = -baDeltaLength - (d - 1);
- const kMaxOverlapF = -baDeltaLength + (d - 1);
- let aIndexPrev1 = NOT_YET_SET;
-
- const nF = d < iMaxF ? d : iMaxF;
- for (let iF = 0, kF = -d; iF <= nF; iF += 1, kF += 2) {
-
-
-
-
- const insert = iF === 0 || (iF !== d && aIndexPrev1 < aIndexesF[iF]);
- const aLastPrev = insert ? aIndexesF[iF] : aIndexPrev1;
- const aFirst = insert
- ? aLastPrev
- : aLastPrev + 1;
-
- const bFirst = bF + aFirst - kF;
- const nCommonF = countCommonItemsF(
- aFirst + 1,
- aEnd,
- bFirst + 1,
- bEnd,
- isCommon
- );
- const aLast = aFirst + nCommonF;
- aIndexPrev1 = aIndexesF[iF];
- aIndexesF[iF] = aLast;
- if (kMinOverlapF <= kF && kF <= kMaxOverlapF) {
-
-
-
- const iR = (d - 1 - (kF + baDeltaLength)) / 2;
-
- if (iR <= iMaxR && aIndexesR[iR] - 1 <= aLast) {
-
-
-
- const bLastPrev = bF + aLastPrev - (insert ? kF + 1 : kF - 1);
-
-
- const nCommonR = countCommonItemsR(
- aStart,
- aLastPrev,
- bStart,
- bLastPrev,
- isCommon
- );
- const aIndexPrevFirst = aLastPrev - nCommonR;
- const bIndexPrevFirst = bLastPrev - nCommonR;
- const aEndPreceding = aIndexPrevFirst + 1;
- const bEndPreceding = bIndexPrevFirst + 1;
- division.nChangePreceding = d - 1;
- if (d - 1 === aEndPreceding + bEndPreceding - aStart - bStart) {
-
-
-
- division.aEndPreceding = aStart;
- division.bEndPreceding = bStart;
- } else {
- division.aEndPreceding = aEndPreceding;
- division.bEndPreceding = bEndPreceding;
- }
- division.nCommonPreceding = nCommonR;
- if (nCommonR !== 0) {
- division.aCommonPreceding = aEndPreceding;
- division.bCommonPreceding = bEndPreceding;
- }
- division.nCommonFollowing = nCommonF;
- if (nCommonF !== 0) {
- division.aCommonFollowing = aFirst + 1;
- division.bCommonFollowing = bFirst + 1;
- }
- const aStartFollowing = aLast + 1;
- const bStartFollowing = bFirst + nCommonF + 1;
- division.nChangeFollowing = d - 1;
- if (d - 1 === aEnd + bEnd - aStartFollowing - bStartFollowing) {
-
-
-
- division.aStartFollowing = aEnd;
- division.bStartFollowing = bEnd;
- } else {
- division.aStartFollowing = aStartFollowing;
- division.bStartFollowing = bStartFollowing;
- }
- return true;
- }
- }
- }
- return false;
- };
- const extendOverlappablePathsR = (
- d,
- aStart,
- aEnd,
- bStart,
- bEnd,
- isCommon,
- aIndexesF,
- iMaxF,
- aIndexesR,
- iMaxR,
- division
- ) => {
- const bR = bEnd - aEnd;
- const aLength = aEnd - aStart;
- const bLength = bEnd - bStart;
- const baDeltaLength = bLength - aLength;
-
- const kMinOverlapR = baDeltaLength - d;
- const kMaxOverlapR = baDeltaLength + d;
- let aIndexPrev1 = NOT_YET_SET;
-
- const nR = d < iMaxR ? d : iMaxR;
- for (let iR = 0, kR = d; iR <= nR; iR += 1, kR -= 2) {
-
-
-
-
- const insert = iR === 0 || (iR !== d && aIndexesR[iR] < aIndexPrev1);
- const aLastPrev = insert ? aIndexesR[iR] : aIndexPrev1;
- const aFirst = insert
- ? aLastPrev
- : aLastPrev - 1;
-
- const bFirst = bR + aFirst - kR;
- const nCommonR = countCommonItemsR(
- aStart,
- aFirst - 1,
- bStart,
- bFirst - 1,
- isCommon
- );
- const aLast = aFirst - nCommonR;
- aIndexPrev1 = aIndexesR[iR];
- aIndexesR[iR] = aLast;
- if (kMinOverlapR <= kR && kR <= kMaxOverlapR) {
-
-
-
- const iF = (d + (kR - baDeltaLength)) / 2;
-
- if (iF <= iMaxF && aLast - 1 <= aIndexesF[iF]) {
- const bLast = bFirst - nCommonR;
- division.nChangePreceding = d;
- if (d === aLast + bLast - aStart - bStart) {
-
-
-
- division.aEndPreceding = aStart;
- division.bEndPreceding = bStart;
- } else {
- division.aEndPreceding = aLast;
- division.bEndPreceding = bLast;
- }
- division.nCommonPreceding = nCommonR;
- if (nCommonR !== 0) {
-
- division.aCommonPreceding = aLast;
- division.bCommonPreceding = bLast;
- }
- division.nChangeFollowing = d - 1;
- if (d === 1) {
-
- division.nCommonFollowing = 0;
- division.aStartFollowing = aEnd;
- division.bStartFollowing = bEnd;
- } else {
-
-
-
- const bLastPrev = bR + aLastPrev - (insert ? kR - 1 : kR + 1);
-
-
- const nCommonF = countCommonItemsF(
- aLastPrev,
- aEnd,
- bLastPrev,
- bEnd,
- isCommon
- );
- division.nCommonFollowing = nCommonF;
- if (nCommonF !== 0) {
-
- division.aCommonFollowing = aLastPrev;
- division.bCommonFollowing = bLastPrev;
- }
- const aStartFollowing = aLastPrev + nCommonF;
- const bStartFollowing = bLastPrev + nCommonF;
- if (d - 1 === aEnd + bEnd - aStartFollowing - bStartFollowing) {
-
-
-
- division.aStartFollowing = aEnd;
- division.bStartFollowing = bEnd;
- } else {
- division.aStartFollowing = aStartFollowing;
- division.bStartFollowing = bStartFollowing;
- }
- }
- return true;
- }
- }
- }
- return false;
- };
- const divide = (
- nChange,
- aStart,
- aEnd,
- bStart,
- bEnd,
- isCommon,
- aIndexesF,
- aIndexesR,
- division
- ) => {
- const bF = bStart - aStart;
- const bR = bEnd - aEnd;
- const aLength = aEnd - aStart;
- const bLength = bEnd - bStart;
-
-
-
-
-
- const baDeltaLength = bLength - aLength;
- let iMaxF = aLength;
- let iMaxR = aLength;
- aIndexesF[0] = aStart - 1;
- aIndexesR[0] = aEnd;
- if (baDeltaLength % 2 === 0) {
-
- const dMin = (nChange || baDeltaLength) / 2;
- const dMax = (aLength + bLength) / 2;
- for (let d = 1; d <= dMax; d += 1) {
- iMaxF = extendPathsF(d, aEnd, bEnd, bF, isCommon, aIndexesF, iMaxF);
- if (d < dMin) {
- iMaxR = extendPathsR(d, aStart, bStart, bR, isCommon, aIndexesR, iMaxR);
- } else if (
-
-
- extendOverlappablePathsR(
- d,
- aStart,
- aEnd,
- bStart,
- bEnd,
- isCommon,
- aIndexesF,
- iMaxF,
- aIndexesR,
- iMaxR,
- division
- )
- ) {
- return;
- }
- }
- } else {
-
- const dMin = ((nChange || baDeltaLength) + 1) / 2;
- const dMax = (aLength + bLength + 1) / 2;
-
-
-
-
- let d = 1;
- iMaxF = extendPathsF(d, aEnd, bEnd, bF, isCommon, aIndexesF, iMaxF);
- for (d += 1; d <= dMax; d += 1) {
- iMaxR = extendPathsR(
- d - 1,
- aStart,
- bStart,
- bR,
- isCommon,
- aIndexesR,
- iMaxR
- );
- if (d < dMin) {
- iMaxF = extendPathsF(d, aEnd, bEnd, bF, isCommon, aIndexesF, iMaxF);
- } else if (
-
-
- extendOverlappablePathsF(
- d,
- aStart,
- aEnd,
- bStart,
- bEnd,
- isCommon,
- aIndexesF,
- iMaxF,
- aIndexesR,
- iMaxR,
- division
- )
- ) {
- return;
- }
- }
- }
-
- throw new Error(
- `${pkg}: no overlap aStart=${aStart} aEnd=${aEnd} bStart=${bStart} bEnd=${bEnd}`
- );
- };
- const findSubsequences = (
- nChange,
- aStart,
- aEnd,
- bStart,
- bEnd,
- transposed,
- callbacks,
- aIndexesF,
- aIndexesR,
- division
- ) => {
- if (bEnd - bStart < aEnd - aStart) {
-
-
- transposed = !transposed;
- if (transposed && callbacks.length === 1) {
-
- const {foundSubsequence, isCommon} = callbacks[0];
- callbacks[1] = {
- foundSubsequence: (nCommon, bCommon, aCommon) => {
- foundSubsequence(nCommon, aCommon, bCommon);
- },
- isCommon: (bIndex, aIndex) => isCommon(aIndex, bIndex)
- };
- }
- const tStart = aStart;
- const tEnd = aEnd;
- aStart = bStart;
- aEnd = bEnd;
- bStart = tStart;
- bEnd = tEnd;
- }
- const {foundSubsequence, isCommon} = callbacks[transposed ? 1 : 0];
- divide(
- nChange,
- aStart,
- aEnd,
- bStart,
- bEnd,
- isCommon,
- aIndexesF,
- aIndexesR,
- division
- );
- const {
- nChangePreceding,
- aEndPreceding,
- bEndPreceding,
- nCommonPreceding,
- aCommonPreceding,
- bCommonPreceding,
- nCommonFollowing,
- aCommonFollowing,
- bCommonFollowing,
- nChangeFollowing,
- aStartFollowing,
- bStartFollowing
- } = division;
- if (aStart < aEndPreceding && bStart < bEndPreceding) {
-
- findSubsequences(
- nChangePreceding,
- aStart,
- aEndPreceding,
- bStart,
- bEndPreceding,
- transposed,
- callbacks,
- aIndexesF,
- aIndexesR,
- division
- );
- }
- if (nCommonPreceding !== 0) {
- foundSubsequence(nCommonPreceding, aCommonPreceding, bCommonPreceding);
- }
- if (nCommonFollowing !== 0) {
- foundSubsequence(nCommonFollowing, aCommonFollowing, bCommonFollowing);
- }
- if (aStartFollowing < aEnd && bStartFollowing < bEnd) {
-
- findSubsequences(
- nChangeFollowing,
- aStartFollowing,
- aEnd,
- bStartFollowing,
- bEnd,
- transposed,
- callbacks,
- aIndexesF,
- aIndexesR,
- division
- );
- }
- };
- const validateLength = (name, arg) => {
- if (typeof arg !== 'number') {
- throw new TypeError(`${pkg}: ${name} typeof ${typeof arg} is not a number`);
- }
- if (!Number.isSafeInteger(arg)) {
- throw new RangeError(`${pkg}: ${name} value ${arg} is not a safe integer`);
- }
- if (arg < 0) {
- throw new RangeError(`${pkg}: ${name} value ${arg} is a negative integer`);
- }
- };
- const validateCallback = (name, arg) => {
- const type = typeof arg;
- if (type !== 'function') {
- throw new TypeError(`${pkg}: ${name} typeof ${type} is not a function`);
- }
- };
- var _default = (aLength, bLength, isCommon, foundSubsequence) => {
- validateLength('aLength', aLength);
- validateLength('bLength', bLength);
- validateCallback('isCommon', isCommon);
- validateCallback('foundSubsequence', foundSubsequence);
- const nCommonF = countCommonItemsF(0, aLength, 0, bLength, isCommon);
- if (nCommonF !== 0) {
- foundSubsequence(nCommonF, 0, 0);
- }
-
- if (aLength !== nCommonF || bLength !== nCommonF) {
-
-
- const aStart = nCommonF;
- const bStart = nCommonF;
- const nCommonR = countCommonItemsR(
- aStart,
- aLength - 1,
- bStart,
- bLength - 1,
- isCommon
- );
-
- const aEnd = aLength - nCommonR;
- const bEnd = bLength - nCommonR;
-
-
- const nCommonFR = nCommonF + nCommonR;
- if (aLength !== nCommonFR && bLength !== nCommonFR) {
- const nChange = 0;
- const transposed = false;
- const callbacks = [
- {
- foundSubsequence,
- isCommon
- }
- ];
-
- const aIndexesF = [NOT_YET_SET];
- const aIndexesR = [NOT_YET_SET];
- const division = {
- aCommonFollowing: NOT_YET_SET,
- aCommonPreceding: NOT_YET_SET,
- aEndPreceding: NOT_YET_SET,
- aStartFollowing: NOT_YET_SET,
- bCommonFollowing: NOT_YET_SET,
- bCommonPreceding: NOT_YET_SET,
- bEndPreceding: NOT_YET_SET,
- bStartFollowing: NOT_YET_SET,
- nChangeFollowing: NOT_YET_SET,
- nChangePreceding: NOT_YET_SET,
- nCommonFollowing: NOT_YET_SET,
- nCommonPreceding: NOT_YET_SET
- };
- findSubsequences(
- nChange,
- aStart,
- aEnd,
- bStart,
- bEnd,
- transposed,
- callbacks,
- aIndexesF,
- aIndexesR,
- division
- );
- }
- if (nCommonR !== 0) {
- foundSubsequence(nCommonR, aEnd, bEnd);
- }
- }
- };
- exports.default = _default;
|