intervalset.js

// 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;
}