A JavaScript module that finds the most ideal path to change an array to another array.
https://array-diff-items-example.netlify.com/
Most diff detecting library detects "Added", "Removed", "Unchanged" operations.
['Orange', 'Apple', 'Banana']
['Grape', 'Apples', 'Banana']
=>
Removed: Orange
Removed: Apple
Added: Grape
Added: Apples
Unchanged: Banana
Such diff detection might be sufficient in many cases, but sometimes we want to detect "Change" rather than "Remove" then "Add".
['Orange', 'Apple', 'Banana']
['Grape', 'Apples', 'Banana']
=>
Removed: Orange
Added: Grape
Changed: Apple => Apples
Removed: Banana
Added: Melon
array-diff-items solves this problem by introducing "cost" to change. It prefers "Change" when its cost to change a to b is less than simply removing a and adding b.
yarn add array-diff-items
import arrayDiffItems from 'array-diff-items';
// type Compare<T> = (left: T, right: T) => number;
// arrayDiffElements: <T>(left: T[], right: T[]) => (compare: Compare<T>) => DiffItem<T>[];const left = ['Banana', 'Apple', 'Orange', 'Grape'];
const right = [ 'Apple', 'Orange', 'Melon', 'Grape Fruit'];
arrayDiffItems(left, right)((a, b) => {
// Return the cost to change "a" to "b".
// When cost is less than 1, that means changing "a" to "b" is preferable to removing "a" and then adding "a".
if (a === b) return 0;
if (a.startsWith(b) || b.startsWith(a)) return 0.5;
return 2;
});
// [
// {"type":"Removed","item":"Banana"},
// {"type":"Unchanged","item":"Apple"},
// {"type":"Unchanged","item":"Orange"},
// {"type":"Added","item":"Melon"},
// {"type":"Changed","left":"Grape","right":"Grape Fruit"}
// ]This implementation uses O(nm) time and space simple dynamic programming algorithm where n and m is length of input arrays.
In practical situation, this algorithm works resonably well.
Comparing to other efficient algorithms (Wu and Manber's, for exmaple) is the future work.
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent