80256
Final Code being produced:
function CircularBuffer(nodeLength) {
// Initialize private data fields
var buffer = new Array(nodeLength),
head = 0,
tail = 0;
// Set default data so that undefined is not returned
for(var j = 0; j < nodeLength; j++) {
buffer[j] = null;
}
// Closure
return {
/// @param node the node inserted into the queue
enqueue: function(node) {
buffer[tail++] = node;
// Set tail pointer to 0 when at the end of the array
tail %= buffer.length;
},
/// @return node the current node where head is set to
dequeue: function() {
var node = null;
// Check if empty before returning nodes
if (!this.empty()) {
node = buffer[head];
// Destroy the processed element
buffer[head++] = null;
}
// Set head pointer to 0 when at the end of the array
head %= buffer.length;
return node;
},
/// @return node the current node where head points to
peek: function() {
return buffer[head];
},
/// @return boolean check if the queue is empty
empty: function() {
return head === tail;
}
};
};The overall code may be daunting but the entire concept is simple as Wikipedia could explain:
Circular Buffers are queues with similar FIFO (First-In-First-Out) processing; however, circular buffers accumulate a fixed amount of space and imitates infinite space by looping through and overriding its previous data slots as demonstrated by the example above.
// Initialize private data fields
var buffer = new Array(nodeLength),
head = 0,
tail = 0;
We begin by initializing the private variables because we don't want direct access to the array as an ADT (Abstract Data Type) should be. The buffer is the array structure which will contain all items (a linked-list can also be used). head is a reading pointer for array and determines the current item to be dequeued; conversely, tail is a writing pointer for the array and determines the current position for the next item to be enqueued.
// Set default data so that undefined is not returned
for(var j = 0; j < nodeLength; j++) {
buffer[j] = null;
}
Here, we want to initialize all of the buffer's slots beforehand because arrays default to undefined when initialized. We set each value to null by default because we'll be using arbitrary data types.
// Closure
return {
...
};
We return an object literal so that we create a closure. In this case, we use closures to make our variables private and all of returned functions public since Javascript does not come equipped with public and private accessor keywords.
/// @param node the node inserted into the queue
enqueue: function(node) {
buffer[tail++] = node;
// Set tail pointer to 0 when at the end of the array
tail %= buffer.length;
},
dequeue: function() {
var node = null;
// Check if empty before returning nodes
if (!this.empty()) {
node = buffer[head];
// Destroy the processed element
buffer[head++] = null;
}
// Set head pointer to 0 when at the end of the array
head %= buffer.length;
return node;
}
Enqueue() and dequeue() go hand-in-hand and comprise the fundamental processes of a queue (Circular Buffer is a type of Queue). Enqueue adds new items to the end of the buffer and dequeue removes elements from the top of the buffer.
tail : item_no : buffer_length
0 : 0 : 4
1 : 1 : 4
2 : 2 : 4
3 : 3 : 4
0 : 4 : 4
The most interesting code is the use of the modulus operator here e.g. tail %= buffer.length which basically sets the tail pointer to zero when at the end of the buffer.
peek: function() {
return buffer[head];
},
empty: function() {
return head === tail;
}Some extra functions include peek and empty as part of the standard Queue methods. Peek checks the current item and empty checks if all items have been processed.
Testing with sample code
var init = function() {
var queue = new CircularBuffer(3);
queue.enqueue('foo');
queue.enqueue('bar');
while(!queue.empty()) {
document.writeln(queue.dequeue());
}
}();Here's a sample self-initializing function that creates a Circular Buffer given a maximum of three items. The string literals: 'foo' and 'bar' are appended to the queue. The final loop displays the circular buffer in order as the items dequeue, resulting in:
foo bar
Conclusion
Circular Buffers aren't difficult to implement as an extension of Queues and are particularly useful for processing arbitrarily large of infinite amounts of data such as data streams. If you like Algorithms, try out the B-Tree Data Structure.
