Month: March 2010

I really like the way Javascript is moving from being this annoying thing you have to deal with when doing web-development to becoming a proper server-side programming languages with standard libraries and fast VMs. Yesterday I cloned the Narwhal git repo and tried to create my own package with a few simple collection types. Narwhal is done by the guys at 280north and conforms to the CommonJS standard, an attempt at a cross-platform standard by the various Javascript platform implementors.

I haven’t quite figured out what goes into creating a proper package, but if you check out and configure Narwhal, you can dump the collection implementation in /lib and the tests in /tests and see it all work. First the collections:

// -- friism Michael Friis

exports.Stack = function() {
  return new stack();
};

exports.Queue = function() {
  return new queue();
};

/**
 * Stack implementation, using native Javascript array
 */

function stack() {
  this.data = [];
};

stack.prototype.pop = function() {
  return this.data.pop();
};

stack.prototype.push = function(o) {
  this.data.push(o);
};

/**
 * Queue implementation. Mechanics lifted from Wikipedia
 * Could be optimised to do fewer slices, see here: 
 * http://safalra.com/web-design/javascript/queues/Queue.js
 */

function queue() {
  this.data = [];
  this.length = 0;
}

queue.prototype.isEmpty = function() {
  return (this.data.length == 0);
};

queue.prototype.enqueue = function(obj) {
  this.data.push(obj);
  this.length = this.data.length;
}

queue.prototype.dequeue = function() {
  var ret = this.data[0];
  this.data.splice(0,1);
  this.length = this.data.length;
  return ret;
}

queue.prototype.peek = function() {
  return this.data[0];
}

queue.prototype.clear = function() {
  this.length = 0;
  this.data = [];
}

… and the tests:

var assert = require("test/assert");

var js5 = require("js5");

exports.testStackSimple = function() {
  var mystack = new js5.Stack();
  var myobject = "1";
  mystack.push(myobject);
  var popped = mystack.pop();
  assert.isEqual(myobject, popped);
};

exports.testStack = function() {
  var mystack = new js5.Stack();
  for(var i = 99; i >= 0; i--) {
    mystack.push(i.toString());
  }

  for(var j = 0; j < 100; j++) {
    assert.isEqual(mystack.pop(), j.toString());
  }
}

exports.testQueue = function() {
  var myqueue = new js5.Queue();
  for(var i = 0; i < 100; i++) {
    myqueue.enqueue(i.toString());
  }

  for(var j = 0; j < 100; j++) {
    assert.isEqual(myqueue.dequeue(), j.toString());
  }
}

if (module == require.main) {
    require("os").exit(require("test").run(exports));
}

I asked for help on the Narwhal IRC channel and Kris Kowal pointed me to Chiron, a module library he's working on that already contains set and dictionary implementations. I recommend checking out the code, it highligts some of the interesting challenges of implementing collections in Javascript.

Also, this "Javascript, the Good Parts" talk by Doug Crockford (author of book of the same name) is really good: