How to get incremental changes between two arrays?

Question

I have a list of items in array, and the number of items are many(more than 100s).

The items in array are updated by user interactions(add, remove, update).

What I want to do is to find incremental changes between the previous and the after array state, so that users can recover and forward between the previous array status and next array status.

This is achievable by saving the before and the after state of the array object. However if the number of items are too many, saving the array object could be waste of memory and it may affect the performance.

My idea is to find incremental changes between before and after, and save only the differences as the following format.

Before: [0,1,2,3]
After:  [1,3,5]
Diff:
[
  ['delete', 0, 0], // [action, index, item]
  ['delete', 1, 2],
  ['insert', 2, 5]
]

I have searched Google and Stackoverflow for this purpose, but answers what I have found was not the exactly what I want.

I would appreciate if I can get some tips from anyone who has tried this way. If my approach was wrong, any criticism would be also helpful.

Answer 1

You could try implementing apply and revert functions for your actions.

function applyMutation(arr, action, index, item) {
  if (action === 'delete') {
    const copy = [...arr];
    copy.splice(index, 1);
    return copy;
  } else if (action === 'insert') {
    const copy = [...arr];
    copy.splice(index, 0, item);
    return copy;
  } else {
    throw new Error(`Invalid action: ${action}`);
  }
}

function revertMutation(arr, action, index, item) {
  if (action === 'delete') {
    const copy = [...arr];
    copy.splice(index, 0, item);
    return copy;
  } else if (action === 'insert') {
    const copy = [...arr];
    copy.splice(index, 1);
    return copy;
  } else {
    throw new Error(`Invalid action: ${action}`);
  }
}

const start = [0, 1, 2, 3];

const mutations = [
  ['delete', 0, 0],
  ['delete', 1, 2],
  ['insert', 2, 5],
];

const applied = mutations.reduce(
  (arr, mutation) => applyMutation(arr, ...mutation),
  start
);

console.log(applied);

const reverted = mutations.reduceRight(
  (arr, mutation) => revertMutation(arr, ...mutation),
  applied
);

console.log(reverted);

If you prefer to do thins in a more object-oriented way, you could do it like this:

class Mutation {
  constructor(index, item) {
    this.index = index;
    this.item = item;
  }

  copy(arr) {
    return [...arr];
  }

  apply(arr) {
    throw new Error('Apply not implemented');
  }

  revert(arr) {
    throw new Error('Revert not implemented');
  }
}

class Delete extends Mutation {
  apply(arr) {
    const copy = this.copy(arr);
    copy.splice(this.index, 1);
    return copy;
  }

  revert(arr) {
    const copy = this.copy(arr);
    copy.splice(this.index, 0, this.item);
    return copy;
  }
}

class Insert extends Mutation {
  apply(arr) {
    const copy = this.copy(arr);
    copy.splice(this.index, 0, this.item);
    return copy;
  }

  revert(arr) {
    const copy = this.copy(arr);
    copy.splice(this.index, 1);
    return copy;
  }
}

const start = [0, 1, 2, 3];

const mutations = [new Delete(0, 0), new Delete(1, 2), new Insert(2, 5)];

const applied = mutations.reduce((arr, mutation) => mutation.apply(arr), start);

console.log(applied);

const reverted = mutations.reduceRight(
  (arr, mutation) => mutation.revert(arr),
  applied
);

console.log(reverted);

You mentioned you wanted to get the needed mutations to get from one array to another. This is an interesting problem. There are, in theory, an infinite number of possible mutations to get from one to the other, and even when restricting yourself to the minimum number needed, there are often multiple solutions. However, you could try something like this.

function applyMutation(arr, action, index, item) {
  if (action === 'delete') {
    const copy = [...arr];
    copy.splice(index, 1);
    return copy;
  } else if (action === 'insert') {
    const copy = [...arr];
    copy.splice(index, 0, item);
    return copy;
  } else {
    throw new Error(`Invalid action: ${action}`);
  }
}

function revertMutation(arr, action, index, item) {
  if (action === 'delete') {
    const copy = [...arr];
    copy.splice(index, 0, item);
    return copy;
  } else if (action === 'insert') {
    const copy = [...arr];
    copy.splice(index, 1);
    return copy;
  } else {
    throw new Error(`Invalid action: ${action}`);
  }
}

function getNeededMutations(from, to) {
  // Get the items that are in 'from' but not in 'to'
  const toDelete = subtractArrays(from, to);

  if (toDelete.length) {
    const firstToDelete = toDelete[0];
    const firstToDeleteIdx = from.indexOf(firstToDelete);
    const mut = ['delete', firstToDeleteIdx, firstToDelete];
    const applied = applyMutation(from, ...mut);

    return [mut, ...getNeededMutations(applied, to)];
  }

  // Get the items that are in 'to' but not in 'from'
  const toInsert = subtractArrays(to, from);

  if (toInsert.length) {
    const firstToInsert = toInsert[0];
    const firstToInsertIdx = to.indexOf(firstToInsert);
    const mut = ['insert', firstToInsertIdx, firstToInsert];
    const applied = applyMutation(from, ...mut);

    return [mut, ...getNeededMutations(applied, to)];
  }

  return [];
}

function subtractArrays(arr1, arr2) {
  const arr2Copy = [...arr2];
  return arr1.filter((v) => {
    const idx = arr2Copy.indexOf(v);

    if (idx === -1) {
      return true;
    }

    arr2Copy.splice(idx, 1);

    return false;
  });
}

const start = [0, 1, 2, 3];

const end = [1, 3, 5];

const needed = getNeededMutations(start, end);

console.log(`Needed mutations: ${JSON.stringify(needed)}`);

const applied = needed.reduce((acc, mut) => {
  return applyMutation(acc, ...mut);
}, start);

console.log(`Array after applying mutations: ${JSON.stringify(applied)}`);

This approach basically starts by deleting everything not needed, then inserting everything missing.