Benutzer:Schnark/js/diff.js/core.js

 (function(global){
 "use strict";
 /*
 This script implements a diff algorithm able to detect block moves.

 Author: Schnark ([https://de.wikipedia.org/wiki/Benutzer:Schnark]) */
 varversion=3.5,/*
 License: choose any of GFDL, CC-by-sa, GPL
 Documentation: [[Benutzer:Schnark/js/diff/core]]

 It doesn't depend on any external library, only the function addEvents()
 requires jQuery to be loaded. This function isn't called internally and
 only serves progressive enhancement.
 <nowiki>
 */

 config={
 charDiff:1,//how often to split up words, 0 to disable
 wordDiffQual:0.3,//quality of a "word diff": 0 -> always show diff on character level ... 1 -> only for very simple cases
 recursion:5,//recursion level, 1 to disable
 tooShort:1,//length of a word to short to be linked on uniqueness
 smallRegion:9,//length (in words/chars) of a region where such a word is considered as long enough
 minMovedLength:10,//minimal length for a block to be considered as moved

 indicateMoves:1,//0: do not show moves, 1: show moved text at new position, 2: show moved text at both positions

 showPar:'¶',//show this sign for deleted/inserted new lines that can't be noticed otherwise
 movedLeft:'^',//or '⧏', show this sign for a block moved left/top
 movedRight:'^',//or '⧐', show this sign for a block moved right/below
 invisible:{//map 'invisible char': 'replacement'
 '\u0000-\u0008\u000B\u000C\u000E-\u001F\u007F-\u009F':true,//set to <span title="U+xxxx">▯</span>
 '\u0009':'<span title="TAB">\u00A0→\u00A0</span>',
 '\u00A0':'<span title="NBSP">\u00A0</span>',
 '\u00AD':'<span title="SHY">▯</span>',
 '\u034F':'<span title="CGJ">▯</span>',
 '\u061C':'\u061C<span title="ALM">▯</span>\u061C',
 '\u1680':'<span title="OGHAM SPACE MARK">\u1680</span>',
 '\u180E':'<span title="MONGOLIAN VOWEL SEPARATOR">\u180E</span>',
 '\u2000':'<span title="EN QUAD">\u2000</span>',
 '\u2001':'<span title="EM QUAD">\u2001</span>',
 '\u2002':'<span title="EN SPACE">\u2002</span>',
 '\u2003':'<span title="EM SPACE">\u2003</span>',
 '\u2004':'<span title="THREE-PER-EM SPACE">\u2004</span>',
 '\u2005':'<span title="FOUR-PER-EM SPACE">\u2005</span>',
 '\u2006':'<span title="SIX-PER-EM SPACE">\u2006</span>',
 '\u2007':'<span title="FIGURE SPACE">\u2007</span>',
 '\u2008':'<span title="PUNCTUATION SPACE">\u2008</span>',
 '\u2009':'<span title="THIN SPACE">\u2009</span>',
 '\u200A':'<span title="HAIR SPACE">\u200A</span>',
 '\u200B':'<span title="ZWSP">▯</span>',
 '\u200C':'<span title="ZWNJ">▯</span>',
 '\u200D':'<span title="ZWJ">▯</span>',
 '\u200E':'\u200E<span title="LRM">▯</span>\u200E',
 '\u200F':'\u200F<span title="RLM">▯</span>\u200F',
 '\u2010':'<span title="HYPHEN">\u2010</span>',
 '\u2011':'<span title="NON-BREAKING HYPHEN">\u2011</span>',
 '\u2012':'<span title="FIGURE DASH">\u2012</span>',
 '\u2013':'<span title="EN DASH">\u2013</span>',
 '\u2014':'<span title="EM DASH">\u2014</span>',
 '\u2015':'<span title="HORIZONTAL BAR">\u2015</span>',
 '\u2028':'<span title="LINE SEPARATOR">▯</span>',
 '\u2029':'<span title="PARAGRAPH SEPARATOR">▯</span>',
 '\u202A':'\u202A<span title="LRE">▯</span>',
 '\u202B':'\u202B<span title="RLE">▯</span>',
 '\u202C':'<span title="PDF">▯</span>\u202C',
 '\u202D':'\u202D<span title="LRO">▯</span>',
 '\u202E':'\u202E<span title="RLO">▯</span>',
 '\u202F':'<span title="NNBSP">\u202F</span>',
 '\u205F':'<span title="MMSP">\u205F</span>',
 '\u2060':'<span title="WJ">▯</span>',
 '\u2061':'<span title="FUNCTION APPLICATION">▯</span>',
 '\u2062':'<span title="INVISIBLE TIMES">▯</span>',
 '\u2063':'<span title="INVISIBLE SEPARATOR">▯</span>',
 '\u2064':'<span title="INVISIBLE PLUS">▯</span>',
 '\u2066':'\u2066<span title="LRI">▯</span>',
 '\u2067':'\u2067<span title="RLI">▯</span>',
 '\u2068':'\u2068<span title="FSI">▯</span>',
 '\u2069':'<span title="PDI">▯</span>\u2069',
 '\u206A':'<span title="INHIBIT SYMMETRIC SWAPPING">▯</span>',
 '\u206B':'<span title="ACTIVATE SYMMETRIC SWAPPING">▯</span>',
 '\u206C':'<span title="INHIBIT ARABIC FORM SHAPING">▯</span>',
 '\u206D':'<span title="ACTIVATE ARABIC FORM SHAPING">▯</span>',
 '\u206E':'<span title="NATIONAL DIGIT SHAPES">▯</span>',
 '\u206F':'<span title="NOMINAL DIGIT SHAPES">▯</span>',
 '\u2212':'<span title="MINUS SIGN">\u2212</span>',
 '\u3000':'<span title="IDEOGRAPHIC SPACE">\u3000</span>',
 '\uFEFF':'<span title="BOM">▯</span>',
 '\uFFF9':'<span title="IAA">\uFFF9</span>',
 '\uFFFA':'<span title="IAS">\uFFFA</span>',
 '\uFFFB':'<span title="IAT">\uFFFB</span>'
 },
 lengthOmit:100,//length that an equal block must reach to be considered as too long to be shown entirely
 lengthOmitPar:20,//minimal number of characters shown before/after a paragraph next to an omited block
 lengthOmitSpace:40,//same, but for break next to space
 lengthOmitOther:50,//same, but for break inside a (probably very long) word
 lengthOmitJoin:20//minimal number of characters that must be omitted, otherwise blocks are joined again
 },

 style={
 equal:'',
 omit:'',
 ins:'text-decoration: none; color: #fff; background-color: #009933;',
 del:'text-decoration: none; color: #fff; background-color: #990033;',
 movedDel:'text-decoration: none; color: #000; background-color: #ff8060;;',
 movedIns:'text-decoration: none; color: #000; background-color: #a0ff99;;',
 movedFrom:'color: #000; text-decoration: none; font-weight: bold;',
 movedTo:'#eaecf0',//background-color
 movedHover:'outline: 1px dashed;',
 movedTarget:'outline: 1px dashed;',
 blocks:[
 ['#000','#ffff80'],//color, background-color
 ['#000','#c0ffff'],
 ['#000','#ffc0e0'],
 ['#000','#a0ffa0'],
 ['#000','#ffd0a0'],
 ['#000','#ffa0a0'],
 ['#000','#a0a0ff'],
 ['#000','#ffbbbb'],
 ['#000','#c0ffa0'],
 ['#000','#d8ffa0'],
 ['#000','#b0a0d0']
 ],
 repeatBlocks:2,//how often to repeat the above colors
 additional:''//additional CSS
 },
 invisibleRe,
 wordSepRe,
 strengthCache={},
 hasOwn=Object.prototype.hasOwnProperty,
 SimpleMap;

 functionhtmlEscape(s){
 returns.replace(/['"<>&]/g,functionescapeCallback(s){
 switch(s){
 case'\'':return'&#039;';
 case'"':return'&quot;';
 case'<':return'&lt;';
 case'>':return'&gt;';
 case'&':return'&amp;';
 }
 });
 }

 /*global mediaWiki, module, define, exports*/
 functionexpose(diff){
 if(typeofmediaWiki==='object'&&typeofmediaWiki.libs==='object'){
 mediaWiki.libs.schnarkDiff=diff;
 if(mediaWiki.hook){
 mediaWiki.hook('userjs.load-script.diff-core').fire(diff);
 }
 }elseif(typeofmodule==='object'){
 module.exports=diff;
 }elseif(typeofdefine==='function'&&define.amd){
 define([],function(){
 returndiff;
 });
 }elseif(typeofexports==='object'){
 exports.schnarkDiff=diff;
 }else{
 global.schnarkDiff=diff;
 }
 }

 //implements all aspects of Map we want to use
 functionSimplePolyfillMap(){
 this.size=0;
 this.values={};
 }

 SimplePolyfillMap.prototype.set=function(key,val){
 this.size=1;//just make sure that size !== 0
 this.values[' '+key]=val;//otherwise things like key === '__proto__' break in Firefox
 };

 SimplePolyfillMap.prototype.get=function(key){
 returnthis.values[' '+key];
 };

 SimplePolyfillMap.prototype.has=function(key){
 return' '+keyinthis.values;
 };

 SimplePolyfillMap.prototype.forEach=function(callback,thisArg){
 varkey;
 for(keyinthis.values){
 if(hasOwn.call(this.values,key)){
 callback.call(thisArg,this.values[key],key.slice(1),this);
 }
 }
 };

 SimpleMap=window.Map&&window.Map.prototype.forEach?window.Map:SimplePolyfillMap;

 functiongetCSS(){
 varcss,i;
 css='.enhanced-diff-equal {'+style.equal+'}';
 css+='.enhanced-diff-omit {'+style.omit+'}';
 css+='ins.enhanced-diff-ins, .insertion-like {'+style.ins+'}';
 css+='del.enhanced-diff-del, .deletion-like {'+style.del+'}';
 css+='del.enhanced-diff-moved-del {'+style.movedDel+'}';
 css+='ins.enhanced-diff-moved-ins {'+style.movedIns+'}';
 css+='a.enhanced-diff-moved-from, a.enhanced-diff-moved-from:visited, a.enhanced-diff-moved-from:hover {'+
 style.movedFrom+'}';
 css+='.enhanced-diff-moved-to, .enhanced-diff-moved-to .enhanced-diff-equal {background-color:'+style.movedTo+';}';
 css+='.enhanced-diff-moved-to ins, .enhanced-diff-moved-to del {border: 3px solid '+style.movedTo+';'+
 'border-left: none; border-right: none;}';
 css+='.enhanced-diff-moved-hover {'+style.movedHover+'}';
 css+='.enhanced-diff-moved-to:target {'+style.movedTarget+'}';
 for(i=0;i<style.blocks.length*style.repeatBlocks;i++){
 css+='.enhanced-diff-block-'+i+','+
 '.enhanced-diff-block-'+i+' .enhanced-diff-equal {color:'+style.blocks[i%style.blocks.length][0]+
 ';background-color:'+style.blocks[i%style.blocks.length][1]+';}';
 css+='.enhanced-diff-block-'+i+' ins, .enhanced-diff-block-'+i+' del {'+
 'border-color:'+style.blocks[i%style.blocks.length][1]+';}';
 }
 css+=style.additional;
 returncss;
 }

 //find the longest increasing subsequence, where longest means highest sum of block lengths
 functionlis(blocks,lengths){
 if(blocks.length===0){
 return[];
 }
 varallSeqs=[],i,j,max,seq;
 for(i=0;i<blocks.length;i++){
 max=-1;
 for(j=0;j<allSeqs.length;j++){
 if(allSeqs[j][0]<blocks[i]){//we could add to this seqence
 if(max===-1||allSeqs[j][1]>allSeqs[max][1]){//it is longer!
 max=j;
 }
 }
 }
 if(max===-1){
 allSeqs.push([blocks[i],lengths[i],[blocks[i]]]);//start a new seqence
 }else{
 seq=[].slice.call(allSeqs[max][2]);//copy
 seq.push(blocks[i]);
 allSeqs.push([blocks[i],allSeqs[max][1]+lengths[i],seq]);
 }
 }
 max=0;
 for(i=1;i<allSeqs.length;i++){
 if(allSeqs[i][1]>allSeqs[max][1]){
 max=i;
 }
 }
 returnallSeqs[max][2];
 }

 //find common prefix/suffix
 /*function commonPrefix (one, two) {
 	var prefix = '';
 	while (one !== '' && two !== '' && one.charAt(0) === two.charAt(0)) {
 		prefix += one.charAt(0);
 		one = one.slice(1);
 		two = two.slice(1);
 	}
 	return prefix;
 }*/
 functioncommonSuffix(one,two){
 varsuffix='';
 while(one!==''&&two!==''&&one.charAt(one.length-1)===two.charAt(two.length-1)){
 suffix=one.charAt(one.length-1)+suffix;
 one=one.slice(0,-1);
 two=two.slice(0,-1);
 }
 returnsuffix;
 }

 functionsplitWords(text){
 returntext.split(wordSepRe).filter(function(x){
 returnx!=='';
 });
 }

 functionconnect(oldWords,newWords,o2n,n2o,oldStart,oldEnd,newStart,newEnd,recursion){
 if(recursion===0){
 return;
 }
 varsmallRegion=(oldEnd-oldStart<=config.smallRegion)&&(newEnd-newStart<=config.smallRegion),
 allWords=newSimpleMap(),
 i,j,
 lookForStart=true,
 nextOldStart,nextOldEnd,nextNewStart,nextNewEnd;

 functionparseWords(words,from,to,conn,which,allWords){//FIXME bottleneck
 vari,j,wicca0,wjcca0,text,texts,textlength,data;
 fori:for(i=from;i<=to;i++){
 if(conn[i]!==-1){//already connected
 continue;
 }
 wicca0=words[i].charCodeAt(0);
 if(wicca0===32||wicca0===13){//only whitespace
 continue;
 }
 texts=[words[i]];
 textlength=words[i].length;//textlength = text.length;
 if(!smallRegion){
 j=i+1;
 while(textlength<=config.tooShort){
 if(j>to||conn[j]!==-1){
 continuefori;
 }
 wjcca0=words[j].charCodeAt(0);
 if(wjcca0===32||wjcca0===13){//only whitespace
 continuefori;
 }
 texts.push(words[j]);
 textlength+=words[j].length;
 j++;
 }
 }
 text=texts.join('');
 if(!allWords.has(text)){
 if(which==='new'){//not in old text
 continue;
 }
 allWords.set(text,{oldCount:1,oldPos:i,newCount:0,newPos:-1});
 }else{
 data=allWords.get(text);
 if(data[which+'Count']===0){
 data[which+'Pos']=i;
 }
 data[which+'Count']++;
 allWords.set(text,data);
 }
 }
 }

 parseWords(oldWords,oldStart,oldEnd,o2n,'old',allWords);
 parseWords(newWords,newStart,newEnd,n2o,'new',allWords);
 if(allWords.size===0){
 return;
 }

 //connect unique words
 allWords.forEach(function(data){
 if(data.oldCount===1&&data.newCount===1){
 o2n[data.oldPos]=data.newPos;
 n2o[data.newPos]=data.oldPos;
 }
 });

 //connect neighbours
 if(o2n[oldStart]===-1&&n2o[newStart]===-1&&oldWords[oldStart]===newWords[newStart]){
 o2n[oldStart]=newStart;
 n2o[newStart]=oldStart;
 }
 for(i=oldStart;i<oldEnd;i++){//connect to right until linebreak
 if(
 o2n[i]!==-1&&//connected
 o2n[i+1]===-1&&//neighbour not connected
 oldWords[i].indexOf('\n')===-1&&//no newline
 n2o[o2n[i]+1]===-1&&//not connected
 oldWords[i+1]===newWords[o2n[i]+1]//equal words
 ){
 o2n[i+1]=o2n[i]+1;
 n2o[o2n[i]+1]=i+1;
 }
 }
 if(o2n[oldEnd]===-1&&n2o[newEnd]===-1&&oldWords[oldEnd]===newWords[newEnd]){
 o2n[oldEnd]=newEnd;
 n2o[newEnd]=oldEnd;
 }
 for(i=oldEnd;i>oldStart;i--){//connect to left
 if(
 o2n[i]!==-1&&//connected
 o2n[i-1]===-1&&//neighbour not connected
 n2o[o2n[i]-1]===-1&&//not connected
 oldWords[i-1]===newWords[o2n[i]-1]//equal words
 ){
 o2n[i-1]=o2n[i]-1;
 n2o[o2n[i]-1]=i-1;
 }
 }
 for(i=oldStart;i<oldEnd;i++){//connect to right
 if(
 o2n[i]!==-1&&//connected
 o2n[i+1]===-1&&//neighbour not connected
 n2o[o2n[i]+1]===-1&&//not connected
 oldWords[i+1]===newWords[o2n[i]+1]//equal words
 ){
 o2n[i+1]=o2n[i]+1;
 n2o[o2n[i]+1]=i+1;
 }
 }

 //resolve islands recursively
 fori:for(i=oldStart;i<=oldEnd;i++){
 if(lookForStart){
 if(o2n[i]===-1){//this could be the next oldStart
 nextOldStart=i;
 lookForStart=false;
 }
 }else{
 if(o2n[i]!==-1){
 nextOldEnd=i-1;
 lookForStart=true;
 //now we have an unresolved island from nextOldStart to nextOldEnd
 if(nextOldStart+2>=nextOldEnd){//too short to be resolvable
 continue;
 }
 //get the corresponding island in the new text
 if(nextOldStart===oldStart){
 nextNewStart=newStart;
 }else{
 nextNewStart=o2n[nextOldStart-1]+1;
 }
 if(nextOldEnd===oldEnd){
 nextNewEnd=newEnd;
 }else{
 nextNewEnd=o2n[nextOldEnd+1]-1;
 }
 if(nextNewStart+2>=nextNewEnd){
 continue;
 }
 for(j=nextNewStart;j<=nextNewEnd;j++){
 if(n2o[j]!==-1){
 continuefori;
 }
 }
 //now we have a coresponding unresolved island from nextNewStart to nextNewEnd
 connect(oldWords,newWords,o2n,n2o,nextOldStart,nextOldEnd,nextNewStart,nextNewEnd,recursion-1);
 }
 }
 }
 }

 functiongetOldBlocks(o2n){
 varret=[],
 last=-1,newBlock=true,
 i;
 for(i=0;i<o2n.length;i++){
 if(o2n[i]===-1){
 newBlock=true;
 ret.push(-1);
 }else{
 if(!newBlock&&o2n[i-1]+1!==o2n[i]){
 newBlock=true;
 }
 if(newBlock){
 newBlock=false;
 last++;
 }
 ret.push(last);
 }
 }
 returnret;
 }
 functiongetNewBlocks(n2o,oldBlocks){
 varret=[],i;
 for(i=0;i<n2o.length;i++){
 if(n2o[i]===-1){
 ret.push(-1);
 }else{
 ret.push(oldBlocks[n2o[i]]);
 }
 }
 returnret;
 }

 functiongetBlockSequence(newBlocks,newChunks){
 varseq=[],len=[],i,current=-1,lastLength=0;
 for(i=0;i<newBlocks.length;i++){
 if(newBlocks[i]!==-1){
 if(newBlocks[i]===current){
 lastLength+=newChunks[i].length;
 }else{
 current=newBlocks[i];
 seq.push(current);
 if(lastLength){
 len.push(lastLength);
 }
 lastLength=newChunks[i].length;
 }
 }
 }
 if(lastLength){
 len.push(lastLength);
 }
 return[seq,len];
 }

 functionrawDiff(oldChunks,newChunks,noMoves){
 vari,o2n=[],n2o=[],oldBlocks,newBlocks,blockSeq,
 ret=[],
 result,
 action='',text='',
 iOld=0,iNew=0,
 commonBlock;

 for(i=0;i<oldChunks.length;i++){
 o2n[i]=-1;
 }
 for(i=0;i<newChunks.length;i++){
 n2o[i]=-1;
 }
 //connect old and new chunks
 connect(oldChunks,newChunks,o2n,n2o,0,oldChunks.length-1,0,newChunks.length-1,config.recursion||1);
 //get the sequence of blocks in the old and new chunks
 oldBlocks=getOldBlocks(o2n);
 newBlocks=getNewBlocks(n2o,oldBlocks);
 result=getBlockSequence(newBlocks,newChunks);
 //longest increasing subsequence = list of blocks that stayed the same
 blockSeq=lis(result[0],result[1]);

 functionout(t,a){
 if(action!==a){
 if((noMoves||text.length<config.minMovedLength)&&(action.charAt(0)==='.'||action.charAt(0)===':')){
 //too short for a move
 action=(action.charAt(0)==='.')?'+':'-';
 }
 if(ret.length>0&&ret[ret.length-1][1]===action){
 ret[ret.length-1][0]+=text;
 }elseif(action!==''){
 ret.push([text,action.charAt(0)]);
 }
 action=a;
 text=t;
 }else{
 text+=t;
 }
 }

 while(iOld<oldBlocks.length||iNew<newBlocks.length){
 if(blockSeq.length===0){
 commonBlock=-2;
 }else{
 commonBlock=blockSeq[0];
 }
 while(iOld<oldBlocks.length&&oldBlocks[iOld]!==commonBlock){
 out(oldChunks[iOld],oldBlocks[iOld]===-1?'-':':'+oldBlocks[iOld]);
 iOld++;
 }
 while(iNew<newBlocks.length&&newBlocks[iNew]!==commonBlock){
 out(newChunks[iNew],newBlocks[iNew]===-1?'+':'.'+newBlocks[iNew]);
 iNew++;
 }
 while(iOld<oldBlocks.length&&oldBlocks[iOld]===commonBlock){
 out(oldChunks[iOld],'=');
 iOld++;
 iNew++;
 }
 if(blockSeq.length>0){
 blockSeq.shift();
 }
 }

 out('','');
 returnret;
 }

 //add numbers to moved blocks
 functionmoveNumbers(diff){
 varnextNumber=0,conn=newSimpleMap(),i,text,action;
 for(i=0;i<diff.length;i++){
 text=diff[i][0];
 action=diff[i][1];
 if(action==='.'||action===':'){
 if(!conn.has(text)){
 conn.set(text,nextNumber++);
 }
 diff[i]=[text,action,conn.get(text)];
 }
 }
 returndiff;
 }

 functionnestedDiff(diff){
 functiongetDot(n){
 vari;
 for(i=0;i<diff.length;i++){
 if(diff[i][1]==='.'&&diff[i][2]===n){
 returni;
 }
 }
 }

 vari=0,j,k,freeNumbers={},old,
 beginColon,beginDot,endColon,endDot,foundEnd,
 colons,dots;
 while(i<diff.length){
 if(diff[i][1]===':'){
 beginColon=i;
 beginDot=getDot(diff[i][2]);
 endColon=beginColon;
 endDot=beginDot;
 foundEnd=false;
 //find sequence of blocks such that all blocks from beginColon to endColon
 //were moved to beginDot to endDot, possibly with insertions/deletions between them
 while(!foundEnd){
 j=endColon+1;
 k=endDot+1;
 if(j<diff.length&&diff[j][1]==='-'){
 j++;
 }
 if(k<diff.length&&diff[k][1]==='+'){
 k++;
 }
 if(
 j<diff.length&&k<diff.length&&
 diff[j][1]===':'&&diff[k][1]==='.'&&
 diff[j][2]===diff[k][2]
 ){
 endColon=j;
 endDot=k;
 }else{
 foundEnd=true;
 }
 }

 if(endColon>beginColon){
 colons=diff[beginColon][0];
 for(j=beginColon+1;j<=endColon;j++){
 if(diff[j][1]===':'){
 colons+=diff[j][0];
 freeNumbers[diff[j][2]]=true;
 }
 }
 dots=[];
 j=beginColon;
 for(k=beginDot;k<endDot;k++){
 if(diff[k][1]==='.'){
 dots.push([diff[k][0],'=']);
 j++;
 if(diff[j][1]==='-'){
 dots.push([diff[j][0],'-']);
 j++;
 }
 }else{//if diff[k][1] === '+'
 dots.push([diff[k][0],'+']);
 }
 }
 dots[0][1]='<';
 dots[0][2]=diff[beginColon][2];
 dots.push([diff[endDot][0],'>']);
 diff.splice(beginColon,endColon-beginColon+1,[colons,':',dots[0][2]]);
 if(beginColon<beginDot){
 beginDot-=endColon-beginColon;
 endDot-=endColon-beginColon;
 }
 dots.unshift(beginDot,endDot-beginDot+1);
 diff.splice.apply(diff,dots);
 if(beginDot<i){
 i-=endDot-beginDot;
 }
 }
 }
 i++;
 }

 //after merging moved blocks some move numbers are now unused,
 //adapt all numbers to use these missing numbers instead of bigger ones
 for(i=0;i<diff.length;i++){
 if(diff[i][1]===':'||diff[i][1]==='.'||diff[i][1]==='<'){
 old=diff[i][2];
 for(jinfreeNumbers){
 if(hasOwn.call(freeNumbers,j)&&j<old){
 diff[i][2]--;
 }
 }
 }
 }
 returndiff;
 }

 //how strong a character divedes a text
 functiongetStrengthReal(char){
 if(char===''){
 return10;
 }
 if(char==='\n'){
 return9;
 }
 if(char===')'){
 return8;
 }
 if('>}]'.indexOf(char)>-1){
 return7;
 }
 if(char===' '){
 return6;
 }
 if('[{|!(,/\\.:;<?¡¿–'.indexOf(char)>-1){
 return5;
 }
 if('"\'«»‘’‚‛""„‟'.indexOf(char)>-1){
 return4;
 }
 if(char.search(/[\u0009\u00A0\u2000-\u200B\u2028\u2029\u202F\u205F-\u2061\u2063\u3000\uFEFF]/)>-1){
 return3;
 }
 if('#&*+-_±'.indexOf(char)>-1){
 return2;
 }
 if(
 char.search(
 /[0-9\u0041-\u005A\u0061-\u007A\u00C0-\u00D6\u00D8-\u00F6\u00F8-\u1FFF\u2C00-\uD7FF\uF900-\uFE1F\uFE30-\uFFEF]/
 )>-1
 ){
 return0;
 }
 return1;
 }
 functiongetStrength(char){
 if(!hasOwn.call(strengthCache,char)){
 strengthCache[char]=getStrengthReal(char);
 }
 returnstrengthCache[char];
 }

 functioncleanBreaks(diff){
 varmovedCount={},i,count,otherCount,type;

 functionshiftcount(index){//calculate the characters to shift
 if(
 index===0||index===diff.length-1||
 diff[index-1][1]!=='='||diff[index+1][1]!=='='||
 '-+.:'.indexOf(diff[index][1])===-1
 ){
 return0;
 }

 varequality1=diff[index-1][0],
 edit=diff[index][0],
 equality2=diff[index+1][0],
 //shift as far left as possible
 suffix=commonSuffix(equality1,edit),
 pos,bestPos,bestScore,char,score;
 if(suffix){
 equality1=equality1.slice(0,-suffix.length);
 edit=suffix+edit.slice(0,-suffix.length);
 equality2=suffix+equality2;
 }

 //go right
 pos=-suffix.length;
 bestPos=pos;
 bestScore=getStrength(equality1.charAt(equality1.length-1));
 while(edit.charAt(0)===equality2.charAt(0)){
 char=edit.charAt(0);
 pos++;
 equality1+=char;
 edit=edit.slice(1)+char;
 equality2=equality2.slice(1);
 score=getStrength(char);
 if(equality2===''){
 score=getStrength('');
 }
 if(score>=bestScore){
 bestScore=score;
 bestPos=pos;
 }
 }
 returnbestPos;
 }

 functiondoshift(index,count){
 if(count===0){
 return;
 }
 vartext=diff[index-1][0]+diff[index][0]+diff[index+1][0];
 diff[index-1][0]=text.slice(0,diff[index-1][0].length+count);
 diff[index][0]=text.slice(diff[index-1][0].length,diff[index-1][0].length+diff[index][0].length);
 diff[index+1][0]=text.slice(text.length-diff[index+1][0].length+count);
 }

 for(i=1;i<diff.length-1;i++){
 count=shiftcount(i);
 if(count===0){
 continue;
 }
 type=diff[i][1];
 if(type==='+'||type==='-'){
 doshift(i,count);
 }
 if(type==='.'||type===':'){
 if(movedCount[diff[i][2]]!==undefined){
 otherCount=movedCount[diff[i][2]][1];
 if(otherCount*count>0){//same direction
 //jscs:disable disallowYodaConditions
 //yes, I shold just update jscs instad
 if(0<count&&otherCount<count){
 count=otherCount;
 }
 if(0>count&&otherCount>count){
 count=otherCount;
 }
 //jscs:enable disallowYodaConditions
 doshift(movedCount[diff[i][2]][0],count);
 doshift(i,count);
 }
 }else{
 movedCount[diff[i][2]]=[i,count];
 }
 }
 }
 returndiff;
 }

 functionwordDiffQual(diff){
 vartotalLength=0,blocks=0,equalLength=0,equalBlocks=0,i;
 for(i=0;i<diff.length;i++){
 if(diff[i][0]===''){
 continue;
 }
 totalLength+=diff[i][0].length;
 blocks++;
 if(diff[i][1]==='='){
 equalLength+=diff[i][0].length;
 equalBlocks++;
 }
 }
 return(2*(equalLength/totalLength)+(equalBlocks/blocks))/3;
 }

 functioncharDiff(diff){
 varret=[],i,j,textDel,textIns,pos,/*common,*/oldChars,newChars,innerDiff;

 functionpush(arr){
 if(ret.length&&ret[ret.length-1][1]===arr[1]&&'.:<>'.indexOf(arr[1])===-1){
 ret[ret.length-1][0]+=arr[0];
 }else{
 ret.push(arr);
 }
 }

 for(i=0;i<diff.length-1;i++){
 if(diff[i][1]==='-'&&diff[i+1][1]==='+'){
 textDel=diff[i][0];
 textIns=diff[i+1][0];
 //simple cases
 if(textDel.indexOf(textIns)>-1){
 pos=textDel.indexOf(textIns);
 if(pos!==0){
 push([textDel.slice(0,pos),'-']);
 }
 push([textIns,'=']);
 if(pos+textIns.length!==textDel.length){
 push([textDel.slice(pos+textIns.length),'-']);
 }
 }elseif(textIns.indexOf(textDel)>-1){
 pos=textIns.indexOf(textDel);
 if(pos!==0){
 push([textIns.slice(0,pos),'+']);
 }
 push([textDel,'=']);
 if(pos+textDel.length!==textIns.length){
 push([textIns.slice(pos+textDel.length),'+']);
 }
 /*			} else if (textDel.charAt(0) === textIns.charAt(0)) {
 				common = commonPrefix(textDel, textIns);
 				push([common, '=']);
 				push([textDel.slice(common.length), '-']);
 				push([textIns.slice(common.length), '+']);
 			} else if (textDel.charAt(textDel.length - 1) === textIns.charAt(textIns.length - 1)) {
 				common = commonSuffix(textDel, textIns);
 				push([textDel.slice(0, textDel.length - common.length), '-']);
 				push([textIns.slice(0, textIns.length - common.length), '+']);
 				push([common, '=']);
 			} else if (suffix of textDel === prefix of textIns) {
 				push([textDel.slice(0, textDel.length - common.length), '-']);
 				push([common, '=']);
 				push([textIns.slice(common.length), '+']);
 			} else if (prefix of textDel === suffix of textIns) {
 				push([textIns.slice(0, textIns.length - common.length), '+']);
 				push([common, '=']);
 				push([textDel.slice(common.length), '-']);*/
 }else{
 //diff on character level
 oldChars=textDel.split('');
 newChars=textIns.split('');
 innerDiff=rawDiff(oldChars,newChars,true);
 if(config.wordDiffQual===0||config.wordDiffQual<=wordDiffQual(innerDiff)){
 //good enough to show it to the user?
 for(j=0;j<innerDiff.length;j++){
 push(innerDiff[j]);
 }
 }else{
 push(diff[i]);
 push(diff[i+1]);
 }
 }
 i++;
 }else{
 push(diff[i]);
 }
 }
 if(i===diff.length-1){
 push(diff[diff.length-1]);
 }
 returnret;
 }

 functiondoDiff(o,n,nested){
 //fix newlines
 o=o.replace(/\r\n?/g,'\n');
 n=n.replace(/\r\n?/g,'\n');

 //trivial changes, we do not cancel common pre/suffixes, this doesn't give clean diffs in some circumstances
 if(o===n){
 return[[o,'=']];
 }
 if(o===''){
 return[[n,'+']];
 }
 if(n===''){
 return[[o,'-']];
 }
 if(n.slice(0,o.length)===o){
 return[[o,'='],[n.slice(o.length),'+']];
 }
 if(o.slice(0,n.length)===n){
 return[[n,'='],[o.slice(n.length),'-']];
 }

 //split into words
 varoldWords=splitWords(o),
 newWords=splitWords(n),
 diff=rawDiff(oldWords,newWords),
 i;

 diff=moveNumbers(diff);

 if(nested){
 diff=nestedDiff(diff);
 }

 //clean up
 for(i=0;i<config.charDiff;i++){
 diff=charDiff(diff);
 }
 diff=cleanBreaks(diff);

 returndiff;
 }

 functionhex(c){
 return'U+'+(c.charCodeAt(0)+0x10000).toString(16).toUpperCase().slice(1);
 }

 functiontoHtml(text,nl,invisible,title){
 varbr=title?'&#10;':'<br />';
 if(nl){
 text=text.replace(/^\n/,config.showPar+'\n')
 .replace(/\n\n$/,'\n'+config.showPar+'\n');
 }
 text=htmlEscape(text);
 if(invisible){
 text=text.replace(invisible,function(c){
 returnconfig.invisible[c]||'<span title="'+hex(c)+'">▯</span>';
 });
 }
 returntext.replace(/^ /,'&nbsp;').replace(/\n /g,br+'&nbsp;').replace(/ {2}/g,' &nbsp;').replace(/\n/g,br);
 }

 functiongetInvisibleRe(){
 varc;
 if(!invisibleRe){
 invisibleRe=[];
 //*sigh* jshint thinks ['['] before a for loop is an
 //array comprehension only available in ES6, so we
 //can't use the simple obvious way (and if you don't
 //sigh at the start of such a comment it thinks you
 //want to set an option)
 invisibleRe.push('[');
 for(cinconfig.invisible){
 if(hasOwn.call(config.invisible,c)){
 invisibleRe.push(c);
 }
 }
 invisibleRe.push(']');
 invisibleRe=newRegExp(invisibleRe.join(''),'g');
 }
 returninvisibleRe;
 }

 functiongetExtract(text,start,end,html){
 varfirst,last;
 if(text.length>=config.lengthOmit){
 first=text.indexOf('\n',config.lengthOmitPar);
 if(first===-1){
 first=text.indexOf(' ',config.lengthOmitSpace);
 }
 if(first===-1){
 first=config.lengthOmitOther;
 }
 last=text.lastIndexOf('\n',text.length-config.lengthOmitPar);
 if(last===-1){
 last=text.lastIndexOf(' ',text.length-config.lengthOmitSpace);
 }
 if(last===-1){
 last=text.length-config.lengthOmitOther;
 }
 if(first+config.lengthOmitJoin<last){
 if(start){
 first=-1;
 }
 if(end){
 last=text.length;
 }
 text=html?
 toHtml(text.slice(0,first+1))+'<span class="enhanced-diff-omit">...</span>'+toHtml(text.slice(last)):
 toHtml(text.slice(0,first+1)+'...'+text.slice(last),false,false,true);
 }else{
 text=toHtml(text,false,false,!html);
 }
 }else{
 text=toHtml(text,false,false,!html);
 }
 returntext;
 }

 functionhtmlDiff(o,n,nested){
 //get diff
 vardiff=doDiff(o,n,nested),
 out=[],
 d,i,text,action,block,
 moved={};

 functionmakeMovedBlockOpen(block){
 return'<span class="enhanced-diff-moved-to enhanced-diff-block-'+block+'" id="moved-block-'+block+'">';
 }

 for(i=0;i<diff.length;i++){
 d=diff[i];
 text=d[0];
 if(text===''){
 continue;
 }
 action=d[1];
 block=d[2];

 if(action===':'&&config.indicateMoves===1){
 text=getExtract(text);
 }elseif(action==='='){
 text=getExtract(text,i===0,i===diff.length-1,true);
 }else{
 text=toHtml(text,true,getInvisibleRe());
 }
 switch(action){
 case'=':
 out.push('<span class="enhanced-diff-equal">'+text+'</span>');
 break;
 case'+':
 out.push('<ins class="enhanced-diff-ins">'+text+'</ins>');
 break;
 case'-':
 out.push('<del class="enhanced-diff-del">'+text+'</del>');
 break;
 case':':
 if(config.indicateMoves===1){
 out.push('<a class="enhanced-diff-moved-from enhanced-diff-block-'+block+'" '+
 'href="#moved-block-'+block+'" title="'+text+'">'+
 config[moved[block]?'movedLeft':'movedRight']+'</a>');
 }elseif(config.indicateMoves===0){
 out.push('<del class="enhanced-diff-del">'+text+'</del>');
 }else{
 out.push('<del class="enhanced-diff-moved-del">'+text+'</del>');
 }
 break;
 case'.':
 moved[block]=true;
 if(config.indicateMoves===1){
 out.push(makeMovedBlockOpen(block)+text+'</span>');
 }elseif(config.indicateMoves===0){
 out.push('<ins class="enhanced-diff-ins">'+text+'</ins>');
 }else{
 out.push('<ins class="enhanced-diff-moved-ins">'+text+'</ins>');
 }
 break;
 case'<':
 out.push(makeMovedBlockOpen(block)+text);
 break;
 case'>':
 out.push(text+'</span>');
 break;
 }
 }
 returnout.join('');
 }

 functionaddEvents($diff,$){
 $=$||jQuery;

 functiongetOther($this){
 varid=$this.attr('href');
 if(id){
 return$diff.find(id);
 }
 id=$this.attr('id');
 return$diff.find('a[href="#'+id+'"]');
 }

 $diff.find('.enhanced-diff-moved-from, .enhanced-diff-moved-to')
 .on('mouseenter',function(){
 var$this=$(this);
 getOther($this).add($this).addClass('enhanced-diff-moved-hover');
 }).on('mouseleave',function(){
 $diff.find('.enhanced-diff-moved-hover').removeClass('enhanced-diff-moved-hover');
 });
 }

 functiongetSet(o){
 return{
 get:function(key){
 varresult={},i;
 if(key===undefined){
 for(keyino){
 if(hasOwn.call(o,key)){
 result[key]=o[key];
 }
 }
 returnresult;
 }
 if(Array.isArray(key)){
 for(i=0;i<key.length;i++){
 result[key[i]]=o[key[i]];
 }
 returnresult;
 }
 returno[key];
 },
 set:function(key,val){
 vark;
 if(val===undefined){
 for(kinkey){
 if(hasOwn.call(key,k)){
 o[k]=key[k];
 }
 }
 }else{
 o[key]=val;
 }
 }
 };
 }

 functionaddInvisible(char,display){
 config.invisible[char]=display;
 invisibleRe=false;
 }

 functionsetWordSep(sep){
 wordSepRe=newRegExp('(['+sep+'])','g');
 }

 setWordSep('\\s×ばつ÷\u2000-\u206F\u3000-\u303F');

 expose({
 version:version,
 lis:lis,//exposed for testing only
 SimplePolyfillMap:SimplePolyfillMap,//exposed for testing only
 SimpleMap:SimpleMap,//exposed for testing only
 getCSS:getCSS,
 diff:doDiff,
 htmlDiff:htmlDiff,
 config:getSet(config),
 style:getSet(style),
 addInvisible:addInvisible,
 setWordSep:setWordSep,
 addEvents:addEvents
 });

 })(this);
 //</nowiki>