In javascript a Map allows uniquely retrieving a “value” based on a single associated “key” – like so:
let m = new Map();
m.set('a', 'my value');
let v = m.get('a'); // v === 'my value'
How can we implement a data structure which uses multiple unordered keys to retrieve an associated value? In such a case the “key” value would always be an array. Let’s call this a “CompoundMap”. Let’s allow a CompoundMap to be instantiated with a “width” value, giving a fixed-size for its compound keys. Like Map, the values used in CompoundMap keys should be able to be anything (e.g. String, Number, Object, Regex, ClientRequest… whatever) E.g.:
let cm = new CompoundMap({ width: 2 });
cm.set([ 'a', 1 ], 'my value');
let v1 = cm.get([ 'a', 1 ]); // v1 === 'my value'
let v2 = cm.get([ 1, 'a' ]); // v2 === 'my value'
let v3 = cm.get([ 'a', 2 ]); // v3 === undefined
let v4 = cm.get([ 'b', 1 ]); // v4 === undefined
let v5 = cm.get([ 2, 'a' ]); // v5 === undefined
let v6 = cm.get([ 1, 'b' ]); // v6 === undefined
One way I can think of is to use a nested trees of Maps:
class CompoundMap {
constructor({ width, entries }) {
if (!width && entries) width = entries[0]?.[0]?.length;
if (!width) throw Error('Must provide "width"');
Object.assign(this, { width, tree: new Map() });
for (let [ cmpKey, val ] of entries ?? []) this.set(cmpKey, val);
}
* treeSearch(tree, cmpKey) {
if (cmpKey.length === 0) throw Error('Compound key should have at least one item');
// A `cmpKey` with length 1 is our "base case"; return the "tree" we reached, and the final key
if (cmpKey.length === 1) return yield { tree, finalKey: cmpKey[0] };
for (let [ n, key ] of cmpKey.entries()) {
let subtree = tree.get(key);
// If no `subtree`, `key` doesn't apply at this current depth
if (!subtree) continue;
// We found a `subtree` - we still need to process the remaining key, which is `cmpKey` with `key` removed
let cmpKeyMinusKey = (() => {
let copy = [ ...cmpKey ];
copy.splice(n, 1); // `n` is the index of `key` in `copy`
return copy;
})();
// Now recursively search for the rest of the key! Note `yield*` helps us implement backtracking - a
// search down some specific chain of subtrees may not succeed, but the overall search could still
// succeed when another chain of subtrees is able to fully consume the `cmpKey`
// (This is also why the runtime for this approach will be horrible...)
yield* this.treeSearch(subtree, cmpKeyMinusKey);
}
}
set(cmpKey, val) {
if (cmpKey.length !== this.width) throw Error(`Compound key must have exactly ${this.width} item(s)`);
let preexisting = this.treeSearch(this.tree, cmpKey).next().value;
if (preexisting) {
// Overwrite existing item
// `this.treeSearch` yields `{ tree, finalKey }`, so overwriting is very simple
let { tree, finalKey } = preexisting;
tree.set(finalKey, val);
} else {
// Write new item
let tree = this.tree;
for (let k of cmpKey.slice(0, -1)) {
if (!tree.has(k)) tree.set(k, new Map());
tree = tree.get(k);
}
tree.set(cmpKey.at(-1), val);
}
return this;
}
get(cmpKey) {
if (cmpKey.length !== this.width) throw Error(`Compound key must have exactly ${this.width} item(s)`);
let preexisting = this.treeSearch(this.tree, cmpKey).next().value;
if (!preexisting) return undefined;
let { tree, finalKey } = preexisting;
return tree.get(finalKey);
}
}
let obj1 = { desc: 'obj' };
let obj2 = { desc: 'obj' };
let tests = [
{
entries: [
{ cmpKey: [ 'a', 1 ], val: 'my value' },
],
lookups: [
{ cmpKey: [ 'a', 1 ], expected: 'my value' },
{ cmpKey: [ 1, 'a' ], expected: 'my value' },
{ cmpKey: [ 'a', 2 ], expected: undefined },
{ cmpKey: [ 'b', 1 ], expected: undefined },
{ cmpKey: [ 2, 'a' ], expected: undefined },
{ cmpKey: [ 1, 'b' ], expected: undefined }
]
},
{
entries: [
{ cmpKey: [ 'a', 'b', 'c' ], val: obj1 },
{ cmpKey: [ 'c', 'd', 'e' ], val: obj2 }
],
lookups: [
{ cmpKey: [ 'a', 'd', 'e' ], expected: undefined },
{ cmpKey: [ 'c', 'b', 'a' ], expected: obj1 },
{ cmpKey: [ 'd', 'e', 'c' ], expected: obj2 }
]
}
];
for (let { entries, lookups } of tests) {
let cm = new CompoundMap({ entries: entries.map(({ cmpKey, val }) => [ cmpKey, val ]) });
for (let { cmpKey, expected } of lookups) {
let received = cm.get(cmpKey);
if (received !== expected) {
console.log(`Test Failed! Expected [ ${cmpKey.join(', ')} ] -> ${JSON.stringify(expected)} ... BUT GOT ${JSON.stringify(received)}`);
} else {
console.log(`Test Passed! [ ${cmpKey.join(', ')} ] -> ${JSON.stringify(expected)}`);
}
}
}If you follow the above logic, however, you will see that the runtime is horrible – I think it’s at least exponential (O(2^n)). Can a CompoundMap be implemented more efficiently?
If we could somehow map arbitrary values to BigInts, through a function like getUniqueIntFor, we could map compound keys to single unique Strings:
let compoundKey = [ 1, 2, 'j', /my regex/u, { arr: [] }, new HttpServer() ];
let uniqueString = compoundKey
.map(anyValue => getUniqueIntFor(anyValue).toString(36))
.sort()
.join('.');
Given this ability, it’s arbitrary to implement CompoundMap. But how to implement getUniqueIntFor?
Is this idea worthwhile?
Otherwise, how can I implement CompoundMap more efficiently?