- commit
- 1b79334855f8bc9ca06e40fc0668a6549ddbe739
- parent
- b9f0a416993dce0b78dbe57d7d7c68ed987f0bcf
- Author
- Tobias Bengfort <tobias.bengfort@posteo.de>
- Date
- 2020-05-03 12:29
simplify fuzzy
Diffstat
| M | static/context.mjs | 61 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++--- |
| D | static/fuzzy.mjs | 182 | ------------------------------------------------------------ |
2 files changed, 58 insertions, 185 deletions
diff --git a/static/context.mjs b/static/context.mjs
@@ -1,5 +1,3 @@1 -1 import * as fuzzy from './fuzzy.mjs';2 -13 1 var applyExact = function(text, [pos, before, after], selection) { 4 2 if (pos >= 0 && text.slice(pos).startsWith(before)) { 5 3 if (selection) { @@ -16,6 +14,63 @@ var applyExact = function(text, [pos, before, after], selection) { 16 14 } 17 15 }; 18 16 -1 17 var fuzzyMerge = function(s1, s2) { -1 18 // https://en.wikipedia.org/wiki/Longest_common_subsequence_problem -1 19 -1 20 var ret = ''; -1 21 var m = []; -1 22 var i; -1 23 var j; -1 24 -1 25 for (i = 0; i < s1.length; i++) { -1 26 m.push([]); -1 27 for (j = 0; j < s2.length; j++) { -1 28 m[i].push(-1); -1 29 } -1 30 } -1 31 -1 32 var getM = (ii, jj) => { -1 33 if (ii < 0 || jj < 0) { -1 34 return 0; -1 35 } -1 36 if (m[ii][jj] === -1) { -1 37 if (s1[ii] === s2[jj]) { -1 38 m[ii][jj] = getM(ii - 1, jj - 1) + 1; -1 39 } else { -1 40 m[ii][jj] = Math.max(getM(ii, jj - 1), getM(ii - 1, jj)); -1 41 } -1 42 } -1 43 return m[ii][jj]; -1 44 }; -1 45 -1 46 i = s1.length - 1; -1 47 j = s2.length - 1; -1 48 -1 49 while (i >= 0 && j >= 0) { -1 50 if (s1[i] === s2[j]) { -1 51 ret = s1[i] + ret; -1 52 i -= 1; -1 53 j -= 1; -1 54 } else if (getM(i, j - 1) > getM(i - 1, j)) { -1 55 ret = s2[j] + ret; -1 56 j -= 1; -1 57 } else { -1 58 ret = s1[i] + ret; -1 59 i -= 1; -1 60 } -1 61 } -1 62 while (j >= 0) { -1 63 ret = s2[j] + ret; -1 64 j -= 1; -1 65 } -1 66 while (i >= 0) { -1 67 ret = s1[i] + ret; -1 68 i -= 1; -1 69 } -1 70 -1 71 return ret; -1 72 }; -1 73 19 74 export var apply = function(text, [pos, before, after], selection) { 20 75 // try exact match 21 76 try { @@ -43,7 +98,7 @@ export var apply = function(text, [pos, before, after], selection) { 43 98 var ctxStart = Math.max(pos - ctxLen, 0); 44 99 var ctxEnd = Math.min(pos + before.length + ctxLen, text.length); 45 100 var ctx = text.slice(ctxStart, ctxEnd);46 -1 var ctxAfter = fuzzy.mergeText(before, after, ctx);-1 101 var ctxAfter = fuzzyMerge(after, ctx); 47 102 return applyExact(text, [ctxStart, ctx, ctxAfter], selection); 48 103 }; 49 104
diff --git a/static/fuzzy.mjs b/static/fuzzy.mjs
@@ -1,182 +0,0 @@1 -1 var intersectRetain = function(a, b) {2 -1 var parts = [];3 -1 a.filter(Array.isArray).forEach(pa => {4 -1 b.filter(Array.isArray).forEach(pb => {5 -1 var start = Math.max(pa[0], pb[0]);6 -1 var end = Math.min(pa[1], pb[1]);7 -1 if (start < end) {8 -1 parts.push([start, end]);9 -1 }10 -1 });11 -1 });12 -1 return parts;13 -1 };14 -115 -1 var getInsertions = function(parts) {16 -1 var ret = [];17 -1 var pos = 0;18 -1 parts.forEach(part => {19 -1 if (Array.isArray(part)) {20 -1 pos += part[1] - part[0];21 -1 } else {22 -1 ret.push([pos, part]);23 -1 pos += part.length;24 -1 }25 -1 });26 -1 return ret;27 -1 };28 -129 -1 var normalize = function(parts) {30 -1 var ret = [];31 -1 parts.forEach(part => {32 -1 if (Array.isArray(part)) {33 -1 if (ret.length && Array.isArray(ret[ret.length - 1])) {34 -1 var last = ret[ret.length - 1];35 -1 if (part[0] <= last[1]) {36 -1 var start = Math.min(part[0], last[0]);37 -1 var end = Math.max(part[1], last[1]);38 -1 ret[ret.length - 1] = [start, end];39 -1 } else {40 -1 ret.push(part);41 -1 }42 -1 } else {43 -1 ret.push(part);44 -1 }45 -1 } else {46 -1 if (ret.length && !Array.isArray(ret[ret.length - 1])) {47 -1 ret[ret.length - 1] += part;48 -1 } else {49 -1 ret.push(part);50 -1 }51 -1 }52 -1 });53 -1 return ret;54 -1 };55 -156 -1 var merge = function(a, b) {57 -1 if (!a || !b) {58 -1 return a || b;59 -1 }60 -161 -1 var parts = [];62 -163 -1 getInsertions(a).forEach(ins => {64 -1 parts.push(ins);65 -1 });66 -1 getInsertions(b).forEach(ins => {67 -1 parts.push(ins);68 -1 });69 -1 intersectRetain(a, b).forEach(part => {70 -1 parts.push(part);71 -1 });72 -173 -1 parts.sort((x, y) => x[0] - y[0]);74 -1 parts = parts.map(part => Number.isInteger(part[1]) ? part : part[1]);75 -176 -1 return normalize(parts);77 -1 };78 -179 -1 var apply = function(s, parts) {80 -1 if (!parts) {81 -1 return s;82 -1 }83 -1 var ret = '';84 -1 parts.forEach(part => {85 -1 if (Array.isArray(part)) {86 -1 ret += s.slice(part[0], part[1]);87 -1 } else {88 -1 ret += part;89 -1 }90 -1 });91 -1 return ret;92 -1 };93 -194 -1 var diff = function(s1, s2) {95 -1 // https://en.wikipedia.org/wiki/Longest_common_subsequence_problem96 -1 if (s1 === s2) {97 -1 return null;98 -1 }99 -1100 -1 var parts = [];101 -1 var m = [];102 -1 var i;103 -1 var j;104 -1105 -1 for (i = 0; i < s1.length; i++) {106 -1 m.push([]);107 -1 for (j = 0; j < s2.length; j++) {108 -1 m[i].push(-1);109 -1 }110 -1 }111 -1112 -1 var getM = (ii, jj) => {113 -1 if (ii < 0 || jj < 0) {114 -1 return 0;115 -1 }116 -1 if (m[ii][jj] === -1) {117 -1 if (s1[ii] === s2[jj]) {118 -1 m[ii][jj] = getM(ii - 1, jj - 1) + 1;119 -1 } else {120 -1 m[ii][jj] = Math.max(getM(ii, jj - 1), getM(ii - 1, jj));121 -1 }122 -1 }123 -1 return m[ii][jj];124 -1 };125 -1126 -1 i = s1.length - 1;127 -1 j = s2.length - 1;128 -1129 -1 while (i >= 0 && j >= 0) {130 -1 if (s1[i] === s2[j]) {131 -1 parts.unshift([i, i + 1]);132 -1 i -= 1;133 -1 j -= 1;134 -1 } else if (getM(i, j - 1) > getM(i - 1, j)) {135 -1 parts.unshift(s2[j]);136 -1 j -= 1;137 -1 } else {138 -1 i -= 1;139 -1 }140 -1 }141 -1 while (j >= 0) {142 -1 parts.unshift(s2[j]);143 -1 j -= 1;144 -1 }145 -1146 -1 return normalize(parts);147 -1 };148 -1149 -1 export var mergeText = function(base, text1, text2) {150 -1 var a = diff(base, text1);151 -1 var b = diff(base, text2);152 -1 var combined = merge(a, b);153 -1 return apply(base, combined);154 -1 };155 -1156 -1157 -1 var assertEqual = function(a, b, msg) {158 -1 if (JSON.stringify(a) !== JSON.stringify(b)) {159 -1 console.warn('test failed:', msg, a, b);160 -1 }161 -1 };162 -1163 -1 var a = [[0, 2], 'si', [7, 8]];164 -1 var b = [[0, 1], 'e', [6, 7], 'ow'];165 -1166 -1 assertEqual(normalize(['foo', 'bar']), ['foobar'], 'normalize');167 -1 assertEqual(normalize([[1, 5], [3, 6]]), [[1, 6]], 'normalize');168 -1 assertEqual(normalize([[1, 3], [3, 6]]), [[1, 6]], 'normalize');169 -1 assertEqual(normalize([[1, 3], [4, 6]]), [[1, 3], [4, 6]], 'normalize');170 -1 assertEqual(normalize([[1, 3], [2, 3]]), [[1, 3]], 'normalize');171 -1172 -1 assertEqual(merge(a, b), [[0, 1], 'esiow'], 'merge');173 -1 assertEqual(merge(b, a), [[0, 1], 'esiow'], 'merge');174 -1175 -1 assertEqual(apply('baseball', a), 'basil', 'apply(a)');176 -1 assertEqual(apply('baseball', b), 'below', 'apply(b)');177 -1178 -1 // assertEqual(diff('baseball', 'basil'), a, 'diff(a)');179 -1 // assertEqual(diff('baseball', 'below'), b, 'diff(b)');180 -1 assertEqual(diff('', 'asd'), ['asd'], 'diff("", "asd")');181 -1182 -1 assertEqual(mergeText('asd', 'asd.', 'Asd'), 'Asd.', 'mergeText');