Skip to main content
clarifying per comment
Source Link

To expand on Loki's comment "Not really a circular buffer as there is no back or front concept implemented here." I have attached a small section of some JavaScript code implementing a dynamic start/end (front/back) that was very useful to me (my head hurts when dealing that kind of "math")

To expand on Loki's comment "Not really a circular buffer as there is no back or front concept implemented here." I have attached a small section of some JavaScript code implementing a dynamic start/end (front/back) that was very useful to me (my head hurts when dealing that kind of "math")

Source Link

You can learn a-lot about the sneaky ways in which to handle circular buffers by examining this JavaScript code (not mine, only excerpt attached). Ignoring the fact that it's JavaScript, it is an excellent example of how to have a dynamic start and end index, such that if your circular buffer is set to have a size of 10, only indexes 0 through 9 will ever be used.

Note, this also implements an optional callback (this.overflow) which is called when an element is about to removed from the buffer.

/**
 * a circular bufffer
 * @class
 */
function CBuffer() {
    this.size = this.start = 0;
    // set to callback fn if data is about to be overwritten
    this.overflow = null;
    // emulate Array based on passed arguments
    if (arguments.length > 1 || typeof arguments[0] !== 'number') {
        this.data = new Array(arguments.length);
        this.end = (this.length = arguments.length) - 1;
        this.push.apply(this, arguments);
    } else {
        this.data = new Array(arguments[0]);
        this.end = (this.length = arguments[0]) - 1;
    }
    // need to `return this` so `return CBuffer.apply` works
    return this;
}


/** @typedef {*} item */

CBuffer.prototype = {
    // properly set constructor
    constructor : CBuffer,

    /* mutator */

    /**
     * pop last item
     *
     * @method
     * @this CBuffer
     * @returns {item}
     */
    pop: function () {
        var item;
        if (this.size === 0) return void 0;
        item = this.data[this.end];
        // remove the reference to the object so it can be garbage collected
        delete this.data[this.end];
        this.end = (this.end - 1 + this.length) % this.length;
        this.size--;
        return item;
    },
    /**
     * push item to the end
     *
     * @method
     * @this CBuffer
     * @returns {item}
     */
    push: function () {
        var i = 0;
        // check if overflow is set, and if data is about to be overwritten
        if (this.overflow && this.size + arguments.length > this.length) {
            // call overflow function and send data that's about to be overwritten
            for (; i < this.size + arguments.length - this.length; i++) {
                this.overflow(this.data[(this.end + i + 1) % this.length], this);
            }
        }
        // push items to the end, wrapping and erasing existing items
        // using arguments variable directly to reduce gc footprint
        for (i = 0; i < arguments.length; i++) {
            this.data[(this.end + i + 1) % this.length] = arguments[i];
        }
        // recalculate size
        if (this.size < this.length) {
            if (this.size + i > this.length) this.size = this.length;
            else this.size += i;
        }
        // recalculate end
        this.end = (this.end + i) % this.length;
        // recalculate start
        this.start = (this.length + this.end - this.size + 1) % this.length;
        // return number current number of items in CBuffer
        return this.size;
    },
    remove: function(predicate, options) {
        options = _.defaults(options, {
            // whether to quash notification via callback of removal
            silent: false, 
        });
        var newData = this.slice();
        var removed = _.remove(newData, predicate);
        this.fill(null); // delete references
        this.data = _.merge(this.data, newData);
        this.start = 0;
        this.size = newData.length;
        this.end = this.size - 1;
        if (!options.silent) {
            for (var i = 0, len = removed.length; i < len; ++i) {
                this.overflow(removed[i], this);
            }
        }
        return removed;
    },
    torray: function (start, end) {
        var length = this.size;

        start = Number(start) || 0;

        if (start < 0) {
            if (start >= end)
                return [];
            start = (-start > length) ? 0 : length + start;
        }

        if (end == null || end > length)
            end = length;
        else if (end < 0)
            end += length;
        else
            end = Number(end) || 0;

        length = start < end ? end - start : 0;

        var result = Array(length);
        for (var index = 0; index < length; index++) {
            result[index] = this.data[
                (this.start + start + index)
                % this.length
            ];
        }
        return result;
    }