tags:

views:

436

answers:

4

I have an interesting situation and I'm wondering if there is a better way to do this. The situation is this, I have a tree structure (an abstract syntax tree, specifically) and some nodes can contain child nodes of various types but all extended from a given base class.

I want to frequently do queries on this tree and I'd like to get back the specific subtypes I'm interested in. So I created a predicate class that I can then pass into a generic query method. At first I had a query method that looked like this:

public <T extends Element> List<T> findAll(IElementPredicate pred, Class<T> c);

where the Class argument was used just to indicate the return type. What bothered me about this approach is that all of my predicates were already for specific types so there is redundant information here. A typical call might look like:

List<Declaration> decls = 
    scope.findAll(new DeclarationPredicate(), Declaration.class);

So I refactored it like this:

public <T extends Element> List<T> findAll(IElementPredicate<T> pred);

Where the IElementPredicate interface looks like this:

public interface IElementPredicate<T extends Element> {
    public boolean match(T e);
    public String getDescription();
    public Class<T> getGenericClass();
}

The point here is that the predicate interface is expanded to provide the Class object instead. It makes writing the actual findAll method a little bit more work and it adds a bit more work in writing the predicate, but those are both essentially tiny "one-time" things and it makes the query call so much nicer because you don't have to add the extra (potentially redundant) argument, e.g.

List<Declaration> decls = scope.findAll(new DeclarationPredicate());

I haven't noticed this pattern before. Is this a typical way of dealing with the semantics of Java generics? Just curious if I'm missing some better pattern.

Commments?

UPDATE:

One question was what do you need the Class for? Here is the implementation of findAll:

public <T extends Element> List<T> findAll(IElementPredicate<T> pred) {
    List<T> ret = new LinkedList<T>();
    Class<T> c = pred.getGenericClass();
    for(Element e: elements) {
     if (!c.isInstance(e)) continue;
     T obj = c.cast(e);
     if (pred.match(obj)) {
      ret.add(c.cast(e));
     }
    }
    return ret;
}

While it is true that match only takes a T, I need to make sure the object is a T before I can call it. For that, I need the "isInstance" and "cast" methods of Class (as far as I can tell).

+1  A: 

If you want, you can use the visitor pattern, or variants, to get around the explicit construction and casting. See the hibernate wiki page on this. I've been thinking about if you will get around your problem completely considering the peculiarities of type erasure, and I am not entirely sure it will work all the way.

edit: I saw your addition. If you would make your predicate hierarchy follow a visitor hierarchy, you wouldn't need the cast before the match call. Like so (untested):

interface Element {
    public boolean accept(ElementPredicateVisitor v);
}

class Declaration implements Element {
    public boolean accept(ElementPredicateVisitor v) {
        return v.visit(this);
    }    
}

class TaxReturn implements Element {
    public boolean accept(ElementPredicateVisitor v) {
        return v.visit(this);
    }    
}


interface IElementPredicate {
    public void match(Element e);
}

class ElementPredicateVisitor implements IElementPredicate {
    public boolean match(Element e) { 
        return e.accept(this); 
    }
    /**
     * default values
     */
    boolean visit(Declaration d) { return false; }
    boolean visit(TaxReturn tr) { return false; }
}

class DeclarationNamePredicate extends ElementPredicateVisitor {
    boolean visit(Declaration d) {
        return d.dSpecificExtraName() == "something"
    }
}

class TaxReturnSumPredicate extends ElementPredicateVisitor {
    boolean visit(TaxReturn tr) {
        return tr.sum() > 1000;
    }
}


public <T extends Element> List<T> findAll(IElementPredicate pred) {
    List<T> ret = new LinkedList<T>();
    for(Element e: elements) {            
        if (pred.match(obj)) {
                ret.add((T) obj);
        }
    }
    return ret;
}
disown
I use visitors frequently (in this very same project, in fact) but in this particular case, the visitor pattern would add a lot more code and complexity than I think would be required.
Michael Tiller
I agree with you, it is sort of a complicators switch in the way that it has large side effects. It is hard to reverse the generalism like you want. I beleive that your solution is the best, because without a visitor I beleive you would need late binding, or explicit type checking (in the way that equals() work). Your solution is better because it centralizes the type checking instead of putting that burden on the implementors. You see this problem in the generic Comparable implementations as well.
disown
And with late binding I meant that Java should implement overloaded method resolution based on the object type, not on the reference type. This is basically what you implemented in your code.
disown
+1  A: 

Your tree structure sounds very much like an XML DOM object. Have you considered translating your tree into a DOM structure and using XPath to do your queries? It might be a lot less custom code.

Jherico
A: 

I think that is nice and clean way of doing it and I would probably do it in the same way.

iny
+1  A: 

The closest "pattern" I think is type token and Generics Tutorial recommends them. You can also turn base predicate into super-type-token (a.k.a. Gafter gadget) and save the extra couple of lines when defining new predicates.

Yardena