clock.js

class Clock {
  constructor() {
    this.time = 0;
    this.bucket = new Array(32);
    for (let i = 0; i < 32; i++) {
      this.bucket[i] = [];
    }
    this.dirty = [];
  }

  setTimeout(fn, dt) {
    this._enqueue({
      callback: fn,
      expires: this.time + dt,
    });
  }

  _enqueue(ev) {
    const dt = ev.expires - this.time;
    if (dt <= 0) {
      ev.callback();
      return;
    }
    // bucket[i] contains events to be triggered in 2^i or more ticks. for example,
    // setTimeout(.., 23) will go into bucket[4] since 2^4 <= 23 < 2^5.
    const i = 31 - Math.clz32(dt);
    this.bucket[i].push(ev);
  }

  setTime(time) {
    if (time > this.time) {
      this.tick(time - this.time);
    }
  }

  tick(dt = 1) {
    if (this.dirty.length !== 0) {
      throw new Error('Not re-entrant');
    }
    const t0 = this.time;
    const t1 = this.time + dt;
    this.time = t1;
    // check n buckets for event expiration based on which bits flipped by advancing
    // time. this ensures that bucket[0] is checked every tick, bucket[1] every other
    // tick, ... bucket[i] every 2^i ticks.
    const n = 32 - Math.clz32(t0 ^ t1);
    for (let i = 0; i < n; i++) {
      for (const ev of this.bucket[i]) {
        this.dirty.push(ev);
      }
      this.bucket[i].length = 0;
    }
    // re-enqueue events that may be expired, or insert them into a new bucket
    for (const ev of this.dirty) {
      this._enqueue(ev);
    }
    this.dirty.length = 0;
  }
}