parsed notations

In all the previous examples, the custom patterns were interpreted at each call of function match(). Especially when match() occurs in a loop, this is not optimal in terms of performance. Fortunately, patterns can be parsed before being used in a match by using the predefined function Matchbod.matcher(String pattern, Class class), that takes a pattern written in some custom notation and the class associated to this notation, and returns a matcher, that is, an object implementing the Matcher interface. This interface defines a method (called matches()) matching some data with the (parsed form of the) pattern.

For instance, a pattern written in the notation for complex numbers can be parsed as follows:

Matcher m = Matchbox.matcher("(1.0+%yi)", Complex.class);
Subst sub = new NonLinearSubst();
if(m.match(new Complex(1, 5), sub))

In order for this to work with a custom notation for a type T, one must implement a method T.matcher(String pat, ParsePosition pos), which parses a sub-pattern starting at a given position and returns a matcher object corresponding to the parsed pattern, and also updates the position to indicate the sub-pattern that was consumed. The matcher method for the Complex type can be written as follows:

public static Matcher matcher(String pat, ParsePosition pos) throws ParseFail {
    Matcher mr, mi = null;
    if(!Matchbox.matchChar('(', pat, pos))
        throw new ParseFail();
    mr = Matchbox.numberMatcher(pat, pos);
    if(pat.charAt(pos.getIndex()) == '+') {
        Matchbox.matchChar('+', pat, pos);
        mi = Matchbox.numberMatcher(pat, pos);
        if(!Matchbox.matchChar('i', pat, pos))
            throw new ParseFail();
    if(!Matchbox.matchChar(')', pat, pos)) throw new ParseFail();
    return new ComplexMatcher(mr, mi);
The numberMatcher(pat, pos) function above is predefined in myPatterns. It parses at the given offset either a variable occurrence or a sub-pattern for a number. In case of a parse error, the method must throw a ParseFail exception.

In case of success, the method must return a matcher. For Complex numbers, one has to define an instantiate the following class:

class ComplexMatcher implements Matcher {
    Matcher mr, mi;
    public ComplexMatcher(Matcher re, Matcher im) {
        mr = re;
        mi = im;
    public boolean match(Object data, Subst sub) {
        if(!(data instanceof Complex)) return false;
        Complex c = (Complex)data;
        return mr.match(, sub) 
        && (mi == null || mi.match(, sub));
That is, the ComplexMatcher represents a compiled pattern written in the complex notation, which contains a sub-matcher for the real part, and an optional sub-matcher for the imaginary part. Thus, the match() method invokes these sub-matchers on the given data (after checking that the data is a Complex), and succeeds if all the sub-matchers succeed.

That's all about defining custom notations. More elaborate examples are included in the myPatterns distribution, including a custom notation for red-black trees.

Next: Performance