TAS Must Die, Chapter 11

More on design patterns. I have this graph of states, and I need to navigate it for multiple reasons. Sometimes I want to count the nodes. Sometimes I want to group them to remove redundencies. Sometimes I just want to generate a printable version. Or generate the lexer.

Say you want to print the state diagram. Normally what happens is that you write the navigation routine and right there in the middle of it, you put your "print" function. You get that working. Then you decide to count the items in the data structure. The navigation code you already have has the print stuff buried in the heart of it. That's no good for counting. So you copy/paste the navigation code and replace the "print" stuff with "count" stuff. About the 3rd time you do this, you realize it sucks and you want a different solution. In C, you'd pass a pointer-to-function as an argument. You'd navigate and then call the function to do the task-specific work. Pretty good stuff, but maybe a little fast-and-loose. As normal with C, you're at the mercy of the programmer's skill, mentality, and deadline.

Java has no pointer-to-function language structure. But using the Visitor design pattern we can cook up something that acts the same and has a little type checking in it. The wikipedia link is very good, but I'll paraphrase.

1. Create an interface called Visitor that has a visit(SomeObject) method, where SomeObject is germane to your problem domain. For this project, I had a graph of states, so my method was

public Interface Visitor {
void visit(State s);
}

2. To the class that manages the navigation data structures, add the following:

void accept(Visitor v) {...}

This is the class that manages navigation. For a binary tree of type node, you might have

public class Node {
// stuff
    public void accept(Visitor v) {
        if (leftChild != null) leftChild.accept(v);
        v.visit(this);
        if (rightChild != null) rigthChild.accept(v);
       }
}

Rock solid. Now, accept() is totally divorced from what the Visitor is actually doing. Visitor is an interface so by definition there's no implementation and no way for accept() to make any assumptions. A particular Visitor could generate a printable Node, count the nodes, search for a match, anything.

In my case, since my graphs (and states) are managed by the Nfa class, I implemented the method there.

3. Create an implementation of Visitor. Add the function-specific code to the visit method.

public class CountVisitor implements Visitor {
    private int count = 0;
    public void visit(State s) {
        count++:
        }
    public int getCount() {
        return count;
        }
    }

4. Add any auxilliary methods to the Visitor implementation as needed, such as getCount() above.

Here's an example from my project.

When I generate my lexer, it's important that my states be numbered starting at zero. For efficiency, the state id will be used as an index into an array! Given that I am creating and destroying hundreds of states as I convert the NFA to a DFA, the state IDs are all over the place. As I navigate my graph of states, the visit(State) method is called once for each state. The visit method simply adds a reference to the state to an Arraylist. Now I know all the states.
When I am done, I call the renumber() method and just iterate over the states, reassigning their IDs. To use the visitor, the following does the trick:

Visitor v = new StateRenumbererVisitor();
nfa.accept(v);
v.renumber();

It can be hard to get your mind around this. Once you do it, however, you'll be hooked.