fast-myers-diff - npm Package Compare versions

Comparing version 1.0.1 to 1.0.2

dist/index.js

@@ -1,1 +0,1 @@
-"use strict";function*diff_rec(t,e,n,o,f,r){const i=[];let c=2*Math.min(n,r)+2,l=new Uint32Array(c),s=new Uint32Array(c),[a,y,u,d,h]=[0,0,0,0,0];for(;;){t:{if(n>0&&r>0){const p=n+r,x=1&p,g=n-r,P=(p>>>1)+x;e:for(let i=0;i<=P;i++){const p=2*Math.max(0,i-r)-i,P=i-2*Math.max(0,i-n);for(let b=p;b<=P;b+=2){const p=b%c+c,[P,A]=[l[(p+1)%c],l[(p-1)%c]];for(d=b===-i||b<i&&A<P?P:A+1,h=d-b,[y,u]=[d,h];d<n&&h<r&&t[e+d]===o[f+h];)d++,h++;l[p%c]=d;const M=g-b;if(1===x&&M>-i&&M<i&&d+s[(c+M%c)%c]>=n){a=2*i-1;break e}}[l,s]=[s,l];for(let b=p;b<=P;b+=2){const p=b%c+c,[P,A]=[l[(p+1)%c],l[(p-1)%c]];y=b===-i||b<i&&A<P?P:A+1,u=y-b,[d,h]=[n-y,r-u];const M=e+n-1,_=f+r-1;for(;y<n&&u<r&&t[M-y]===o[_-u];)y++,u++;l[p%c]=y;const m=g-b;if(0===x&&m>=-i&&m<=i&&y+s[(c+m%c)%c]>=n){[a,y,u]=[2*i,n-y,r-u];break e}}[l,s]=[s,l]}if((a>1||y!==d&&u!==h)&&(i.push([e+d,n-d,f+h,r-h]),[n,r]=[y,u],n>0&&r>0))break t}if(r>n){const[t,o]=[e+n,f+n];yield[t,t,o,o+r]}else if(r<n){const[t,o]=[e+r,f+r];yield[t,t+n,o,o]}if(0===i.length)return;[e,n,f,r]=i.pop()}c=2*Math.min(n,r)+2,a=l[1]=s[1]=0}}function*diff(t,e){let[n,o,f]=[0,t.length,e.length];for(;n<o&&n<f&&t[n]===e[n];)n++;if(n===o&&o===f)return;for(;o>n&&f>n&&t[--o]===e[--f];);const r=diff_rec(t,n,o+1-n,e,n,f+1-n);let i=r.next().value;for(const t of r){const[e,n,o,f]=t;if(e===n){if(o===i[3]){i[3]=f;continue}if(i[2]===i[3]&&e>=i[0]&&e<=i[1]){[i[2],i[3]]=[o,f];continue}}else if(e===i[1]){i[1]=n;continue}yield i,i=t}yield i}function*lcs(t,e){let[n,o,f]=[0,t.length,e.length];for(;n<o&&n<f&&t[n]===e[n];)n++;if(n>0&&(yield[0,0,n]),n===o&&o===f)return;let[r,i]=[o,f];for(;r>n&&i>n&&t[--r]===e[--i];);const c=diff_rec(t,n,r+1-n,e,n,i+1-n);let[l,s,a,y]=c.next().value,u=n+y-a;n+=s-l;for(const t of c)[l,s,,y]=t,n!==l&&(t.length--,[t[0],t[1],t[2]]=[n,u,l-n],yield t),[n,u]=[s,y];n<o&&(yield[n,u,o-n])}function*calcPatch(t,e){const n=ArrayBuffer.isView(e)?Uint8Array.prototype.subarray:e.slice;for(const[o,f,r,i]of diff(t,e))yield[o,f,n.call(e,r,i)]}function*applyPatch(t,e){let n=0;const o=ArrayBuffer.isView(t)?Uint8Array.prototype.subarray:t.slice;for(const[f,r,i]of e)n<f&&(yield o.call(t,n,f)),i.length>0&&(yield i),n=r;n<t.length&&(yield o.call(t,n))}Object.defineProperty(exports,"__esModule",{value:!0}),exports.diff=diff,exports.lcs=lcs,exports.calcPatch=calcPatch,exports.applyPatch=applyPatch;
+"use strict";function*diff_rec(t,e,o,f,n,c){const i=[];let l=0,r=2*Math.min(o,c)+2;const s=new Uint32Array(2*r);let[a,y]=[0,r],[d,u,h,p,x]=[0,0,0,0,0];for(;;){t:{if(o>0&&c>0){const g=o+c,P=1&g,b=o-c,A=(g>>>1)+P;e:for(let i=0;i<=A;i++){const l=2*Math.max(0,i-c)-i,g=i-2*Math.max(0,i-o);for(let A=l;A<=g;A+=2){const l=A%r+r,[g,M]=[s[a+(l+1)%r],s[a+(l-1)%r]];for(p=A===-i||A<i&&M<g?g:M+1,x=p-A,[u,h]=[p,x];p<o&&x<c&&t[e+p]===f[n+x];)p++,x++;s[a+l%r]=p;const _=b-A;if(1===P&&_>-i&&_<i&&p+s[y+(r+_%r)%r]>=o){d=2*i-1;break e}}[a,y]=[y,a];for(let A=l;A<=g;A+=2){const l=A%r+r,[g,M]=[s[a+(l+1)%r],s[a+(l-1)%r]];u=A===-i||A<i&&M<g?g:M+1,h=u-A,[p,x]=[o-u,c-h];const _=e+o-1,m=n+c-1;for(;u<o&&h<c&&t[_-u]===f[m-h];)u++,h++;s[a+l%r]=u;const k=b-A;if(0===P&&k>=-i&&k<=i&&u+s[y+(r+k%r)%r]>=o){[d,u,h]=[2*i,o-u,c-h];break e}}[a,y]=[y,a]}if((d>1||u!==p&&h!==x)&&(i[l++]=[e+p,o-p,n+x,c-x],[o,c]=[u,h],o>0&&c>0))break t}if(c>o){const[t,f]=[e+o,n+o];yield[t,t,f,f+c]}else if(c<o){const[t,f]=[e+c,n+c];yield[t,t+o,f,f]}if(0===l)return;[e,o,n,c]=i[--l]}r=2*Math.min(o,c)+2,[a,y]=[0,r],d=s[1]=s[y+1]=0}}function*diff(t,e){let[o,f,n]=[0,t.length,e.length];for(;o<f&&o<n&&t[o]===e[o];)o++;if(o===f&&f===n)return;for(;f>o&&n>o&&t[--f]===e[--n];);const c=diff_rec(t,o,f+1-o,e,o,n+1-o);let i=c.next().value;for(const t of c){const[e,o,f,n]=t;if(e===o){if(f===i[3]){i[3]=n;continue}if(e>=i[0]&&e<=i[1]&&i[2]===i[3]){[i[2],i[3]]=[f,n];continue}}else if(e===i[1]){i[1]=o;continue}yield i,i=t}yield i}function*lcs(t,e){let[o,f,n]=[0,t.length,e.length];for(;o<f&&o<n&&t[o]===e[o];)o++;if(o>0&&(yield[0,0,o]),o===f&&f===n)return;let[c,i]=[f,n];for(;c>o&&i>o&&t[--c]===e[--i];);const l=diff_rec(t,o,c+1-o,e,o,i+1-o);let[r,s,a,y]=l.next().value,d=o+y-a;o+=s-r;for(const t of l)[r,s,,y]=t,o!==r&&(t.length--,[t[0],t[1],t[2]]=[o,d,r-o],yield t),[o,d]=[s,y];o<f&&(yield[o,d,f-o])}function*calcPatch(t,e){const o=ArrayBuffer.isView(e)?Uint8Array.prototype.subarray:e.slice;for(const[f,n,c,i]of diff(t,e))yield[f,n,o.call(e,c,i)]}function*applyPatch(t,e){let o=0;const f=ArrayBuffer.isView(t)?Uint8Array.prototype.subarray:t.slice;for(const[n,c,i]of e)o<n&&(yield f.call(t,o,n)),i.length>0&&(yield i),o=c;o<t.length&&(yield f.call(t,o))}Object.defineProperty(exports,"__esModule",{value:!0}),exports.diff=diff,exports.lcs=lcs,exports.calcPatch=calcPatch,exports.applyPatch=applyPatch;

package.json

 {
   "name": "fast-myers-diff",
-  "version": "1.0.1",
+  "version": "1.0.2",
   "description": "A fast, minimal, memory-efficient diff algorithm on strings, arrays, and typed arrays.",
@@ -5,0 +5,0 @@ "main": "dist/index.js",

README.md

@@ -11,6 +11,6 @@ Fast-Myers-Diff
   where N and M are the lengths of the input sequences and D is the number of differences.
-* The original recursive algorithm is replaced by an iterative version with a minimal stack handling altered parameters for right-recursion.
+* The original recursive algorithm is replaced by an iterative version with a minimal stack storing the altered parameters for right-recursion.
   All other recursive calls are tail calls replaced with simple jumps (via `break` or `continue`). Huge inputs may blow the heap, but you'll never overflow the stack!
-* Allocation is minimized by pre-allocating buffer space to be re-used by each simulated recursive call, and tracking indices into the original inputs.
-  The core diff algorithm performs no slice operations or other copying of data.
+* Allocation is minimized by pre-allocating buffer space to be re-used by each simulated recursive call, and tracking indices into the original inputs. The core diff algorithm performs no slice operations or other copying of data. This also minimizes garbage production and GC pause time.
+* Buffers are allocated contiguously (using typed arrays) to improve cache locality.
 
@@ -17,0 +17,0 @@ Because the core algorithm does not slice or copy data, it depends only on being able to compare elements of the inputs at arbitrary indices.

No alert changes

Improved metrics

Total package byte prevSize

9055

increased by1.92%

No dependency changes