Circular buffer in JavaScript

javascript data-structures circular-buffer

39,594

Solution 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= {};

Solution 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);},

Solution 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.

Solution 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.

Solution 5

Here's my take. Specifically this is a very simple object implementation of a circular/ring sliding buffer.

A little side note. Despite the fact that people call it similar names, "circular", "ring", "queue", it should be worth clarifying, because they can mean different things.

A ring/circular queue. You can add elements to the head, and crop them from the end. Min size is 0, max size is the size of underlying array. The queue wraps around the underlying array.
The same thing, a queue, FIFO, first-in-first-out, but with variable (indefinite) max size, and implemented using standard push() and unshift() array methods. To add element, you simply push() it onto an array, and to consume element you unshift() it, that's it, pretty standard functions, no need to invent anything.
A sliding buffer of constant size, where new elements are added to the head (right), the buffer slides back (left), and left-most excessive elements are automatically lost. Conceptually it is a sliding buffer, it just happens to get implemented most efficiently as a circular/ring one.

This is the implementation of a (3) kind. This can be used, and is primarily intended, as a back-end of a data visualization widget, e.g. a sliding line graph for real-time monitoring.

The object:

function make_CRS_Buffer(size) {
    return {
        A:  [],
        Ai: 0,
        Asz:    size,
        add:    function(value) {
            this.A[ this.Ai ] = value;
            this.Ai = (this.Ai + 1) % this.Asz;
        },
        forall: function(callback) {
            var mAi = this.A.length < this.Asz ? 0 : this.Ai;
            for (var i = 0; i < this.A.length; i++) {
                callback(this.A[ (mAi + i) % this.Asz ]);
            }

        }
    };
}

Usage:

var buff1 = make_CRS_Buffer(5);

buff1.add(cnt);

buff1.forall(value => {
    b1.innerHTML += value + " ";
});

And, a complete functional example, with two buffers running in parallel:

var b1 = document.getElementById("b1");
var b2 = document.getElementById("b2");

var cnt = 0;

var buff1 = make_CRS_Buffer(5);
var buff2 = make_CRS_Buffer(12);


function add() {
	buff1.add(cnt);
	buff2.add(cnt);
	cnt ++;
	
	b1.innerHTML = "";
	buff1.forall(value => {
		b1.innerHTML += value + " ";
	});
	
	b2.innerHTML = "";
	buff2.forall(value => {
		b2.innerHTML += value + " ";
	});
}

function make_CRS_Buffer(size) {
	return {
		A:	[],
		Ai:	0,
		Asz:	size,
		add:	function(value) {
			this.A[ this.Ai ] = value;
			this.Ai = (this.Ai + 1) % this.Asz;
		},
		forall:	function(callback) {
			var mAi = this.A.length < this.Asz ? 0 : this.Ai;
			for (var i = 0; i < this.A.length; i++) {
				callback(this.A[ (mAi + i) % this.Asz ]);
			}
		
		}
	};
}

<!DOCTYPE html>
<html>
<body>

<h1>Circular/Ring Sliding Buffer</h1>

<p><i>(c) 2020, Leonid Titov</i>

<div id="b1" style="
	background-color: hsl(0,0%,80%);
	padding: 5px;
">empty</div>

<div id="b2" style="
	background-color: hsl(0,0%,80%);
	padding: 5px;
">empty</div>

<br>
<button onclick="add()">Add one more</button>

</body>
</html>

Hope it'll be useful.

View more solutions

39,594