Ring buffers and moving averages

[mateogianolio]

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.

[ebhc]

Unfortunately something is wrong with your implementation. At the end of the example sequence of pushes and pops, i would expect the for loop to produce 3,4,5,6,7 as its lines of output. But as it stands, it produces 7,3,4,5,6.

Also, if subsequent to your example, you pop, 7 comes off as expected (leaving 3,4,5,6 as the iterator's lines of output as expected). But if you then push 8, instead of the iterator outputting 8,3,4,5,6, it outputs 8,4,5,6,7 instead, with 3 being overwritten when there should have been space for it and the popped 7 magically reappearing.

Evidently this is a tricky thing to get right. :) Good luck.

EDIT: Hmm. There seems to be some confusion here between push/pop and enqueue/dequeue. In a stack, if you do a push immediately followed by a pop, it should pop what you just pushed. But in your example, when you pop after pushing 3, it pops 1. So you "pop" from the wrong end of the structure, effectively making your "push" an enqueue and your "pop" a dequeue...

[mateogianolio]

You are right of course. pop and push only make sense when dealing with stacks and not with queues, which is essentially what a ring buffer is (also called a circular queue). Sorry for the confusion. I will edit the article in a moment. Thanks for your comment!