Has anyone already implemented a circular buffer in JavaScript? How would you do that without having pointers?
20 Answers
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);},
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.
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)};`);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... :)
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.
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;
}
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));
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;
}
}
/**
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;
}
Related