Description
Long time no post, so I'll just casually sneak in how to create a simple ring buffer in JavaScript. As a bonus, we will use the ring buffer class to implement a simple moving average.
Let's get started by looking at the awesome visualisation from the "How it works" part of the Wikipedia page.
As you can see, a ring buffer is a circular form of an array. In the beginning it is empty, then you enqueue values until you reach the end. Once it is full and you perform an enqueue operation, you start overwriting the oldest data. Also notice that there are two pointers; the read pointer (or head) is following the enqueue operations and the write pointer (or tail) is following the dequeue operations. That's the information we need to start implementing it!
class RingBuffer {
constructor(capacity) {
this.buffer = new Array(capacity);
this.capacity = capacity;
this.head = this.tail = this.size = 0;
}
}Nothing special here. I chose Array to make it generic, but you can use anything (I think the most effective would be Uint8Array, or maybe Buffer). I also added a this.size to track the ring buffer's size, which will come in handy once we implement the moving average.
Onto the enqueue() function:
enqueue(data) {
var next = this.head + 1;
if (next >= this.capacity)
next = 0;
if (this.size < this.capacity)
this.size++;
this.buffer[this.head] = data;
this.head = next;
}We increment the head pointer until we reach the capacity, then we start over again. Same with size, but once we reach the capacity we stop changing it.
Add the dequeue() function:
dequeue() {
var data = this.buffer[this.tail],
next = this.tail + 1;
if (next >= this.capacity)
next = 0;
if (this.size > 0)
this.size--;
this.tail = next;
return data;
}This is actually almost the same as enqueue(), except we decrease the size and return data.
We now have a fully working ring buffer, but no way to efficiently iterate through it. Let's make use of some [Symbol.iterator] magic to add a default iterator to our class.
*[Symbol.iterator]() {
for (var i = 0; i < this.size; i++)
yield this.buffer[(this.tail + i) % this.capacity];
}The * denotes a generator function (read more about them in my previous post about generic binary trees).
Let's try it and see if it works...
var rb = new RingBuffer(5);
rb.enqueue(1);
rb.enqueue(2);
rb.enqueue(3);
rb.dequeue();
rb.enqueue(4);
rb.enqueue(5);
rb.enqueue(6);
rb.enqueue(7);
for (var value of rb)
console.log(value);Can you visualise the result before running the code?
Now that we have the ring buffer, implementing a simple moving average is trivial.
function movingAverage(rb) {
var sum = 0;
for (var value of rb)
sum += value;
return sum / rb.size;
}That's all folks. Until next time.