algorithm visualization

Event Handling for JSAV Data Structures

For a while now, I've been meaning to start a series of articles on JSAV features. The current documentation only works as a reference to the API and does not explain or give enough examples. Also, it does not argue why things are done certain way and writing these things down makes me really think them through. As I recently implemented a support for easy attachment of event handlers to data structures, that seems like as good as any topic to start.

The Way Things Were

In general, attaching event handlers with jQuery is easy. That is, unless the HTML is generated by the library and there is no reason you should need to know the structure of it. Also, getting the JSAV object for the node/index matching the DOM element is tricky. The old way for doing this was something like:

// register a click event handler to all JSAV array indices
$(".jsavindex").click(function() {
//find the index of the clicked item
var index = $(this).parent().find(".jsavindex").index(this);
// do something with the array
});

Events for the Array Indices

To ease this, a recent commit introduced a better way to attach events to arrays and trees. Both structures support following events: click, dblclick, mousedown, mousemove, mouseup, mouseenter, and mouseleave. While the names are reasonably self-explaining, you can check jQuery event documentation for details on the events.

For a JSAV array, there are functions with the same name as the events that can be used to register event handlers for that event type. So, for example, to add a function to be called whenever mouse enters an array index, you can do the following:

arr.mouseenter(function(index) {
this.highlight(index);
});

The event handler function gets as the first parameter the index of the array element that the user interacted with. The this variable is set to point to the JSAV array. Naturally you don't need to pass an anonymous function as the event handler, but you can use any function as the parameter. A good example of this are the JSAV array functions, most of which take an index as the first parameter. The API documentation gives the following example that illustrates this well:

arr.mouseenter(arr.highlight).mouseleave(arr.unhighlight);

This also shows that the event binding functions return the structure itself, so you can safely chain the function calls.

Another parameter the event handler gets is the jQuery event object. You can use that in case you need to, for example, stop the propagation of the event.

arr.dblclick(function(index, event) {
event.stopPropagation();
// ... do something else..
}); 

Note: most of the JSAV functions that change some properties of the structures also store the changes to the animation history. For events that are fired often (such as mousemove), the history can get really long quite fast. Thus, make sure you don't misuse the events.

Events for Trees

For trees, there are functions for binding handlers for the same set of events: click, dblclick, mousedown, mousemove, mouseup, mouseenter, and mouseleave. These functions can be called for the JSAV tree instance. The actual event handlers will be bound to either nodes or edges of the tree.

Let's begin with a simple example:

var tree = jsav.ds.tree();
// ... tree.click(function(e) {
this.highlight();
});

What this would do is bind the anonymous function to be called whenever a node in the tree is clicked. The event handler function gets as a parameter the jQuery event object. Inside the handler, this will refer to the node or edge that the event was triggered for.

Like I mentioned, the event handler will be bound to the nodes by default. My assumption here, based on our experience with TRAKLA2 assignments, is that this is the more common use case. But don't worry, binding handlers for edges is almost as simple, you just need to add one option. Like this

tree.click(myEdgeClickHandler, { edge: true });

This will bind the function to only edges, and inside the handler, this will refer to the JSAV edge object triggering the event. If you want (although I can't come up with a good use case), you can bind the handler to both by adding another option node with value true.

Custom Arguments

The above describes the basic usage of the implementation, but there are other ways to deal with even more complex requirements. First of, custom arguments can be passed to the event handler. For example, to change a CSS property of an array index on mouseenter and remove it on mouseleave, the code needed with the above functions is something like:

arr.mouseenter(function(index) {
this.css(index, {"color": "red"});
}.mouseleave(function(index) {
this.css(index, {"color": "black"});
});

To ease this, the event binding functions all take a second, optional, parameter to specify custom parameters for the handler. This parameter should be an array with as many items as you want to pass as arguments for the event handler. With custom arguments, the above example can be simplified to:

arr.mouseenter([{"color": "red"}], arr.css)
 .mouseleave([{"color": "black"}], arr.css);

So, it uses the array's css function and passes the arguments for that function as parameter when registering the event handler. The function calls made by JSAV would be identical to the those made in the version not using custom arguments, except for the jQuery event object being the last argument. Ordering the parameters for the binding function to be event data first is just to be more consistent with jQuery.

Binding Custom Events

While writing this blog post, I realized there should probably be a way to bind custom events as well. While not required at the moment, I can already see a need to bind, for example, touch events. So, a later commit added on function to array and tree that allows binding any events. As the first parameter, the function takes the event name(s). The other required argument is again the event handler. For example

arr.on("touchstart", myEventHandler);

would register the function myEventHandler to be triggered when touchstart event is triggered.

Custom data for the handler can also be specified as the second parameter:

arr.on("touchstart", {myVal: "cat"}, myEventHandler);

And for trees, a last options parameter can be passed.

Summary

As a summary, here are the function signatures for the functions in array and tree:

arr.eventName([data,] handler);
arr.on(eventName, [data,] handler);
tree.eventName([data,] handler [, options]);
tree.on(eventName, [data,] handler [, options]);

What do you think? Any questions or suggestions on how to improve?

OEmbed Endpoint for TRAKLA2 Algorithm Visualizations

This summer in the Program Visualization Workshop 2011, I had a paper with a colleague about the use of web services to help algorithm visualization (AV) systems. One potential service we identified and implemented was an OEmbed endpoint for embedding AVs into hypertext learning materials such as ebooks. OEmbed is "a format for allowing an embedded representation of a URL on third party sites". To make it more understandable, let's go through an example of the OEmbed endpoint for TRAKLA2 AVs.

Example Request

Let's say we want to embed the TRAKLA2 Binary Search Tree search AV on our own HTML page. The BST search AV is located at http://www.cse.hut.fi/en/research/SVG/TRAKLA2/exercises/BST_search-28.html. The OEmbed endpoint where we can query for information to embed the TRAKLA2 AVs is running at http://trakla.cs.hut.fi/oembed/. To request the embedding information for the BST search AV, we simply make a request to the oembed endpoint with a HTTP GET parameter url specifying the URL of the resource we want to embed. So, we make a request to URL http://trakla.cs.hut.fi/oembed/?url=http://www.cse.hut.fi/en/research/SVG/TRAKLA2/exercises/BST_search-28.html

Example Response

A request to the URL above will give the following JSON response.

{"version": "1.0", 
 "type": "rich", 
 "html": "<applet code=\"applications.exerciseapplet.ExerciseApplet.class\" archive=\"http://www.cse.hut.fi/en/research/SVG/TRAKLA2/exercises/matrix.jar\" width=\"610\" height=\"600\"<<param name=\"swap\" value=\"on\" /><param name=\"ex\" value=\"content.exercises.BST_search\" /></applet>"}

The response indicates that it is using version 1.0 of the OEmbed specification and the type of he object to be embedded is rich. That tells us that we should look for the html property for the HTML to embed the object. Adding that HTML to a page, we can embed the AV.

How to Actually Embed

The request and the actual embedding of the HTML in the response can be done on a server or on a client. Here, I'll concentrate on the client side as it brings with it a new problem: same origin policy permitting JavaScript in browser to only access resources from the same origin as the page was loaded. This is obviously done for security reasons, but it also inhibits a script to load the JSON data from the trakla.cs.hut.fi domain. But not to worry, there is a simple workaround known as JSONP or "JSON with padding". JSONP requires the service to support it, and the OEmbed endpoint we have implemented does.

With JSONP, a callback function is specified in the request. This callback function is than called with the returned data as parameter. The callback can be appended to the URL as callback GET parameter, for example, a request to URL http://trakla.cs.hut.fi/oembed/?callback=foo&url=http://www.cse.hut.fi/en/research/SVG/TRAKLA2/exercises/BST_search-28.html In the response, the data will then call the function foo: foo({"version": "1.0", ...});

Now, we only need to implement a function foo to handle the data. Or, we can use jQuery to simplify things.

A Complete HTML + JavaScript Example

Let's assume we have an HTML page where we load the jQuery JavaScript library and have an element where we want to embed the BST search AV.

<div id="embedHere"></div>
<script src="http://ajax.googleapis.com/ajax/libs/jquery/1.6.2/jquery.min.js"></script>

Now, we can make the request and embed the AV with the following piece of JavaScript.

$(function() {
  $.getJSON("http://trakla.cs.hut.fi/oembed/?url=http://www.cse.hut.fi/en/research/SVG/TRAKLA2/exercises/BST_search-28.html&callback=?", 
    function(data) {
      $("#embedHere").html(data.html);
    })
});

What is happening here is the code using the jQuery function getJSON to load the JSON from the specified URL. The callback parameter is specified using callback=? GET parameter. jQuery will generate a unique ID for the callback function, which is given as the second parameter for the getJSON function. The function gets the response JSON as a parameter, data, and sets the HTML content of the element with id embedHere to be the html in the data. The end result is the AV to be embedded on the page.

Benefits of the approach

So, why would anyone want to do it this complicated when one could just copy and paste the HTML into a page? Well, with a single AV that is possible. The real benefits come when we embed multiple AVs and do not want to keep the HTML up to date. Embedding the content using OEmbed, the responsibility of the up-to-date embedding information is on the creator of the AV (system). Furthermore, this gives the AV creator the possibility to update the embedding information or even the content of the AV. Hopefully, one day we'll be able to replace the TRAKLA2 AV applets with JavaScript versions using the JSAV library. Those embedding the AVs through OEmbed would benefit from our update immediately without any manual updates.

Status of the Service

The service is up and running online, and can be used to embed resources available on the TRAKLA2 exercise site. So go give it a try and let me know what you think and how it could be improved!

The code for the service is available on GitHub. At the moment, it is a bit TRAKLA2 specific, but with reasonable effort it could be improved to be a more generic AV embedding service.

CSS3 Transformations and Transitions for Algorithm Visualization

CSS3 offers some interesting new properties that could be used for algorithm visualization. Here, I'll first introduce the new properties and then proceed to show and explain some demos that I've created. You can skip the nonsense and view the demos: bubble sortselection sort

CSS3 (or Cascading Stylesheets 3)

CSS3 includes several modules useful for web designers and web developers. Here, we are only interested in a couple: CSS Transforms, CSS Transitions, and CSS Animations. These are the modules that make it possible to add animation effects to web pages using CSS classes.

CSS Transforms CSS3 transforms allows translation, rotation, and scaling of elements in 2D and 3D. A two-dimensional transformation is applied to an element through the transform property. This property contains a list of transform functions. The transform-origin property establishes the origin of transformation for an element.

The transform functions in the specification are translate, scale, rotate, and skew. There are also versions of translate, scale, and skew to transform only X or Y dimension, that is, translateX and translateY, for example. Furthermore, the matrix transform functions allows for matrix transformations. Multiple transform functions can be used in a single transform property.

CSS Transitions The new CSS3 Transitions module defines CSS properties that can be used to change values of properties smoothly from one value to another over a specified duration. The transition behaviour is specified using a number of CSS properties.

  • transition-property specifies the properties that are smoothly changed. All animatable properties (not all CSS properties can be transitioned) that have changed can be animated using the value 'all'.
  • transition-duration is used to specify the length of the transition and transition-delay when the transition will start.
  • transition-timing-function describes the way the intermediate values are calculated. This allows a transition to change speed. There are several timing functions specified, for example, linear, ease-in, and ease-out.
  • transition property is a shorthand property that allows setting all of the above with one CSS property.

Listing below gives an example of how one would specify a transformation and a smooth transition.

    #selected {
      transition-property: transform, background-color, opacity;
      transform: translate(200px) scale(0.6);
      background-color: yellow;
      opacity: 0.2;
    }

The specified transformation would look like something in the picture below, assuming the original object had a red background and was not transparent.

css3transition-example

CSS Animation The CSS3 Animations module includes features to enable more fine-grained animation. This includes properties like keyframes that enable composing more controlled transitions. The module is an extension of the Transitions module.

Algorithm Visualizations with CSS3

To test how the new CSS3 properties work for visualizing algorithms, I created a couple of demos of sorting algorithms. Check out the bubble sort and selection sort demos. You'll need a browser that supports the new features, such as recent version of Chrome or Safari. If you don't have such browser, go install one or see the picture below.

CSS3 Algorithm Visualization demo screenshot

You can move backward and forward in the animation obviously using the links. When moving, the current codeline is highlighted, variable values updated, and the swaps of array elements animated. In addition to moving backward and forward, you can also change the layout to focus on the code or the data structure.

Technical Details

The animations are generated by an (ugly) Python script. This script is general enough that it would allow creation of animations of other sorting algorithms (or other algorithms working with arrays) by writing and annotating the python code. The code in the created animations is the actual Python code used to run the algorithm.

The Python code generates a JavaScript array of CSS class names as well as the corresponding CSS3 properties. An example of a highlight operation is shown below. 

/* codeline highlight */
.css-line2-5 { background-color: #afa; }
/* array element highlight */
.css-elem2-5 { background-color: yellow; }
/* moving an array element */
.css-elem2-6 {
   -webkit-transform: translate(-102px,0);
   -moz-transform: translate(-102px,0);
   transform: translate(-102px,0);
}

When moving backward or forward in the animation, JavaScript updates the CSS class attributes of the codelines, variables, and array cells changed in the operation. The browser then animates the changes according to the CSS properties.

Conclusion

While the browser support for CSS3 transformations is improving, they still can't be used for learning material that all students need to be able to access. But, they work well enough on some mobile browsers (such as iPhone and Android phones) to be useful when building AVs for mobile devices.

A Comprehensive Taxonomy of Algorithm Animation Languages

The article "A comprehensive taxonomy of algorithm animation languages" was finally published in the Journal of Visual Languages & Computing in volume 21, issue 1 (doi). I'd like to thank my co-authors Lauri Malmi, Ari Korhonen, and Thomas Naps for their hard work in writing this article. The abstract of the article:

In this paper, we present a taxonomy of algorithm animation languages that augments Price's well-known taxonomy of software visualization. Whereas Price's taxonomy is directed to classifying features and characteristics of visualization systems, the new taxonomy focuses on evaluating current animation languages. The taxonomy can be used by algorithm visualization system designers as a tool to compare visualization system languages with each other as well as for designing and implementing new systems and language features. In addition, the taxonomy provides guidelines to the features that are needed for transferring animations between systems. This is an ongoing project that elaborates upon the work reported on in a briefer version of the taxonomy.

The main categories of the presented taxonomy are Visualization, Dynamics, User Interaction, and MetaLanguage:

  • The category Visualization describes the features of the language used to create static visualizations for describing one state in the animation. In essence, it considers the variety of supported object types, that is, the building blocks used in the animation as well as ways to position and style the objects.
  • The category Dynamics describes the level and versatility of animation effects available in the language and how the final animation can be customized through the language. These are the ways the visualizations can be changed when moving from state to state.
  • The category User Interaction describes the type and level of interaction provided for the end-user of animations that can be specified using the language.
  • The category MetaLanguage describes the support of features that are not directly related to algorithm animation but instead are useful in the animation creation process. These are features that are not directly visible to the end user.

The figure below shows the two highest levels of the taxonomy. The paper also includes an evaluation of many of the existing AA languages. So, go read it and let me know what you think!