Monday, October 25, 2010

Navigating a Maze

My goal with my drawing program and moving icon programs is to be able to combine them so that the icons will treat the drawn lines as walls. This is my initial pass at that.

I started with the icon mover from last time which already had a Map class.  I added helper methods that will disconnect adjacent cells. breakCells to disconnect a cell from its neighbor and breakPoint to disconnect the two pairs of points that are diagonally touching at a point. breakCells takes a grid cell point, and breakPoint takes a lattice point. The relationship is that a grid cell has the same coordinates as the lattice point at its upper left corner.
  1 Map.prototype.breakCells = function(point, dir) {
  2   var cell = this.getCell(point);
  3   if (cell) cell.eraseEdge(dir); 
  4   cell = this.getAdjacentCell(point, dir);
  5   if (cell) cell.eraseEdge(dir.opposite());
  6 } 
  7 Map.prototype.breakPoint = function(point) {
  8   this.breakCells(point, Dir.NORTHWEST); 
  9   this.breakCells(point.delta(-1, 0), Dir.NORTHEAST); 
 10 }
The cell.eraseEdge just marks that edge as non-traversable so that it won't be included when the cell.getNeighbors call is made.

For this initial implementation I am sticking to the simpler case of just handling horizontal and vertical lines. I want to break apart any two cells that has a line that crosses between them and break any point that a line touches. I added a method breakGridLine which does this.
  1 Map.prototype.breakGridLine = function(line, dir, dx, dy){
  2   var p1 = line.p1; 
  3   while (!p1.eq(line.p2)) { 
  4     this.breakPoint(p1); 
  5     this.breakCells(p1, dir); 
  6     p1 = p1.delta(dx, dy); 
  7   } 
  8   this.breakPoint(line.p2); 
  9 }
dx and dy are the deltas that describe how to traverse the line and dir is the direction of the cells that are on the other side of the line.

Now I just added another method that loops over all the lines and breaks them apart.
  1 Map.prototype.breakLines = function(lines) {
  2   for (var i in lines) {
  3     var line = lines[i]; 
  4     if (line.slope.rise == 0) {
  5       this.breakGridLine(line, Dir.NORTH, 1, 0);
  6     } else if (line.slope.run == 0) {
  7       this.breakGridLine(line, Dir.WEST, 0, 1);
  8     } else { 
  9       // ignore diagonal lines for now 
 10     } 
 11   } 
 12 }
If we call this method with the lines from a drawn map, our existing BFS searching algorithm will now cause our icons to traverse the grid. Now its just a matter of calling the breakLines method when we start to move icons.
  1 IconControls.prototype.setLines = function(lines) {
  2   this.map = new Map(this.iconLayer.grid.width, this.iconLayer.grid.height);
  3   this.map.breakLines(lines); 
  4 }
And of course the HTML to add the buttons, etc, which I won't bore you with today. Anyway, here is the demo.

Demo

       

Monday, October 18, 2010

Why Are Web Frameworks So Bad

I debated what punctuation was appropriate for this post. Should it be a period because I this post will explain the answer? Should it be a question mark because I am trying to understand? Should it be an exclamation point because I am surprised? After a little bit of thought, I think it should be "Why are web frameworks so bad?!?!?!?!?!?!" because I want to rant!

Oh, and as a quick caveat, I am talking about the two environments that are primarily used in the business world today, i.e. .NET and Java.

ASP.NET

ASP.NET tries to just extend Windows Forms programming so that creating a web app is just like creating a desktop app. The promise being that the legion of Windows programmers will suddenly be able to create rich web apps without learning anything new. The reality - programming for the web has different constraints than programming for the desktop, and while ASP.NET tries to hide it reality leaks through. Any time you go off the beaten path you risk getting bitten. Unless you truly understand the seven stages of the page life-cycle, problems can arise like losing user input.

What It Gets Right
Code Behind
An ASP.NET page is actually two files.  There is the .aspx file which is where you put your HTML with a minimal amount of code.  The other file is the .aspx.cs file (assuming C#) which has specific methods that will be called prior to displaying the .aspx.  You can put the meat of your code in this C# file, and populate variables which can be used in the .aspx.  This makes for a good separation of concerns between coding and markup.

Components
It is also easy to create a custom ASP.NET component with its own markup (.ascx) and code behind (.ascx.cs) files.  These components can then be fairly easily embedded into your pages (or other components).  This works fairly well.

What It Gets Wrong
Wow - where to start.  I guess I'll limit myself to the three biggest complaints that I have.

Complexity
When you create a page in ASP.NET you are logically building a tree of Components. The HTML is generated by walking this tree. So far so good. The complication comes in that the HTML form variables that are posted back are specified and accessed via these components. So after the user performs an action, the webserver must be able to exactly recreate the Component tree from before so that your ASP code can access any user modified values. Recreating this tree is no trivial task, and while it just works most of the time, if you do something that causes it to break - understanding and tracking down your bugs can be a nightmare. And dynamically creating components based on user input is likely to cause this breakage unless you *really* understand what is going on. Ugh.

Doesn't fit the web model
ASP.NET really tries to mimic non web GUI programming. A .aspx page is a single Form containing lots of Components. What this translates to is a single HTML form that typically has all its buttons post back to the same page. So if you want to logically have different forms on your web page that go to different places, you can't do it. You can fake it, via redirects after the postback, but this is really a perversion of web semantics. Oh, plus the built in components that try to hide the fact that they really just turn into a <div> or an image tag or what not, don't give you full access to the HTML properties of those tags. i.e. ASP.NET forces (strongly encourages?) you to write web pages in a very specific way whether that makes sense for the end user or not.

Page Bloat
ASP.NET adds a hidden input variable called __VIEWSTATE to the pages it creates. This variable contains serialized data that is used after a post to help it recreate the Component tree exactly. This can be potentially quite large, which slows down page load time. Even though broadband is fairly common, many connections don't have a high upload speed, and this data is both downloaded and uploaded with every page view, often causing website to load slowly. To make matters worse, if you don't really understand how this variable is used (and you can create sites without even being aware of its existence), it is really easy to end up with a lot of extra data in this variable that isn't even needed.

Java

Java provides multiple option. First there were Servlets and JSPs, which are functional but often require you to mix your code and your mark up and write generally ugly code. To solve this a number of frameworks which either sit on top of or replace JSPs have come out like Struts, Facelets, JSF, and Seam. Seam is actually a framework that uses other frameworks, just in case this wasn't confusing enough.  For this conversation I'll be talking about Seam using Facelets since that is what I am currently playing with.

What It Gets Right
Hmm... Well, I guess these frameworks are much better than the original Servlet/JSP approach for separating HTML markup and code.

What It Gets Wrong
Again, I'll pick three complaints to highlight.

Dependency Injection Magic
In Seam you can use annotations to give a Name to your class.  You now have access to a variable of that name in the xhtml front end markup.  Some people would probably feel that this belongs in the "what it gets right" category, however I think it is too much magic for my taste.  When I am reading an xhtml file and I come across a variable, there is no easy way to know what it is.  I have to go to every class to find the one with the appropriate annotation.  This does not make for easy to understand code.

Too Many Config Files
Seam claims to have greatly improved the "too many config files" problem, but my current project has:
  • components.xml
  • faces-config.xml
  • jboss-web.xml
  • pages.xml
  • web.xml
  • Plus a page.xml file for every .xhtml page
As you've probably noticed, in addition to a lot of files every single one of these config files is in XML which means there is also a lot of extra verbosity.

Ugly Syntax
Do you remember back when you learned C?  You write printf("hello world\n"); inside a main and it doesn't compile.  Why not?  Oh, you need to tell the compiler to include the standard i/o library.  Pretty soon you just automatically put #include <stdio.h> at the top of all of your programs.  Similarly, with our facelet code we have includes so that we can have access to the special tags in our xhtml.  Here is an example of the concise and easy to remember way this is specified:

<ui:composition xmlns="http://www.w3.org/1999/xhtml"
  xmlns:ui="http://java.sun.com/jsf/facelets"
  xmlns:h="http://java.sun.com/jsf/html"
  xmlns:f="http://java.sun.com/jsf/core"
  xmlns:a="http://richfaces.org/a4j"
  xmlns:rich="http://richfaces.org/rich"
  xmlns:s="http://jboss.com/products/seam/taglib">


I don't think anything further needs to be said.

What Do I Want
This is probably a topic for a whole other post, but here are a couple quick thoughts.
  • Simple and clear separation of code and markup so I can minimize the amount of code that is intermingled with html
  • A library of useful existing components
  • Easy to write my own html components
  • Makes it easy to do the common web stuff (session management, cookies, parameter passing, url building, security precautions, etc.)
  • Does NOT hide any aspects of the web, just SIMPLIFY it
    • I want to know how and what parameters are passed
    • I want to know how they go in/out of components libraries
    • I want it to be easy to integrate components (e.g. javascript libraries) that were written without any knowledge of this framework.
    • I want to be able to control the specific HTML that is generated.
  • Good documentation - something Java does well is good JavaDoc documentation on the supplied system libraries.  I want my frameworks to have similar quality documentation.
  • Is transparent about what it does, so when I have a bug I can easily find it by reading the aforementioned document, rather than having to do Google searches in the hope of finding a blog post or stackoverflow question which describes *and* answers my problem.

    Monday, October 11, 2010

    Breadth First Search for Moving Icons

    While I can move icons around on a grid, they aren't really moving the way I want. For the app that I am envisioning, icons should only be allowed to move in the four cardinal directions and the four diagonals. This post is about how I enforce that, and about setting some things in place for future enhancements.

    To help I've created a Map class and a Cell class. A map consists of a bunch of cells that are connected. The cells correspond to the squares in a grid that the icons are allowed to be and they are connected along the paths that they are allowed to move. Until I've added support for drawing walls, each cell is connected along the 8 directions around it. The exception, of course, are along the 4 edges where the cells are only connect to the cells that exist.

    To calculate distance, I follow the D & D convention and round the diagonal from √2 to 1.5. But since I like integer arithmetic I make the four cardinal directions have a distance of 2 and the diagonals have a distance of 3. Now that I have a map, rather than just drawing a straight line from the start to the finish, I calculate the shortest legal path and make these moves.
      1 IconControls.prototype.click = function(x, y){
      2   var point = this.iconLayer.getGridPoint(x, y);
      3   var cell = this.map.getCell(point);
      4   var icon = this.iconLayer.findIcon(point);
      5   if (icon) { 
      6     this.activeIcon = icon; 
      7     this.lastCell = cell; 
      8   } else if (this.activeIcon) {
      9     var path = this.map.shortestPath(this.lastCell, cell);
     10     if (path) { 
     11       for (var i in path) {
     12         this.activeIcon.moveTo(path[i].point);
     13       } 
     14       this.lastCell = cell; 
     15     } else { 
     16       alert("destination is unreachable.");
     17     } 
     18   } 
     19 }
    In the above code, lines 6-7 handle the case where you click on an icon and lines 9-17 move the icon. The shortestPath method call on line 9 returns a contiguous set of cells that comprise a path from start to finish, if one exists.  The loop in lines11-13 then moves the icon to each of these cells in turn.  Line 16 warns the user if no path exists.  This isn't possible yet, but will be once we start adding walls to our grid.

    To calculate the shortest path, I set the destination cell as having a cost of 0 and all of the other cells as having a large cost. I now do a breadth first search from the destination to the source, recording the distance in each cell along the way.  I can now calculate the path from source to destination with a greedy algorithm.  Note that since the triangle inequality holds, the shortest path will have as few or few steps than any other path, and so a breadth first search is good enough and I don't need to use Djikstra's algorithm.  If, in the future, this condition does not hold, I will have to rewrite this code.
      1 Map.prototype.shortestPath = function(src, dest){
      2   for (var i in this.cells) {
      3     this.cells[i].cost = this.MAX_COST;
      4   } 
      5   dest.cost = 0; 
      6   var queue = new PriorityQueue();
      7   queue.push(dest, 0); 
      8   while (!queue.isEmpty()) { 
      9     var cell = queue.pop(); 
     10     if (cell == src) return this.createPath(src, dest);
     11     var choices = cell.getNeighbors(); 
     12     for (var i in choices) {
     13       var move = choices[i]; 
     14       var cost = cell.cost + move.cost; 
     15       if (cost >= move.cell.cost) continue;
     16       move.cell.cost = cost; 
     17       queue.push(move.cell, cost); 
     18     } 
     19   } 
     20   return null; // no such path
     21 }
    Lines 2-7 initialize our state while line 8-19 is the main loop of the search. getNeighbors returns the list of valid neighbors of this cell and the cost to move there (2 for the cardinal directions, and 3 for the diagonals) and this list is sorted by cost.  On line 15 we check if the cost of moving to a cell from the current location is lower than any previously considered path.  If it is, we set the cost on line 16 so we won't try another path with the same cost and on line 17 we push that node into our priority queue of nodes to consider.  The createPath call on line 10 calculates the path using the stored cost in each cell.
      1 Map.prototype.createPath = function(src, dest){
      2   var list = [src]; 
      3   while (src != dest) { 
      4     var cost = this.MAX_COST;
      5     var next; 
      6     var moves = src.getNeighbors(); 
      7     for (var i in moves) {
      8       var cell = moves[i].cell; 
      9       if (cell.cost < cost) { 
     10         next = cell; 
     11         cost = cell.cost; 
     12       } 
     13     } 
     14     list.push(next); 
     15     src = next; 
     16   } 
     17   return list; 
     18 }
    As describe above, this algorithm just greedily chooses nodes closer to the destination until it reaches the destination.  The loop in lines 7-13 makes the greedy calculation and it is added to the path on line 14.

    Demo

    This demo is just like the previous demo, except the icons will move only along the 8 main directions.  As before click an icon, click a destination, lather, rinse, and repeat.

    Monday, October 4, 2010

    Tell it to the Bear

    In 1992, I was on a team that was one of the finalists for SuperQuest and we spent three weeks that summer at Reed College to work on our projects. While there, we were told a story about solving computer problems that has stuck with me.

    Reed College's computer lab had a couple of TAs on hand so that students who were stuck on their programming assignments could get help. However, there was due diligence that you had to do first. Outside the TAs' office, there was a desk. On the desk was a teddy bear. Before you could go in to see the TA you had to explain your problem to the stuffed animal. Only if the bear couldn't solve your problem were you allowed to talk to the TA. Apparently they had one smart bear, as a good percentage of the students who talked to the bear never went on to the TA and sometimes there was a line to talk to the bear even when it was off hours and there were no TAs on duty.

    On the surface this seems insane - how could a stuffed bear solve programming problems? And yet, I suspect many of you are nodding along and not surprised at all that this works. I have, on numerous occasions, when stuck, explained my problem to someone else, and figured out the solution before they even said anything to me. I have also been the bear for many other people, watching them solve their problem as they tell it to me.

    it's a very specific way of thinkingSo why does this work so well? Obviously explaining your problem to anyone (anything) makes you stop and think. However, it is more than just random thinking, it's a very specific way of thinking.  You have to explain not just your solution, but the problem to the listener. This forced thinking through of the problem will often show a part of the problem that your incorrect solution is ignoring. You are also forced to be orderly, go over every part of the solution, and explain any shortcuts that you took and the assumptions made. Explaining your assumptions will often highlight errors and actually verbalizing the steps taken can show when steps are missing. The other thing that happens when you are talking, is it forces you to slow your thoughts down. This can sometimes be enough to pop you out of your rut and let your brain come up with a better idea.

    So should we all have a teddy bear to have on our desk at work? I'll be honest, I am not sure I have the courage to have a conversation with a stuffed animal where coworkers could see and hear me. However, I think there is a business opportunity here. You could sell Answer Bears to organizations and then sell consulting services (at an outrageous rate, of course) to firms to set up the bear's desk, procedures for talking to the bear, etc. If you can make it the next technology fad, you'll get rich!  Until someone does this though, if you don't have anyone to talk through problems with, it is worth going through the steps as if you were.

    Monday, September 27, 2010

    Moving images in JavaScript

    So now that I have a drawing program and can save drawings, I am ready for the next step. I want to be able to place an icon on the grid and be able to move it around, treating the lines drawn as walls. This next app is a little simpler though and will just move icons around. I will leave it for a future app to combine the two.

    My first step was to get an icon. I have no artistic skill, so I downloaded icons. To make sure I don't step on anyone's licensed toes I grabbed images from commons.wikimedia.org.

    Next was to create the HTML. The HTML looks very similar to the drawing program, except that I have an icon layer rather than a drawing layer. Also, I don't need to show any control information, so I am did away with the control layer.
    <div id='windowContainer'> 
      <canvas id="gridLayer" class="gridLayer" height="500" width="800"></canvas>
      <canvas id="iconLayer" class="gridLayer" height="500" width="800"></canvas>
    </div> 
    
    Next I created some helper classes. I have an Icon class which holds the image, the location of the icon, knows how to move the icon, and how to draw the icon. I have an IconLayer class which keeps track of all of the icons and is responsible for drawing/clearing the icon layer as a whole. I have a IconControl class which is responsible for tracking mouse clicks and calling the move methods on the appropriate icon at the appropriate time. I also reused the Grid class and Geometry classes from before.
    function Icon(img, iconLayer, gridPt) { /* code */ }
    Icon.prototype.draw = function() { /* code */ }
    Icon.prototype.setGridPoint = function(point) { /* code */ }
    Icon.prototype.moveTo = function(point) { /* code */ }
    
    function IconLayer(canvas, grid) { /* code */ }
    IconLayer.prototype.draw = function() { /* code */ }
    IconLayer.prototype.addIcon = function(img, gridPoint) { /* code */ }
    IconLayer.prototype.findIcon = function(point){ /* code */ }
    
    function IconControls(iconLayer) { /* code */ }
    IconControls.prototype.click = function(x, y) { /* code */ }
    
    I want the movement of the icons to be visible to the user which means that I can't just draw them at their destination. So, to move an icon, I'll erase it, draw it slightly closer to the new locations, and then wait a little bit and repeat the process. However, if I have two icons moving, I don't want to be redrawing twice as often. My solution to this is to have each icon, when it is moving, to just update its own location, but not to redraw. The IconLayer will periodically redraw itself with the icons in their new location. To keep from redrawing repeatedly when no icons are moving, the IconLayer will only redraw as long as at least one Icon is moving.

    I was concerned about threading issues, but it appears that while JavaScript is asynchronous, it is actually single threaded. This means I shouldn't have to worry about race conditions. Of course if a function goes into an infinite loop, it does mean nothing else will run. Anyway, here are the methods for moving an icon.
      1 Icon.prototype.movePerUnit = 5; 
      2 Icon.prototype.delayPerMove = 50; 
      3 Icon.prototype.moveTo = function(point){ 
      4   this.moveQueue.push({gridPoint:point, realPoint:this.grid.getReal(point)});
      5   if (!this.moving) {
      6     this.moving = true;
      7     this.iconLayer.incrMovingIcon(); 
      8     this.moveImpl(); 
      9   } 
     10 } 
     11 Icon.prototype.moveImpl = function(){ 
     12   var move = this.nextMove();
     13   if (!move) { 
     14     this.moving = false;
     15     this.iconLayer.decrMovingIcon(); 
     16   } else { 
     17     this.realPoint.x += move.dx; 
     18     this.realPoint.y += move.dy; 
     19     if (--move.steps < 1) { 
     20       this.realPoint = move.realPoint; 
     21       this.gridPoint = move.gridPoint; 
     22     } 
     23     setTimeout(this.moveFunc, this.delayPerMove);
     24   } 
     25 } 
     26 Icon.prototype.nextMove = function(){ 
     27   var move = this.moveQueue.peek();
     28   while (move != null && this.gridPoint.eq(move.gridPoint)) {
     29     this.moveQueue.pop(); 
     30     move = this.moveQueue.peek(); 
     31   } 
     32   if (move && !move.steps) { 
     33     move.steps = move.gridPoint.dis(this.gridPoint) * this.movePerUnit;
     34     move.dx = (move.realPoint.x - this.realPoint.x) / move.steps; 
     35     move.dy = (move.realPoint.y - this.realPoint.y) / move.steps; 
     36   } 
     37   return move; 
     38 }
    The moveTo method (lines 3-10) pushes the new move onto the moveQueue and then starts the move, if necessary. moveToImpl method does the real action of making a move. Lines 14-15 handles ending a move. Lines 17-18 actually make the move. Lines 20 and 21 make sure that we end on the right spot and gets rid of rounding errors that might've happend along the way. Lines 23 makes sure that the moveImpl function which will get called repeatedly. nextMove calculates the next move.  The loop on lines 28-31 finds the next move in the queue that isn't the current location. Lines 33-35 calculate how the move will be made, if that hasn't already been done for this move object.

    The function this.moveFunc that is referenced on line 23 is defined in the Icon constructor as
    var self = this;
    this.moveFunc = function() {self.moveImpl();};
    This is done so that we will have access to the appropriate this value when moveImpl is called by the setTimeout function. IconLayer's methods incrMovingIcon and decrMovingIcon called on lines 7 and 15 tell the IconLayer to start or stop drawing, if needed. These methods look like:
      1 IconLayer.prototype.refreshTimeout = 25;
      2 IconLayer.prototype.incrMovingIcon = function(){
      3   if (this.movingIconCt == 0) {
      4     this.drawTimer = setInterval(this.drawFunc, this.refreshTimeout);
      5   } 
      6   this.movingIconCt++; 
      7 } 
      8 IconLayer.prototype.decrMovingIcon = function(){
      9   this.movingIconCt--; 
     10   if (this.movingIconCt == 0) {
     11     clearInterval(this.drawTimer); 
     12     this.draw(); 
     13   } 
     14 }
    drawFunc (on line 4) is similar to moveFunc up above and is set in the constructor and refers to draw. draw just clears the IconLayer and then draws all of the Icons in their current location.  These methods scream "race-condition" to me, but as I stated above, JavaScript is actually run single-threaded, so this isn't an issue.


    Well, that was the meat of the code.  The only other interesting thing was the loading of the images. I originally just added the icons right away in the script, like:
      1 var names = ["smile", "frown", "kiss", "cool"];
      2 for (var i = 0; i < names.length; i++) {
      3   var img = document.getElementById(names[i] + "_icon");
      4   iconLayer.addIcon(img, {x: i*2, y:0});
      5 } 
      6 iconLayer.draw(); // ERROR! - doesn't work.
    and this caused errors because JavasScript would try drawing the image to the canvas before the browser had actually downloaded the whole image. Oops. I had to use the image.onload method to add the images after they were loaded. However, I really wanted to run after the last image was loaded. The code to do that is below. I add each icon as they are loaded, and keep a count. I don't call draw until the last one is loaded. Note that I actually add a property to the image object so that I will have access to it inside the onload method. And since onload is a property of the image, these parameters are accessible via the this variable inside the onload function, which is still kind of odd to my C++/Java/C# brain, but I am getting used to it.
      1 var names = ["smile", "frown", "kiss", "cool"];
      2 var loaded = 0;
      3 for (var i = 0; i < names.length; i++) {
      4   var img = document.getElementById(names[i] + "_icon");
      5   img.my_x = 2*i; 
      6   img.onload = function() { 
      7     iconLayer.addIcon(this, {x: this.my_x, y:0});
      8     loaded++; 
      9     if (loaded == names.length) { 
     10       iconLayer.draw(); 
     11     } 
     12   } 
     13 }
    Demo

    Anyway, here's the demo.  Click on one of the icons.  Click a destination.  Lather, rinse, repeat.

    Monday, September 20, 2010

    Javascript Prototype Inheritance

    A common desire when coding in an OO way is to create a class that inherits from another class. So how do you do this in Javascript? You can find various links on the web about how you can do this. However, just because “you can program FORTRAN in any language," doesn't mean that I want to program Java in Javascript. So, to me, learning Javascript means learning the Javascript way of doing things. It turns out that asking about inheritance in Javascript is the wrong question and you shouldn't want that, at least not exactly.

    Prototype
    Every object in Javascript has a prototype property. This prototype object is specified at the Function level. Whenever you try to look up a property on an object (and remember, object methods are really just properties), if the object doesn't have the specified property, it will try to look it up on the prototype property. Let's say we have a class defined as such:
    function Car() { 
    } 
    Car.prototype.wheels = 4; 
    Car.prototype.drive = function() { /* do something */ }
    And code that looks like:
    var car = new Car(); 
    var wheelCt = car.wheels;
    As you would expect, wheelCt = 4. Here's how it got its value:
    1. look at car.wheels - the car object has no property called "wheels"
    2. get the property car.prototype which is the Car.prototype object
    3. look at the wheels property of this object, which is 4.
    So now I want to create a Sedan object. I would like it to "inherit" the properties from Car. The way to do that is to instantiate a Car object and use this object as the Sedan prototype.
      1 Sedan.prototype = new Car() 
      2 Sedan.prototype.constructor = Sedan 
      3 function Sedan(color) { 
      4   this.color = color; 
      5 } 
      6 Sedan.prototype.doors = 4; 
      7  
      8 var newCar = new Sedan();
      9 var newWheelCt = newCar.wheels;
    As you would expect, newWheelCt = 4.  Here's how it got its value:
    1. look at newCar.wheels - the sedan object has no property called "wheels"
    2. get the property newCar.prototype (call it sedanProto) which is the Car object we created on line 1
    3. look at the wheels property of sedanProto - it has no property called "wheels"
    4. Get the property sedanProto.protototype which is the Car.prototype object
    5. look at the wheels property of this object, which is 4.
    We can, of course create further types and assign their prototypes to Sedan to increase this hierarchy as much as we want.

    Oh, in case your curious about the line 2 - each prototype object has a constructor property which is the Function that it is associated with.  The can be used to determine what "type" an object is at runtime.  If we don't set it then Sedan's prototype's constructor will still be associated with Car which is not what we want.

    Difference From Class Based Inheritance
    Behaviorally this is pretty similar to inheritance as we all know it - Sedan gets the properties of Car. So how does it differ? Well, a big difference is that in Class based inheritance there is effectively one Car object for every Sedan object. With the prototype approach there is a single Car object, the one assigned to the prototype, and it is shared by all the Sedans. This means that you can't send parameters from the constructor of Sedan to the constructor of Car (see below for ways around this). You have to know the parameters for the superclass constructor at class declaration time, like below.
      1 function Polygon(sides) { 
      2   this.sides = sides; 
      3 } 
      4  
      5 Square.prototype = new Polygon(4);
      6 Square.prototype.constructor = Square 
      7 function Square(length) { 
      8   this.length = length; 
      9 }
    So what if we wanted to add perimeter function to Polygon so all polygons have it. Something like:
    Polygon.prototype.perimeter = function() {return this.length * this.sides;}
    How does polygon get the length field? Obviously we could make the perimeter method take a length parameter, but that wouldn't make for a very good example. One thing that we could do, which is very disconcerting as a Java programmer, is nothing - it'll actually work as is.
    var s1 = new Square(5);
    var p1 = s1.perimeter();  // returns 20
    Even though Polygon doesn't have a length property, because of JavaScript's dynamicness, at runtime everything is hunky-dory since Square's this does have a length property.

    What if we really want Polygon to have a length property and not make every derived class specify this property? Maybe we have a base class with a bunch of instance properties that we want inherited? Well, there are a couple of approaches. One is to create a method that acts like a constructor in the base class and have the derived constructors call it.
    Polygon.prototype.init = function(length) { this.length = length; }
    function Square(length) { 
      this.init(length); 
    } 
    Another option is to write the base constructor so that it will handle 0 or all the arguments, and then call the base constructor:
      1 function Polygon(sides, length) { 
      2   this.sides = sides; 
      3   this.length = length; 
      4 } 
      5  
      6 Square.prototype = new Polygon();  // the prototype object has undefined sides and length property
      7 Square.prototype.constructor = Square 
      8 function Square(length) { 
      9   Polygon.call(this, 4, length);  // let Polygon's constructor update our properties
     10 }
    Note that a new Polygon is NOT created on line 9.  Polygon's constructor is being executed on Square's this property.  One thing you have to watch out with this approach is that when we instantiate a Polygon to assign it to a Square prototype (line 6), we are not passing any arguments. As long as in the Polygon constructor we are just assigning them to properties, that is fine. However, if we are going to dereference them (e.g. to do more advanced calculations), we must first check that they are defined or else we will get the equivalent of a null pointer exception.

    Wrong Approach
    One solution that might seem like a good idea is to set the prototype in the constructor, as such:
      1 function Square(length) { 
      2   this.__proto__ = new Polygon(4, length); // bad idea
      3 } 
      4 Square.prototype.area = function() { return this.length * this.length; }
      5  
      6 var square = new Square(10);
      7 var sideCt = square.sides; // returns 4
      8 var area = square.area() // ERROR! no such method
    This does give you access to the "superclass" properties, so line 7 will work as you would expect.  However, you are overwriting the default prototype object, so you lose all of its properties.  In the example above this means that the square object doesn't actually have the area method defined on line 4, which will cause an error to happen on line 8.  You'll also notice on line 3 that the actual name of the prototype property is __proto__, which is a good indicator that you shouldn't use it directly.

    Summary Is-A vs. Has-A

    In Class based inheritance, a derived class has an Is-A relationship with its parent class. An instance of the derived class is an instance of the parent class, just with more properties.  In the JavaScript prototype approach, the "derived" class Has-An instance of the "parent" class.  When property lookups are made on the derived instance, if it doesn't have the property it delegates the call to the parent object.  However, this automatic delegation can make the object behave as if it "is-a" parent object.  Which means I am going to stop writing now before I confuse you (or myself) any more.

    Monday, September 13, 2010

    Extending the Drawing Program with AJAX

    Recently I wrote a simple drawing program.  Now I want to be able to save what I drew and then reload it.  I want the data saved on a server somewhere, and I want the act of saving and loading to be done via AJAX. This is the story of how I accomplished this.

    Decisions

    Ruby on Rails vs. Google App Engine

    My first decision was what to use as my server platform.  I've had some experience with Java Servlets, ASP.NET, PHP, and Ruby on Rails.  Ruby on Rails is definitely the coolest of these.  However, given that I am a Google fan-boy, I at least considered the Google App Engine which also looks pretty cool.  However, laziness won out and I stuck to Rails because I know it and I am already tackling a bunch of new things on this project.  Plus I want to know Rails better.  At some point I'll have to come up with a project to try out with Google, and see if I want to change my mind.

    JQuery vs. Prototype

    As I said above, I want to accomplish the interaction between the client and the server via AJAX.  Well, actually I want to pass JSON messages, not XML, but I think they still call it AJAX.  Anyway, while I could do this myself, it seems to make sense to take advantage of existing libraries.  While there are a ton of JavaScript libraries, the two that seem to be the most popular are jQuery and Prototype.  Prototype is distributed with Rails and so is the natural choice.  But supposedly jQuery is much more lightweight and efficient, so I am going to go with jQuery.

    I realize that neither of the choices above seem to be very well researched.  Well, this is just a toy project - if I spend forever researching all the options then I'll never get anything done.  Just by doing something, hopefully I'll be better informed in the future.

    What I Did

    First I created a rails project:
    rails drawing
    and then I imported the HTML and JavaScript that I wrote into the public directory of the project.

    Of course I needed a database to store the maps in.  I decided to use SQLite for now because it is so easy to set up.  I'll probably move to mysql or something if/when I deploy it for real.  I then used the rails scaffold command to generate the stub rails code.

    ruby script/generate scaffold Map name:string content:text

    In theory, I don't really need the generated map controller and views.  However, being able to point a browser at <host>/map/ and see all of the uploaded maps provides a very easy way to test if maps are being saved.  I then created my AJAX controller with a save_map and load_map action.  Since these are intended to be used in an AJAX fashion, I didn't create any views for them.

    Ruby

    My intent was for the drawing program to pass the map as a JSON object to the AJAX call.  The controller could just save that to the database and read it back for a load.  As far as Ruby is concerned it is just a string.  Here is the ruby code that makes that work.
    class MyAjaxController < ApplicationController
      
      def save_map
        name = params[:name]
        mapData = params[:map].to_json
        map = Map.find(:first, :conditions=>{:name=>name})
        map.content = mapData if map
        map = Map.new(:name=>name, :content=>mapData) unless map
        map.save!
        render :text=>"ok"
      end
    
      def load_map
        name = params[:name]
        map = Map.find(:first, :conditions=>{:name=>name})
        render :text=>map.content
      end
    end
    As you can see, the save method just reads the name and map value from the posted parameters.  Since ruby tries to parse these as objects, I call to_json to get the map contents back into a string.  Then I just save it to the database (either as a new row, or updating an existing row).  load_map just returns the map content that was saved with the given name.  Neither of these methods have much in the way of error checking, so they are definitely not "production" ready, but they work great as a proof of concept.

    HTML

    Here are the controls I added to the page to allow saving and loading.
    <input type="text" id="name"/>
    <input type="submit" id="save" value="Save" />
    <input type="submit" id="load" value="Load" />
    

    JavaScript

    The JavaScript for making the AJAX call looks like this:
      1 $("#save").click(function() {
      2   var data = draw.save(); 
      3   var name = $("#name").get(0).value;
      4   $.post('/my_ajax/save_map', {name:name, map:data}, function() {
      5       alert("Map saved!"); 
      6   });  
      7 }); 
      8  
      9 $("#load").click(function() {
     10   var name = $("#name").get(0).value;
     11   $.getJSON('/my_ajax/load_map', {name:name}, function(data, textStatus) {
     12     control.reset(); 
     13     draw.load(data); 
     14   });  
     15 });
    Everything that starts with a $ is a jQuery function.  #save, #load, and #name refer to the HTML controls I've put on the page. The draw variable is the DrawingRecord instance, and control is a ControlLayer instance from the original drawing program.  I added a save and a load method to the DrawingRecord to save and restore the map.  Both Ajax calls $.post(...);   $.getJSON(...); take a URL, an object to pass to the server, and a function which is called when thecall returns (i.e. the A in AJAX).
    As for what the draw.save() method returns, originally I just tried using the DrawingRecord.lines object.  Unfortunately this caused problems - apparently jQuery tried to package up all the methods as well as the fields of the object.  So instead I made the save and load methods in DrawingRecord package up all of the points into a single array which can be easily passed back and forth.
      1 DrawingRecord.prototype.save = function(){
      2   var lines = [] 
      3   for (var i in this.lines) {
      4     var line = this.lines[i];
      5     lines.push(line.p1.x, line.p1.y, line.p2.x, line.p2.y); 
      6   } 
      7   return {lines:lines} 
      8 } 
      9 DrawingRecord.prototype.load = function(data) {
     10   this.reset(); 
     11   this.dontDraw = true;
     12   var temp = []; 
     13   for (var index in data.lines) {
     14     temp.push(parseInt(data.lines[index])); 
     15     if (temp.length == 4) {
     16       this.addLine(new Point(temp[0], temp[1]), new Point(temp[2], temp[3]));
     17       temp = []; 
     18     } 
     19   } 
     20   this.dontDraw = false;
     21   this.draw(); 
     22 }
    And with that, it basically all works.  Unfortunately, I can't have a live demo of this to put in this blog as I don't have a live server that I want to have committed to serving this project forever.