Sunday, August 29, 2010

JavaScript Drawing Program

I have decided to create a simple drawing program in JavaScript.  My goal is to provide a simple <draw straight lines on graph paper> application. I won't support curves, line styles, or colors. I would like to support erase and undo/redo. All points will be automatically snapped to lattice points. My vision is that you'll start with a piece of graph paper (i.e. a light blue grid). You should be able to click on two points to create a line. It would be nice if it showed you what you were about to draw before you draw it. i.e. this should be just like many other drawing program, just with less features.

If you don't want to read any of the details, jump to the bottom and see the end result.

Implementation Highlights

HTML 5 provides this nice tag, <canvas>, which looks very useful for drawing. Every modern browser, except Internet Explorer, seems to support it including the Android and iPhone mobile devices. Since I am writing this for myself, I am ok with IE not being supported.

I see this app as having 3 layers. The bottom layer is the grid. The middle layer is the actual drawing. The top layer is the control layer where it shows you what you are about to draw. It seems logical to me to implement this as 3 canvas instances that are all in the same location. I do this by putting all 3 canvas instance in the same div, and positioning them absolutely to the top left of this div. This seems to do the trick, as when I play with it, all 3 are superimposed and drawing on a higher layer covers the lower layer, and erasing the higher layer reshows the lower layer.
  1 <html> 
  2   <head> 
  3     <style> 
  4 #windowcontainer {position:relative; height:400px;}
  5 .gridLayer {position: absolute; top: 0px; left: 0px;}
  6     </style> 
  7     <script> 
  8 // javascript code goes here 
  9     </script> 
 10   </head> 
 11   <body>  
 12     <div id='windowContainer'>  
 13       <canvas id="gridLayer" class="gridLayer" height="400" width="600"></canvas> 
 14       <canvas id="drawLayer" class="gridLayer" height="400" width="600"></canvas> 
 15       <canvas id="controlLayer" class="gridLayer" height="400" width="600"></canvas> 
 16     </div> 
 17   </body> 
 18 </html>
Now I create 3 classes, one for handling each layer. The Grid knows how to map between browser coordinates and lattice coordinates, as well as how to draw itself. The DrawingRecord knows how to draw lines and keeps track of all of the lines that have been drawn. The ControLayer actually registers the mouse listeners and determines when lines should be drawn, delegating functionality to the other two objects when appropriate.
  1 function Grid(canvas, width, height) { 
  2   this.ctx = canvas.getContext('2d');
  3   this.width = width; 
  4   this.height = height; 
  5 } 
  6 Grid.prototype.color = "#00FFFF"; 
  7 Grid.prototype.size = 25; 
  8 Grid.prototype.offsetX = 10; 
  9 Grid.prototype.offsetY = 10; 
 10 Grid.prototype.draw = function(){ /* implementation */ }
 11 Grid.prototype.getLatticePoint = function(x, y){ /* implementation */ }
 12 Grid.prototype.getReal = function(latticePoint){ /* implementation */ }
 13  
 14 function DrawingRecord(canvas, grid){ 
 15   this.canvas = canvas; 
 16   this.ctx = canvas.getContext('2d');
 17   this.grid = grid; 
 18   this.lines = {}; 
 19   this.nextLine = 0;
 20 } 
 21 DrawingRecord.prototype.addLine = function(p1, p2){ /* implementation */ }
 22 DrawingRecord.prototype.eraseLine = function(p1, p2){ /* implementation */ }
 23 DrawingRecord.prototype.draw = function(){ /* implementation */ }
 24 DrawingRecord.prototype.reset = function() { /* implementation */ }
 25  
 26 function ControlLayer(canvas, grid, drawRecord){
 27   this.ctx = canvas.getContext('2d');
 28   this.canvas = canvas; 
 29   this.grid = grid; 
 30   this.drawRecord = drawRecord; 
 31 } 
 32 ControlLayer.prototype.drawTempLine = function(){ /* implementation */ }
 33 ControlLayer.prototype.click = function(e){ /* implementation */ }
 34 ControlLayer.prototype.onmousemove = function(e){ /* implementation */ }
 35 ControlLayer.prototype.registerMouse = function(){
 36   var self = this;
 37   this.canvas.addEventListener("click", 
 38                    function(e){ self.click(e); }, 
 39                    false); 
 40   this.canvas.onmousemove = function(e){ self.onmousemove(e); }
 41 }
You can see one interesting JavaScript thing that I learned in the registerMouse method in lines 36-40.  I create a self variable which is the same as this.  If I don't do this, when canvas.onmousemove is called, the this object will refer to the canvas not the ControlLayer, since it is canvas's onmousemove that is being called.  Since I don't actually want an infinite loop, I can't do this.  By creating a local 'self' variable I make it a free variable (if I am using the closure terminology correctly) which will refer to this ControlLayer object for all time.

Erasing Lines

Erasing a line segment was more complicated than I had first hoped. It turns out that there doesn't seem to be a "clearLine" method in the canvas context. So, to accomplish an erase I do something like:
  1. Remove the line segment from the list of lines that have been drawn
    1. For each existing line segments
      1. If it doesn't overlap with the erase line segment go to next segment
      2. Remove the existing line segment.
      3. Determine if the overlap if full or partial, and if partial, add the shorter new line segment(s) back to the list.
  2. Clear the drawing layer
  3. Redraw all of the existing line segments
Undo/Redo

An undo feature is always really nice to have, and I once read (I don't remember where) about a project where it was a real pain to retrofit it in after the fact.  So undo/redo is one of the first features I am writing.  Logically, what I have is a stack of actions.  Undo moves us down the stack and redo moves us back up.  Since functions are first class objects, it is easy to store them on the stack.  Redo is easy, as I just run the command again.  But what about undo?  My first thought was to have undo just do the inverse function, so if the action was drawLine, then undo would eraseLine.   Unfortunately eraseLine isn't actually the opposite of drawLine, as I'll show.

Imagine I draw a horizontal line on the x-axis from 1 to 4.  Now I draw a second line from 3 to 6.  When I undo, if I erase from 3 to 6, I'll have erased too much.  I really want to only erase from 4 to 6 so I don't erase any of the first line.

With some work, I could actually determine the real inverse action, and I may still need to do that.  However, a much simpler, though more computationally expensive, idea occurred to me.  If a user has done actions 0 through N, and then does an Undo, rather than try to reverse step N, just clear the state and then replay actions 0 through N-1.  This feels wasteful, but if I turn off drawing while doing this, this is just replaying a bunch of simple calculations which will happen really quick (assuming we aren't talking millions of steps - but if you are doing that much work, this toy drawing program is not for you), and then I can just do a single draw of the final state.  i.e. something like:
  1 function UndoStack(draw){ 
  2   this.stack = []; 
  3   this.maxCmds = 0;
  4   this.curCmd = 0;
  5   this.draw = draw; 
  6 } 
  7 UndoStack.prototype.add = function(cmd) { 
  8   this.stack[this.curCmd++] = cmd;
  9   this.maxCmds = this.curCmd;
 10 } 
 11 UndoStack.prototype.undo = function(){ 
 12   this.draw.reset(); 
 13   this.draw.dontDraw = true;
 14   this.curCmd--; 
 15   for (var i = 0; i < this.curCmd; i++) {
 16     this.stack[i](); 
 17   } 
 18   this.draw.dontDraw = false;
 19   this.draw.draw(); 
 20 } 
 21 UndoStack.prototype.redo = function(){ 
 22   this.stack[this.curCmd++]();
 23 }
And the code in the ControlLayer looks like
  1 var p1 = this.firstPoint;
  2 var p2 = this.currentPoint;
  3 var drawRecord = this.drawRecord;
  4 var drawFunc = this.erase ? drawRecord.eraseLine 
  5                           : drawRecord.addLine; 
  6 var func; 
  7 if (this.rect) { // draw all 4 sides of rectangle as one action
  8   func = function(){ 
  9     drawFunc.call(drawRecord, p1, new Point(p2.x, p1.y));
 10     drawFunc.call(drawRecord, p1, new Point(p1.x, p2.y));
 11     drawFunc.call(drawRecord, p2, new Point(p2.x, p1.y));
 12     drawFunc.call(drawRecord, p2, new Point(p1.x, p2.y));
 13   } 
 14 } else { 
 15   func = function(){drawFunc.call(drawRecord, p1, p2);}
 16 } 
 17 func(); 
 18 this.undoStack.add(func);
Geometry
Computation geometry problems are a set of problems that always seem to bite me in programming contests. So I tried to keep things simple and created a couple of helper classes.

Point
I created a Point class, which just has an x and y coordinate and the ability to compare points with Fortran style methods .lt, .ge, .eq, etc.  My definition of ordering is, Point A is less than Point B iff A.x < B.x OR (A.x == B.x AND A.y < B.y).  This definition provides the expected ordering of points that are collinear which is useful when calculating line overlaps.

Line
My Line class is just two points, p1 and p2.  For simplicity, I ensure that p1 < p2.  I also store a slope object of the line which is just a rise and a run.  The slope is canonicalized so that rise and run are in lowest terms, and that run is nonnegative.
  1 function Slope(p1, p2) { 
  2   var rise = p1.y - p2.y; 
  3   var run = p1.x - p2.x; 
  4   var gcd = Slope.gcd(Math.abs(rise), Math.abs(run));
  5   rise /= gcd; 
  6   run /= gcd; 
  7   if (run < 0) {
  8     rise *= -1; 
  9     run *= -1; 
 10   } else if (run == 0) {
 11     rise = 1; 
 12   } 
 13   this.rise = rise; 
 14   this.run = run; 
 15 }
I can now determine if two lines overlap by seeing if they are collinear
  1 Line.prototype.collinear = function(line) {
  2   if (!this.slope.eq(line.slope)) return false;
  3   if (!this.p1.eq(line.p1) &&
  4       !this.slope.eq(new Line(this.p1, line.p1).slope)) return false;
  5   return true;
  6 }
and if their endpoints overlap.
  1 Line.prototype.overlaps = function(line) {
  2   return this.collinear(line) &&
  3          this.p1.lt(line.p2) && this.p2.gt(line.p1);
  4 }

Demo
And here is what the end product looks like, at least if you are using a compatible browser.  Feel free to view the source and see all the code that I left out of the examples above, if you are at all curious.


   


Saturday, August 21, 2010

Learning JavaScript

So I've decided to learn JavaScript. There are a couple of motivations behind this. The practical one is that I have various ideas that I think would be cool on hand-held devices like my Droid or an iPhone or iPad. The obvious drawback is writing for one platform is not going to be compatible with the other, and it is going to be hard enough to find time to write an app once, much less twice. However, if I write the app in JavaScript and make it available as a webpage, it is suddenly available everywhere.

The second motivation is some reading I've done on the web about how JavaScript is a misunderstood language, and it is more like Lisp than like Java. After reading this I felt I owed it to myself to at least learn something about the language, and stop being one of those people who looks down on it "because nobody wants to be a web developer. No self-respecting, rootin'-tootin', core-dump-debugging programmer wants to be one, anyway."

Oh, and let's not forget all of the amazing things Google has done with JavaScript.

JavaScript for Programmers

So to learn, I am going to be writing some programs and I will lean heavily on examples found on the web. Unfortunately, the majority of what is out there is geared towards non programmers. Meaning there is a lot of, "This is a variable. This is a loop. And, if you are ready for it, here is a function!" Or, as one book I saw in the library said, "JavaScript is a programming language, but don't let that scare you." What I am looking for is something geared towards programmers.

While I can't do it justice (only partially because I don't know anywhere near enough), here are a few things I've learned along the way. (and since some of my sources are old, this may be inaccurate).

What I've Learned So Far

Syntactically it is a C family language. So control structures (if, for, while, curly braces) work the way you'd expect.

JavaScript seems to have five types, though in some sense everything is an object.
  • boolean
  • number
  • string
  • object
  • function
Variables are passed by value to functions but, like Java, object variables are really references to the object, so for most purposes you can treat it as pass by reference. And yes, functions can be stored in variables and passed around. (Boy, I hope Java 7 really is going to include closures).

JavaScript is Object Oriented in the sense that everything is an object, but it doesn't have classes in the sense of Java and C++. However, you can treat it like it does, but I think then you are missing some of the power of JavaScript. It follows more of a property pattern, or what Steve Yegge calls the Universal Design Pattern.

So how do you use your own objects? (I'm going to ignore all the built in objects since you can go search the web for them yourself.)

Choice one - ad hoc
  1 var obj = new Object();
2 obj.name = 'hello world';
3 alert(obj.name);
Yep - you can just create an object and start assigning its properties, without defining them first. You can also treat these properties as if they were values in an associative array.
  4 var name = obj["name"];
Choice two - create a standard definition
  5 function Person(name, age) {
6 this.name = name;
7 this.age = age;
8 this.field = 'some value';
9
10 this.getOlder = function() {this.age++;}
11 this.changeName = personChangeName;
12 }
13 function personChangeName(newName) {
14 this.name = newName;
15 }
Note that inside this Person function (aka a constructor) we have access to a 'this' field which acts like this in Java. There are two methods defined in Person, done two different ways. The method getOlder is defined inline - which actually means that a new function is created every time this constructor gets called. If we refer to an existing method, like personChangeName, the function is only created once, but it still has access to the 'this' variable. Now, as expected, you can create a Person object and call its methods and access its fields.
 16 var bart = new Person("Bart Simpson", 10);
17 var me = new Person("Madking", 17); // I can pretend, right?
18 me.getOlder(); // Now I can vote!
19 alert(me.name + " is " + me.age + " and has field: " + me.field);
However, like the ad-hoc method, we can still attach new properties or methods to a Person object at any time.
 20 me.sayHi = function() { alert("hi: " + this.name); };
21 me.species = "Wannabe Blogger";
We can also assign properties to the function/Class itself. (ala static methods/variables)
 22 Person.staticVar = "not a constant";
23 Person.staticFunction = function() { /* do something */ };
There is a special Class variable called 'prototype'. Every instance automatically gets the fields and functions defined by its prototype.
 24 Person.prototype.sayBye = function() { alert("bye: " + this.name); };
25 Person.prototype.species = "Homo Sapien";
So every Person object (like "me") now has a function called "sayBye", and a field "species". However, individual objects can override these "inherited" properties. So the me object is still of species "Wannabe Blogger". Note that this means that even though it looks like "bart" and "me" are both instances of Person, this isn't true in the Java sense of the world. me has a "sayHi"method which bart doesn't have. Also note that you can add new fields and methods to both the objects and their prototype (thereby affecting all objects of this type that already or will exist) at any time.

Last couple notes

Arrays and Associative Arrays are commonly used data structures. In JavaScript, every object is an Associative Array mapping strings to anything. However you can also use non-negative integers as your key ala an array. And if the object is an Array object, it will have array-like methods and properties (like length). Arrays can be sparse, so you can have an array and assign element 0 and 100 and nothing in between, if you want. In this case, the length will be 101, i.e. the lowest unassigned index. There is also convenient literal syntax for defining arrays and associative arrays (objects) which is fairly self explanatory.
  1 var myArray = [1, 2, "mixed type", new Person("Lisa", 7), 3];
2 var myObject = {
3 name : "Homer",
4 age : 36,
5 wife : new Person("Marge", 34),
6 talk : function() { alert("DOH!"); }
7 };
Oh, and strings can be contained inside of either single or double quotes. Though it is poor style to randomly switch between them as I did in my examples above.

One other cool thing about JavaScript is the low barrier to entry. Open your favorite editor (or least favorite, doesn't matter), and create an html file. Put any/all of the code above inside a script tag. Nope open the file up in your browser of choice. VoilĂ , you have written a JavaScript program.
<script>
alert("java script is working!"); // replace with your own code
</script>
Yes, there is supposed to be an attribute in the script tag, and it should be embedded inside a body element of an html element, but this lazy approach seems to work if you are just playing around.

Monday, August 16, 2010

Don't Reuse. Rewrite!

As Isaac Newton said, "If I have seen further it is only by standing on the shoulders of giants." This is the promise of reuse. By taking advantage of libraries and frameworks we are able to write large complex systems at a fraction of the time and effort that it would be without.

And yet...

Just like anything else in an engineering discipline, it is about tradeoffs. Using an external library causes an external dependency. An external dependency is one more thing that has to be learned to understand a whole system. It may have bugs or just be poorly documented. Two years from now when you are moving to new hardware, it may not support the new hardware. In short using a third party library is far from free even if it is free as in beer or speech.

"If it's a core business function -- do it yourself, no matter what."So when should you use an existing library vs. writing it yourself? Joel Spolsky says, "If it's a core business function -- do it yourself, no matter what." This is is good advice. However, I would also say that if the effort of writing it yourself is not much more than that of integrating the library, then you should write it yourself.

So what brought this up? On my last post about JNDI, SQL, and JUnit, I used a few third party packages. Joseph Graves emailed me and told me how he had solved the SQL problem by writing his own mock JDBC library, and that it looked like it would be simple to do so for JNDI. While I still think using HSQLDB was the right thing for my situation, he had a good point about JNDI. Did I really need to add an external dependency when all I wanted was effectively a global Map? And so I rewrote the JNDI part as follows:
  1 import java.util.HashMap;
2 import java.util.Hashtable;
3 import java.util.Map;
4
5 import javax.naming.Binding;
6 import javax.naming.Context;
7 import javax.naming.Name;
8 import javax.naming.NameClassPair;
9 import javax.naming.NameParser;
10 import javax.naming.NamingEnumeration;
11 import javax.naming.NamingException;
12 import javax.naming.spi.InitialContextFactory;
13
14 public class MockInitialContextFactory implements InitialContextFactory {
15
16 private static Context sInitialContext;
17
18 public synchronized Context getInitialContext(Hashtable<?, ?> environment)
19 throws NamingException {
20 if (sInitialContext == null) {
21 sInitialContext = new MockContext();
22 }
23 return sInitialContext;
24 }
25
26
27 static class MockContext implements Context {
28
29 private Map<String, Object> mMap = new HashMap<String, Object>();
30
31 public Object lookup(String name) throws NamingException {
32 return mMap.get(name);
33 }
34
35 public void bind(String name, Object obj) throws NamingException {
36 mMap.put(name, obj);
37 }
38
39 // remainder of auto-generated stub methods with default implementation
40 }
41 }
As you can see, with just a handful of meaningful lines of code (and Eclipse's stub generation) I was able to remove the dependency on two third party jars, thereby simplifying the whole system.

Monday, August 9, 2010

JNDI, SQL, and JUnit

So I recently had a problem that I would've assumed many people in Java land have had. I have some code that will live in an app container (Tomcat, JBoss, or Weblogic probably), and I want to write unit tests for it.

Here is what the code does.
  • Get a database connection using JNDI (from the app container)
  • Does some database stuff
Here are my self imposed goals for the unit tests:
  • Runnable out of the box. (i.e. if you can checkout and build the project, you can run the unit tests)
  • Does not require an app container. I don't want to require a running instance of JBoss just to have access to JNDI so I can run unit tests.
  • Each developer has their own unit testing database sandbox to run unit tests in, so they won't/can't collide with each other.
  • Ideally the unit testing database is checked into the repository.
These seemed like reasonable goals to me, and I figured a few minutes of Google searching would give a couple of options of how this is typically done. Since it took more than that, I'll write up what I did.

HSQLDB

StackOverflow led me to HSQLDB. With HSQLDB I am able to get an in-memory database, which is perfect for unit testing. And I can make sure all other team members can use it, just by including the jar file in the check-in. Well, that seems easy enough.

JNDI

Now all I had to do was to make the HSQLDB DataSource available via JDBC. This should be easy enough, right? Right? Ugh.

I found this blog that seems to be the standard way to inject a JNDI datasource without an app container. Seems easy enough, except that when I tried to follow the directions, I got a ClassNotFoundException for org.apache.naming.java.javaURLContextFactory. It seems that this class is included with Tomcat. I suppose I could've gone and gotten the Tomcat jar to include in the project, but this didn't feel right with my goal to be app container agnostic.

So with a little more searching I found an in-memory JNDI context on SourceForge. Well, that seems to be what I want.

[edit - As I wrote in my follow up post, Don't Reuse. Rewrite!, I ended up writing my own in memory JNDI context, since all I needed were the bind and lookup methods.]

Huh - now that I write it up, it seems much less painful than it was when I was trying to track all this down myself.

Implementation Summary

Download two packages:
I added 3 jars to my CLASSPATH.
  • hsqldb.jar - comes with the HSQLDB download.
  • jndi.jar - comes with the in-memory JNDI context. [edit - don't use any more]
  • util.jar - also with the in-memory JNDI context. (and yes - they really did name the jar file unit.jar) [edit - don't use any more]
As for the actual unit testing code, I am using JUnit 4. This means that I can put the setup code once per class. As such my code looks something like:
  1 import java.sql.Connection;
2 import java.sql.Statement;
3
4 import javax.naming.Context;
5 import javax.naming.InitialContext;
6 import javax.sql.DataSource;
7
8 import jndi.naming.provider.MemoryContextFactory;
8 import mypackage.MockInitialContextFactory;
9
10 import org.hsqldb.jdbc.JDBCDataSource;
11 import org.junit.BeforeClass;
12
13 public class MyUnitTest {
14 private static final String JNDI_NAME="my_JNDI_name";
15
16 @BeforeClass
17 public static void setUpBeforeClass() throws Exception {
18 createJNDIContext();
19 createDBTable();
20 }
21
22 public static void createJNDIContext() throws Exception {
23 JDBCDataSource ds = new JDBCDataSource();
24 ds.setDatabase("jdbc:hsqldb:mem:mymemdb");
25 ds.setUser("SA");
26
27 System.setProperty(Context.INITIAL_CONTEXT_FACTORY,
28 MemoryContextFactory.class.getName());
28 MockInitialContextFactory.class.getName());
29 InitialContext ic = new InitialContext();
30 ic.bind(JNDI_NAME, ds);
31 }
32
33 private static void createDBTable() throws Exception {
34 DataSource ds = (DataSource)new InitialContext().lookup(JNDI_NAME);
35 Connection conn = ds.getConnection();
36 String create = "CREATE TABLE MY_TABLE ("
37 // Insert column description here.
38 + " )";
39 Statement stmt = conn.createStatement();
40 stmt.executeUpdate(create);
41 conn.close();
42 }
43
44 // Unit Tests go here
45 }
46
Note - this code was colorized by: http://puzzleware.net/codehtmler/default.aspx.