You can learn a-lot about the sneaky ways in which to handle circular buffers by examining this JavaScript code (not mine, only excerpt attached). Ignoring the fact that it's JavaScript, it is an excellent example of how to have a dynamic start and end index, such that if your circular buffer is set to have a size of 10, only indexes 0 through 9 will ever be used.
Note, this also implements an optional callback (this.overflow
) which is called when an element is about to removed from the buffer.
/**
* a circular bufffer
* @class
*/
function CBuffer() {
this.size = this.start = 0;
// set to callback fn if data is about to be overwritten
this.overflow = null;
// emulate Array based on passed arguments
if (arguments.length > 1 || typeof arguments[0] !== 'number') {
this.data = new Array(arguments.length);
this.end = (this.length = arguments.length) - 1;
this.push.apply(this, arguments);
} else {
this.data = new Array(arguments[0]);
this.end = (this.length = arguments[0]) - 1;
}
// need to `return this` so `return CBuffer.apply` works
return this;
}
/** @typedef {*} item */
CBuffer.prototype = {
// properly set constructor
constructor : CBuffer,
/* mutator */
/**
* pop last item
*
* @method
* @this CBuffer
* @returns {item}
*/
pop: function () {
var item;
if (this.size === 0) return void 0;
item = this.data[this.end];
// remove the reference to the object so it can be garbage collected
delete this.data[this.end];
this.end = (this.end - 1 + this.length) % this.length;
this.size--;
return item;
},
/**
* push item to the end
*
* @method
* @this CBuffer
* @returns {item}
*/
push: function () {
var i = 0;
// check if overflow is set, and if data is about to be overwritten
if (this.overflow && this.size + arguments.length > this.length) {
// call overflow function and send data that's about to be overwritten
for (; i < this.size + arguments.length - this.length; i++) {
this.overflow(this.data[(this.end + i + 1) % this.length], this);
}
}
// push items to the end, wrapping and erasing existing items
// using arguments variable directly to reduce gc footprint
for (i = 0; i < arguments.length; i++) {
this.data[(this.end + i + 1) % this.length] = arguments[i];
}
// recalculate size
if (this.size < this.length) {
if (this.size + i > this.length) this.size = this.length;
else this.size += i;
}
// recalculate end
this.end = (this.end + i) % this.length;
// recalculate start
this.start = (this.length + this.end - this.size + 1) % this.length;
// return number current number of items in CBuffer
return this.size;
},
remove: function(predicate, options) {
options = _.defaults(options, {
// whether to quash notification via callback of removal
silent: false,
});
var newData = this.slice();
var removed = _.remove(newData, predicate);
this.fill(null); // delete references
this.data = _.merge(this.data, newData);
this.start = 0;
this.size = newData.length;
this.end = this.size - 1;
if (!options.silent) {
for (var i = 0, len = removed.length; i < len; ++i) {
this.overflow(removed[i], this);
}
}
return removed;
},
torray: function (start, end) {
var length = this.size;
start = Number(start) || 0;
if (start < 0) {
if (start >= end)
return [];
start = (-start > length) ? 0 : length + start;
}
if (end == null || end > length)
end = length;
else if (end < 0)
end += length;
else
end = Number(end) || 0;
length = start < end ? end - start : 0;
var result = Array(length);
for (var index = 0; index < length; index++) {
result[index] = this.data[
(this.start + start + index)
% this.length
];
}
return result;
}