Attempt at Circular Buffer - Javascript

Question

Right! Here is my attempt at a circular buffer (For use in a graphing program, using the canvas element). Have yet to get round to testing it out.

Question is - Can anyone see any flaws in my logic? Or bottlenecks?

/**
*   A circular buffer class.
*   @To add value -> bufferObject.addValue(xValue, yValue);
*   @To get the First-in value use -> bufferObject.getValue(0);
*   @To get the Last-in value use -> bufferObject.getValue(bufferObject.length);
**/

var circularBuffer = function (bufferSize) {

    this.bufferSize = bufferSize;
    this.buffer = new Array(this.bufferSize); // After testing on jPerf -> 2 x 1D array seems fastest solution.

    this.end = 0;
    this.start = 0;

    // Adds values to array in circular.
    this.addValue = function(xValue, yValue) {
        this.buffer[this.end] = {x : xValue, y: yValue};
        if (this.end != this.bufferSize) this.end++;
        else this.end = 0;
        if(this.end == this.start) this.start ++;
    };

    // Returns a value from the buffer
    this.getValue = function(index) {

        var i = index+this.start;

        if(i >= this.bufferSize) i -= this.bufferSize; //Check here.

        return this.buffer[i]
    };

    // Returns the length of the buffer
    this.getLength = function() {
        if(this.start > this.end || this.start == this.bufferSize) {
            return this.xBuffer.length;
        } else {
            return this.end - this.start;
        }
    };

    // Returns true if the buffer has been initialized.
    this.isInitialized = function() {
        if(this.end != this.start) return true;
        else return false;
    };
}

Please feel free to reuse this code.

Updated twice (and tested!).

Yes, the index into the buffer is calculated too often in this.getValue. x and y pairs run together so you should be able to get point = this.buffer[index]; y = point.y x=point.x or similar. — vogomatix
– vogomatix, Commented Nov 21, 2013 at 11:24
Thanks for the quick reply! Not sure if I understand it wholly yet. Might make more sense to me after this coffee. — User2
– User2, Commented Nov 21, 2013 at 11:32
Got it. Do you mean adding a variable like... [convertIndex = index+this.start;] and then reusing that. If so, done. Thanks! — User2
– User2, Commented Nov 21, 2013 at 11:34
My sexy rewrite -> [ this.getValue = function(index) { var i = index+this.start; if(i >= this.bufferSize) i -= this.bufferSize; return { x : this.xBuffer[i], y : this.yBuffer[i], }; };] — User2
– User2, Commented Nov 21, 2013 at 11:40
Thats a start :-), but I think you can also merge xBuffer and yBuffer into simply buffer. It's also best to edit your original question as you make changes and just simply note you've updated it — vogomatix
– vogomatix, Commented Nov 21, 2013 at 11:42

Community · Accepted Answer · 2017-05-23 11:51:05Z

1

Update: Found another implementation Circular buffer in JavaScript

Made class variables private, corrected old xBuffer reference. Will do more edits tonight.

/**
*   A circular buffer class.
*   @To add value -> bufferObject.addValue(xValue, yValue);
*   @To get the First-in value use -> bufferObject.getValue(0);
*   @To get the Last-in value use -> bufferObject.getValue(bufferObject.length);
**/

var circularBuffer = function (buffer_size) {

    var bufferSize = buffer_size;
    var buffer = new Array(bufferSize); // After testing on jPerf -> 2 x 1D array seems fastest solution.

    var end = 0;
    var start = 0;

    // Adds values to array in circular.
    this.addValue = function(xValue, yValue) {
        buffer[end] = {x : xValue, y: yValue};
        if (end != bufferSize) end++;
        else end = 0;
        if(end == start) start++;
    };

    // Returns a value from the buffer
    this.getValue = function(index) {

        var i = index+start;

        if(i >= bufferSize) i -= bufferSize; //Check here.

        return buffer[i];
    };

    // Returns the length of the buffer
    this.getLength = function() {
        if(start > end || start == bufferSize) {
            return buffer.length;
        } else {
            return end - start;
        }
    };

    // Returns true if the buffer has been initialized.
    this.isInitialized = function() {
        return (end != start) ? true : false;
    };
}

edited May 23, 2017 at 11:51

CommunityBot

11 silver badge

answered Nov 21, 2013 at 14:04

vogomatix

5,1352 gold badges27 silver badges51 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

User2 Over a year ago

You've been brilliant dude. Thanks. Don't worry about doing anymore (Unless its for personal achievement :D). Looks beautiful!

vogomatix Over a year ago

I tend to polish my answers whenever I browse Stackoverflow on other issues :-)

vogomatix Over a year ago

Suggest you look at the link - this version probably works but the earlier solutions may be more elegant. In particular, pushing and popping may remove the need for complex index calculations

Steve Hibbert · Accepted Answer · 2015-05-21 10:12:38Z

I implemented Vogomatix's code above, and got a few bugs. The code writes off the end of the buffer, expanding the buffer size automatically, and the addValue function is bound to a particular type. I've adjusted the code to work with any object type, added some private subroutines to simplify, and added a function to dump the contents out to a string, with an optional delimiter. Also used a namespace.

What's missing is a removeValue() but it would be just a check of count to be greater than zero, then a call to _pop().

This was done because I needed a rolling, scrolling text buffer for inbound messages, that did not grow indefinitely. I use the object with a textarea, so I get behaviour like a console window, a scrolling text box that does not chew up memory indefinitely.

This has been tested with expediency in mind, in that I am coding quickly, posted here in the hope that fellow OverFlow-ers use and anneal the code.

///////////////////////////////////////////////////////////////////////////////
// STYLE DECLARATION
// Use double quotes in JavaScript


///////////////////////////////////////////////////////////////////////////////
// Global Namespace for this application
//

var nz = nz || {};
nz.cbuffer = new Object();


///////////////////////////////////////////////////////////////////////////////
// CIRCULAR BUFFER
//

// CREDIT: 
// Based on...
// Vogomatix http://stackoverflow.com/questions/20119513/attempt-at-circular-buffer-javascript
// But re-written after finding some undocumented features...
/**
*   A circular buffer class, storing any type of Javascript object.
*   To add value -> bufferObject.addValue(obj);
*   To get the First-in value use -> bufferObject.getValue(0);
*   To get the Last-in value use -> bufferObject.getValue(bufferObject.length);
*   To dump to string use -> bufferObject.streamToString(sOptionalDelimiter); // Defaults to "\r\n"
**/

nz.cbuffer.circularBuffer = function (buffer_size) {

    var bufferSize = buffer_size > 0 ? buffer_size : 1; // At worst, make an array of size 1
    var buffer = new Array(bufferSize);

    var end = 0; // Index of last element.
    var start = 0; // Index of first element.
    var count = 0; // Count of elements

    // 'Private' function to push object onto buffer.
    this._push = function (obj) {
        buffer[end] = obj; // Write
        end++; // Advance        
        if (end == bufferSize) {
            end = 0; // Wrap if illegal
        }
        count++;
    }

    // 'Private' function to pop object from buffer. 
    this._pop = function () {
        var obj = buffer[start];
        start++;
        if (start == bufferSize) {
            start = 0; // Wrap
        }
        count--;
        return obj;
    }

    // Adds values to buffer.
    this.addValue = function (obj) {
        if (count < bufferSize) {
            // Just push
            this._push(obj);
        }
        else {
            // Pop, then push
            this._pop();
            this._push(obj);
        }
    }

    // Returns a value from the buffer.  Index is relative to current notional start.
    this.getValue = function (index) {

        if (index >= count || index < 0) return; // Catch attempt to access illegal index

        var i = index + start;

        if (i >= bufferSize) {
            i -= bufferSize;
        }

        return buffer[i];
    }

    // Returns the length of the buffer.
    this.getLength = function () {
        return count;
    }

    // Returns all items as strings, separated by optional delimiter.
    this.streamToString = function (delim) {

        delim = (typeof delim === "undefined") ? "\r\n" : delim; // Default syntax; Default to CRLF

        var strReturn = "";

        var once = 0;
        var index = 0;
        var read = index + start;
        for (; index < count; ++index) {
            if (once == 1) strReturn += delim.toString();
            strReturn += buffer[read].toString();
            read++;
            if (read >= bufferSize) read = 0;
            once = 1;
        }

        return strReturn;
    }
}

Collectives™ on Stack Overflow

Attempt at Circular Buffer - Javascript

2 Answers 2

3 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related