Created
February 20, 2019 07:12
-
-
Save oychao/c9124b18cd1f15ba425d4b5de38985ef to your computer and use it in GitHub Desktop.
keyed list diff algorithm created by charlesouyang - https://repl.it/@charlesouyang/keyed-list-diff-algorithm
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// actions constants | |
const REMOVE = 'REMOVE'; | |
const INSERT = 'INSERT'; | |
const MOVE = 'MOVE'; | |
/** | |
* calculate LIS (positive numbers only) | |
* @param arr array of number | |
*/ | |
const calcLis = function (arr) { | |
const M = [-1]; // marks | |
const P = []; // previous path | |
const S = []; // result sequence | |
let i, left, mid, right, len; | |
for (i = 0; i < arr.length; i++) { | |
if (arr[i] < 0) { | |
continue; | |
} | |
left = 1; | |
right = arr.length; | |
while (left < right) { | |
mid = Math.floor((left + right) / 2); | |
if (arr[M[mid]] <= arr[i]) { | |
left = mid + 1; | |
} else { | |
right = mid; | |
} | |
} | |
M[left] = i; | |
P[i] = M[left - 1]; | |
} | |
len = M.length - 1; | |
i = M[len]; | |
while (i !== -1) { | |
S[len-- - 1] = arr[i]; | |
i = P[i]; | |
} | |
return S; | |
}; | |
/** | |
* trim same elements for two arrays, return deviation counts of beginning | |
* and ending | |
* @param list1 new sequence | |
* @param list2 old sequence | |
*/ | |
const trimTwoLists = function (list1, list2) { | |
let sd = 0; | |
let ed = 0; | |
let idx1 = 0, idx2 = 0; | |
const { length: len1 } = list1; | |
const { length: len2 } = list2; | |
while (sd < len1 && sd < len2 && list1[idx1].key === list2[idx1].key) { | |
sd++; | |
idx1 = sd; | |
idx2 = sd; | |
} | |
idx1 = len1 - ed - 1; | |
idx2 = len2 - ed - 1; | |
while (sd + ed < len1 && sd + ed < len2 && list1[idx1].key === list2[idx2].key) { | |
ed++; | |
idx1 = len1 - ed - 1; | |
idx2 = len2 - ed - 1; | |
} | |
return [sd, ed]; | |
}; | |
/** | |
* diff two arrays of number, Takes O(nlogn) time in expectation | |
* @param list1 array of characters | |
* @param list2 array of characters | |
*/ | |
const diff = function (list1, list2) { | |
const { length: len1 } = list1; | |
const { length: len2 } = list2; | |
const [sd, ed] = trimTwoLists(list1, list2); | |
const PTailIns = []; // tail insertions | |
const PMovs = []; // move patches | |
const IM = new Map(); // index map | |
const IT = new Array(len2 - sd - ed).fill(-1); // key table | |
let shouldMoved = false; // no need to move if LIS.length == IT.length(positive numbers only) | |
let i, j, k, end, last, patch; // other temp variables | |
for (i = sd, end = len2 - ed; i < end; i++) { | |
IM.set(list2[i].key, i); | |
} | |
last = -1; | |
for (i = sd, end = len1 - ed; i < end; i++) { | |
j = IM.get(list1[i].key); | |
if (j !== undefined) { | |
IT[j - sd] = i; | |
if (j < last) { | |
shouldMoved = true; | |
} else { | |
last = j; | |
} | |
} else { | |
list1[i].patch.type = REMOVE; | |
} | |
} | |
const LIS = calcLis(IT); | |
last = IT.length; | |
for (i = len2 - ed - 1, j = LIS.length - 1, end = sd - 1; i > end; i--) { | |
k = i - sd; | |
if (IT[k] === -1) { | |
if (last !== IT.length) { | |
({ patch } = list1[IT[last]]); | |
patch.type = INSERT; | |
(patch.payload = patch.payload || []).push(list2[i]); | |
} else { | |
PTailIns.push(list2[i]); | |
} | |
} else if (shouldMoved) { | |
if (j < 0 || LIS[j] !== IT[k]) { | |
PMovs.push({ type: MOVE, payload: [list2[i], IT[last] === undefined ? len1 : IT[last]] }); | |
} else { | |
j--; | |
} | |
} | |
last = IT[k] === -1 ? last : k; | |
} | |
return [PMovs, PTailIns, list1]; | |
}; | |
/** | |
* normalize sequence | |
* @param strSeq string sequence | |
*/ | |
const prepareData = function (strSeq) { | |
const list = strSeq.split('').map(s => ({ | |
key: s, | |
patch: {}, | |
next: null | |
})); | |
let i, len; | |
for (i = 0, len = list.length - 1; i < len; i++) { | |
list[i].next = list[i + 1]; | |
} | |
return list; | |
}; | |
/** | |
* print sequence | |
* @param seq sequence | |
*/ | |
const printSeq = function (seq) { | |
console.log('SEQ:\t' + seq.reduce((acc, item) => { | |
acc.push(item.key); | |
return acc; | |
}, [])); | |
}; | |
/** | |
* reconcile diffs, here we just print it | |
* @param P position move patches | |
* @param la patched origin list | |
*/ | |
const reconcile = function (P) { | |
const [movs, PTailIns, list] = P; | |
let i, j, len, key, type, payload; | |
for (i = 0, len = movs.length; i < len; i++) { | |
({ payload } = movs[i]); | |
console.log(`move\t${payload[0].key} before ${payload[1]}(index)`); | |
} | |
for (i = PTailIns.length - 1, len = -1; i > len; i--) { | |
console.log(`insert\t${PTailIns[i].key} before ${list.length + PTailIns.length - i - 1}(index)`); | |
} | |
for (i = list.length - 1, len = -1; i > len; i--) { | |
({ key, patch: { type, payload } } = list[i]); | |
if (type === REMOVE) { | |
console.log(`remove\t${key} ${i}`); | |
} else if (type === INSERT) { | |
for (j = payload.length - 1; j > -1; j--) { | |
console.log(`insert\t${payload[j].key} before ${list[i].key}(item)`); | |
} | |
} | |
} | |
}; | |
// test, NOTE: character shall be unique in each sequence | |
const la = prepareData('hagb'); | |
const lb = prepareData('adbgc'); | |
printSeq(la); | |
printSeq(lb); | |
const P = diff(la, lb); | |
reconcile(P); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment