Fix #156

[dirb]

this should fix #156

[kimptoc]

Thanks @dirb . Does it fix the example given in the problem? Could you add a similar test for that to the PR?

[dirb]

@kimptoc I tested it with the built in tests, and also with the example in #156 using with this code:

'use strict';

const jsondiffpatch = require('jsondiffpatch');
const options = {
    objectHash: function (obj) {
        return obj.id || JSON.stringify(obj);
    }
};

const ARRAY_LENGTH = 7000;
const seedData = {
    field1: 'some string data',
    field2: 'some another string data. Este es completa basura escrito en español',
    field3: 'This is a complete garbage and should not be considered even',
    timestamp: Date.now()
};
const LARGE_STRING = 'This becomes much more larger field than it was before. It might even contain unicode characters as well \uFFFF \
                    This one has completely different characters than it used to before \uFFFF';

function createData(){    
    let result = [];
    for (let i=0; i < ARRAY_LENGTH; i++) {
        if(Math.random() > 0.5) {
            result.push(Object.assign({}, seedData, {
                timestamp: Date.now(),
                field1 : LARGE_STRING,
                field3 : LARGE_STRING
            }));
        } else {
            result.push(seedData);
        }        
    }
    return result;    
}

function deepEqual(obj1, obj2) {
  if (obj1 === obj2) {
    return true;
  }
  if (obj1 === null || obj2 === null) {
    return false;
  }
  if ((typeof obj1 === 'object') && (typeof obj2 === 'object')) {
    if (obj1 instanceof Date) {
      if (!(obj2 instanceof Date)) {
        return false;
      }
      return obj1.toString() === obj2.toString();
    }
    if (Array.isArray(obj1)) {
      if (!Array.isArray(obj2)) {
        return false;
      }
      if (obj1.length !== obj2.length) {
        return false;
      }
      var length = obj1.length;
      for (var i = 0; i < length; i++) {
        if (!deepEqual(obj1[i], obj2[i])) {
          return false;
        }
      }
      return true;
    } else {
      if (Array.isArray(obj2)) {
        return false;
      }
    }
    var name;
    for (name in obj2) {
      if (!Object.prototype.hasOwnProperty.call(obj1, name)) {
        return false;
      }
    }
    for (name in obj1) {
      if (!Object.prototype.hasOwnProperty.call(obj2, name) || !deepEqual(obj1[name], obj2[name])) {
        return false;
      }
    }
    return true;
  }
  return false;
};

function testForLargeArray () {
    let largeArray1 = createData();
    let largeArray2 = createData();
    let differ = jsondiffpatch.create(options);
    let diff = differ.diff(largeArray1, largeArray2);
    let patched = jsondiffpatch.patch(jsondiffpatch.clone(largeArray1), diff);
    console.assert(deepEqual(largeArray2, patched));
}
testForLargeArray();

But I'm not familiarised with the tests enough to add it.

[dirb]

Sorry because I didn't write a better description before, this PR reimplement the backtracking function in a iterative way. It works as the recursive version only that it pushes the items in reverse order, but that doesn't afcet it because the items get pushed at the same time that their indices.

I also made others optimizations by doing the comparision of matching items at the begining an the end before doing the matrix, this only would benefit in some cases but will reduce the use of memory on them.