Monday, December 27, 2010

Binding Ctrl-Tab in Eclipse

When I am working in a multi-tab environment my fingers expect to be able to navigate through the tabs with CTRL-TAB and CTRL-SHIFT-TAB. In Eclipse this means I would expect to be able to use CTRL-TAB to switch between the files I am editing. However, by default it is set to CTRL-F6.

How To Fix It
The hot-keys are specified under the menu: Window > Preferences > General > Keys
First you need to unbind the commands "Next Tab" and "Previous Tab" by choosing that command and clicking the "Unbind Command" button.

Next bind the commands "Next Editor" and "Previous Editor" by choosing that command and pressing the keys CTRL-TAB or CTRL-SHIFT-TAB where it says Binding.

Monday, December 20, 2010

JavaScript Namespaces

In my JavaScript programming I have been putting all of my classes and variables in the global namespace. Since global variables are considered evil, I want to clean up my code. The obvious thing to do is to use namespaces, but JavaScript doesn't support namespaces. Luckily JavaScript is powerful enough that you can fake it pretty well. StackOverflow has a discussion on ways to do it. A couple ideas that I really like are the Module Pattern and a namespace library.

The main idea is that you create an object to act as a namespace and then you make all of your objects and functions and classes (which are really function objects) be properties of this "namespace" object. Here is the approach I've decided to take with the JavaScript project I've been working on. This may not be the best way to do it, but it is what I am trying for now as I learn this.

Global Namespace Object
First, I need to create a global namespace object which should have a unique name. I'll call it myNamespace, and here is how it is defined:
  1 var myNamespace = {   
  2   namespace : function(name, func) { 
  3     var parts = name.split("."); 
  4     var space = this;
  5     for (var i in parts) {
  6       var part = parts[i]; 
  7       var next = space[part]; 
  8       if (!next) next = {}; 
  9       next.namespace = this.namespace; 
 10       space[part] = next; 
 11       space = next; 
 12     }     
 13     if (func) { 
 14       func.call(space); 
 15     } 
 16     return space; 
 17   } 
 18 };
Basically, it is just an object. What it provides is a namespace method which takes a dot.separated.namespace and returns the namespace object corresponding to that particular name, creating it if necessary. This means that if I make the call myNamespace.namespace("dot.separated.namespace"), it will create the objects: myNamespace.dot, myNamespace.dot.separated, and myNamespace.dot.separated.namespace. I've made the decision to make the myNamespace object implicit and not specified in the namespace parameter call because it seems less redundant. The code that does this is fairly forward and lives in the loop on lines 5-12 and the return statement on line 16.

The other thing that I've done is added an optional function parameter to the namespace object which will automatically be called on the newly created namespace (line 14). I will explain the idea through examples.

Using This Namespace Object
The simplest way to use this is to just add your variables to the namespace object. i.e. rather than having code in global namespace like:
var x = 5; 
function sort(arr) { /* code */ }
you do something like:
myNamespace.x = 5; 
myNamespace.sort = function(arr) { /* code */ }
or you can even namespace it further:
myNamespace.namespace("util"); 
myNamespace.util.sort = function(arr) { /* code */}
As you can see, by doing this the only global variable you have created is the myNamespace object and everything else is a property of it.

So what's with the optional function parameter? It lets you define an entire namespace all at once and even allows the idea of private variables and functions from the Module Pattern. Here's an example:
  1 myNamespace.namespace("util.collection", function() { 
  2   var InternalType = function(){/*class that is only used by this namespace*/}
  3   InternalType.prototype.sort = function() { /* code */ } 
  4  
  5   var Stack = function() { /* code */ }
  6   Stack.prototype.push = function(value) { /* code */} 
  7   // etc. 
  8  
  9   this.Stack = Stack;  // make the Stack type public in this namespace
 10 });
Basically lines 2-8 are the internal namespace definition. Anything that gets added to the this variable (like Stack on line 9) become the public part of the namespace. Once we've defined the namespace we can then use the public classes and variables in it.
var stack = new myNamespace.util.collection.Stack();
And, of course, we can use one namespace in another namespace:
  1 myNamespace.namespace("my.app.package1", function() { 
  2   var Stack = myNamespace.util.collection.Stack;  // similar to a java import
  3  
  4   var doSomething = function(x) { 
  5     var stack = new Stack();
  6     stack.push(x); 
  7    /* do more stuff */ 
  8   } 
  9  
 10   // define public aspects of this namespace
 11   this.doSomething = doSomething; 
 12 });
One thing I want to point out is the Stack variable on line 2. Fully qualifying everything makes for unwieldy code which is why Java has import statements and C# has using statements. Since the namespaces and the classes are all really just objects, you can create your own variables with shorter names to refer to the fully qualified object. As long as you do this inside a function (for example the anonymous function being passed to the namespace method), the Stack variable is not polluting the global namespace.

Take Home Message

Make sure you respect the global namespace.

Whether you use the function and internally scoped objects or not, the important thing is that the only variable added to the global namespace is myNamespace. As such it is easy to avoid collisions with any other libraries, just change the name "myNamespace" to something that is unique to your code. This allows you to play nice with others and not worry about 3rd party apps messing up your functionality.

Monday, December 13, 2010

Programming with Magic

Many of today's software tools work by "magic". For example, Hibernate magically turns objects and method calls into database tables and SQL statements. JSF and Facelets turn markup and Java sbeans into rich web applications. Seam magically makes all of this work together.

Why do I say magic? As Arthur C. Clarke said, "Any sufficiently advanced technology is indistinguishable from magic." For the majority of developers, these tools qualify as sufficiently advanced technology. These tools just work, and the details of how they work under the covers is irrelevant. For the most part, this is great. The less brain power I have to spend on the infrastructure, the more brain power I have left to solve my domain specific problems. However, there is a danger.

The danger is when the tools don't work as expected, or you are trying to use them in new ways. This is where the "magical" qualities of these tools really shine through. Do some searches for these tools and you will find loads of questions on how to solve specific problems or accomplish specific tasks. Sometimes you'll find the questions answered succinctly. More often you'll see a dialog where multiple suggestions are made before a solution is found.  And sometimes the conversation has petered out with no solution. (I seem to always come across the latter when I am search for solutions).

Why are there so many questions, and so many not satisfactorily answered? It's because of the magic in the tools. When you are using magic, it is not clear what doing something new will do. I've had a number of problems that were fixed by adding an incantation to a config file. How was I supposed to know that without being an expert in the tool? That last question is the danger of magic. When you are using tools that you don't really understand, how are you are supposed to solve unexpected problems?

Example
Here's a specific problem I recently had involving Hibernate, Facelets, and Seam. I have two Hibernate entity classes:
  1 @Entity 
  2 public class Person {
  3   @Id Long id; 
  4   String firstName; 
  5   String lastName; 
  6 } 
  7  
  8 @Entity 
  9 public class Task {
 10   @Id Long id; 
 11   String name; 
 12   @ManyToOne(fetch = FetchType.LAZY) Person assignedPerson; 
 13 }
I have a Seam EntityQuery that returns a list of Tasks, as well as handling pagination and sorting (handled by Seam's EntityQuery class.
  1 @Name("taskList") 
  2 public class TaskList extends EntityQuery<Task> {
  3   public TaskList() { 
  4     setEjbql("SELECT task FROM Task task"); 
  5   } 
  6 }
I have a facelet page that has a table showing all the tasks. It looks something like:
  1 <rich:dataTable value="#{taskList.resultList}" var="task"> 
  2   <h:column> 
  3     <f:facet name="header"> 
  4       <s:link styleClass="columnHeader" value="Task ID"> 
  5         <f:param name="sort" value="task.id" /> 
  6       </s:link> 
  7     </f:facet> 
  8     #{task.id} 
  9   </h:column> 
 10   <h:column> 
 11     <f:facet name="header"> 
 12       <s:link styleClass="columnHeader" value="Name"> 
 13         <f:param name="sort" value="task.name" /> 
 14       </s:link> 
 15     </f:facet> 
 16     #{task.name} 
 17   </h:column> 
 18   <h:column> 
 19     <f:facet name="header"> 
 20       <s:link styleClass="columnHeader" value="Assigned Person"> 
 21         <f:param name="sort" value="task.assignedPerson.lastName" /> 
 22       </s:link> 
 23     </f:facet> 
 24     #{task.assignedPerson.lastName} 
 25   </h:column> 
 26 </rich:dataTable>
And just like that (after adding all the appropriate headers, config files, jar files, etc.) I have a web page that will show me a 3 column table of all my task objects that are in the database. Not only that, each column header is a link that when clicked returns the table sorted by the column. There's a lot of going on here. Explaining it all is beyond the scope of this post, just trust me. It's magic, after all.  :)

Problem
My test dataset included four tasks, two assigned to one person, one assigned to a different person, and one without an assignment (i.e. a null assignedPerson field).

Everything worked great until I tried to sort by last name. When I sorted by last name, it successfully sorted, but it suddenly only showed me the three tasks that were assigned to a person. The fourth task was missing. Why?
Task IDNameAssigned Person
1Buy GroceriesHaddox-Schatz
2Write BookClarke
3Write BlogHaddox-Schatz
4Achieve World PeaceProblem Row

Since these tools aren't really magic, they do sometimes provide helpful diagnostics. In this case, I had logging turned up so that I could see all of the SQL that was actually being run by Hibernate. When getting the list of tables, the code was effectively running the query
SELECT * FROM Task
and then running separate
SELECT lastName FROM Person WHERE Person.id=?
queries to get the names of the people. When sorting by task name the Task query became
SELECT * FROM Task ORDER BY Name

So what happens when you want to order by the assigned person's last name? Well, now you have to have a JOIN to order correctly. The query it generated when I tried sorting by last name was something like
SELECT * FROM Task t JOIN Person p 
         WHERE t.assignedPersonId = p.id ORDER BY p.lastName
And now the problem is highlighted. With the JOIN, only the tasks that have assigned people are returned by the query, which explains why I lose the one row when I sort by last name. The SQL solution here is to use a LEFT JOIN rather than a JOIN. i.e.
SELECT * FROM Task t LEFT JOIN Person p
         WHERE t.assignedPersonId = p.id ORDER BY p.lastName

Great, I have the solution... except that I don't.

I don't write the SQL, Hibernate does. Is there some command or configuration or something that I can do to get it to use a LEFT JOIN when it needs to do a join for ORDER BY? This is where the magic hurts. I don't know what incantation to utter. I don't even know how to find such an incantation, or to determine if it is even possible. This means I am left to my least favorite form of programming - googling for solutions.

Solution
I eventually found that if I changed my EJBQL in the task list constructor (line 4 in the second example above) to
SELECT task FROM Task task left join fetch task.assignedPerson
that it worked. Apparently, if you explicitly always do a LEFT JOIN, the ORDER BY will use that LEFT JOINed object. Oh, and despite EJBQLs case insensitivity when it comes to key words and my proclivity to write SQL keywords in all caps, you'll notice that I had the text "left join fetch" in lower case. If I had that in upper case then Seam's EntityQuery class doesn't handle it correctly.

Conclusion
In this particular case I found a solution to my problem, though I still don't understand why Hibernate's automagically generated SQL returns different result sets based on the ORDER BY clause. (i.e. why didn't they generate the LEFT JOIN to begin with?)  Sometimes I am unable to find a solution and so have to redesign my code around an apparent limitation of the tool. I say apparent, because if I am not an expert in the tool, its possible I am just missing the magical incantation I needed to accomplish my task. In either case, it is very unsatisfying as a developer to not really understand my tools and why I have to write my code the way I do.

I don't want to be a code wizard, I just want to be a software engineer.

Monday, December 6, 2010

Selectively Displaying a Map in JavaScript

So I've now created the ability for an icon to navigate through a maze. For the next step, I think it would be interesting if the user could only see the portion of the maze that the icon could see. I am envisioning a scenario where everything that the icon can see looks as before, areas that the icon can't see and you've never seen aren't visible, and places that you can't see, but you have seen are grayed out (representing your memory).

Algorithm
The first (and arguably hardest) step is determine which cells can be seen from a given location.  Here is the algorithm that I have come up with:
  • The cell with the icon is visible
  • Any other cell is visible if
    • the cell(s) directly closer to the icon are visible
    • AND it is legal to move directly to the cell(s) closer to the icon
Also, to make sure diagonal lines that are borders can be seen, any cell with a line running through it (I'll call this a "broken" cell) that borders a visible cell is visible.

To handle "memory", when calculating what cells are visible, I first mark any cells that were visible as OLD so they can be shown in gray if they are not still visible.

Implementation
The first method that I have is the easiest - it just marks every existing visible cell as previously visible.
  1 Map.prototype.prepareVisibleCells = function(){
  2   for (var i in this.cells) {
  3     var cell = this.cells[i];
  4     if (cell.visible == Visible.VISIBLE) {
  5       cell.visible = Visible.OLD; 
  6     } else if (cell.visible == Visible.BORDER) {
  7       cell.visible = Visible.OLD_BORDER;
  8     } 
  9     cell.visited = false; 
 10   } 
 11 }
There are two things I want to point out in this method. The first is that I mark every cell as not having been visited in line 9. I'll use this property to make sure I don't process a cell twice. The second is that I have two types of cells, VISIBLE and BORDER. VISIBLE cells are what they sound like. BORDER cells correspond to the "broken" cells I talked about above that I'll show as visible, but that you can't see through.

The second method is the one where I calculate which cell(s) are between the current cell and the start cell (the one with the icon). Let me show an example to explain what I want.
AB
C
D


E

In the above example, cell A and C are visible as long as they directly connect to the icon. B is visible if it is connected to A and A is visible. Similarly E is visible if it is connected to C and C is visible. But what about D? D is between the horizontal line A-B and the diagonal line C-E. The choice I made is that D is only visible if it can be seen on both the diagonal, and the horizontal. I.e. D is connected to A and A is visible and D is connected to C and C is visible. The code that determines which direction to go looks like:
  1 Map.prototype.getClosestDirs = function(start, cell) {
  2   var dx = start.point.x - cell.point.x; 
  3   var dy = start.point.y - cell.point.y; 
  4   var sx = this.signum(dx);
  5   var sy = this.signum(dy);
  6   var dir1 = Dir.getDir(sx, sy); 
  7   if (Math.abs(dx) > Math.abs(dy)) sy = 0;
  8   if (Math.abs(dx) < Math.abs(dy)) sx = 0;
  9   var dir2 = Dir.getDir(sx, sy); 
 10   return [dir1, dir2]; 
 11 }
The signum call on lines 5 and 6 is just the signum function. I realize that the Map class is probably not an appropriate place for this function, but that is where it is for now.

If the cell is on one of the 4 cardinal directions from the start, lines 2-6 calculate that cardinal direction, otherwise it finds the diagonal that the cell is closest to. Lines 7-9 determine which of the 4 cardinal directions the cell is closest too, unless it is exactly on the diagonal. Line 10 returns these two directions that were found. Note that they are the same if the cell is exactly on one of the 8 main directions from the start cell.

Now that we have these two helper functions, we can do a breadth first search from the icon to determine what is visible.
  1 Map.prototype.setVisibleCells = function(point) {
  2   this.prepareVisibleCells(); 
  3   var start = this.getCell(point);
  4   start.visited = true; 
  5   var queue = new Queue();
  6   queue.push(start); 
  7   while (!queue.isEmpty()) { 
  8     var cell = queue.pop(); 
  9     if (cell != start) { 
 10       if (cell.isBroken) { 
 11         cell.visible = Visible.BORDER; 
 12         continue; 
 13       } 
 14       var dirs = this.getClosestDirs(start, cell);
 15       if (!cell.isVisibleDir(dirs[0]) || !cell.isVisibleDir(dirs[1]))continue;
 16     } 
 17     cell.visible = Visible.VISIBLE; 
 18     for (var i in Dir.dirs) {
 19       var dir = Dir.dirs[i]; 
 20       var nextCell = cell.getAdjacent(dir);
 21       if (!nextCell || nextCell.visited) continue;
 22       nextCell.visited = true; 
 23       queue.push(nextCell); 
 24     } 
 25   } 
 26 }
Lines 2-6 set up the state for the BFS algorithm, while lines 7-25 are the main loop. Lines 10-12 is where I determine if the cell has a line going through it (i.e. is "broken"). Since I know only cells adjacent to VISIBLE cells will ever get processed, I can mark this cell as a BORDER so it will be shown. The isVisibleDir calls made on line 15 check if the the cell in the given direction is both connected and visible. If not, then this cell is not visible, and we can continue to the next cell in the BFS queue.

If we get to line 17, then this cell is VISIBLE and we mark it as such. In lines 18-24 we iterate through all of the cells that are adjacent to this cell, and add them to the queue, if they haven't already been added to the queue (i.e. marked as visited). And with that, we have an algorithm that calculates which cells should be visible.

Hiding Cells
To actually limit the visibility I added another canvas layer that is on top of the other layers and I have a VisibleLayer class that manages this layer. Whenever the icon we are following moves into a new cell Map.setVisibleCells is called and then VisibleLayer.draw is called to hide parts of the map.
  1 VisibleLayer.prototype.coverSquare = function(point, style) {
  2   var realPoint = this.getReal(point);
  3   this.ctx.fillStyle = style; 
  4   this.ctx.fillRect(realPoint.x, realPoint.y, this.grid.size, this.grid.size);   
  5 } 
  6 VisibleLayer.prototype.draw = function(map) {
  7   this.clear(); 
  8   this.ctx.save(); 
  9   for (var i in map.cells) {
 10     var cell = map.cells[i]; 
 11     if (cell.visible == Visible.OLD || cell.visible == Visible.OLD_BORDER) {
 12       this.coverSquare(cell.point, "rgba(0, 0, 0, 0.5)");
 13     } else if (!(cell.visible == Visible.VISIBLE || cell.visible == Visible.BORDER)) {
 14       this.coverSquare(cell.point, "rgb(0, 0, 0)");
 15     } 
 16   } 
 17   this.ctx.restore(); 
 18 }
The draw method just iterates over all the cells in the map and if they are VISIBLE or a BORDER, draws a black square over the cell, and if they are OLD or OLD_BORDER then it draws a black square with the alpha set to one half, so that it can still be seen through.

The ctx is the 2d context of the canvas, gotten via the call
this.ctx = canvas.getContext('2d');
The calls to ctx.save() and ctx.restore() ensure that at the end of this method that canvas drawing context is the same as the beginning despite the setting of fillStyle on line 3. The getReal method that is called on line 2 calculates the actual x and y coordinates based on the logical coordinates of the cell, and the clear() call on line 7 clears this layer, making ever cell visible except for the ones that get covered by the calls on lines 12 and 14.

Odds and Ends
To help separate the walls from the shadows, I changed the color of the walls from black to brown and made them thicker.  I also increased the size of the grid cells that are shown on the screen to make things easier to see. The new icon was downloaded from the site http://www.wpclipart.com/money/treasure/.

Demo