Source Code
You can download the complete source for the HTML5/Javascript version of the visualizations (both compressed and uncompressed) here:- visualization1.4.tar.gz, visualization.1.4.tar
- visualization1.3.tar.gz, visualization.1.3.tar
- visualization1.2.tar.gz, visualization.1.2.tar
- visualization1.1.tar.gz, visualization.1.1.tar
A few notes / warnings:
- Do not try to look at the code to understand the algorithms. I have done one or two tricky things to get the visualizations to work property that rather obscure the algorithms themselves. Your favorte textbook, or even wikipedia, is a better bet for appropriate source code.
- Like all software projects, this one is a bit of a living thing -- it started life as a Java project, was rewritten in ActionScript3 (that is, flash), and then ported to Javascript. It was also my opportunity to learn flash and javascript, so by the time I figured out the best way to do things, half of the software was already written. I've done some going back to clean stuff up, but there is still a quite a lot of ugliness. Next time all my code will be pretty :).
Visualization Creation Tutorial
To creeate a new visualization, you need to create a javascript file and an HTML file. The HTML file should just be copied from a template, changing only one or two items (like the name of the javascript file). Examples of the HTML template and how to change it are at the end of this tutorial. In the javascript file, you will create a function (an object, really, but functions are objects in javascript) that:- Creates any appropriate controls to control you visualization (inserting elements, deletig elements, etc)
- Creates callbacks for these controls that implement the visualizations. The visualizations are implemented by sending an array of strings to the animation manager -- the animation manager will then implement the animation, and handle all of the animation controls for you
- Listen for an undo event from the animation manager. When an undo event is detected, roll back the last operation
Using Algorithm function
Creating the javascript function is stil farily complicated, even when using the rest of the library. Many of the ugly details can be automated if your function "subclasses" the Algorithm function (located in AlgorithmLibrary/Algorithm.js (which is sort of a faux "class"). Consider the skeleton "MyAlgorithm" function included in the tarfile: Looking at various pieces of the file in turn:Copyright: Code is released under in a FreeBSD license.
// Copyright 2011 David Galles, University of San Francisco. All rights reserved. // // Redistribution and use in source and binary forms, with or without modification, are // permitted provided that the following conditions are met: // // 1. Redistributions of source code must retain the above copyright notice, this list of // conditions and the following disclaimer. // // 2. Redistributions in binary form must reproduce the above copyright notice, this list // of conditions and the following disclaimer in the documentation and/or other materials // provided with the distribution. // // THIS SOFTWARE IS PROVIDED BY David Galles ``AS IS'' AND ANY EXPRESS OR IMPLIED // WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND // FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALLOR // CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR // CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR // SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON // ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF // ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. // // The views and conclusions contained in the software and documentation are those of the // authors and should not be interpreted as representing official policies, either expressed // or implied, of the University of San Francisco
function MyAlgorithm(am, w, h) { this.init(am, w, h); } MyAlgorithm.prototype = new Algorithm(); MyAlgorithm.prototype.constructor = MyAlgorithm; MyAlgorithm.superclass = Algorithm.prototype;
- Call the superclass counstructor. Note the syntax, it's a little odd, but we are forcing javascript into an tradtional object-oriented paradigm, so it will complain a little at us.
- Add necessary controls
- Initialize our "Memory Manager". For the most part, we will use a very simple memory manager -- the old Pascal-style "Never free" memory manager. Start the free list at 0, and then increment it every time you need a new piece of memory.
- Initialize any data structures we will be using
MyAlgorithm.prototype.init = function(am, w, h) { // Call the unit function of our "superclass", which adds a couple of // listeners, and sets up the undo stack MyAlgorithm.superclass.init.call(this, am, w, h); this.addControls(); // Useful for memory management this.nextIndex = 0; // TODO: Add any code necessary to set up your own algorithm. Initialize data // structures, etc. }
MyAlgorithm.prototype.addControls = function() { this.controls = []; // Add any necessary controls for your algorithm. // There are libraries that help with text entry, buttons, check boxes, radio groups // // To add a button myButton: // this.mybytton = addControlToAlgorithmBar("Button", "MyButtonText"); // this.mybytton.onclick = this.myCallback.bind(this); // this.controls.push(this.mybutton); // where myCallback is a method on this function that implemnts the callback // // To add a text field myField: // this.myField = addControlToAlgorithmBar("Text", ""); // this.myField.onkeydown = this.returnSubmit(this.myField, // this.anotherCallback.bind(this), // callback to make when return is pressed // maxFieldLen, // integer, max number of characters allowed in field // intOnly); // boolean, true of only digits can be entered. // this.controls.push(this.myField); // // To add a textbox: // this.myCheckbox = addCheckboxToAlgorithmBar("Checkbox Label"); // this.myCheckbox.onclick = this.checkboxCallback.bind(this); // this.controls.push(myCheckbox); // // To add a radio button group: // this.radioButtonList = addRadioButtonGroupToAlgorithmBar(["radio button label 1", // "radio button label 2", // "radio button label 3"], // "MyButtonGroupName"); // this.radioButtonList[0].onclick = this.firstRadioButtonCallback.bind(this); // this.controls.push(this.radioButtonList[0]); // this.radioButtonList[1].onclick = this.secondRadioButtonCallback.bind(this); // this.controls.push(this.radioButtonList[1]); // this.radioButtonList[2].onclick = this.thirdRadioButtonCallback.bind(this); // this.controls.push(this.radioButtonList[1]); // // Note that we are adding the controls to the controls array so that they can be enabled / disabled // by the animation manager (see enableUI / disableUI below) }
- This reset method is called, which resets the state of your object to exactly how it was before any operations were performed
- All of the operations up until the last one are replayed (though the animation information is thrown away
- We end up in the same state that we were in right before the last operation was done
MyAlgorithm.prototype.reset = function() { // Reset all of your data structures to *exactly* the state they have immediately after the init // function is called. This method is called whenever an "undo" is performed. Your data // structures are completely cleaned, and then all of the actions *up to but not including* the // last action are then redone. If you implement all of your actions through the "implementAction" // method below, then all of this work is done for you in the Animation "superclass" // Reset the (very simple) memory manager this.nextIndex = 0; }
////////////////////////////////////////////// // Callbacks: ////////////////////////////////////////////// // // All of your callbacks should *not* do any work directly, but instead should go through the // implement action command. That way, undos are handled by ths system "behind the scenes" // // A typical example: // //MyAlgorithm.prototype.insertCallback = function(event) //{ // // Get value to insert from textfield (created in addControls above) // var insertedValue = this.insertField.value; // // // If you want numbers to all have leading zeroes, you can add them like this: // insertedValue = this.normalizeNumber(insertedValue, 4); // // // Only do insertion if the text field is not empty ... // if (insertedValue != "") // { // // Clear text field after operation // this.insertField.value = ""; // // Do the actual work. The function implementAction is defined in the algorithm superclass // this.implementAction(this.insertElement.bind(this), insertedValue); // } //} // Note that implementAction takes as parameters a function and an argument, and then calls that // function using that argument (while also storing the function/argument pair for future undos) ////////////////////////////////////////////// // Doing actual work ////////////////////////////////////////////// // The functions that are called by implementAction (like insertElement in the comments above) need to: // // 1. Create an array of strings that represent commands to give to the animation manager // 2. Return this array of commands // // We strongly recommend that you use the this.cmd function, which is a handy utility function that // appends commands onto the instance variable this.commands // // A simple example: // //MyAlgorithm.simpleAction(input) //{ // this.commands = []; // Empty out our commands variable, so it isn't corrupted by previous actions // // // Get a new memory ID for the circle that we are going to create // var circleID = nextIndex++; // var circleX = 50; // var circleY = 50; // // // Create a circle // this.cmd("CreateCircle", circleID, "Label", circleX, circleY); // circleX = 100; // // Move the circle // this.cmd("Move", circleID, circleX, circleY); // // First Animation step done // this.cmd("Step"); // circleX = 50; // circleY = 100; // // Move the circle again // this.cmd("Move", circleID, circleX, circleY); // // Next Animation step done // this.cmd("Step"); // // Return the commands that were generated by the "cmd" calls: // return this.commands; //}
// Called by our superclass when we get an animation started event -- need to wait for the // event to finish before we start doing anything MyAlgorithm.prototype.disableUI = function(event) { for (var i = 0; i < this.controls.length; i++) { this.controls[i].disabled = true; } } // Called by our superclass when we get an animation completed event -- we can /// now interact again. MyAlgorithm.prototype.enableUI = function(event) { for (var i = 0; i < this.controls.length; i++) { this.controls[i].disabled = true; } }
//////////////////////////////////////////////////////////// // Script to start up your function, called from the webapge: //////////////////////////////////////////////////////////// var currentAlg; function init() { var animManag = initCanvas(); currentAlg = new MyAlgorithm(animManag, canvas.width, canvas.height); }
Animation Commands
The commands that we give to the animatino manager are a list (array) of strings. Each string starts with the name of the command (case-insensitive) followed by a list of arguments, separated by the token <;>. The first argument of (almost) every command is the ID of the object you want to create or access. So, the string to Move element 37 to position (100, 120) would be:- "Move<;>37<;>100<;>120"
Object Creation and Deletion Commands
Object creation commands take as a first argument an integer representing the index of the object to create. This integer must not be the same as another object that is currently active in the system (though you can reuse numbers once the objects have been deleted). Like all commands, the creation commands have some required and some optional parameters.- CreateCircle: objectID, label, [initial_x, initial_y]
- objectID: Non-negative integer that represents the ID of this object. Must be different from any ID currently active. Should be as small as posslbe for better performance.
- label: the label that appears in the middle of the circle. It may contain end of line (\n) characters, which allows you to place a multi-line label in the circle. Labels are centered in circles.
- initial_x: (optional, defaults to 0) the initial x position of the circle
- initial_y: (optional, defaults to 0) the initial u position of the circle
- CreateRectange: objectID, label, width, height, [initial_x, initial_y, xJustify, yJustufy, backgroundColor, foregroundColor]
- objectID: Non-negative integer that represents the ID of this object. Must be different from any ID currently active. Should be as small as posslbe for better performance.
- label: the label that appears in the middle of the rectangle. It may contain end of line (\n) characters, which allows you to place a multi-line label in the rectangle. Labels are centered in rectangles.
- width: The width of the rectangle, in pixels
- height: The height of the rectangle, in pixels
- initial_x: (optional, defaults to 0) the initial x position of the rectangle
- initial_y: (optional, defaults to 0) the initial u position of the rectangle
- xJustify: (optional, defaults to "center"). One of "center", "left", "right" -- If the rectangle is at location (x, y), does x stand for the left, center, or right of the rectangle
- yJustify: (optional, defaults to "center"). One of "center", "top", "bottom" -- If the rectangle is at location (x,y0 does y stand for the top, center, or bottom of the rectangle
- foregroundColor: The initial color of the foregorund of the rectangle, using string representations of HTML colors ("#FF0000" for red, "#00FF00" for green, and so on). Defaults to black
- backgroundColor: The initial color of the background of the rectangle, using HTML colors (#FF0000 for red, #00FF00 for green, and so on). Defaults to white.
- CreateHighlightCircle: objectID, color, [initial_x, initial_y, radius]
A highlight circle is much like a standard circle, except that it has no label, and no background color, so that it does not obscure other objects like a circle does.- objectID: Non-negative integer that represents the ID of this object. Must be different from any ID currently active. Should be as small as posslbe for better performance.
- color: The initial color of the circle, using HTML colors ("#FF0000" for red, "#00FF00" for green, and so on)
- initial_x: (optional, defaults to 0) the initial x position of the circle
- initial_y: (optional, defaults to 0) the initial u position of the circle
- radius: (optional, defaults to 20) The radius of the circle.
- CreateLabel: objectID, label, [initial_x, initial_x, centered]
- objectID: Non-negative integer that represents the ID of this object. Must be different from any ID currently active. Should be as small as posslbe for better performance.
- label: the text of the label. It may contain end of line (\n) characters, which allows you to place a multi-line labels.
- initial_x: (optional, defaults to 0) the initial x position of the label
- initial_y: (optional, defaults to 0) the initial y position of the label
- centered: (optional, defaults to true) true or 1 if the label should be centered, false or 0 if it should not.
- CreateLinkedList: objectID, label, width, height, [initial_x, initial_y, linkPercent, verticalOrientation, linkPosEnd, numLabels]
- objectID: Non-negative integer that represents the ID of this object. Must be different from any ID currently active. Should be as small as posslbe for better performance.
- label: The label inside this linked list element (or the first label, if there are more than one)
- width: The width of the linked list element, in pixels
- height: The height of the linked list element, in pixels
- initial_x: (optional, defaults to 0) the initial x position of the linked list element
- initial_y: (optional, defaults to 0) the initial y position of the linked list element
- linkPercent: (optional, defaults to 0.25) The percentage of the linked list element that the outgoing pointer takes up.
- verticalOrientation: (optional, defaults to true). Should the linked list element be vertial (true) or horizontal (false)
- linkPosEnd: (optional, defaults to false). Should the poiner appear at the bottom or left of the linked list element (true), or the top or right of the linked list element (false)
- numLabels: (optional, defaults to 1). The number of labels that the linked lists element can hold. See the adjacency list implementat of a graph visualization for an example of a linked list element with more than 1 label.
- CreateBTreeNode: objectID, widthPerLabel, height, numLabels, inital_x, initial_y, backgroundColor, foregroundColor Somewhat special-purpose animated object created for B-Trees. Single rectangle containing any number of labels, with no dividing lines between the labels. Edges can be attached between each label, and to the left of the leftmost label, and to the right of the rightmost label. See the BTree and B+ Tree visualizations for examples.
- objectID: Non-negative integer that represents the ID of this object. Must be different from any ID currently active. Should be as small as posslbe for better performance.
- widthPerLabel: The width of the B-Tree node is the number of labels * the width per label. Value is in pixels.
- height: Height of the B-Tree node in pixels
- numLabels: The number of labels in the BTree node.
- initial_x: The initial x position of the B-Tree node
- initial_y: The initial y position of the B-Tree node
- backgroundColor: The initial color of the background of the rectangle, using HTML colors (#FF0000 for red, #00FF00 for green, and so on)
- backgroundColor: The initial color of the forground of the rectangle, using HTML colors (#FF0000 for red, #00FF00 for green, and so on)
- Delete: objectID
- objectID: The ID of the object to delete. All edges incident on this object will be removed. (If the delete is undone, then all such edges will be restored). Once an Animated Element has been deleted, its ID is free to be used again. Note that overly complicated ID management (which is really memory management, since IDs are just indicies into a "memory array" of active animated objects) is not necessarily recommended, since it can lead to some subtle bugs.
Object Manipulation Commands
- Move: objectID, toX, toY Move the object smoothly over the next step from the current position to the new position
- objectID: The ID of the object to move. The object must exists, or an exception will be thrown
- toX: The new X location to move to
- toY: The new Y location to move to
- SetPosition: objectID, toX, toY Move the object immediately to the new position at the beginning of the next step
- objectID: The ID of the object to move. The object must exists, or an exception will be thrown
- toX: The new X location to move to
- toY: The new Y location to move to
- SetForegroundColor: objectID, color Sets the foreground color (outline color and label color) of an object. Note that if an object has several labels this will set the color of all labels.
- objectID: The ID of the object to modify. The object must exists, or an exception will be thrown
- color: New foreground color (string representing HTML color, like "#ff0000")
- SetBackgroundColor: objectID, color Sets the background color of current object. Note that if an object has several labels this will set the color of an object.
- objectID: The ID of the object to modify. The object must exist, or an exception will be thrown
- color: New background color
- SetHighlight: objectID, highlightVal Mark an object as either highlighted or unhighlighted, based on the value of highlightVal. Objects that are highlighted will pulse red. Any object can be highlighted (thought labels are slightly harder to read when highlighted) Note that if an object is left highlighted after an animation is ended, it will not pulse until the animation starts again. Edges can be highlighted using the highlight edge command.
- objectID: The ID of the object to modify. The object must exists, or an exception will be thrown
- highlightVal: 1 or true, turn on highlighting. 0 or false, turn off highlighting.
- SetText: objectID, newText, [textIndex] Sets the value of the label associated with the object (the printing withing a circle, for instance).
- objectID: The ID of the object to modify. The object must exists, or an exception will be thrown
- newText: The new text of the label
- textIndex: (optional, defaults to 0) Index of the text label to change. Only used in objects that have more than one text label (B-Tree nodes, Linked List nodes). If the object does not support multiple labels, this is ignored.
- SetAlpha: objectID Sets the alpha (transparency) of the object. 0 is completely transparent, 1 is completely opaque. Works for all objects.
- objectID: The ID of the object to modify. The object must exists, or an exception will be thrown.
- SetHeight: objectID, newHeight Sets the height (in pixels) of the object.
- objectID: The ID of the object to modify. The object must exists, or an exception will be thrown
- newHeight: The new height of the object.
- SetWidth: objectID, newWIdth Sets the width (in pixels) of the object.
- objectID: The ID of the object to modify. The object must exists, or an exception will be thrown
- newWidth: The new width of the object.
- SetTextColor: objectID, newColor, [textIndex] Sets the color of the label associated with the object
- objectID: The ID of the object to modify. The object must exists, or an exception will be thrown
- newColor: The new color to set. As with all colors, should be a html color string
- textIndex: (optional, defaults to 0) If the object contain multiple labels (such as a linked-list node, or a B-Tree node) determine which label to change the color of. If the object only has one label, this parameter is ignored.
- SetNull: objectID, nullValue Currently only used for linked-list elements. Should the area set aside for the pointer in the linked list object be drawn as a null pointer (slash through the field)? This should probably be automated (draw the slash if and only if the node is not connected to anything), but for now this must be done manually.
- objectID: The ID of the object to modify. The object must exists, or an exception will be thrown
- nullValue: 0 or false for do not draw the slash, 1 or true for draw the slash.
- SetNumElements: objectID, numElements Currently only used for B-Tree nodes. Changes the number of labels stored in this B-tree node. Should probably be extended to at least Linked-list nodes.
- objectID: The ID of the object to modify. The object must exists, or an exception will be thrown
- numElements: integer, the number of elements this B-Tree node should have
- AlignRight: object1ID, object2ID Align object1 so that it is immediately to the right of object2. Very handy for lining up labels (where you don't necessarily know the width of the label), but can be used with any two objects.
- object1ID: The ID of the object to move. The object must exists, or an exception will be thrown
- object2ID: The ID of the object used to align object1. The object must exists, or an exception will be thrown
- AlignLeft: object1ID, object2ID Align object1 so that it is immediately to the left of object2. Very handy for lining up labels (where you don't necessarily know the width of the label), but can be used with any two objects.
- object1ID: The ID of the object to move. The object must exists, or an exception will be thrown
- object2ID: The ID of the object used to align object1. The object must exists, or an exception will be thrown
- AlignTop: object1ID, object2ID Align object1 so that it is immediately on top of of object2. Very handy for lining up labels (where you don't necessarily know the width of the label), but can be used with any two objects.
- object1ID: The ID of the object to move. The object must exists, or an exception will be thrown
- object2ID: The ID of the object used to align object1. The object must exists, or an exception will be thrown
- AlignBottom: object1ID, object2ID Align object1 so that it is immediately below object2. Very handy for lining up labels (where you don't necessarily know the width of the label), but can be used with any two objects.
- object1ID: The ID of the object to move. The object must exists, or an exception will be thrown
- object2ID: The ID of the object used to align object1. The object must exists, or an exception will be thrown
Edge Manipulation Commands
Edges are manipulated by giving the two objects associated with the edge. While edges can be graphically directed or undirected, all edges under the hood have a direction, which is the direction that they were given when the edge was created. There can only be one edge from any object to any other object (though there can be an edge from object1 to object2, and a different edge from object2 to object1.) Edges are always referred to by two IDs - the objectID of the "from" object, followed by the objectID of the "to" object. Any object can be connected to any other object.- Connect: fromID, toID, [linkColor, curve, directed, label, anchorPosition]
- fromID: The ID of the object at the tail of the new edge
- toID: The ID of the object at the head of the new edge
- linkColor: (optional, defaults to "#000000") The color of the edge
- linkColor: (optional, defaults to false) true for a diected edge, false for an undirected edge
- curve: (optional, defaults to 0.0) The "curviness" of the edge. 0.0 is perfectly straight, positive values arc to the right, negative values arc to the left.
- directed (optional, defaults to true). True if the edge is directed, false if the edge is undirected
- label (optional, defaults to ""). The label that appears along the edge (useful for things like edge costs in graphs)
- anchorPosition (optional, defaults to 0) If the edge could have more than one attachment postion at the "from" node, (currently only used for B-Tree nodes, but could well be expanded to things like doubly-linked lists) the index of the attachment position to use. Ignored for animated objects that do not have multiple attachment positions
- Disconnect: fromID, toID Removes an edge between two elements. If there is no edge, then this operation is a no-op.
- fromID: The ID of the "From" direction of the edge
- toID: The ID of the "To" direction of the edge
- SetAlpha: objectID Sets the alpha (transparency) of the object. 0 is completely transparent, 1 is completely opaque
- objectID: The ID of the object to modify. The object must exists, or an exception will be thrown
- SetEdgeHighlight: fromID, toID, highlightVal Mark an edge as either highlighted or unhighlighted, based on the value of highlightVal. Edges that are highlighted will pulse red.
- fromID: The ID of the "From" direction of the edge
- toID: The ID of the "To" direction of the edge
- higlightVal: 0 or false, turn of higlighting. 1 or true, turn on highlighting.
- ,
Special Commands
- Step: <No parameters> The step command allows you to keep everything from happening at once. The way that most animations will work is that you will create a group of objects, then do a step, then do some movements, then do a step, then do more movements, then do a step, and so on. All commands that appear between adjacent steps will happen simultaneously. Each step represents where the animation will pause when it is in single-step mode.
- SetLayer objectID, newLayer Sets the layer of the object. All objects default to layer 0, and the "shown" layer always defaults to 0. You can change the layers of different objects, and then change the list of which layers are currently shown, to show or hide objects dynamically. (This is often useful for allowing the user to show or hide information, or to alternate between different versions of a representation). An object will only appear if its layer is one of the layers listed to be shown. An edge will only appear of each of the objects that it connect are to be shown. While commands cannot be executed while an animation is running, the global set of visible layers can be changed while an animation is running
- objectID: The ID of the object to modify. The object must exists, or an exception will be thrown
- layer: The new layer for this object. Each object must live in one and only one layer (though any combination of layers can be shown at any given time)
Simple Stack Example
Everything make sense so far? Time for a simple, complete example. A simple stack visualization can be found at: Looking at the complete SimpleStack.js file in its entirety:All code released under a FreeBSD license
// Copyright 2011 David Galles, University of San Francisco. All rights reserved. // // Redistribution and use in source and binary forms, with or without modification, are // permitted provided that the following conditions are met: // // 1. Redistributions of source code must retain the above copyright notice, this list of // conditions and the following disclaimer. // // 2. Redistributions in binary form must reproduce the above copyright notice, this list // of conditions and the following disclaimer in the documentation and/or other materials // provided with the distribution. // // THIS SOFTWARE IS PROVIDED BY David Galles ``AS IS'' AND ANY EXPRESS OR IMPLIED // WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND // FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALLOR // CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR // CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR // SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON // ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF // ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. // // The views and conclusions contained in the software and documentation are those of the // authors and should not be interpreted as representing official policies, either expressed // or implied, of the University of San Francisco
function SimpleStack(am, w, h) { this.init(am, w, h); } SimpleStack.prototype = new Algorithm(); SimpleStack.prototype.constructor = SimpleStack; SimpleStack.superclass = Algorithm.prototype;
SimpleStack.ELEMENT_WIDTH = 30; SimpleStack.ELEMENT_HEIGHT = 30; SimpleStack.INSERT_X = 30; SimpleStack.INSERT_Y = 30; SimpleStack.STARTING_X = 30; SimpleStack.STARTING_Y = 100; SimpleStack.FOREGROUND_COLOR = "#000055" SimpleStack.BACKGROUND_COLOR = "#AAAAFF"
function SimpleStack( ...However, all of the work of the constructor is done in the init function -- that way constructors of subclass can effectively call the constructors of their superclasses. For the init function in this case, we need to do very little work. In this simple example we are not adding any elements to the canvas at load time. All we need to do is set up our own internal data structures. We are keeping track of two arrays -- an array that stores the actual stack (stackValues), and an array that stores the objectIDs of the elements of the stack (stackID)
SimpleStack.prototype.init = function(am, w, h) { // Call the unit function of our "superclass", which adds a couple of // listeners, and sets up the undo stack SimpleStack.superclass.init.call(this, am, w, h); this.addControls(); // Useful for memory management this.nextIndex = 0; this.stackID = []; this.stackValues = []; this.stackTop = 0; }
this.popButton.onclick = this.popCallbackto add our callbacks. Why not? This would pass in the proper function, but not the proper contex -- essentially, it would be passing a pointer to the code of the function, without saving the "this" pointer. So we need to bind the "this" pointer to our function before we store it.
SimpleStack.prototype.addControls = function() { this.controls = []; this.pushField = addControlToAlgorithmBar("Text", ""); this.pushField.onkeydown = this.returnSubmit(this.pushField, this.pushCallback.bind(this), // callback to make when return is pressed 4, // integer, max number of characters allowed in field false); // boolean, true of only digits can be entered. this.controls.push(this.pushField); this.pushButton = addControlToAlgorithmBar("Button", "Push"); this.pushButton.onclick = this.pushCallback.bind(this); this.controls.push(this.pushButton); this.popButton = addControlToAlgorithmBar("Button", "Pop"); this.popButton.onclick = this.popCallback.bind(this); this.controls.push(this.popButton); }
Function.prototype.bind = function() { var _function = this; var args = Array.prototype.slice.call(arguments); var scope = args.shift() return function() { for (var i = 0; i < arguments.length; i++) { args.push(arguments[i]); } return _function.apply(scope, args); } }Moving on ... Next up is the reset function. All visualizations must implement the reset method. The reset method needs to restore all of our variables to the state that they were in right after the call to init. In our case, we only have 2 variables of importance. We could have recreated the arrays stackID and stackValues, but that is not necessary in this case, since we don't care about the current values in those arrays -- we will write over any value before we read it, once the stack top is 0.
SimpleStack.prototype.reset = function() { // Reset the (very simple) memory manager. // NOTE: If we had added a number of objects to the scene *before* any user // input, then we would want to set this to the appropriate value based // on objects added to the scene before the first user input this.nextIndex = 0; // Reset our data structure. (Simple in this case) this.stackTop = 0; }
SimpleStack.prototype.pushCallback = function() { var pushedValue = this.pushField.value; if (pushedValue != "") { this.pushField.value = ""; this.implementAction(this.push.bind(this), pushedValue); } } SimpleStack.prototype.popCallback = function() { this.implementAction(this.pop.bind(this), ""); }
SimpleStack.prototype.push = function(pushedValue) { this.commands = []; this.stackID[this.stackTop] = this.nextIndex++; this.cmd("CreateRectangle", this.stackID[this.stackTop], pushedValue, SimpleStack.ELEMENT_WIDTH, SimpleStack.ELEMENT_HEIGHT, SimpleStack.INSERT_X, SimpleStack.INSERT_Y); this.cmd("SetForegroundColor", this.stackID[this.stackTop], SimpleStack.FOREGROUND_COLOR); this.cmd("SetBackgroundColor", this.stackID[this.stackTop], SimpleStack.BACKGROUND_COLOR); this.cmd("Step"); var nextXPos = SimpleStack.STARTING_X + this.stackTop * SimpleStack.ELEMENT_WIDTH; var nextYPos = SimpleStack.STARTING_Y; this.cmd("Move", this.stackID[this.stackTop], nextXPos, nextYPos); this.cmd("Step"); // Not necessary, but not harmful either this.stackTop++; return this.commands; } SimpleStack.prototype.pop = function(unused) { this.commands = []; if (this.stackTop > 0) { this.stackTop--; this.cmd("Move", this.stackID[this.stackTop], SimpleStack.INSERT_X, SimpleStack.INSERT_Y); this.cmd("Step"); this.cmd("Delete", this.stackID[this.stackTop]); this.cmd("Step"); // OPTIONAL: We can do a little better with memory leaks in our own memory manager by // reclaiming this memory. It is recommened that you *NOT* do this unless // you really know what you are doing (memory management leads to tricky bugs!) // *and* you really need to (very long runnning visualizaitons, not common) // Because this is a stack, we can reclaim memory easily. Most of the time, this // is not the case, and can be dangerous. // nextIndex = this.stackID[this.stackTop]; } return this.commands; }
// Called by our superclass when we get an animation started event -- need to wait for the // event to finish before we start doing anything SimpleStack.prototype.disableUI = function(event) { for (var i = 0; i < this.controls.length; i++) { this.controls[i].disabled = true; } } // Called by our superclass when we get an animation completed event -- we can /// now interact again. SimpleStack.prototype.enableUI = function(event) { for (var i = 0; i < this.controls.length; i++) { this.controls[i].disabled = false; } }
//////////////////////////////////////////////////////////// // Script to start up your function, called from the webapge: //////////////////////////////////////////////////////////// var currentAlg; function init() { var animManag = initCanvas(); currentAlg = new SimpleStack(animManag, canvas.width, canvas.height); }
HTML Template
This visualization system is a combination of HTML and javascript -- you need a webpage to embed the javascript, and that webpage needs the following items:- A bunch of <script> tags in the header to load oll of the necessary scripts. These files need to be included in the correct order, based on dependancies. (It would be nice if javascript had a standard #include-like mechanism to avoid manually inserting all of these files in the HTM. While there are some ways around it -- dynamically inserting the <script> tags using javascript calls -- not all browsers seem to work with these somewhat hacky methods. A brute-force inclusion of all the files, in the proper order, works everywhere)
- An empty table with the id "algoControlSection" where the algorithm specific controls are to be placed
- A canvas element, where the animations will appear
- An empty table with the id "GeneralAnimationControls" where general animation controls are to be placed
- An onload = "init();" command in the body tag to kick everything off
<!DOCTYPE html> <html> <head> <title> Place your title here </title> <!-- css sheet for how the page is laid out --> <link rel="stylesheet" href="visualizationPageStyle.css"> <!-- jqueury stuff. Only used for the animation speed slider. --> <link rel="stylesheet" href="ThirdParty/jquery-ui-1.8.11.custom.css"> <script src="ThirdParty/jquery-1.5.2.min.js"></script> <script src="ThirdParty/jquery-ui-1.8.11.custom.min.js"></script> <!-- Javascript for the actual visualization code --> <script type = "text/javascript" src = "AnimationLibrary/CustomEvents.js"> </script> <script type = "text/javascript" src = "AnimationLibrary/UndoFunctions.js"> </script> <script type = "text/javascript" src = "AnimationLibrary/AnimatedObject.js"> </script> <script type = "text/javascript" src = "AnimationLibrary/AnimatedLabel.js"> </script> <script type = "text/javascript" src = "AnimationLibrary/AnimatedCircle.js"> </script> <script type = "text/javascript" src = "AnimationLibrary/AnimatedRectangle.js"> </script> <script type = "text/javascript" src = "AnimationLibrary/AnimatedLinkedList.js"> </script> <script type = "text/javascript" src = "AnimationLibrary/HighlightCircle.js"> </script> <script type = "text/javascript" src = "AnimationLibrary/Line.js"> </script> <script type = "text/javascript" src = "AnimationLibrary/ObjectManager.js"> </script> <script type = "text/javascript" src = "AnimationLibrary/AnimationMain.js"> </script> <script type = "text/javascript" src = "AlgorithmLibrary/Algorithm.js"> </script> <script type = "text/javascript" src = "Place path to your javascript file here"> </script> </head> <body onload="init();" class="VisualizationMainPage"> <div id = "container"> <div id="header"> <h1>Place your Header here </h1> </div> <div = id = "mainContent"> <div id = "algoControlSection"> <!-- Table for buttons to control specific animation (insert/find/etc) --> <!-- (filled in by javascript code specific to the animtion) --> <table id="AlgorithmSpecificControls"> </table> </div> <!-- Drawing canvas where all animation is done. Note: can be resized in code --> <canvas id="canvas" width="1000" height="500"></canvas> <div id = "generalAnimationControlSection"> <!-- Table for buttons to control general animation (play/pause/undo/etc) -> <!-- (filled in by javascript code, specifically AnimationMain.js) --> <table id="GeneralAnimationControls"> </table> </div> </div> <!-- mainContent --> <div id="footer"> <p><a href="Algorithms.html">Algorithm Visualizations</a></p> </div> </div><!-- container --> </body> </html>
Quirks and Advanced Techniques
Object Display Order
If two object overlap, which one is placed on top? The animation system uses the following rules to determine draw order:- All non-highlighted items are drawn before all highlighted items (so highlighted items will appear on top of non-highlighted items)
- All items with the same highlight state are drawn in order of their identifiers (so objects with larger identifiers will be drawn in front of objects with small identifiers)