JavaScript sync two arrays (of objects) / find delta

Question

I have two arrays, old and new, which hold objects at each position. How would I sync or find the delta (i.e. what is new, updated and deleted from the new array compared to the old array)

var o = [
    {id:1, title:"title 1", type:"foo"},
    {id:2, title:"title 2", type:"foo"},
    {id:3, title:"title 3", type:"foo"}
];

var n = [
    {id:1, title:"title 1", type:"foo"},
    {id:2, title:"title updated", type:"foo"},
    {id:4, title:"title 4", type:"foo"}
];

With the above data, using id as the key, we'd find that item with id=2 has an updated title, item with id=3 is deleted, and item with id=4 is new.

Is there an existing library out there that has useful functions, or is it a case of loop and inner loop, compare each row..e.g.

for(var i=0, l=o.length; i<l; i++)
{   
    for(var x=0, ln=n.length; x<ln; x++)
    {
        //compare when o[i].id == n[x].id    
    }  
}

Do this kind of comparison three times, to find new, updated and deleted?

Combe

You could speed things up a little, if the ids are unique and you use an object with the id as keys. – Feoff

You should explain what is the output? An object with three properties? {added: 4], changed: [2], deleted: [3]} – Surcharge

Output would probably be best in three arrays. The deleted would only need IDs, added and changed would need the full "row" / object – Combe

@Feoff the input will always be arrays of objects. I could of course convert them to objects with keys before the comparison starts – Combe

@Fergal: Since they are arrays, is their order important? Or do they represent sets? – Exit

@Bergi: if there is something unique to use as an identifier, then order is not important. I may also want to perform a sync where there is no identifier. In that case order would be important because there is nothing else to find what objects should be compared. – Combe

Answer 1

There's no magic to do what you need. You need to iterate through both objects looking for changes. A good suggestion is to turn your structure into maps for faster searches.

/**
 * Creates a map out of an array be choosing what property to key by
 * @param {object[]} array Array that will be converted into a map
 * @param {string} prop Name of property to key by
 * @return {object} The mapped array. Example:
 *     mapFromArray([{a:1,b:2}, {a:3,b:4}], 'a')
 *     returns {1: {a:1,b:2}, 3: {a:3,b:4}}
 */
function mapFromArray(array, prop) {
    var map = {};
    for (var i=0; i < array.length; i++) {
        map[ array[i][prop] ] = array[i];
    }
    return map;
}

function isEqual(a, b) {
    return a.title === b.title && a.type === b.type;
}

/**
 * @param {object[]} o old array of objects
 * @param {object[]} n new array of objects
 * @param {object} An object with changes
 */
function getDelta(o, n, comparator)  {
    var delta = {
        added: [],
        deleted: [],
        changed: []
    };
    var mapO = mapFromArray(o, 'id');
    var mapN = mapFromArray(n, 'id');    
    for (var id in mapO) {
        if (!mapN.hasOwnProperty(id)) {
            delta.deleted.push(mapO[id]);
        } else if (!comparator(mapN[id], mapO[id])){
            delta.changed.push(mapN[id]);
        }
    }

    for (var id in mapN) {
        if (!mapO.hasOwnProperty(id)) {
            delta.added.push( mapN[id] )
        }
    }
    return delta;
}

// Call it like
var delta = getDelta(o,n, isEqual);

See http://jsfiddle.net/wjdZ6/1/ for an example

Surcharge

Thanks, saves me having to think too hard ;) – Combe

@Combe That's not a good thing, the better thing for you to would be to try it on your own, and then ask questions if you couldn't get it to work. If you can get it to work but want suggestions, then you can ask at codereview.stackexchange.com – Surcharge

Well, I was kind of joking. I did try and got it working mostly (a few more lines required is all) while keeping an eye on this page. But the way you converted the arrays to objects really reduced the lines of code (using hasOwnProperty) – Combe

@JuanMendes I have a similar issue. I have array with more values like this: {id:3, title:"title 3", mobileNumber: "123456789", email: "[email protected]" type:"foo"} . You are checking using a.title == b.title but how do I check when I have more values? – Vina

@satyadev just implement your isEqual with all the required checks – Surcharge

@JuanMendes I'm confused how do I return a Boolean value when a.title==b.title is true and a.email==b.email is false ? – Vina

return a.title==b.title && a.email==b.email – Surcharge

Answer 2

This is typescript version of @Juan Mendes answer

  mapFromArray(array: Array<any>, prop: string): { [index: number]: any } {
    const map = {};
    for (let i = 0; i < array.length; i++) {
      map[array[i][prop]] = array[i];
    }
    return map;
  }

  isEqual(a, b): boolean {
    return a.title === b.title && a.type === b.type;
  }

  getDelta(o: Array<any>, n: Array<any>, comparator: (a, b) => boolean): { added: Array<any>, deleted: Array<any>, changed: Array<any> } {
    const delta = {
      added: [],
      deleted: [],
      changed: []
    };
    const mapO = this.mapFromArray(o, 'id');
    const mapN = this.mapFromArray(n, 'id');
    for (const id in mapO) {
      if (!mapN.hasOwnProperty(id)) {
        delta.deleted.push(mapO[id]);
      } else if (!comparator(mapN[id], mapO[id])) {
        delta.changed.push(mapN[id]);
      }
    }

    for (const id in mapN) {
      if (!mapO.hasOwnProperty(id)) {
        delta.added.push(mapN[id]);
      }
    }
    return delta;
  }

Frowst

Answer 3

Same as @Juan Mendes but for built-in Maps and a bit more efficient (on finding added values)

function mapDelta(oldMap, newMap, compare) {

    var delta = {
        added: [],
        deleted: [],
        changed: []
    };

    var newKeys = new Set(newMap.keys());

    oldMap.forEach(function (oldValue, oldKey) {
        newKeys.delete(oldKey);
        var newValue = newMap.get(oldKey);
        if (newValue == undefined) {
            delta.deleted.push({ key: oldKey, value: oldValue });
            return;
        }
        else if (!compare(oldValue, newValue)) {
            delta.changed.push({ key: oldKey, oldValue: oldValue, newValue: newValue });
        }
    });

    newKeys.forEach(function (newKey) {
        delta.added.push({ key: newKey, value: newMap.get(newKey) });
    });

    return delta;
}

and using typescript

function mapDelta<K, T>(oldMap: Map<K, T>, newMap: Map<K, T>, compare: (a: T, b: T) => boolean) {

  const delta = {
    added: [] as { key: K, value: T }[],
    deleted: [] as { key: K, value: T }[],
    changed: [] as { key: K, oldValue: T, newValue: T }[]
  };

  const newKeys = new Set(newMap.keys());

  oldMap.forEach((oldValue, oldKey) => {
    newKeys.delete(oldKey);
    const newValue = newMap.get(oldKey);
    if (newValue == undefined) {
      delta.deleted.push({ key: oldKey, value: oldValue });
      return;
    } else if (!compare(oldValue, newValue)) {
      delta.changed.push({ key: oldKey, oldValue: oldValue, newValue: newValue });
    }
  })

  newKeys.forEach((newKey) => {
    delta.added.push({ key: newKey, value: newMap.get(newKey) });
  })

  return delta;
}

Wont