Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
intmap.js
const WNIL = 0;
const WVAL = 1;
const WBIN = 2;
const WEXT = 3;
var wnil = ({ctr:WNIL});
var wval = (val) => ({ctr:WVAL, val});
var wbin = (lft, rgt) => ({ctr:WBIN, lft, rgt});
var wext = (len, key, map) => ({ctr:WEXT, len, key, map});
const winsert = (len, key, val, wm) => {
switch (wm.ctr) {
case WNIL:
return wext(len, key, wval(val));
case WVAL:
return wext(len, key, wval(val));
case WBIN:
if ((key & 1) === 0) {
return wbin(winsert(len-1, key>>>1, val, wm.lft), wm.rgt);
} else {
return wbin(wm.lft, winsert(len-1, key>>>1, val, wm.rgt));
}
case WEXT:
var slen = 0;
var l0 = len;
var k0 = key;
var l1 = wm.len;
var k1 = wm.key;
while (l0 > 0 && l1 > 0 && !((k0 ^ k1) & 1)) {
slen++;
l0--;
l1--;
k0 = k0 >>> 1;
k1 = k1 >>> 1;
}
if (slen === wm.len) {
return wext(wm.len, wm.key, winsert(len - slen, key >>> slen, val, wm.map));
} else {
var dbit = (key >>> slen) & 1;
var dlen = slen + 1;
if (dbit === 0) {
return wext(slen, key, wbin(
wext( len - dlen, key >>> dlen, wval(val)),
wext(wm.len - dlen, wm.key >>> dlen, wm.map)));
} else {
return wext(slen, key, wbin(
wext(wm.len - dlen, wm.key >>> dlen, wm.map),
wext( len - dlen, key >>> dlen, wval(val))));
}
}
}
};
const wlookup = (len, key, wm) => {
switch (wm.ctr) {
case WNIL:
return null;
case WVAL:
return wm.val;
case WBIN:
if ((key & 1) === 0) {
return wlookup(len - 1, key >>> 1, wm.lft);
} else {
return wlookup(len - 1, key >>> 1, wm.rgt);
}
case WEXT:
return wlookup(len - wm.len, key >>> wm.len, wm.map);
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.