diff_match_patch.js

var diff_match_patch=function(){this.Diff_Timeout=1;this.Diff_EditCost=4;this.Match_Threshold=.5;this.Match_Distance=1E3;this.Patch_DeleteThreshold=.5;this.Patch_Margin=4;this.Match_MaxBits=32},DIFF_DELETE=-1,DIFF_INSERT=1,DIFF_EQUAL=0;diff_match_patch.Diff=function(a,b){this[0]=a;this[1]=b};diff_match_patch.Diff.prototype.length=2;diff_match_patch.Diff.prototype.toString=function(){return this[0]+","+this[1]};
diff_match_patch.prototype.diff_main=function(a,b,d,c){"undefined"==typeof c&&(c=0>=this.Diff_Timeout?Number.MAX_VALUE:(new Date).getTime()+1E3*this.Diff_Timeout);if(null==a||null==b)throw Error("Null input. (diff_main)");if(a==b)return a?[new diff_match_patch.Diff(DIFF_EQUAL,a)]:[];"undefined"==typeof d&&(d=!0);var e=d,f=this.diff_commonPrefix(a,b);d=a.substring(0,f);a=a.substring(f);b=b.substring(f);f=this.diff_commonSuffix(a,b);var g=a.substring(a.length-f);a=a.substring(0,a.length-f);b=b.substring(0,
b.length-f);a=this.diff_compute_(a,b,e,c);d&&a.unshift(new diff_match_patch.Diff(DIFF_EQUAL,d));g&&a.push(new diff_match_patch.Diff(DIFF_EQUAL,g));this.diff_cleanupMerge(a);return a};
diff_match_patch.prototype.diff_compute_=function(a,b,d,c){if(!a)return[new diff_match_patch.Diff(DIFF_INSERT,b)];if(!b)return[new diff_match_patch.Diff(DIFF_DELETE,a)];var e=a.length>b.length?a:b,f=a.length>b.length?b:a,g=e.indexOf(f);return-1!=g?(d=[new diff_match_patch.Diff(DIFF_INSERT,e.substring(0,g)),new diff_match_patch.Diff(DIFF_EQUAL,f),new diff_match_patch.Diff(DIFF_INSERT,e.substring(g+f.length))],a.length>b.length&&(d[0][0]=d[2][0]=DIFF_DELETE),d):1==f.length?[new diff_match_patch.Diff(DIFF_DELETE,
a),new diff_match_patch.Diff(DIFF_INSERT,b)]:(e=this.diff_halfMatch_(a,b))?(b=e[1],f=e[3],a=e[4],e=this.diff_main(e[0],e[2],d,c),d=this.diff_main(b,f,d,c),e.concat([new diff_match_patch.Diff(DIFF_EQUAL,a)],d)):d&&100<a.length&&100<b.length?this.diff_lineMode_(a,b,c):this.diff_bisect_(a,b,c)};
diff_match_patch.prototype.diff_lineMode_=function(a,b,d){var c=this.diff_linesToChars_(a,b);a=c.chars1;b=c.chars2;c=c.lineArray;a=this.diff_main(a,b,!1,d);this.diff_charsToLines_(a,c);this.diff_cleanupSemantic(a);a.push(new diff_match_patch.Diff(DIFF_EQUAL,""));for(var e=c=b=0,f="",g="";b<a.length;){switch(a[b][0]){case DIFF_INSERT:e++;g+=a[b][1];break;case DIFF_DELETE:c++;f+=a[b][1];break;case DIFF_EQUAL:if(1<=c&&1<=e){a.splice(b-c-e,c+e);b=b-c-e;c=this.diff_main(f,g,!1,d);for(e=c.length-1;0<=e;e--)a.splice(b,
0,c[e]);b+=c.length}c=e=0;g=f=""}b++}a.pop();return a};
diff_match_patch.prototype.diff_bisect_=function(a,b,d){for(var c=a.length,e=b.length,f=Math.ceil((c+e)/2),g=2*f,h=Array(g),l=Array(g),k=0;k<g;k++)h[k]=-1,l[k]=-1;h[f+1]=0;l[f+1]=0;k=c-e;for(var m=0!=k%2,n=0,w=0,p=0,r=0,u=0;u<f&&!((new Date).getTime()>d);u++){for(var v=-u+n;v<=u-w;v+=2){var q=f+v;var t=v==-u||v!=u&&h[q-1]<h[q+1]?h[q+1]:h[q-1]+1;for(var y=t-v;t<c&&y<e&&a.charAt(t)==b.charAt(y);)t++,y++;h[q]=t;if(t>c)w+=2;else if(y>e)n+=2;else if(m&&(q=f+k-v,0<=q&&q<g&&-1!=l[q])){var x=c-l[q];if(t>=
x)return this.diff_bisectSplit_(a,b,t,y,d)}}for(v=-u+p;v<=u-r;v+=2){q=f+v;x=v==-u||v!=u&&l[q-1]<l[q+1]?l[q+1]:l[q-1]+1;for(t=x-v;x<c&&t<e&&a.charAt(c-x-1)==b.charAt(e-t-1);)x++,t++;l[q]=x;if(x>c)r+=2;else if(t>e)p+=2;else if(!m&&(q=f+k-v,0<=q&&q<g&&-1!=h[q]&&(t=h[q],y=f+t-q,x=c-x,t>=x)))return this.diff_bisectSplit_(a,b,t,y,d)}}return[new diff_match_patch.Diff(DIFF_DELETE,a),new diff_match_patch.Diff(DIFF_INSERT,b)]};
diff_match_patch.prototype.diff_bisectSplit_=function(a,b,d,c,e){var f=a.substring(0,d),g=b.substring(0,c);a=a.substring(d);b=b.substring(c);f=this.diff_main(f,g,!1,e);e=this.diff_main(a,b,!1,e);return f.concat(e)};
diff_match_patch.prototype.diff_linesToChars_=function(a,b){function d(l){for(var k="",m=0,n=-1,w=c.length;n<l.length-1;){n=l.indexOf("\n",m);-1==n&&(n=l.length-1);var p=l.substring(m,n+1);(e.hasOwnProperty?e.hasOwnProperty(p):void 0!==e[p])?k+=String.fromCharCode(e[p]):(w==f&&(p=l.substring(m),n=l.length),k+=String.fromCharCode(w),e[p]=w,c[w++]=p);m=n+1}return k}var c=[],e={};c[0]="";var f=4E4,g=d(a);f=65535;var h=d(b);return{chars1:g,chars2:h,lineArray:c}};
diff_match_patch.prototype.diff_charsToLines_=function(a,b){for(var d=0;d<a.length;d++){for(var c=a[d][1],e=[],f=0;f<c.length;f++)e[f]=b[c.charCodeAt(f)];a[d][1]=e.join("")}};diff_match_patch.prototype.diff_commonPrefix=function(a,b){if(!a||!b||a.charAt(0)!=b.charAt(0))return 0;for(var d=0,c=Math.min(a.length,b.length),e=c,f=0;d<e;)a.substring(f,e)==b.substring(f,e)?f=d=e:c=e,e=Math.floor((c-d)/2+d);return e};
diff_match_patch.prototype.diff_commonSuffix=function(a,b){if(!a||!b||a.charAt(a.length-1)!=b.charAt(b.length-1))return 0;for(var d=0,c=Math.min(a.length,b.length),e=c,f=0;d<e;)a.substring(a.length-e,a.length-f)==b.substring(b.length-e,b.length-f)?f=d=e:c=e,e=Math.floor((c-d)/2+d);return e};
diff_match_patch.prototype.diff_commonOverlap_=function(a,b){var d=a.length,c=b.length;if(0==d||0==c)return 0;d>c?a=a.substring(d-c):d<c&&(b=b.substring(0,d));d=Math.min(d,c);if(a==b)return d;c=0;for(var e=1;;){var f=a.substring(d-e);f=b.indexOf(f);if(-1==f)return c;e+=f;if(0==f||a.substring(d-e)==b.substring(0,e))c=e,e++}};
diff_match_patch.prototype.diff_halfMatch_=function(a,b){function d(k,m,n){for(var w=k.substring(n,n+Math.floor(k.length/4)),p=-1,r="",u,v,q,t;-1!=(p=m.indexOf(w,p+1));){var y=f.diff_commonPrefix(k.substring(n),m.substring(p)),x=f.diff_commonSuffix(k.substring(0,n),m.substring(0,p));r.length<x+y&&(r=m.substring(p-x,p)+m.substring(p,p+y),u=k.substring(0,n-x),v=k.substring(n+y),q=m.substring(0,p-x),t=m.substring(p+y))}return 2*r.length>=k.length?[u,v,q,t,r]:null}if(0>=this.Diff_Timeout)return null;
var c=a.length>b.length?a:b,e=a.length>b.length?b:a;if(4>c.length||2*e.length<c.length)return null;var f=this,g=d(c,e,Math.ceil(c.length/4));c=d(c,e,Math.ceil(c.length/2));if(g||c)g=c?g?g[4].length>c[4].length?g:c:c:g;else return null;if(a.length>b.length){c=g[0];e=g[1];var h=g[2];var l=g[3]}else h=g[0],l=g[1],c=g[2],e=g[3];return[c,e,h,l,g[4]]};
diff_match_patch.prototype.diff_cleanupSemantic=function(a){for(var b=!1,d=[],c=0,e=null,f=0,g=0,h=0,l=0,k=0;f<a.length;)a[f][0]==DIFF_EQUAL?(d[c++]=f,g=l,h=k,k=l=0,e=a[f][1]):(a[f][0]==DIFF_INSERT?l+=a[f][1].length:k+=a[f][1].length,e&&e.length<=Math.max(g,h)&&e.length<=Math.max(l,k)&&(a.splice(d[c-1],0,new diff_match_patch.Diff(DIFF_DELETE,e)),a[d[c-1]+1][0]=DIFF_INSERT,c--,c--,f=0<c?d[c-1]:-1,k=l=h=g=0,e=null,b=!0)),f++;b&&this.diff_cleanupMerge(a);this.diff_cleanupSemanticLossless(a);for(f=1;f<
a.length;){if(a[f-1][0]==DIFF_DELETE&&a[f][0]==DIFF_INSERT){b=a[f-1][1];d=a[f][1];c=this.diff_commonOverlap_(b,d);e=this.diff_commonOverlap_(d,b);if(c>=e){if(c>=b.length/2||c>=d.length/2)a.splice(f,0,new diff_match_patch.Diff(DIFF_EQUAL,d.substring(0,c))),a[f-1][1]=b.substring(0,b.length-c),a[f+1][1]=d.substring(c),f++}else if(e>=b.length/2||e>=d.length/2)a.splice(f,0,new diff_match_patch.Diff(DIFF_EQUAL,b.substring(0,e))),a[f-1][0]=DIFF_INSERT,a[f-1][1]=d.substring(0,d.length-e),a[f+1][0]=DIFF_DELETE,
a[f+1][1]=b.substring(e),f++;f++}f++}};
diff_match_patch.prototype.diff_cleanupSemanticLossless=function(a){function b(n,w){if(!n||!w)return 6;var p=n.charAt(n.length-1),r=w.charAt(0),u=p.match(diff_match_patch.nonAlphaNumericRegex_),v=r.match(diff_match_patch.nonAlphaNumericRegex_),q=u&&p.match(diff_match_patch.whitespaceRegex_),t=v&&r.match(diff_match_patch.whitespaceRegex_);p=q&&p.match(diff_match_patch.linebreakRegex_);r=t&&r.match(diff_match_patch.linebreakRegex_);var y=p&&n.match(diff_match_patch.blanklineEndRegex_),x=r&&w.match(diff_match_patch.blanklineStartRegex_);
return y||x?5:p||r?4:u&&!q&&t?3:q||t?2:u||v?1:0}for(var d=1;d<a.length-1;){if(a[d-1][0]==DIFF_EQUAL&&a[d+1][0]==DIFF_EQUAL){var c=a[d-1][1],e=a[d][1],f=a[d+1][1],g=this.diff_commonSuffix(c,e);if(g){var h=e.substring(e.length-g);c=c.substring(0,c.length-g);e=h+e.substring(0,e.length-g);f=h+f}g=c;h=e;for(var l=f,k=b(c,e)+b(e,f);e.charAt(0)===f.charAt(0);){c+=e.charAt(0);e=e.substring(1)+f.charAt(0);f=f.substring(1);var m=b(c,e)+b(e,f);m>=k&&(k=m,g=c,h=e,l=f)}a[d-1][1]!=g&&(g?a[d-1][1]=g:(a.splice(d-
1,1),d--),a[d][1]=h,l?a[d+1][1]=l:(a.splice(d+1,1),d--))}d++}};diff_match_patch.nonAlphaNumericRegex_=/[^a-zA-Z0-9]/;diff_match_patch.whitespaceRegex_=/\s/;diff_match_patch.linebreakRegex_=/[\r\n]/;diff_match_patch.blanklineEndRegex_=/\n\r?\n$/;diff_match_patch.blanklineStartRegex_=/^\r?\n\r?\n/;
diff_match_patch.prototype.diff_cleanupEfficiency=function(a){for(var b=!1,d=[],c=0,e=null,f=0,g=!1,h=!1,l=!1,k=!1;f<a.length;)a[f][0]==DIFF_EQUAL?(a[f][1].length<this.Diff_EditCost&&(l||k)?(d[c++]=f,g=l,h=k,e=a[f][1]):(c=0,e=null),l=k=!1):(a[f][0]==DIFF_DELETE?k=!0:l=!0,e&&(g&&h&&l&&k||e.length<this.Diff_EditCost/2&&3==g+h+l+k)&&(a.splice(d[c-1],0,new diff_match_patch.Diff(DIFF_DELETE,e)),a[d[c-1]+1][0]=DIFF_INSERT,c--,e=null,g&&h?(l=k=!0,c=0):(c--,f=0<c?d[c-1]:-1,l=k=!1),b=!0)),f++;b&&this.diff_cleanupMerge(a)};
diff_match_patch.prototype.diff_cleanupMerge=function(a){a.push(new diff_match_patch.Diff(DIFF_EQUAL,""));for(var b=0,d=0,c=0,e="",f="",g;b<a.length;)switch(a[b][0]){case DIFF_INSERT:c++;f+=a[b][1];b++;break;case DIFF_DELETE:d++;e+=a[b][1];b++;break;case DIFF_EQUAL:1<d+c?(0!==d&&0!==c&&(g=this.diff_commonPrefix(f,e),0!==g&&(0<b-d-c&&a[b-d-c-1][0]==DIFF_EQUAL?a[b-d-c-1][1]+=f.substring(0,g):(a.splice(0,0,new diff_match_patch.Diff(DIFF_EQUAL,f.substring(0,g))),b++),f=f.substring(g),e=e.substring(g)),
g=this.diff_commonSuffix(f,e),0!==g&&(a[b][1]=f.substring(f.length-g)+a[b][1],f=f.substring(0,f.length-g),e=e.substring(0,e.length-g))),b-=d+c,a.splice(b,d+c),e.length&&(a.splice(b,0,new diff_match_patch.Diff(DIFF_DELETE,e)),b++),f.length&&(a.splice(b,0,new diff_match_patch.Diff(DIFF_INSERT,f)),b++),b++):0!==b&&a[b-1][0]==DIFF_EQUAL?(a[b-1][1]+=a[b][1],a.splice(b,1)):b++,d=c=0,f=e=""}""===a[a.length-1][1]&&a.pop();d=!1;for(b=1;b<a.length-1;)a[b-1][0]==DIFF_EQUAL&&a[b+1][0]==DIFF_EQUAL&&(a[b][1].substring(a[b][1].length-
a[b-1][1].length)==a[b-1][1]?(a[b][1]=a[b-1][1]+a[b][1].substring(0,a[b][1].length-a[b-1][1].length),a[b+1][1]=a[b-1][1]+a[b+1][1],a.splice(b-1,1),d=!0):a[b][1].substring(0,a[b+1][1].length)==a[b+1][1]&&(a[b-1][1]+=a[b+1][1],a[b][1]=a[b][1].substring(a[b+1][1].length)+a[b+1][1],a.splice(b+1,1),d=!0)),b++;d&&this.diff_cleanupMerge(a)};
diff_match_patch.prototype.diff_cleanupSplitSurrogates=function(a){for(var b,d=0;d<a.length;d++){var c=a[d],e=c[1][0],f=c[1][c[1].length-1];0===c[1].length?a.splice(d--,1):(f&&this.isHighSurrogate(f)&&(b=f,c[1]=c[1].slice(0,-1)),b&&e&&this.isHighSurrogate(b)&&this.isLowSurrogate(e)&&(c[1]=b+c[1]),0===c[1].length&&a.splice(d--,1))}return a};diff_match_patch.prototype.isHighSurrogate=function(a){a=a.charCodeAt(0);return 55296<=a&&56319>=a};
diff_match_patch.prototype.isLowSurrogate=function(a){a=a.charCodeAt(0);return 56320<=a&&57343>=a};
diff_match_patch.prototype.digit16=function(a){switch(a){case "0":return 0;case "1":return 1;case "2":return 2;case "3":return 3;case "4":return 4;case "5":return 5;case "6":return 6;case "7":return 7;case "8":return 8;case "9":return 9;case "A":case "a":return 10;case "B":case "b":return 11;case "C":case "c":return 12;case "D":case "d":return 13;case "E":case "e":return 14;case "F":case "f":return 15;default:throw Error("Invalid hex-code");}};
diff_match_patch.prototype.decodeURI=function(a){try{return decodeURI(a)}catch(h){for(var b=0,d="";b<a.length;)if("%"!==a[b])d+=a[b++];else{var c=(this.digit16(a[b+1])<<4)+this.digit16(a[b+2]);if(0===(c&128))d+=String.fromCharCode(c),b+=3;else{if("%"!==a[b+3])throw new URIError("URI malformed");var e=(this.digit16(a[b+4])<<4)+this.digit16(a[b+5]);if(128!==(e&192))throw new URIError("URI malformed");e&=63;if(192===(c&224))d+=String.fromCharCode((c&31)<<6|e),b+=6;else{if("%"!==a[b+6])throw new URIError("URI malformed");
var f=(this.digit16(a[b+7])<<4)+this.digit16(a[b+8]);if(128!==(f&192))throw new URIError("URI malformed");f&=63;if(224===(c&240))d+=String.fromCharCode((c&15)<<12|e<<6|f),b+=9;else{if("%"!==a[b+9])throw new URIError("URI malformed");var g=(this.digit16(a[b+10])<<4)+this.digit16(a[b+11]);if(128!==(g&192))throw new URIError("URI malformed");g&=63;if(240===(c&248)&&(c=(c&7)<<18|e<<12|f<<6|g,65536<=c&&1114111>=c)){d+=String.fromCharCode((c&65535)>>>10&1023|55296);d+=String.fromCharCode(56320|c&1023);
b+=12;continue}throw new URIError("URI malformed");}}}}return d}};diff_match_patch.prototype.diff_xIndex=function(a,b){var d=0,c=0,e=0,f=0,g;for(g=0;g<a.length;g++){a[g][0]!==DIFF_INSERT&&(d+=a[g][1].length);a[g][0]!==DIFF_DELETE&&(c+=a[g][1].length);if(d>b)break;e=d;f=c}return a.length!=g&&a[g][0]===DIFF_DELETE?f:f+(b-e)};
diff_match_patch.prototype.diff_prettyHtml=function(a){a=this.diff_cleanupSplitSurrogates(a);for(var b=[],d=/&/g,c=/</g,e=/>/g,f=/\n/g,g=/\t/g,h=/ /g,l=0;l<a.length;l++){var m=a[l][0],n=a[l][1].replace(d,"&amp;").replace(c,"&lt;").replace(e,"&gt;").replace(f,"&para;<br>").replace(g,"&emsp;").replace(h,"&nbsp;");switch(m){case DIFF_INSERT:b[l]='<ins style="background:#e6ffe6;">'+n+"</ins>";break;case DIFF_DELETE:b[l]='<del style="background:#ffe6e6;">'+n+"</del>";break;case DIFF_EQUAL:b[l]="<span>"+n+"</span>"}}return b.join("")};
diff_match_patch.prototype.diff_text1=function(a){for(var b=[],d=0;d<a.length;d++)a[d][0]!==DIFF_INSERT&&(b[d]=a[d][1]);return b.join("")};diff_match_patch.prototype.diff_text2=function(a){for(var b=[],d=0;d<a.length;d++)a[d][0]!==DIFF_DELETE&&(b[d]=a[d][1]);return b.join("")};
diff_match_patch.prototype.diff_levenshtein=function(a){for(var b=0,d=0,c=0,e=0;e<a.length;e++){var f=a[e][1];switch(a[e][0]){case DIFF_INSERT:d+=f.length;break;case DIFF_DELETE:c+=f.length;break;case DIFF_EQUAL:b+=Math.max(d,c),c=d=0}}return b+=Math.max(d,c)};
diff_match_patch.prototype.diff_toDelta=function(a){a=this.diff_cleanupSplitSurrogates(a);for(var b=[],d=0;d<a.length;d++)switch(a[d][0]){case DIFF_INSERT:b[d]="+"+encodeURI(a[d][1]);break;case DIFF_DELETE:b[d]="-"+a[d][1].length;break;case DIFF_EQUAL:b[d]="="+a[d][1].length}return b.join("\t").replace(/%20/g," ")};
diff_match_patch.prototype.diff_fromDelta=function(a,b){for(var d=[],c=0,e=0,f=b.split(/\t/g),g=0;g<f.length;g++){var h=f[g].substring(1);switch(f[g].charAt(0)){case "+":try{d[c++]=new diff_match_patch.Diff(DIFF_INSERT,this.decodeURI(h))}catch(k){throw Error("Illegal escape in diff_fromDelta: "+h);}break;case "-":case "=":var l=parseInt(h,10);if(isNaN(l)||0>l)throw Error("Invalid number in diff_fromDelta: "+h);h=a.substring(e,e+=l);"="==f[g].charAt(0)?d[c++]=new diff_match_patch.Diff(DIFF_EQUAL,h):
d[c++]=new diff_match_patch.Diff(DIFF_DELETE,h);break;default:if(f[g])throw Error("Invalid diff operation in diff_fromDelta: "+f[g]);}}if(e!=a.length)throw Error("Delta length ("+e+") does not equal source text length ("+a.length+").");return d};diff_match_patch.prototype.match_main=function(a,b,d){if(null==a||null==b||null==d)throw Error("Null input. (match_main)");d=Math.max(0,Math.min(d,a.length));return a==b?0:a.length?a.substring(d,d+b.length)==b?d:this.match_bitap_(a,b,d):-1};
diff_match_patch.prototype.match_bitap_=function(a,b,d){function c(v,q){var t=v/b.length,y=Math.abs(d-q);return f.Match_Distance?t+y/f.Match_Distance:y?1:t}if(b.length>this.Match_MaxBits)throw Error("Pattern too long for this browser.");var e=this.match_alphabet_(b),f=this,g=this.Match_Threshold,h=a.indexOf(b,d);-1!=h&&(g=Math.min(c(0,h),g),h=a.lastIndexOf(b,d+b.length),-1!=h&&(g=Math.min(c(0,h),g)));var l=1<<b.length-1;h=-1;for(var k,m,n=b.length+a.length,w,p=0;p<b.length;p++){k=0;for(m=n;k<m;)c(p,
d+m)<=g?k=m:n=m,m=Math.floor((n-k)/2+k);n=m;k=Math.max(1,d-m+1);var r=Math.min(d+m,a.length)+b.length;m=Array(r+2);for(m[r+1]=(1<<p)-1;r>=k;r--){var u=e[a.charAt(r-1)];m[r]=0===p?(m[r+1]<<1|1)&u:(m[r+1]<<1|1)&u|(w[r+1]|w[r])<<1|1|w[r+1];if(m[r]&l&&(u=c(p,r-1),u<=g))if(g=u,h=r-1,h>d)k=Math.max(1,2*d-h);else break}if(c(p+1,d)>g)break;w=m}return h};
diff_match_patch.prototype.match_alphabet_=function(a){for(var b={},d=0;d<a.length;d++)b[a.charAt(d)]=0;for(d=0;d<a.length;d++)b[a.charAt(d)]|=1<<a.length-d-1;return b};
diff_match_patch.prototype.patch_addContext_=function(a,b){if(0!=b.length){if(null===a.start2)throw Error("patch not initialized");for(var d=b.substring(a.start2,a.start2+a.length1),c=0;b.indexOf(d)!=b.lastIndexOf(d)&&d.length<this.Match_MaxBits-this.Patch_Margin-this.Patch_Margin;)c+=this.Patch_Margin,d=b.substring(a.start2-c,a.start2+a.length1+c);c+=this.Patch_Margin;0<a.start2-c&&diff_match_patch.prototype.isLowSurrogate(b[a.start2-c])&&c++;(d=b.substring(a.start2-c,a.start2))&&a.diffs.unshift(new diff_match_patch.Diff(DIFF_EQUAL,
d));a.start2+a.length1+c<b.length&&diff_match_patch.prototype.isHighSurrogate(b[a.start2+a.length1+c])&&c++;(c=b.substring(a.start2+a.length1,a.start2+a.length1+c))&&a.diffs.push(new diff_match_patch.Diff(DIFF_EQUAL,c));a.start1-=d.length;a.start2-=d.length;a.length1+=d.length+c.length;a.length2+=d.length+c.length}};
diff_match_patch.prototype.patch_make=function(a,b,d){if("string"==typeof a&&"string"==typeof b&&"undefined"==typeof d){var c=a;b=this.diff_main(c,b,!0);2<b.length&&(this.diff_cleanupSemantic(b),this.diff_cleanupEfficiency(b))}else if(a&&"object"==typeof a&&"undefined"==typeof b&&"undefined"==typeof d)b=a,c=this.diff_text1(b);else if("string"==typeof a&&b&&"object"==typeof b&&"undefined"==typeof d)c=a;else if("string"==typeof a&&"string"==typeof b&&d&&"object"==typeof d)c=a,b=d;else throw Error("Unknown call format to patch_make.");
if(0===b.length)return[];b=this.diff_cleanupSplitSurrogates(b);d=[];a=new diff_match_patch.patch_obj;for(var e=0,f=0,g=0,h=c,l=0;l<b.length;l++){var k=b[l][0],m=b[l][1];e||k===DIFF_EQUAL||(a.start1=f,a.start2=g);switch(k){case DIFF_INSERT:a.diffs[e++]=b[l];a.length2+=m.length;c=c.substring(0,g)+m+c.substring(g);break;case DIFF_DELETE:a.length1+=m.length;a.diffs[e++]=b[l];c=c.substring(0,g)+c.substring(g+m.length);break;case DIFF_EQUAL:m.length<=2*this.Patch_Margin&&e&&b.length!=l+1?(a.diffs[e++]=
b[l],a.length1+=m.length,a.length2+=m.length):m.length>=2*this.Patch_Margin&&e&&(this.patch_addContext_(a,h),d.push(a),a=new diff_match_patch.patch_obj,e=0,h=c,f=g)}k!==DIFF_INSERT&&(f+=m.length);k!==DIFF_DELETE&&(g+=m.length)}e&&(this.patch_addContext_(a,h),d.push(a));return d};
diff_match_patch.prototype.patch_deepCopy=function(a){for(var b=[],d=0;d<a.length;d++){var c=a[d],e=new diff_match_patch.patch_obj;e.diffs=[];for(var f=0;f<c.diffs.length;f++)e.diffs[f]=new diff_match_patch.Diff(c.diffs[f][0],c.diffs[f][1]);e.start1=c.start1;e.start2=c.start2;e.length1=c.length1;e.length2=c.length2;b[d]=e}return b};
diff_match_patch.prototype.patch_apply=function(a,b){if(0==a.length)return[b,[]];a=this.patch_deepCopy(a);var d=this.patch_addPadding(a);b=d+b+d;this.patch_splitMax(a);for(var c=0,e=[],f=0;f<a.length;f++){var g=a[f].start2+c,h=this.diff_text1(a[f].diffs),l=-1;if(h.length>this.Match_MaxBits){var k=this.match_main(b,h.substring(0,this.Match_MaxBits),g);-1!=k&&(l=this.match_main(b,h.substring(h.length-this.Match_MaxBits),g+h.length-this.Match_MaxBits),-1==l||k>=l)&&(k=-1)}else k=this.match_main(b,h,
g);if(-1==k)e[f]=!1,c-=a[f].length2-a[f].length1;else if(e[f]=!0,c=k-g,g=-1==l?b.substring(k,k+h.length):b.substring(k,l+this.Match_MaxBits),h==g)b=b.substring(0,k)+this.diff_text2(a[f].diffs)+b.substring(k+h.length);else if(g=this.diff_main(h,g,!1),h.length>this.Match_MaxBits&&this.diff_levenshtein(g)/h.length>this.Patch_DeleteThreshold)e[f]=!1;else{this.diff_cleanupSemanticLossless(g);h=0;var m;for(l=0;l<a[f].diffs.length;l++){var n=a[f].diffs[l];n[0]!==DIFF_EQUAL&&(m=this.diff_xIndex(g,h));n[0]===
DIFF_INSERT?b=b.substring(0,k+m)+n[1]+b.substring(k+m):n[0]===DIFF_DELETE&&(b=b.substring(0,k+m)+b.substring(k+this.diff_xIndex(g,h+n[1].length)));n[0]!==DIFF_DELETE&&(h+=n[1].length)}}}b=b.substring(d.length,b.length-d.length);return[b,e]};
diff_match_patch.prototype.patch_addPadding=function(a){for(var b=this.Patch_Margin,d="",c=1;c<=b;c++)d+=String.fromCharCode(c);for(c=0;c<a.length;c++)a[c].start1+=b,a[c].start2+=b;c=a[0];var e=c.diffs;if(0==e.length||e[0][0]!=DIFF_EQUAL)e.unshift(new diff_match_patch.Diff(DIFF_EQUAL,d)),c.start1-=b,c.start2-=b,c.length1+=b,c.length2+=b;else if(b>e[0][1].length){var f=b-e[0][1].length;e[0][1]=d.substring(e[0][1].length)+e[0][1];c.start1-=f;c.start2-=f;c.length1+=f;c.length2+=f}c=a[a.length-1];e=c.diffs;
0==e.length||e[e.length-1][0]!=DIFF_EQUAL?(e.push(new diff_match_patch.Diff(DIFF_EQUAL,d)),c.length1+=b,c.length2+=b):b>e[e.length-1][1].length&&(f=b-e[e.length-1][1].length,e[e.length-1][1]+=d.substring(0,f),c.length1+=f,c.length2+=f);return d};
diff_match_patch.prototype.patch_splitMax=function(a){for(var b=this.Match_MaxBits,d=0;d<a.length;d++)if(!(a[d].length1<=b)){var c=a[d];a.splice(d--,1);for(var e=c.start1,f=c.start2,g="";0!==c.diffs.length;){var h=new diff_match_patch.patch_obj,l=!0;h.start1=e-g.length;h.start2=f-g.length;""!==g&&(h.length1=h.length2=g.length,h.diffs.push(new diff_match_patch.Diff(DIFF_EQUAL,g)));for(;0!==c.diffs.length&&h.length1<b-this.Patch_Margin;){g=c.diffs[0][0];var k=c.diffs[0][1];g===DIFF_INSERT?(h.length2+=
k.length,f+=k.length,h.diffs.push(c.diffs.shift()),l=!1):g===DIFF_DELETE&&1==h.diffs.length&&h.diffs[0][0]==DIFF_EQUAL&&k.length>2*b?(h.length1+=k.length,e+=k.length,l=!1,h.diffs.push(new diff_match_patch.Diff(g,k)),c.diffs.shift()):(k=k.substring(0,b-h.length1-this.Patch_Margin),h.length1+=k.length,e+=k.length,g===DIFF_EQUAL?(h.length2+=k.length,f+=k.length):l=!1,h.diffs.push(new diff_match_patch.Diff(g,k)),k==c.diffs[0][1]?c.diffs.shift():c.diffs[0][1]=c.diffs[0][1].substring(k.length))}g=this.diff_text2(h.diffs);
g=g.substring(g.length-this.Patch_Margin);k=this.diff_text1(c.diffs).substring(0,this.Patch_Margin);""!==k&&(h.length1+=k.length,h.length2+=k.length,0!==h.diffs.length&&h.diffs[h.diffs.length-1][0]===DIFF_EQUAL?h.diffs[h.diffs.length-1][1]+=k:h.diffs.push(new diff_match_patch.Diff(DIFF_EQUAL,k)));l||a.splice(++d,0,h)}}};diff_match_patch.prototype.patch_toText=function(a){for(var b=[],d=0;d<a.length;d++)b[d]=a[d];return b.join("")};
diff_match_patch.prototype.patch_fromText=function(a){var b=[];if(!a)return b;a=a.split("\n");for(var d=0,c=/^@@ -(\d+),?(\d*) \+(\d+),?(\d*) @@$/;d<a.length;){var e=a[d].match(c);if(!e)throw Error("Invalid patch string: "+a[d]);var f=new diff_match_patch.patch_obj;b.push(f);f.start1=parseInt(e[1],10);""===e[2]?(f.start1--,f.length1=1):"0"==e[2]?f.length1=0:(f.start1--,f.length1=parseInt(e[2],10));f.start2=parseInt(e[3],10);""===e[4]?(f.start2--,f.length2=1):"0"==e[4]?f.length2=0:(f.start2--,f.length2=
parseInt(e[4],10));for(d++;d<a.length;){e=a[d].charAt(0);try{var g=decodeURI(a[d].substring(1))}catch(h){throw Error("Illegal escape in patch_fromText: "+g);}if("-"==e)f.diffs.push(new diff_match_patch.Diff(DIFF_DELETE,g));else if("+"==e)f.diffs.push(new diff_match_patch.Diff(DIFF_INSERT,g));else if(" "==e)f.diffs.push(new diff_match_patch.Diff(DIFF_EQUAL,g));else if("@"==e)break;else if(""!==e)throw Error('Invalid patch mode "'+e+'" in: '+g);d++}}return b};
diff_match_patch.patch_obj=function(){this.diffs=[];this.start2=this.start1=null;this.length2=this.length1=0};
diff_match_patch.patch_obj.prototype.toString=function(){var a=["@@ -"+(0===this.length1?this.start1+",0":1==this.length1?this.start1+1:this.start1+1+","+this.length1)+" +"+(0===this.length2?this.start2+",0":1==this.length2?this.start2+1:this.start2+1+","+this.length2)+" @@\n"];diff_match_patch.prototype.diff_cleanupSplitSurrogates(this.diffs);for(var b=0;b<this.diffs.length;b++){switch(this.diffs[b][0]){case DIFF_INSERT:var d="+";break;case DIFF_DELETE:d="-";break;case DIFF_EQUAL:d=" "}a[b+1]=d+
encodeURI(this.diffs[b][1])+"\n"}return a.join("").replace(/%20/g," ")};this.diff_match_patch=diff_match_patch;this.DIFF_DELETE=DIFF_DELETE;this.DIFF_INSERT=DIFF_INSERT;this.DIFF_EQUAL=DIFF_EQUAL;