Skip to content

Instantly share code, notes, and snippets.

@sebinsua
Last active Aug 14, 2022
Embed
What would you like to do?
function createMultiMap(items, { getKeys } = {}) {
if (typeof getKeys !== "function") {
throw new Error(
"The `getKeys` function passed into `createMultiMap` must be a function."
);
}
function set(m, keys, value) {
if (keys.length === 0) {
return;
}
const [first, ...rest] = keys;
let innerMap = m.has(first) ? m.get(first) : new Map();
m.set(first, innerMap);
for (let [index, key] of rest.entries()) {
if (index === rest.length - 1) {
innerMap.set(key, value);
} else if (!innerMap.has(key)) {
innerMap.set(key, new Map());
}
innerMap = innerMap.get(key);
}
}
const map = items.reduce((m, item) => {
const keys = getKeys(item);
set(m, keys, item);
return m;
}, new Map());
return {
has(keys) {
if (keys.length === 0) {
return false;
}
let has = false;
let innerMap = map;
for (let key of keys) {
if (!innerMap.has(key)) {
has = false;
break;
}
innerMap = innerMap.get(key);
has = true;
}
return has;
},
get(keys) {
if (keys.length === 0) {
return;
}
let innerMap = map;
for (let key of keys) {
if (!innerMap.has(key)) {
return;
}
innerMap = innerMap.get(key);
}
return innerMap;
},
set(keys, value) {
if (keys.length === 0) {
return;
}
set(map, keys, value);
},
};
}
@sebinsua
Copy link
Author

sebinsua commented Aug 14, 2022

I never unit tested the above so I'm sure it might be subtly broken in some way.

Also, I feel it would be a good idea to see whether something like this could be used to create a trie data structure (e.g. following this great article by Chidi Williams). Or, whether it's best to build this as a normal graph.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment