Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
// FIXME: glitch doesn't know about Map/Set for some reason
var Map = window['Map'];
var Set = window['Set'];
/**
* @typedef {{i: number, o: *}}
*/
var IntervalData;
const debug = false;
/**
* IntervalSet works with multiple numeric ranges. It allows objects be set over ranges
* and those objects to combine if they are found adjacent.
*
* @template {*} T
*/
export class IntervalSet {
/**
* @param {function(T, (boolean|undefined))} callback to call when an object's data has changed
*/
constructor(callback=() => {}) {
this._callback = callback;
/**
* @private {!Array<IntervalData>}}
*/
this._s = [];
/**
* @private {!Map<T, !Map<IntervalData, IntervalData>>} Map from left side object to right side.
*/
this._m = new Map();
}
/**
* @param {number} v
* @return {?T}
*/
at(v) {
const index = bisectRight(this._s, v)
if ((index % 2) === 0) {
return null; // not within range
}
return this._s[index].o;
}
/**
* @param {T} o
* @return {Array<{start: number, end: number}>}
*/
find(o) {
const m = this._m.get(o);
if (m === undefined) {
return null;
}
const parts = [];
m.forEach((end, start) => {
parts.push({start: start.i, end: end.i});
});
return parts;
}
/**
*/
*ranges() {
const s = this._s;
const l = s.length;
for (let i = 0; i < l; i += 2) {
const p = s[i];
yield {start: p.i, end: s[i+1].i, o: p.o};
}
}
debug() {
console.debug('ranges');
for (const r of this.ranges()) {
console.info(`[${r.start},${r.end}] =>`, r.o);
}
console.debug('objects');
this._m.forEach((_, o) => {
const parts = this.find(o).map(({start, end}) => `${start},${end}`);
console.info(o, 'at', parts.join(','));
});
}
/**
* @return {null|{start: number, end: number}}
*/
extent() {
const s = this._s;
if (s.length === 0) {
return null;
}
return {start: s[0].i, end: s[s.length - 1].i};
}
_findLeftSplit(at, o) {
const s = this._s;
const index = bisectLeft(s, at);
const ar = s[index];
if ((index % 2) === 0 || o === ar.o) {
return {index, mod: null};
} else if (ar.i === at) {
return {index: index + 1, mod: null};
}
// splice new [end,start] at odd index if it differs
// nb. we could just move the previous end 'backwards', but hard to indicate change
s.splice(index, 0,
{i: at, o: ar.o}, // new end value for (index-1)
{i: at, o: null}, // nb. will be replaced
);
this._with(ar.o, (m) => {
// replace prev start => new end above
m.set(s[index - 1], s[index]);
});
return {index: index + 1, mod: ar.o};
}
_findRightSplit(at, o) {
const s = this._s;
const index = bisectRight(s, at);
const ar = s[index - 1];
if ((index % 2) === 0 || o === ar.o) {
return {index, mod: null};
} else if (ar.i === at) {
return {index: index - 1, mod: null};
}
// splice new [end,start] at odd index if it differs
// nb. we could just move the following start 'forwards', but hard to indicate change
s.splice(index, 0,
{i: at, o: null}, // nb. will be replaced
{i: at, o: ar.o}, // new start for next end
);
this._with(ar.o, (m) => {
// remove previous entry that will be replaced
m.delete(s[index-1]); // nb. this happens in clearRemoved _anyway_
// insert new start above => prev end
m.set(s[index+1], s[index+2]);
});
return {index: index + 1, mod: ar.o}; // include what we just spliced
}
/**
* @param {number} start
* @param {number} end
* @param {T} o
* @return {boolean} whether anything was changed
*/
set(start, end, o) {
debug && console.time('set');
if (o == null) {
throw new TypeError('null arg passed to set');
}
const out = this._change(start, end, o);
debug && console.timeEnd('set');
return out;
}
/**
* @param {number} start
* @param {number} end
* @return {boolean} whether anything was changed
*/
clear(start, end) {
return this._change(start, end);
}
/**
* @param {T} o object to remove
* @param {boolean} whether it was removed
*/
remove(o) {
const m = this._m.get(o);
if (m === undefined) {
return false;
}
this._m.delete(o);
// TODO(samthor): (where n=length, m=occurances) This is actually O(n). It could instead be O(mlogn).
let count = m.size;
const s = this._s;
for (let i = 0; i < s.length && count !== 0; ) {
if (s[i].o === o) {
s.splice(i, 2);
--count;
// don't increment, we just removed us
// ... although we should never be adjacent _anyway_, so uhh
} else {
i += 2;
}
}
this._callback(o); // ignore result, already destroyed!
return true;
}
/**
* @param {number} start
* @param {number} end
* @param {?T=} o
* @return {boolean} whether anything was changed
*/
_change(start, end, o=null) {
if (typeof start !== 'number' || typeof end !== 'number' || isNaN(start) || isNaN(end)) {
throw new TypeError('non-number or NaN passed to IntervalSet');
} else if (end <= start) {
return false;
}
let {index: indexLeft, mod: modLeft} = this._findLeftSplit(start, o);
let {index: indexRight, mod: modRight} = this._findRightSplit(end, o);
if (o === null) {
// removal branch
if (indexLeft % 2 || indexRight % 2) {
throw new Error('invalid odd range for remove');
} else if (indexLeft === indexRight) {
if (modLeft || modRight) {
throw new Error('remove had modifications on equal');
}
return false;
}
const removed = this._s.splice(indexLeft, indexRight - indexLeft);
this._cleanup(removed, [modLeft, modRight]);
return true;
}
// addition branch
const alreadyAdded = this._m.has(o);
// nb. if indexes are odd, we're _within_ matching range
if (indexLeft % 2) {
--indexLeft;
start = this._s[indexLeft].i;
}
if (indexRight % 2) {
end = this._s[indexRight].i;
++indexRight;
}
// check if it's the same data
const r = this._s.slice(indexLeft, indexRight);
if (r.length === 2 && r[0].i === start && r[1].i === end && r[0].o === o) {
return false;
}
// replace
debug && console.debug('removed', this._s.slice(indexLeft, indexRight), 'to replace for', start, end);
const leftSide = {i: start, o};
const rightSide = {i: end, o}
this._s.splice(indexLeft, indexRight - indexLeft, leftSide, rightSide);
this._with(o, (m) => m.set(leftSide, rightSide));
if (alreadyAdded) {
this._cleanup(r, [modLeft, modRight, o]);
} else {
this._cleanup(r, [modLeft, modRight], o);
}
return true;
}
/**
* @param {!Array<IntervalData>}} removed
* @param {!Array<?T>} changed
* @param {?T=} anew
*/
_cleanup(removed, changed, anew=null) {
const calls = new Map();
removed.forEach((r, i) => {
if (r.o && (i % 2) === 0) {
// delete all removed left sides
const status = this._with(r.o, (m) => m.delete(r));
calls.set(r.o, status ? undefined : false); // 'undefined' means no real change
}
});
changed.forEach((o) => {
if (o && !calls.has(o)) {
calls.set(o, undefined);
}
});
anew && calls.set(anew, true);
calls.forEach((arg, o) => this._callback(o, arg));
}
/**
* @param {T} o
* @param {!Map<IntervalData, IntervalData>} fn
*/
_with(o, fn) {
const prev = this._m.get(o);
const pass = prev || new Map();
fn(pass);
if (pass.size === 0) {
if (prev !== undefined) {
this._m.delete(o);
}
return false; // completely gone
}
if (prev === undefined) {
this._m.set(o, pass);
}
return true; // something is here
}
}
/**
* @param {!Array<IntervalData>} a
* @param {number} x
* @return {number}
*/
function bisectLeft(a, x) {
let low = 0, high = a.length;
while (low < high) {
const mid = ~~((low + high) / 2);
if (a[mid].i < x) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
/**
* @param {!Array<IntervalData>} a
* @param {number} x
* @return {number}
*/
function bisectRight(a, x) {
let low = 0, high = a.length;
while (low < high) {
const mid = ~~((low + high) / 2);
if (x < a[mid].i) {
high = mid;
} else {
low = mid + 1;
}
}
return low;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment