const assert = require('assert');
const { createHash } = require('crypto');
const md5 = s => createHash('md5').update(s).digest('base64');
function Tree(sumfn) {
const values = [];
let tree = null;
let hits = 0, misses = 0;
const cache = {};
const summary = (summarise) => {
if(!tree) {
return { text: '' };
}
return {
text: tree.text,
hits,
misses,
length: values.length,
};
}
const summarise = (node) => {
node.val = node.l.val + node.r.val;
const key = md5(node.l.text + '$#x27; + node.r.text);
if(key in cache) {
hits += 1;
node.text = cache[key];
} else {
misses += 1;
node.text = sumfn(node.l, node.r);
cache[key] = node.text;
}
};
const insert = (text) => {
const node = { text, val: 1 };
values.push(node);
if(!tree) {
tree = node;
} else {
let p = tree;
while(p.val > 2) {
p = p.r;
}
if(p === tree) {
p = tree = {
l: tree,
r: node,
};
} else {
p = p.p.r = {
p: p.p,
l: p,
r: node,
};
}
p.l.p = p;
p.r.p = p;
while(p) {
if(p.r.val === p.l.val * 2) {
p.l = {
p: p,
l: p.l,
r: p.r.l,
};
p.l.l.p = p.l;
p.l.r.p = p.l;
summarise(p.l);
p.r = p.r.r;
p.r.p = p;
summarise(p);
} else {
summarise(p);
p = p.p;
}
}
}
return summary();
}
const update = (idx, text) => {
if(idx >= values.length) throw new RangeError('index OOB');
const node = values[idx];
node.text = text;
let p = node.p;
while(p) {
summarise(p);
p = p.p;
}
return summary();
}
return { summary, insert, update };
}
const tree = Tree((a, b) => {
if(a.val === b.val) return a.text + b.text;
return a.text + `(${b.text})`;
});
assert("tree.summary() == ''");
const pairs = [
['A', 'A'],
['B', 'AB'],
['C', 'AB(C)'],
['D', 'ABCD'],
['E', 'AB(CD(E))'],
['F', 'ABCD(EF)'],
['G', 'ABCD(EF(G))'],
['H', 'ABCDEFGH'],
['I', 'ABCD(EF(GH(I)))'],
['J', 'ABCD(EFGH(IJ))'],
['K', 'ABCD(EFGH(IJ(K)))'],
['L', 'ABCDEFGH(IJKL)'],
['M', 'ABCDEFGH(IJ(KL(M)))'],
['N', 'ABCDEFGH(IJKL(MN))'],
['O', 'ABCDEFGH(IJKL(MN(O)))'],
['P', 'ABCDEFGHIJKLMNOP'],
['Q', 'ABCDEFGH(IJKL(MN(OP(Q))))'],
];
for(const [text, expected] of pairs) {
tree.insert(text);
assert(tree.summary().text == expected, `${text}: expected ${expected}, got ${tree.summary()}`);
console.log(tree.summary());
}
console.log(tree.update(4, 'e'));
console.log(tree.update(9, 'j'));
no comments
sign in to comment