A circular buffer with timed expiry, useful for tracking real-time activities like mouse/touch positions for gesture detection.

TimedCircularQueue.js

/**
 * Creates a new queue that reuses space and expires elements.
 *
 * This data type is optimized for frequent additions and expirations. One use
 * case is keeping track of mouse/touch positions every frame for gesture
 * detection (instead of, for example, pushing and shifting elements onto /
 * off of an array, which would churn memory).
 *
 * If you frequently need to do something with the values that requires
 * knowing how many values there are, the best approach is usually to walk the
 * values and then check whether there were enough of them. Other approaches
 * like copying the values into an array - even if the array is reused - are
 * usually needlessly inefficient.
 *
 * Usage example:
 *
 * ```javascript
 * var x = new TimedCircularQueue(3000, 5);
 * x.add(1); x.add(2);
 * console.log('Should be [2, 1]');
 * x.walk((v) => console.log(v));
 * x.add(3); x.add(4); x.add(5); x.add(6);
 * console.log('Should be [6, 5, 4, 3, 2]');
 * x.walk((v) => console.log(v));
 * setTimeout(() => {
 *     x.add(7); x.add(8);
 *     setTimeout(() => {
 *         console.log('should be [8, 7]');
 *         x.walk((v) => console.log(v));
 *     }, 2000);
 * }, 2000);
 * ```
 *
 * @param {Number} timeout
 *   The amount of time in milliseconds between when a value is added to the
 *   queue and when it expires. Pass `Infinity` if you don't want elements to
 *   time out, in which case the instance becomes a simple circular buffer.
 * @param {Number} [bufferSize=60]
 *   The size of the circular buffer, i.e. the number of non-expired values
 *   that the queue can hold before it starts expiring old values.
 */
function TimedCircularQueue(timeout, bufferSize) {
    this.buffer = new Array(bufferSize || 60);
    this.index = 0;
    this.timeout = timeout;
}

/**
 * Adds an element to the queue.
 *
 * May expire the oldest value if the buffer is full of non-expired values.
 *
 * @param {} value
 *   The value to add to the queue.
 *
 * @chainable
 */
TimedCircularQueue.prototype.add = function(value) {
    if (typeof this.buffer[this.index] !== 'object') {
        this.buffer[this.index] = Object.create(null);
    }
    this.buffer[this.index].value = value;
    this.buffer[this.index].timestamp = performance.now();
    this.index = (this.index + 1) % this.buffer.length;
    return this;
};

/**
 * Invokes a callback on each non-expired value in the queue.
 *
 * Values do not expire while the queue is being walked. Specifically, the
 * callback will be passed each value that was not expired when the method was
 * called. However, values can expire between walks.
 *
 * Values are encountered in the reverse order in which they were added - that
 * is, the queue is FIFO (first in, first out).
 */
TimedCircularQueue.prototype.walk = function(operation) {
  var l = this.buffer.length,
      i = this.index,
      c = l,
      now = performance.now();
    for (; c > 0; c--) {
        i = (i - 1 + l) % l; // Step backwards and wrap
        // We'll encounter all valid elements before any invalid ones,
        // so we end early if an invalid element is encountered
        if (!this.buffer[i] || now - this.buffer[i].timestamp > this.timeout) {
            return;
        }
        operation(this.buffer[i].value);
    }
};