/*
 * Javascript Diff Algorithm
 *  By John Resig (http://ejohn.org/)
 *  Modified by Chu Alan "sprite"
 *  Modified further by Allan Tokuda for patent diffs
 *
 * More Info:
 *  http://ejohn.org/projects/javascript-diff-algorithm/
 * 
 * License: Creative Commons Attribution 2.5
 * http://creativecommons.org/licenses/by/2.5/
 *
 *  You are free:
 *
 *      * to Share - to copy, distribute and transmit the work
 *      * to Remix - to adapt the work
 *
 *  Under the following conditions:
 *
 *      * Attribution. You must attribute the work in the manner specified by
 *        the author or licensor (but not in any way that suggests that they
 *        endorse you or your use of the work).
 *
 */

function escape(s) {
    var n = s;
    n = n.replace(/&/g, "&");
    n = n.replace(/</g, "&lt;");
    n = n.replace(/>/g, "&gt;");
    n = n.replace(/"/g, "&quot;");

    return n;
}

function diffString( o, n ) {
  /* delete trailing whitespace */
  o = o.replace(/\s+$/, '');
  n = n.replace(/\s+$/, '');

  /* delete HTML tags */
//  o = o.replace(/<[^>]+>/g, '');
//  n = n.replace(/<[^>]+>/g, '');

  /* split into word array */
  var out = diff(o == "" ? [] : o.split(/\s+|\s*<[^>]+>\s*/g), n == "" ? [] : n.split(/\s+|\s*<[^>]+>\s*/g) );
  var str = "";

  /* keep a list of spacings between words for string reconstruction later */
  var oSpace = o.match(/\s+|\s*<[^>]+>\s*/g); 
  if (oSpace == null) { oSpace =   ["\n"]; } 
  else                { oSpace.push("\n"); }

  var nSpace = n.match(/\s+|\s*<[^>]+>\s*/g);
  if (nSpace == null) { nSpace =   ["\n"]; } 
  else                { nSpace.push("\n"); }

  /* construct output string "str", including <ins>ertion tags and <del>etion tags */
  if (out.n.length == 0) {
      //for (var i = 0; i < out.o.length; i++) {
      //  str += '<del>' + escape(out.o[i]) + oSpace[i] + "</del>";
      //}
  } else {
    if (out.n[0].text == null) {
      //for (n = 0; n < out.o.length && out.o[n].text == null; n++) {
      //  str += '<del>' + escape(out.o[n]) + oSpace[n] + "</del>";
      //}
    }

    for ( var i = 0; i < out.n.length; i++ ) {
      if (out.n[i].text == null) {
        str += '<ins>' + escape(out.n[i]) + nSpace[i] + "</ins>";
      } 
      else {
        var pre = "";

        //for (n = out.n[i].row + 1; n < out.o.length && out.o[n].text == null; n++ ) {
        //  pre += '<del>' + escape(out.o[n]) + oSpace[n] + "</del>";
        //}
        str += " " + out.n[i].text + nSpace[i] + pre;
      }
    }
  }
  
  return str;
}

function randomColor() {
    return "rgb(" + (Math.random() * 100) + "%, " + 
                    (Math.random() * 100) + "%, " + 
                    (Math.random() * 100) + "%)";
}
function diffString2( o, n ) {
  o = o.replace(/\s+$/, '');
  n = n.replace(/\s+$/, '');

  var out = diff(o == "" ? [] : o.split(/\s+/), n == "" ? [] : n.split(/\s+/) );

  var oSpace = o.match(/\s+|\s*((<[^>]+>)\+\s*)+/g);
  if (oSpace == null) {
    oSpace = ["\n"];
  } else {
    oSpace.push("\n");
  }
  var nSpace = n.match(/\s+|\s*((<[^>]+>)\+\s*)+/g);
  if (nSpace == null) {
    nSpace = ["\n"];
  } else {
    nSpace.push("\n");
  }

  var os = "";
  var colors = new Array();
  for (var i = 0; i < out.o.length; i++) {
      colors[i] = randomColor();

      if (out.o[i].text != null) {
          os += '<span style="background-color: ' +colors[i]+ '">' + 
                escape(out.o[i].text) + oSpace[i] + "</span>";
      } else {
          os += "<del>" + escape(out.o[i]) + oSpace[i] + "</del>";
      }
  }

  var ns = "";
  for (var i = 0; i < out.n.length; i++) {
      if (out.n[i].text != null) {
          ns += '<span style="background-color: ' +colors[out.n[i].row]+ '">' + 
                escape(out.n[i].text) + nSpace[i] + "</span>";
      } else {
          ns += "<ins>" + escape(out.n[i]) + nSpace[i] + "</ins>";
      }
  }

  return { o : os , n : ns };
}


/* accepts two arrays of words, old and new */
/* returns ... */

function diff( o, n ) {

  /* create index of word locations */

  var ns = new Object();
  var os = new Object();

  for ( var i = 0; i < n.length; i++ ) {
    if ( ns[ n[i] ] == null )
         ns[ n[i] ] = { rows: new Array(), o: null };
    ns[ n[i] ].rows.push( i );
  }
  
  for ( var i = 0; i < o.length; i++ ) {
    if ( os[ o[i] ] == null )
         os[ o[i] ] = { rows: new Array(), n: null };
    os[ o[i] ].rows.push( i );
  }
  
  /* find each word that occurs exactly once in each string, and 
     add an attribute for where the word occurs in the opposite string. */

  for ( var i in ns ) {
    if ( ns[i].rows.length == 1 && typeof(os[i]) != "undefined" && os[i].rows.length == 1 ) {
      n[ ns[i].rows[0] ] = { text: n[ ns[i].rows[0] ], row: os[i].rows[0] };
      o[ os[i].rows[0] ] = { text: o[ os[i].rows[0] ], row: ns[i].rows[0] };
    }
  }

  /* loop forwards through the new string;
     for each word marked as occurring once, 
     that is followed by a word NOT marked, 
     and whose connecting word in the old string is followed by a word that
        exists,
        is also not marked,
        and is the same word,
        
            add another reference between those following words.
     */
  
  for ( var i = 0; i < n.length - 1; i++ ) {
    if ( n[i].text != null && n[i+1].text == null && n[i].row + 1 < o.length && o[ n[i].row + 1 ].text == null && 
         n[i+1] == o[ n[i].row + 1 ] ) {
      n[i+1] = { text: n[i+1], row: n[i].row + 1 };
      o[n[i].row+1] = { text: o[n[i].row+1], row: i + 1 };
    }
  }

  /* and repeat above looping backwards. */
  
  for ( var i = n.length - 1; i > 0; i-- ) {
    if ( n[i].text != null && n[i-1].text == null && n[i].row > 0 && o[ n[i].row - 1 ].text == null && 
         n[i-1] == o[ n[i].row - 1 ] ) {
      n[i-1] = { text: n[i-1], row: n[i].row - 1 };
      o[n[i].row-1] = { text: o[n[i].row-1], row: i - 1 };
    }
  }
  
  return { o: o, n: n };
}