Writing and testing data structures and algorithms in JavaScript

Maarten Winkels

Tonight in one of our knowledge exchange sessions, one of my colleagues challenged us to writing a TagCloud in JavaScript. He had prepared a nice setup with a server producing twitter hashtags over a WebSocket to the browser and using Processing.js to produce a graphical representation of the tags zooming by on twitter. Since he had already done all the heavy lifting in integrating all these fancy new frameworks, what was left to do, you might ask. Well, we still needed to implement the algorithm to count the number of tags on the continuous stream, sorting this list on the bases of the counts and making sure the system wouldn't run out of memory by removing less used tags in some smart way. His point to all of this was, that although JavaScript is being prophesized in some circles as the new-old-new language of the future, writing and testing a non-trivial algorithm in it is a big challenge.

In the remainder of the hour, we tried in several pairs to implement the missing algorithm and it has to be said that we all failed miserably. It has to be said that none of us were JavaScript experts, but I (for one) felt (in the beginning...) that I should have enough experience in IT in general and a little in JavaScript to make this work. But alas...

Driving back home, I decided not to give in so easily and to try and use some decent frameworks to overcome this challenge.

JavaScript testing: YUI

I turned to finding a testing framework first. Sure enough, most javascript testing frameworks focus on fancy UI stuff like asynchronous testing, integration testing or automated multi-browser testing. I was looking for none of that, but a simple xUnit like framework, that I could run in a browser to test the functionality of a number of JavaScript classes. After a few minutes I found YUI which seemed to fit the bill. Setting up was easy enough:

<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<title>Testing TagCounter with YUI</title>
</head>
  <body class="yui-skin-sam">
    <div id="yui-main"><div id="testReport"></div></div>
    <script type="text/javascript" src="http://yui.yahooapis.com/3.0.0/build/yui/yui-min.js"></script>
    <script type="text/javascript" src="js_cols/base.js"></script>
    <script type="text/javascript" src="TagCounter.js"></script>
    <script type="text/javascript" src="TagCounter_Test.js"></script>
  </body>
 </html>

This static html file is all that is neede to run my tests. The tests themselves are written in the TagCounter_Test.js file:

/**
 * Unit Tests for TagCounter
 */
YUI({
  combine: true,
  timeout: 10000
}).use("node", "console", "test", function (Y) {
  var assert = Y.Assert;

  var TagCounterTestCase = new Y.Test.Case({
    // test case name - if not provided, one is generated
    name: "TagCounter Tests",

    "test should increment count": function () {
      var tc = new TagCounter();
      tc.add("my-tag");
      assert.areEqual(1, tc.map().get("my-tag"));
      tc.add("my-tag");
      assert.areEqual(2, tc.map().get("my-tag"));
    }
  });
  
  //create the console
  var r = new Y.Console({
    newestOnTop : false,
    style: 'block'
  });

  r.render("#testReport");
  Y.Test.Runner.add(TagCounterTestCase);
  Y.Test.Runner.run();
});

Opening the HTML file in FireFox shows the picture below.

It seems like I'm ready to implement the TagCounter TDD style!

Implementation: js_cols

To make this simple test pass, all I need is a simple HashMap with some basic features, like contains, get and remove, but... this is not java! After some googling, I found js_cols, a neat JavaScript collections framework, that basically had all the support that I wanted, including a LinkedHashMap implementation that can be used to implement a LRU cache, just like good old java! The LRU feature is going to help me to remove "old" tags, keeping the memory required to process the tags within reasonable limits.

To make the first test succeed, only a few lines of code are needed:

js_cols.require('js_cols.LinkedHashMap');
function TagCounter(maxSize) {
	this.tagCounts = new js_cols.LinkedHashMap(maxSize, true);
};
TagCounter.prototype.add = function (tag) {
	if (this.tagCounts.contains(tag)) {
		this.tagCounts.insert(tag, this.tagCounts.get(tag) + 1);
	} else {
		this.tagCounts.insert(tag,1);
	}
};
TagCounter.prototype.map = function () {
	return this.tagCounts;
};

In the end, however, we want the map method to return only the most popular tags, while our counter should keep track of a longer list. To implement this, we need two steps:

  1. First we need to sort the tags by their number of appearances in descending order, keeping in mind that multiple tags can have the same number.
  2. Then we need to take the top x most popular tags.

The test:

...
    "test should return limited sized map": function () {
    	var tc = new TagCounter(3);
    	tc.add("my-old-tag");
    	tc.add("my-old-tag");
    	tc.add("my-old-tag");
    	assertSame(tc.map(2), [["my-old-tag", 3]]);
    	tc.add("my-first-tag");
    	tc.add("my-first-tag");
    	assertSame(tc.map(2), [["my-old-tag", 3], ["my-first-tag", 2]]);    	
    	tc.add("my-second-tag");
    	assertSame(tc.map(2), [["my-old-tag", 3], ["my-first-tag", 2]]);    	
    	tc.add("my-third-tag");
    	assertSame(tc.map(2), [["my-first-tag", 2], ["my-third-tag", 1]]);    	
    }
  });
  
  function assertSame(map, expected) {
	  var keys = map.getKeys();
	  assert.areEqual(expected.length, keys.length);
	  for(var i=0,len=expected.length; value=expected[i], i<len; i++) {
		  assert.areEqual(value[0], keys[i]);
		  assert.areEqual(value[1], map.get(value[0]));
	  }
  };
...

In the test we now add a method assertSame to make it easier to express our expectations of the map method: The map should contain the expected number of tags with their counts in the right order. Therefor the expectation is a list of [tag, count]-tuples.

We can again use the collection library classes to implement this: The RedBlackMultiMap class implements a key-sorted map that allows multiple values for the same key.

TagCounter.prototype.map = function (opt_size) {
	var orderedMap = new js_cols.RedBlackMultiMap(function (a,b) {return b-a;});
	this.tagCounts.forEach(orderedMap.insert, orderedMap);
	var result = new js_cols.LinkedHashMap();
	if (opt_size) {
		var i = 0;
		orderedMap.forEach(function (value, key) {
			if (i < opt_size) {
				result.insert(value, key);
			}
			i++;
		});
	} else {
		orderedMap.forEach(result.insert, result);
	}
	return result;
};

On line 2 the RedBlackMultiMap constructor is used with a comparator function that will invert the natural ordering of numbers. This way we sort in descending order.
On line 3 all items of the tagCount map are inserted into the orderedMap reversing the key-value relation. The fact that the forEach method take a function that has the value as the first and the key as the second argument (which would usually be confusing) now appears a handy feature!
On lines 4 to 7, the key-value relation is again reversed, making sure to only take the top opt_size items from the map (when set).

Conclusion

Looking at the simplicity of the code and the tests, I would say that it is definitely possible to write well tested and documented JavaScript algorithms and data structures. I completely agree with my colleague, however, that such code is not often found in your run-of-the-mill web application project. Maybe it is time to start treating the JavaScript code in our projects more as Java code and make sure that it is properly structured and tested.

Comments (2)

  1. Bartosz Majsak - Reply

    June 24, 2011 at 8:37 am

    If you are looking for something more xUnit-style you should defenitely have a look at JS Test Driver http://code.google.com/p/js-test-driver/

  2. Tip - Reply

    February 19, 2012 at 10:35 pm

    Google Closure API - used in GWT - is also a very nice and clean alternative. More straightforward than YUI.

    http://closure-library.googlecode.com/svn/docs/class_goog_testing_TestCase.html

Add a Comment