Circular Buffer

A circular buffer, cyclic buffer or ring buffer is a data structure that uses a single, fixed-size buffer as if it were connected end-to-end.

The useful property of a circular buffer is that it does not need to have its elements shuffled around when one is consumed. (If a non-circular buffer were used then it would be necessary to shift all elements when one is consumed.) In other words, the circular buffer is well-suited as a FIFO buffer while a standard, non-circular buffer is well suited as a LIFO buffer.

Wikipedia

var buffer = new CircularBuffer(5); //an empty circular buffer of size 5

Methods

getIterator()

This method returns an iterator for scanning the buffer. The iterator is useful in order to get a full decoupling in your classes. This avoid, to the class that uses the iterator, to know what type of data structure stores the data.

var buffer = new CircularBuffer(5);
var it = buffer.getIterator();
for(it.first(); !it.isDone(); it.next()) {
  var item = it.getItem();
  //do something
}

The iterator starts from the oldest item stored in the buffer.

Complexity: O(1)

write(item)

This method writes the item at the head of the buffer. The item could be whatever you want.

var buffer = new CircularBuffer(3);
buffer.write(0); //buffer contains (from the oldelst item) 0
buffer.write(1); //buffer contains (from the oldelst item) 0, 1
buffer.write(2); //buffer contains (from the oldelst item) 0, 1, 2
buffer.write(3); //buffer contains (from the oldelst item) 1, 2, 3

Complexity: O(1)

free(from, to)

This method frees all the position from the position from and to the position to of the buffer. If from is lower than to, the method free all but the positions from the position to to the position from.

var buffer = new CircularBuffer(5);
buffer.write(0); //buffer contains (from the oldelst item) 0
buffer.write(1); //buffer contains (from the oldelst item) 0, 1
buffer.write(2); //buffer contains (from the oldelst item) 0, 1, 2
buffer.write(3); //buffer contains (from the oldelst item) 0, 1, 2, 3
buffer.write(4); //buffer contains (from the oldelst item) 0, 1, 2, 3, 4
buffer.free(0, 2); //buffer contains (from the oldelst item) 2, 3, 4
buffer.write(5); //buffer contains (from the oldelst item) 2, 3, 4
buffer.write(6); //buffer contains (from the oldelst item) 2, 3, 4, 5, 6
buffer.free(3, 1); //buffer contains (from the oldelst item) 3, 4

Complexity: O(n)

freeAll()

This method frees all the position of the buffer.

var buffer = new CircularBuffer(5);
buffer.write(0); //buffer contains (from the oldelst item) 0
buffer.write(1); //buffer contains (from the oldelst item) 0, 1
buffer.write(2); //buffer contains (from the oldelst item) 0, 1, 2
buffer.freeAll(); //buffer is empty

Complexity: O(1)

read(index)

This method reads the item stored at the position index. If the index is out of bound, then will be calculate the module of the index, so it will be a valid position.

var buffer = new CircularBuffer(4);
buffer.write(0);
buffer.write(1);
buffer.write(2);
buffer.write(3);
buffer.read(2); //2
buffer.read(-1); //3
buffer.read(8); //0

Complexity: O(1)

isEmpty()

This method checks if the buffer is empty or not.

var buffer = new CircularBuffer(3);
buffer .isEmpty() //true
buffer .write(2);
buffer .write(4);
buffer .isEmpty(); //false

Complexity: O(1)

isFull()

This method checks if the buffer is full or not.

var buffer = new CircularBuffer(3);
buffer .isFull() //false
buffer .write(2);
buffer .write(4);
buffer .write(6);
buffer .isFull(); //true

isFull: O(1)

clone()

This method returns a clone of the buffer. The items are cloned only if there's a method clone() to invoke, otherwise they will be shared with the old buffer. This problem there is not if items are not object.

var buffer= new CircularBuffer(5);
buffer.write(2);
buffer.write(3);
buffer.write(4);
buffer.write(5);
var clone = buffer.clone(); //clone contains (from the oldest item) 2, 3, 4, 5

Complexity: O(n)

resize(size)

This method resize the buffer. If the new size is greater than the older, then possible item stored before the position of the tail will be written immediatly after the head position. Instead, if the new size is lower than the older, only oldest will be preserved.

var buffer= new CircularBuffer(2);
buffer.write(2);
buffer.write(3);
buffer.write(4); //buffer contains (from the index 0) 4, 3
buffer.resize(4); //buffer contains (from the index 0) empty, 3, 4, empty
buffer.write(5);
buffer.write(6); //buffer contains (from the index 0) 6, 3, 4, 5
buffer.resize(3); //buffer contains (from the index 0) 5, 3, 4

Complexity: O(n)