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

Almost 10 years later, an answer using JavaScript ES6:

    class CircularBuffer {
      constructor(bufferLength) {
        this.buffer = [];
        this.pointer = 0;
        this.bufferLength = bufferLength;
      }
      
      push(element) {
        if(this.buffer.length === this.bufferLength) {
           this.buffer[this.pointer] = element;
        } else {
           this.buffer.push(element);
        }
        this.pointer = (this.pointer + 1) % this.bufferLength;
      }
    
      get(i) {
        return this.buffer[i];
      }
      
      //Gets the ith element before last one 
      getLast(i) {
        return this.buffer[this.pointer+this.bufferLength-1-i];
      }
    
    }

//To use it:

let circularBuffer = new CircularBuffer(3);
circularBuffer.push('a');
circularBuffer.push('b');
circularBuffer.push('c');
// should print a,b,c
console.log(`0 element: ${circularBuffer.get(0)}; 1 element: ${circularBuffer.get(1)}; 2 element: ${circularBuffer.get(2)};`);

console.log('Last element: '+circularBuffer.getLast(0)); // should print 'c'

circularBuffer.push('d');

// should print d,b,c
console.log(`0 element: ${circularBuffer.get(0)}; 1 element: ${circularBuffer.get(1)}; 2 element: ${circularBuffer.get(2)};`);

Answer 5

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

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.

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

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

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

Answer 8

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

A lot of answers, but didn't see something like the following functional simple approach... Something like (ES6):

const circularAdd = maxSize => (queue, newItem) =>
  queue.concat([newItem]).slice(Math.max(0, queue.length + 1 - maxSize));

This can be used as a reducer. E.g. in observable streams in scan.

// Suppose newItem$ is a simple new value emitter
const itemBuffer$ = newItem$.pipe(scan(circularAdd(100), []));
// itemBuffer$ will now emit arrays with max 100 items, where the new item is last

edit

Not really an answer to this particular question I see now, cause it doesn't provide a read position... :)

Answer 11

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 12

I recommend using that TypeScript circular array implementation: https://gist.github.com/jerome-benoit/c251bdf872473d1f86ea3a8b90063c90. It is lean and the API is the same as the standard array object.

Answer 13

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 14

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 15

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 16

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 17

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;
}

Answer 18

I prefer simpler approaches. This should be a three-liner, IMO.

Something like

const makeRing = sz                   => ({ sz, buf: new Array(size) }),
      at       = ({sz, buf}, pos)     => buf[pos % sz],
      set      = ({sz, buf}, pos, to) => buf[pos % sz] = to;

Then you can just

const ring = makeRing(10);

ring.buf.fill(1);
set(ring, 35, 'TWO!');

console.log(ring.buf);
console.log(at(ring, 65));

Answer 19

I wasn't doing any perf checks, but as per my understanding sequential array access should be faster than linked list. Also I've noticed that multiple implementations suffer from obsolete prototype based ES3 (at least) style which makes my eyeballs pop. Also none of them support dynamic size increase i.e. "growing". So here's how I see this implementation. Feel free to expand as per your needs:

export class Dequeue<T> {
    private buffer: T[];
    private head: number;
    private tail: number;
    private size: number;

    constructor(initialCapacity: number) {
        this.buffer = [];
        this.buffer.length = initialCapacity;
        this.head = this.tail = this.size = 0;
    }

    public enqueue(value: T): T {
        let next = this.head + 1;
        let buffer = this.buffer;
        let length = buffer.length;

        if (length <= next) {
            next -= length;
        }

        if (buffer.length <= this.size) {
            buffer.length += length;

            for (let index = next; index < length; index++) {
                buffer[index + length] = buffer[index];
            }
        }

        this.size++;
        buffer[this.head] = value;
        this.head = next;

        return value;
    }

    public dequeue(): T | undefined {
        if (this.size > 0) {
            this.size--;

            let buffer = this.buffer;
            let length = buffer.length;
            let value = buffer[this.tail];

            let next = this.tail + 1;

            if (length <= next) {
                next -= length;
            }

            this.tail = next;

            return value;
        } else {
            return undefined;
        }
    }

    public get length() {
        return this.size;
    }
}

To prevent propagation of undefined in the interface I can suggest the following version:

export function Throw(message: string): never {
    throw new Error(message);
}

export class Dequeue<T> {
    private buffer: T[];
    private head: number;
    private tail: number;
    private size: number;

    constructor(initialCapacity: number) {
        this.buffer = [];
        this.buffer.length = initialCapacity;
        this.head = this.tail = this.size = 0;
    }

    public enqueue(value: T): T {
        let next = this.head + 1;
        let buffer = this.buffer;
        let length = buffer.length;

        if (length <= next) {
            next -= length;
        }

        if (buffer.length <= this.size) {
            buffer.length += length;

            for (let index = next; index < length; index++) {
                buffer[index + length] = buffer[index];
            }
        }

        this.size++;
        buffer[this.head] = value;
        this.head = next;

        return value;
    }

    public dequeue(defaultValueFactory: () => T = () => Throw('No elements to dequeue')): T {
        if (this.size > 0) {
            this.size--;

            let buffer = this.buffer;
            let length = buffer.length;
            let value = buffer[this.tail];

            let next = this.tail + 1;

            if (length <= next) {
                next -= length;
            }

            this.tail = next;

            return value;
        } else {
            return defaultValueFactory();
        }
    }

    public get length() {
        return this.size;
    }
}

Answer 20

  /**
    example: [1,2,3].bPush(-1,'a')   //[1,2,3,'a']
                    .bPush(0,'b')    //[1,2,3,'a']
                    .bPush(-1,'c')   //[1,2,3,'a','c']
                    .bPush(3,'e')    //['a','c','e']
    bufferSize zero or undefined does nothing; returns array as is
    bufferSize negative is same as push
    bufferSize > 0 creates a circular buffer appending newest & overwriting oldest
  */
  Array.prototype.bPush = function (bufferSize, newItem) {
    if (!bufferSize) return this;
    if (bufferSize > 0 && this.length >= bufferSize) {
      while( this.length >= bufferSize) this.shift();
    }
    this.push(newItem);
    return this;
  }

Answer 21

I have ported my python library to JavaScript via OpenAI, it's somewhat python-esque, but is highly functional (supports .slice, .extend, a genuine .pop, as well as python style .remove(value). Use .append instead of .push)

class CircularList {
    /** https://stackoverflow.com/questions/4151320/efficient-circular-buffer/40784706#40784706 */
    constructor(size, data = []) {
        if (Array.isArray(size)) {
            this.size = size.length;
            this._data = [...size];
        } else {
            this.size = size;
            this._data = [...data].slice(-size);
        }
        this.end = this._data.length % this.size;
    }

    extend(data) {
        this._data.push(...data);
        this._data = this._data.slice(-this.size);
        this.end = this._data.length % this.size;
    }

    pop(index = -1) {
        /**
         * Remove and return item at index (default last).
         */
        if (this._data.length === 0) {
            throw new Error("pop from empty list");
        }

        const idx = (index + this.end) % this.size;
        const result = this._data.splice(idx, 1)[0];
        this.end = (this.end - 1 + this.size) % this.size;
        return result;
    }

    index(value) {
        try {
            let idx = this._data.indexOf(value);
            idx = (idx - this.end + this.size) % this.size;
            return idx;
        } catch {
            return -1;
        }
    }

    remove(value) {
        const idx = this.index(value);
        if (idx !== -1) {
            this.pop(idx);
        }
    }

    append(value) {
        /** Append an element */
        if (this._data.length === this.size) {
            this._data[this.end] = value;
        } else {
            this._data.splice(this.end, 0, value);
        }
        this.end = (this.end + 1) % this.size;
    }

    asArray() {
        return [...this._data.slice(this.end), ...this._data.slice(0, this.end)];
    }

    get(key = -1) {
        /** Get element by end, relative to the current end */
        let idx;
        key = key >>> 0;
        if (this._data.length === this.size) {
            idx = (key + this.end) % this.size;
        } else {
            idx = key % this._data.length;
        }
        return this._data[idx];
    }

    slice(...args) {
        const result = [];
        for (let i = 0; i < this._data.length; ++i) {
            result.push(this.get(i));
        }
        return Array.prototype.slice.apply(result, args);
    }

    toString() {
        /** Return string representation */
        return `Circular List: ${this.asArray().toString()} (${this._data.length} out of ${this.size} items)`;
    }
}