javascript circular buffers

March 30, 2012 – 7:17 pm

A while back I was introduced to Circular Buffers and the idea intrigued me. The simplest implementation in JavaScript would be to just push() and pop() to/from an array, but that isn’t good for memory or garbage collection times. So I wrote an implementation that uses pointers and a fixed size array. It has a limited API at the moment, but works much the same as the native Array(). First the code, then I’ll give some examples (it’s also available on github):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
function CBuffer() {
    // handle cases where "new" keyword wasn't used
    if (!( this instanceof CBuffer )) {
        if ( arguments.length > 1 || typeof arguments[0] !== 'number' ) {
            return CBuffer.apply( new CBuffer(), arguments );
        } else {
            return new CBuffer( arguments[0] );
        }
    }
    // this is the same in either scenario
    this.size = this.start = 0;
    // build CBuffer 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;
    }
    return this;
}

CBuffer.prototype = {
    // push item to the end
    push : function() {
        var i = 0;
        // push items to the end, wrapping and erasing existing items
        // using arguments variable directly to reduce gc footprint
        for ( ; 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.end - this.size + 1;
        if ( this.start < 0 ) this.start += this.length;
        // return number current number of items in CBuffer
        return this.size;
    },
    // shift first item
    shift : function() {
        var item;
        // check if there are any items in CBuff
        if ( this.size === 0 ) return undefined;
        // store first item for return
        item = this.data[ this.start ];
        // delete first item from memory
        delete this.data[ this.start ];
        // recalculate start of CBuff
        this.start = ( this.start + 1 ) % this.length;
        // decrement size
        this.size--;
        return item;
    },
    first : function() {
        return this.data[ this.start ];
    },
    last : function() {
        return this.data[ this.end ];
    },
    idx : function( arg ) {
        return this.data[( this.start + arg ) % this.length ];
    }
};

Let’s start with instantiating a new CBuffer() object. Just remember with all of these, the new keyword is optional:

1
2
3
4
5
6
// length of 5, no items in buffer
new CBuffer( 5 );
// length 2, items [ 1, 2 ] are in buffer
new CBuffer( 1, 2 );
// length 1, item [ 'awesome' ] is in buffer
new CBuffer( 'awesome' );

When a new buffer has been created the length is unchangeable. While it does offer a performance improvement, the key is to minimize Garbage Collection as much as possible.

Let’s create a new circular buffer and push some stuff to the end:

1
2
var newbuff = new CBuffer( 5 );
newbuff.push( 'i', 'am', 'a', 'buffer' ); // ~= [ 'i', 'am', 'a', 'buffer', ]

If we want to just grab the first item in the buffer, use .first(). But if the item should be removed, returned and destroyed used .shift().

1
2
3
newbuff.first() // returns 'i'
newbuff.shift() // returns 'i'
// newbuff ~= [ , 'am', 'a', 'buffer', ]

The start pointer has now moved forward and the original first item has been returned and destroyed. So let’s continue to push stuff on:

1
newbuff.push( 'want', 'to', 'play' ) // ~= [ 'to', 'play', 'a', 'buffer', 'want' ]

Say what?! Where did my stuff go? Well, it was truncated. When more items are pushed to the buffer than it has spots for it starts over. From here let’s shift of the latest data:

1
2
newbuff.shift() // returns 'a'
// newbuff ~= [ 'to', 'play', , 'buffer', 'want' ]

I think this shows the general idea of how to use this little library. Good luck with it.

By trevnorris | Posted in javascript | Comments (3)

defactor your deferreds and kill your callbacks

January 8, 2012 – 12:14 am

Defactor is a project that began after submitting a pull request for myQuery, then deciding to try my had at a selector engine I began to create my own called rufus (which isn’t online so don’t bother looking for it). Early I decided the syntax should work like the following:

1
2
3
4
5
6
7
8
9
rufus( 'div' )
    .on( 'click' )  // begin tying events to the click event
        .animate( {} ) // animate the clicked element
            .exec( fn )  // execute a function once the animation is complete
            .end()       // return to previous context
        .ajax( {} )  // make an ajax call, returns a new deferred
            .success( fn )  // if successful
            .fail( fn )     // if error
            .complete( fn ) // when call completes

I figured the core of a fully chainable asynchronous API would begin with a library similar to jQuery’s Deferred object. I was first introduced to this concept during an interview at Mozilla, and haven’t been able to leave them alone since. To begin explaining the concept, here’s line taken directly from jQuery’s API documentation:

“[Deferred] is a chainable utility object that can register multiple callbacks into callback queues, invoke callback queues, and relay the success or failure state of any synchronous or asynchronous function”

After using jQuery.Deferred in a couple small projects I began to want more than simple pass/fail. But how to build a Deferred object that would understand complex events? It didn’t take very many attempts to realize it wasn’t possible. Then I wondered “why not let the developer decide on their own level of complexity?” The concept for Defactor was born.

Defactor allows a developer to create a many-to-many relationship of, what are now called, queues and triggers. Defactor first instantiates a new object of itself, then self-populates with names for the different queue/trigger relations that were added using the add( trigger, queue ) command. To finish the process the create() method is invoked to generate the new Deferred object.

Queues are registered against triggers, then the functions are passed to a queue to be executed later. Different queues will fire depending on which trigger is called. Here is an example (the names for the triggers and queues are similar to those used in jQuery.Deferred):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var Defer = defactor()
    .add( 'resolve', 'done always' )
    .add( 'reject', 'fail always' )
    .create();

var ss = Defer()
    .done(function( arg ) {
        console.log( 'done' );
    })
    .fail(function( args ) {
        console.log( 'fail' );
    })
    .always(function() {
        console.log( 'always' );
    });

ss.resolve( [context,] args );
// LOG: done
// LOG: always

While the above example has been simplified to a pass/fail modal, I hope you can see how more complex Deferred objects can be generated.

In the v0.2.0 release the API will change by allowing an optional final argument to add(). This function will be called on an arguments set that will be passed to the queue. Code will help me explain:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var Defer = defactor()
    .add( 'resolve', 'debug', function( opts ) {
        // debug opts
        return this;
    })
    .add( 'resolve', 'done' );

var ss = new Defer()
    .done(function() {
        //
    })
    .debug({
        // opts object that are passed to the function
    });

ss.resolve();

This library is still very early, and while I don’t see many drastic deviations from the API that is currently there, backwards compatibility isn’t guaranteed until the release of v1.0. Which will hopefully be within the next few months. Grab the source.

By trevnorris | Posted in defactor | Comments (0)

apply the new operator

September 14, 2011 – 9:16 pm

A while back I was trying to write a function would return a new instance of a function which had n number of arguments. Just last week I finally figured out how. Below is a completely generic example of how to return a new instance of a function regardless if the developer uses the new operator.

1
2
3
4
5
6
function MyFunc() {
    if (!( this instanceof arguments.callee ))
        return arguments.callee.apply( new arguments.callee(), arguments );
    // do stuff here
    return this;
}

The key to have this syntax work is the return this; at the bottom of the function. Fortunately we can shrink down the verbosity of the expression by using the function name. Below is a simple example to create an object that will sum its arguments.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function SumObj() {
    if (!( this instanceof SumObj ))
        return SumObj.apply( new SumObj(), arguments );
    this.args = Array.prototype.slice.call( arguments );
    return this;
}

SumObj.prototype.sum = function() {
    var total = 0,
        i = 0;
    for ( ; i < this.args.length; i++ )
        total += this.args[i];
    return total;
}

SumObj( 1, 2, 3 ) === { args : [ 1, 2, 3 ]};
SumObj( 2, 3, 5 ).sum() === 10;
By trevnorris | Posted in javascript | Comments (0)

jStat with Flot integration

July 14, 2011 – 3:37 am

Today I pushed Flot integration into jStat’s master branch. The entire thing is only a couple dozen lines of code. The syntax follows fairly close to Flot’s API. Here’s a snippet from the Flot test page:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var betaInst = jStat.beta( 3, 4 );
j$.flot( '#betadiv', [{
    data : betaInst.pdf,
    label : 'PDF'
},{
    data : betaInst.cdf,
    label : 'CDF',
    yaxis : 2
}],{
    flotopts : {
        yaxes : [{}, { position : 'right' }]
    },
    start : 0,
    stop : 1,
    step : 1001
});

The big thing is that you can pass the instantiated object itself for the data, which will be used to calculate the data points on the fly. Here’s an image of what the above example would look like:

Beta Dist Flot Example

By trevnorris | Posted in jstat | Comments (1)

jStat is alive

March 31, 2011 – 1:22 am

In April 2010 I began working on a JavaScript statistical library called jStat. After hammering out a bunch of basic functionality I didn’t pay much attention to it. Then a few weeks ago across the wire comes a new JavaScript statistical library called, well, jStat. It even had its own website. The author of that library, Matthew Williams, had done a lot more of the graphical work and created some sick demos on the webpage. So I dropped him a line and asked if we could merge projects. Lo and behold, he was rock awesome and so we started up a repo at GitHub.

It’s been wicked busy the last week as we’ve been hammering out the details of the framework. Right now it’s in the process of being completely revamped, and we invite everyone who wants to come check it out.

The API is sickly cool. Granted we took one from the jQuery book of chainability, but that doesn’t make it any less sweet. For example, if you want to start working with a vector and calculate their sums, means, etc. you can chain all these together and pass callback functions to retrieve the results once they’ve been calculated. The passed callback function will be called as many times as objects have been passed to the jStat object. For example:

1
2
3
4
5
6
7
8
9
j$( vector ).sum( function( val ) {
    // do something with the sum
}).mean( function( val ) {
    // and here's the mean
}).min( function( val ) {
    // needed that min value
}).max( function( val ) {
    // and why not grab the max value while we're at it
});

or if that’s too complicated then you can just not pass a callback and it will return the results instead:

1
2
3
j$( vector ).sum(); // returns the sum
j$( matrix ).sum(); // returns an array of the sum of columns
j$( matrix ).sum( true ); // returns the sum of everything

and if that’s still too complicated, or not performant enough, then you can tap into the underlying static methods:

1
j$.sum( array ); // returns sum of array

The API is supposed to be as flexible as possible so it will be applicable in almost any scenario. The core file also doesn’t have any dependencies so it will run server-side with something like Node.js. While we have set specific goals for ourselves, it’s been left open enough to allow almost anyone to jump in with additional items.

It’s been my life the last week, and hope someone else can have as much fun with it as I have.

By trevnorris | Posted in jstat | Tagged , | Comments (0)

jqml – jQuery JSONML plugin

March 24, 2011 – 12:40 am

After taking Stephen’s comment into account on my last post, I’ve decided to turn the code into a jQuery plugin. Being a boring, and very unimaginative, developer I decided to call it jqml (grab the source here). Compressed, the code is under 1/2KB.

The same method is used to generate element attributes that is used in jQuery (jQuery.fn.attr.call). While simple, this also provides a tremendous amount of flexibility and power. Events can be tied to elements as they are being created. Here’s an example:

1
2
3
4
5
6
7
8
9
$.jqml(['nav', ['a', 'home page', {
    href: '/index.html',
    click: function(e) {
        // do stuff
}}], ['a', 'about us', {
    href: '/about.html',
    click: function(e) {
        // do more stuff
}}]]).prependTo('body');

One reason I like building the DOM in JavaScript using JSON is because of the ability to step through each part of the generation process. If an element or attribute isn’t coming out as expected, that code is easy to locate and troubleshoot. Another fun use case is to incorporate immediately executing anonymous functions. This way many elements can be created from a data set and a few lines of code:

1
2
3
4
5
6
7
8
9
10
11
$.jqml(['table', (function() {
    var dataArray = ['tbody'];
    for (var i = 0; i < data.length; i++) {
        dataArray.push(['tr',
            ['td', data[i][0]],
            ['td', data[i][1]],
            ['td', data[i][2]]
        ]);
    }
    return dataArray;
})()]).data(data).appendTo('#dataTable');

Above you’ll see the addition of .data(). This helps me track where specific data objects are being used. If AJAX is used to update that table’s data, via .data(), then a simple queue can be created to iterate over all elements that have been updated. No worries about passing arguments around, or polluting the global namespace. The data is where it’s needed.

When something like templating in JavaScript is necessary, using JSONML is my preferred method. Debugging has been easy, overall performance is great, and to me something just feels better.

Update: As you’ll see in the URL, the project was named jsql. But for some reason I named the repository jqml. So as to not break any links that currently exist out there I’ve kept the name as jqml and updated this post to match, but not changed the URL to this post.

By trevnorris | Posted in javascript | Tagged , , , | Comments (4)

jQuery pull request for JSONML support

March 21, 2011 – 9:31 pm

I created my first jQuery pull from my fork[link] request over the weekend. It contains a small update to support native JSONML support in the core. One really cool feature in jQuery is the ability to build an element and pass an object with all the attributes you wish to assign. Here’s an example:

1
2
3
4
5
6
7
$('<p />', {
    'class': 'my-paragraph',
    click: function() {
        // do stuff
    },
    text: 'I\'m a paragraph!'
});

The disadvantage to this is only a single element can be created simply with ties to events. If more than a single element needs to be created the ability is lost to tie into the event queue. Adding native JSONML support would allow for the creation of complex DOM structures where each element can be individually customized. Here’s an example:

1
2
3
4
5
6
7
8
9
10
11
$([['div', {
    'class': 'outer-div',
    hover: function() {
        // hover stuff
    }
}, ['p', 'I\'m a paragraph!', {
    'class': 'my-paragraph',
    click: function() {
        // click stuff
    }
]]]);

Let me know if you think this would be a good feature addition to the jQuery core. Or if not, let me know why.

By trevnorris | Posted in javascript | Tagged , , | Comments (0)

javascript immutable emulation

January 26, 2011 – 12:20 am

While working with Taffy DB the other day I got a strange idea of how to create an object that supports multiple instances, and happens to be immutable-ish:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
(function(window, undefined) {
    function privateFunc(val) {
        this.val = val;
    };
    privateFunc.prototype.print = function() {
        return this.val;
    };
    window.publicFunc = function(val) {
        var newObj = new privateFunc(val);
        newObj.constructor = privateFunc.constructor;
        return newObj;
    };
    for (var i in privateFunc.prototype) publicFunc.prototype[i] = privateFunc.prototype[i];
})(this);

publicFunc.prototype.print = function() { return false; };

var test0 = publicFunc('qwerasdf');
var test1 = publicFunc('something else');

console.log(test0.print());  // returns 'qwerasdf'
console.log(test1.print());  // returns 'something else'

The object isn’t entirely immutable. A user could over write publicFunc and do whatever they want. But it is impossible to change a single instance method of privateFunc (that I’ve been able to find). The reason this works is because the constructor is being over written on instantiation and the code itself isn’t accessible to the user.

Using a pattern like this does have drawbacks. For example, there is no way to check if an object is an instance of privateFunc. But this technique might come in use some time when that isn’t necessary.

By trevnorris | Posted in javascript | Tagged , | Comments (0)

code share with Node.js and the browser

January 24, 2011 – 9:46 pm

While working in JavaScript I like to execute my code through Node.js from my editors terminal for quick testing. Unfortunately the usual pattern of wrapping code doesn’t quite work:

1
2
3
(function(window, undefined) {
    // code here...
})(window);

Luckily the fix was pretty simple. By replacing window with this we have access to the Node.js module system. Here’s an example of what it would look like in an external file:

1
2
3
4
5
(function(window, undefined) {
    window.myFunc = function() {
        // do stuff
    };
})(this);

From here the code can be pulled in easily to a Node.js file for execution:

1
var myFunc = require('/path/to/file.js').myFunc;
By trevnorris | Posted in nodejs | Tagged , | Comments (0)

so the posting begins…

November 29, 2010 – 2:40 am

well, looks like i’m finally going to start posting my code. while this blog is mainly for me to keep track of thoughts and other misc code samples, hopefully someone else out in the giant web will find it useful.

here we go…

By trevnorris | Posted in misc | Comments (0)