Circular buffer in JavaScript

Question

Has anyone already implemented a circular buffer in JavaScript? How would you do that without having pointers?

Answer 1

Strange co-incidence, I just wrote one earlier today! I don't know what exactly your requirements are but this might be of use.

It presents an interface like an Array of unlimited length, but ‘forgets’ old items:

// Circular buffer storage. Externally-apparent 'length' increases indefinitely
// while any items with indexes below length-n will be forgotten (undefined
// will be returned if you try to get them, trying to set is an exception).
// n represents the initial length of the array, not a maximum
function CircularBuffer(n) {
    this._array= new Array(n);
    this.length= 0;
}
CircularBuffer.prototype.toString= function() {
    return '[object CircularBuffer('+this._array.length+') length '+this.length+']';
};
CircularBuffer.prototype.get= function(i) {
    if (i<0 || i<this.length-this._array.length)
        return undefined;
    return this._array[i%this._array.length];
};
CircularBuffer.prototype.set= function(i, v) {
    if (i<0 || i<this.length-this._array.length)
        throw CircularBuffer.IndexError;
    while (i>this.length) {
        this._array[this.length%this._array.length]= undefined;
        this.length++;
    }
    this._array[i%this._array.length]= v;
    if (i==this.length)
        this.length++;
};
CircularBuffer.IndexError= {};

Answer 2

var createRingBuffer = function(length){

  var pointer = 0, buffer = []; 

  return {
    get  : function(key){return buffer[key];},
    push : function(item){
      buffer[pointer] = item;
      pointer = (length + pointer +1) % length;
    }
  };
};

Update: in case you fill the buffer with numbers only, here are some one liner plugins:

min  : function(){return Math.min.apply(Math, buffer);},
sum  : function(){return buffer.reduce(function(a, b){ return a + b; }, 0);},

Answer 3

Like many others, I liked noiv's solution, but I wanted a somewhat nicer API:

var createRingBuffer = function(length){
  /* https://stackoverflow.com/a/4774081 */
  var pointer = 0, buffer = []; 

  return {
    get  : function(key){
        if (key < 0){
            return buffer[pointer+key];
        } else if (key === false){
            return buffer[pointer - 1];
        } else{
            return buffer[key];
        }
    },
    push : function(item){
      buffer[pointer] = item;
      pointer = (pointer + 1) % length;
      return item;
    },
    prev : function(){
        var tmp_pointer = (pointer - 1) % length;
        if (buffer[tmp_pointer]){
            pointer = tmp_pointer;
            return buffer[pointer];
        }
    },
    next : function(){
        if (buffer[pointer]){
            pointer = (pointer + 1) % length;
            return buffer[pointer];
        }
    }
  };
};

Improvements over original:

• get supports default argument (returns last item pushed onto buffer)
• get supports negative indexing (counts from right)
• prev moves buffer back one and returns what's there (like popping without delete)
• next undoes prev (moves buffer forward and returns it)

I used this to store a command history which I could then flip through in an app using its prev and next methods, which nicely return undefined when they have nowhere to go.

Answer 4

This is a quick mockup of the code you could use (it probably isn't working and has bugs in it, but it shows the way it could be done):

var CircularQueueItem = function(value, next, back) {
    this.next = next;
    this.value = value;
    this.back = back;
    return this;
};

var CircularQueue = function(queueLength){
    /// <summary>Creates a circular queue of specified length</summary>
    /// <param name="queueLength" type="int">Length of the circular queue</type>
    this._current = new CircularQueueItem(undefined, undefined, undefined);
    var item = this._current;
    for(var i = 0; i < queueLength - 1; i++)
    {
        item.next = new CircularQueueItem(undefined, undefined, item);
        item = item.next;
    }
    item.next = this._current;
    this._current.back = item;
}

CircularQueue.prototype.push = function(value){
    /// <summary>Pushes a value/object into the circular queue</summary>
    /// <param name="value">Any value/object that should be stored into the queue</param>
    this._current.value = value;
    this._current = this._current.next;
};

CircularQueue.prototype.pop = function(){
    /// <summary>Gets the last pushed value/object from the circular queue</summary>
    /// <returns>Returns the last pushed value/object from the circular queue</returns>
    this._current = this._current.back;
    return this._current.value;
};

using this object would be like:

var queue = new CircularQueue(10); // a circular queue with 10 items
queue.push(10);
queue.push(20);
alert(queue.pop());
alert(queue.pop());

You could of course implement it using array as well with a class that would internally use an array and keep a value of the current item index and moving that one.

Answer 5

I use personally the implementation of Trevor Norris that you can find here: https://github.com/trevnorris/cbuffer

and I'm quite happy with it :-)

Answer 6

Short and sweet:

// IMPLEMENTATION
function CircularArray(maxLength) {
  this.maxLength = maxLength;
}

CircularArray.prototype = Object.create(Array.prototype);

CircularArray.prototype.push = function(element) {
  Array.prototype.push.call(this, element);
  while (this.length > this.maxLength) {
    this.shift();
  }
}

// USAGE
var ca = new CircularArray(2);
var i;

for (i = 0; i < 100; i++) {
  ca.push(i);
}

console.log(ca[0]);
console.log(ca[1]);
console.log("Length: " + ca.length);

Output:

98
99
Length: 2

Answer 7

I couldn't get Robert Koritnik's code to work, so I edited it to the following which seems to work:

    var CircularQueueItem = function (value, next, back) {
        this.next = next;
        this.value = value;
        this.back = back;
        return this;
    };

    var CircularQueue = function (queueLength) {
        /// <summary>Creates a circular queue of specified length</summary>
        /// <param name="queueLength" type="int">Length of the circular queue</type>
        this._current = new CircularQueueItem(undefined, undefined, undefined);
        var item = this._current;
        for (var i = 0; i < queueLength - 1; i++) {
            item.next = new CircularQueueItem(undefined, undefined, item);
            item = item.next;
        }
        item.next = this._current;
        this._current.back = item;

        this.push = function (value) {
            /// <summary>Pushes a value/object into the circular queue</summary>
            /// <param name="value">Any value/object that should be stored into the queue</param>
            this._current.value = value;
            this._current = this._current.next;
        };
        this.pop = function () {
            /// <summary>Gets the last pushed value/object from the circular queue</summary>
            /// <returns>Returns the last pushed value/object from the circular queue</returns>
            this._current = this._current.back;
            return this._current.value;
        };
        return this;
    }

To use:

    var queue = new CircularQueue(3); // a circular queue with 3 items
    queue.push("a");
    queue.push("b");
    queue.push("c");
    queue.push("d");
    alert(queue.pop()); // d
    alert(queue.pop()); // c
    alert(queue.pop()); // b
    alert(queue.pop()); // d
    alert(queue.pop()); // c

Answer 8

I really like how noiv11 solved this and for my need I added an extra property 'buffer' which returns the buffer:

var createRingBuffer = function(length){

  var pointer = 0, buffer = []; 

  return {
    get  : function(key){return buffer[key];},
    push : function(item){
      buffer[pointer] = item;
      pointer = (length + pointer +1) % length;
    },
    buffer : buffer
  };
};

// sample use
var rbuffer = createRingBuffer(3);
rbuffer.push('a');
rbuffer.push('b');
rbuffer.push('c');
alert(rbuffer.buffer.toString());
rbuffer.push('d');
alert(rbuffer.buffer.toString());
var el = rbuffer.get(0);
alert(el);

Answer 9

Instead of implementing circular queue with JavaScript, we can use some inbuilt functions of array to achieve circular queue implementation.

example: Suppose we need to implement the circular queue for length 4.

var circular = new Array();
var maxLength = 4;
var addElementToQueue = function(element){
    if(circular.length == maxLength){
        circular.pop();
    }
    circular.unshift(element);
};
addElementToQueue(1);
addElementToQueue(2);
addElementToQueue(3);
addElementToQueue(4);

Output:

circular [4, 3, 2, 1]

If you try to add another element to this array eg:

addElementToQueue(5);

Output:

circular [5, 4, 3, 2]

Answer 10

One approach would be to use a linked list as others have suggested. Another technique would be to use a simple array as the buffer and to keep track of the read and write positions via indices into that array.

Answer 11

I think you should be able to do this by just using objects. Something like this:

var link = function(next, value) {
    this.next = next;
    this.value = value;
};

var last = new link();
var second = link(last);
var first = link(second);
last.next = first;

Now you'd just store the value in each link's value property.

Answer 12

Thanks noiv for your simple and efficient solution. I also needed to be able to access the buffer like PerS did, but i wanted to get the items in the order they were added. So here's what i ended up with:

function buffer(capacity) {
    if (!(capacity > 0)) {
        throw new Error();
    }

    var pointer = 0, buffer = [];

    var publicObj = {
        get: function (key) {
            if (key === undefined) {
                // return all items in the order they were added
                if (pointer == 0 || buffer.length < capacity) {
                    // the buffer as it is now is in order
                    return buffer;
                }
                // split and join the two parts so the result is in order
                return buffer.slice(pointer).concat(buffer.slice(0, pointer));
            }
            return buffer[key];
        },
        push: function (item) {
            buffer[pointer] = item;
            pointer = (capacity + pointer + 1) % capacity;
            // update public length field
            publicObj.length = buffer.length;
        },
        capacity: capacity,
        length: 0
    };

    return publicObj;
}

Here is the test suite:

QUnit.module("buffer");

QUnit.test("constructor", function () {
    QUnit.expect(4);

    QUnit.equal(buffer(1).capacity, 1, "minimum length of 1 is allowed");
    QUnit.equal(buffer(10).capacity, 10);

    QUnit.throws(
        function () {
            buffer(-1);
        },
        Error,
        "must throuw exception on negative length"
    );

    QUnit.throws(
        function () {
            buffer(0);
        },
        Error,
        "must throw exception on zero length"
    );
});

QUnit.test("push", function () {
    QUnit.expect(5);

    var b = buffer(5);
    QUnit.equal(b.length, 0);
    b.push("1");
    QUnit.equal(b.length, 1);
    b.push("2");
    b.push("3");
    b.push("4");
    b.push("5");
    QUnit.equal(b.length, 5);
    b.push("6");
    QUnit.equal(b.length, 5);
    b.push("7");
    b.push("8");
    QUnit.equal(b.length, 5);
});

QUnit.test("get(key)", function () {
    QUnit.expect(8);

    var b = buffer(3);
    QUnit.equal(b.get(0), undefined);
    b.push("a");
    QUnit.equal(b.get(0), "a");
    b.push("b");
    QUnit.equal(b.get(1), "b");
    b.push("c");
    QUnit.equal(b.get(2), "c");
    b.push("d");
    QUnit.equal(b.get(0), "d");

    b = buffer(1);
    b.push("1");
    QUnit.equal(b.get(0), "1");
    b.push("2");
    QUnit.equal(b.get(0), "2");
    QUnit.equal(b.length, 1);
});

QUnit.test("get()", function () {
    QUnit.expect(7);

    var b = buffer(3);
    QUnit.deepEqual(b.get(), []);
    b.push("a");
    QUnit.deepEqual(b.get(), ["a"]);
    b.push("b");
    QUnit.deepEqual(b.get(), ["a", "b"]);
    b.push("c");
    QUnit.deepEqual(b.get(), ["a", "b", "c"]);
    b.push("d");
    QUnit.deepEqual(b.get(), ["b", "c", "d"]);
    b.push("e");
    QUnit.deepEqual(b.get(), ["c", "d", "e"]);
    b.push("f");
    QUnit.deepEqual(b.get(), ["d", "e", "f"]);
});

Answer 13

Shameless self plug:

If you are looking for a rotating node.js buffer, I wrote one that can be found here: http://npmjs.org/packages/pivot-buffer

Documentation is currently lacking, but RotatingBuffer#push allows you to append a buffer to the current buffer, rotating the previous data if new length is greater than the length specified in the constructor.

Answer 14

Its very easy if you now what Array.prototype.length is:

function CircularBuffer(size) {
  Array.call(this,size); //superclass
  this.length = 0; //current index
  this.size = size; //buffer size
};

CircularBuffer.prototype = Object.create(Array.prototype);
CircularBuffer.prototype.constructor = CircularBuffer;
CircularBuffer.prototype.constructor.name = "CircularBuffer";

CircularBuffer.prototype.push = function push(elem){
  Array.prototype.push.call(this,elem);
  if (this.length >= this.size) this.length = 0;
  return this.length;
}

CircularBuffer.prototype.pop = function pop(){
  var r = this[this.length];
  if (this.length <= 0) this.length = this.size;  
  this.length--;
  return r;
}