Simple wildcard pattern matcher in Java (follow-up)

Question

This is a follow-up review of Simple wildcard pattern matcher in Java

I have built a simple wild card pattern matcher algorithm.

I am concerned where it can be improved further.

• Main concern is algorithm.
• Any other improvements are welcome too.

What it should does:

• Match * -> one or more of any character
• Match ? -> any single character similar to the file search wild card pattern (ex: Windows file search)

Code:

public class SimpleMatch {

    //state enums
    private static enum State {

        JUST_STARTED, NORMAL, EAGER, END
    }

    //constants
    private static final char MATCH_ALL = '*';
    private static final char MATCH_ONE = '?';

    private final int ptnOutBound; // pattern out bound
    private final int strOutBound; // string out bound
    private final String pattern; // pattern
    private final String matchString; // string to match

    private int ptnPosition; // position of pattern
    private int strPosition; // position of string
    private State state = State.JUST_STARTED; // state
    private boolean matchFound = false; // is match

    public SimpleMatch(String pattern, String matchStr) {

        if (pattern == null || matchStr == null) {
            throw new IllegalArgumentException(
                    "Pattern and String must not be null");
        }

        this.pattern = pattern;
        this.matchString = matchStr;
        int pl = pattern.length();
        int sl = matchStr.length();
        if (pl == 0 || sl == 0) {
            throw new IllegalArgumentException(
                    "Pattern and String must have at least one character");
        }
        ptnOutBound = pl - 1;
        strOutBound = sl - 1;
        ptnPosition = 0;
        strPosition = 0;

    }

    private void calcState() {
        //calculate state
        if (state == State.END) {
            return;
        }

        if (!patternCheckBound() || !matchStrCheckBound()) {
            state = State.END;
        } else if (patternChar() == MATCH_ALL) {
            if (!patternNextCheckBound()) {
                state = State.END;
                matchFound = true;
            } else {
                state = State.EAGER;
            }
        } else {
            state = State.NORMAL;
        }
    }

    private void eat() {
        //eat a character
        if (state == State.END) {
            return;
        }

        matchFound = false;

        if (state == State.EAGER) {

            int curStrPosition = strPosition;
            int curPtnPosition = ptnPosition;
            strPosition++;
            ptnPosition++;
            if (match()) {
                state = State.END;
                matchFound = true;
                return;
            } else {
                strPosition = curStrPosition;
                ptnPosition = curPtnPosition;
                state = State.EAGER;
            }
            strPosition++;
        } else if (state == State.NORMAL) {
            if (matchOne()) {
                strPosition++;
                ptnPosition++;
                matchFound = true;
            } else {
                state = State.END;
            }
        }
    }

    private boolean matchOne() {
        // match one
        char pc = patternChar();
        return (pc == MATCH_ONE || pc == matchStrChar());
    }

    private char patternChar() {
        // pattern current char
        return pattern.charAt(ptnPosition);
    }

    private char matchStrChar() {
        // str current char
        return matchString.charAt(strPosition);
    }

    private boolean patternCheckBound() {
        //pattern position bound check
        return ptnPosition <= ptnOutBound;
    }

    private boolean patternNextCheckBound() {
        //pattern next position bound check
        return (ptnPosition + 1) <= ptnOutBound;
    }

    private boolean matchStrCheckBound() {
        //string bound check
        return strPosition <= strOutBound;
    }

    /**
* Match and return result
*
* @return true if match
*/

    public boolean match() {
        if (ptnOutBound > strOutBound) {
            return false;
        }
        while (state != State.END) {
            calcState();
            eat();
        }
        return matchFound;
    }

    /**
* Match and return result
*
* @param pattern pattern
* @param matchStr string to match
* @return true if match
* @throws IllegalArgumentException
*/
    public static boolean match(String pattern, String matchStr) throws
            IllegalArgumentException {
        return new SimpleMatch(pattern, matchStr).match();
    }

}

Unit Test:

This code currently passes following jUnit Test Cases

import org.junit.Assert;
import org.junit.Test;

/**
* Unit Test for SimpleMatch
*
* @author Bhathiya
*/
public class SimpleMatchTest {

    @Test
    public void test1() {
        SimpleMatch m = new SimpleMatch("a*", "bb");
        Assert.assertFalse(m.match());
    }

    @Test
    public void test2() {
        SimpleMatch m = new SimpleMatch("a*b", "anj");
        Assert.assertFalse(m.match());
    }

    @Test
    public void test3() {
        SimpleMatch m = new SimpleMatch("a?b", "acd");
        Assert.assertFalse(m.match());
    }

    @Test
    public void test4() {
        SimpleMatch m = new SimpleMatch("a*", "abcdefg");
        Assert.assertTrue(m.match());
    }

    @Test
    public void test5() {
        SimpleMatch m = new SimpleMatch("a*ba", "abba");
        Assert.assertTrue(m.match());

    }

    @Test
    public void test6() {
        SimpleMatch m = new SimpleMatch("bhathiya", "bhathiya");
        Assert.assertTrue(m.match());
    }

    @Test
    public void test7() {
        SimpleMatch m = new SimpleMatch("a?", "a1");
        Assert.assertTrue(m.match());
    }

    @Test
    public void test8() {
        SimpleMatch m = new SimpleMatch("bhathiya", "blah");
        Assert.assertFalse(m.match());
    }

    @Test
    public void test9() {
        SimpleMatch m = new SimpleMatch("/img/abc.jpg", "/img/abc.jpg");
        Assert.assertTrue(m.match());
    }

    @Test
    public void test11() {
        SimpleMatch m = new SimpleMatch("/x/*/z/abc.jpg", "/x/a/z/abc.jpg");
        Assert.assertTrue(m.match());
    }

    @Test
    public void test12() {
        SimpleMatch m = new SimpleMatch("/x/*/z/abc.jpg", "/x/a/j/abc.jpg");
        Assert.assertFalse(m.match());
    }

    @Test
    public void test13() {
        SimpleMatch m = new SimpleMatch("a", "a");
        Assert.assertTrue(m.match());
    }

    @Test
    public void test14() {
        SimpleMatch m = new SimpleMatch("a", "b");
        Assert.assertFalse(m.match());
    }

    @Test
    public void test15() {
        SimpleMatch m = new SimpleMatch("aa", "ab");
        Assert.assertFalse(m.match());
    }

    @Test
    public void test16() {
        SimpleMatch m = new SimpleMatch("aaaa", "a");
        Assert.assertFalse(m.match());
        m = new SimpleMatch("aaaa", "aaa");
        Assert.assertFalse(m.match());
        m = new SimpleMatch("aaaa", "aa");
        Assert.assertFalse(m.match());
    }

    @Test
    public void test17() {
        SimpleMatch m = new SimpleMatch("a*", "a");
        Assert.assertFalse(m.match());
    }

    @Test
    public void test18() {
        SimpleMatch m = new SimpleMatch("a*xxxxxxxxxxb", "axxxxxxxxxxxb");
        Assert.assertTrue(m.match());
    }

    @Test
    public void test19() {
        SimpleMatch m = new SimpleMatch("a*xxxxxxxxxxb", "axxxxxxxxxxxc");
        Assert.assertFalse(m.match());
    }

    @Test
    public void test20() {
        SimpleMatch m = new SimpleMatch("a*b*c*d", "abbccdd");
        Assert.assertTrue(m.match());
    }

    @Test
    public void test21() {
        SimpleMatch m = new SimpleMatch("a*xxxxxxx*xxb", "axxxxxxxxxhelloxxb");
        Assert.assertTrue(m.match());
    }

    @Test
    public void test22() {
        SimpleMatch m = new SimpleMatch("a*xxxxxxxxxx*", "axxxxxxxxxxxhello");
        Assert.assertTrue(m.match());
    }

    @Test
    public void test23() {
        SimpleMatch m = new SimpleMatch(
                "start*in-part-1*in-part-2*in-part-3*end",
                "start[because]in-part-1[I'm]in-part-2[Batman]in-part-3[!]end");
        Assert.assertTrue(m.match());
    }
}

Related Links:

• travis-ci: https://travis-ci.org/JaDogg/SimpleMatch
• repository: https://github.com/JaDogg/SimpleMatch

Answer 1

Using mutation with recursion

You've written a lot of code to solve a mildly difficult problem. I think that this excerpt from eat() is indicative of the complexity:

int curStrPosition = strPosition;
int curPtnPosition = ptnPosition;
strPosition++;
ptnPosition++;
if (match()) {
    state = State.END;
    matchFound = true;
    return;
} else {
    strPosition = curStrPosition;
    ptnPosition = curPtnPosition;
    state = State.EAGER;
}
strPosition++;

Your solution relies on mutual recursion: match() calls eat(), which calls match(). Recursion is a powerful technique because…

• Local reasoning can be extended to solve a larger complex problem.
• Backtracking state can be stored in the call stack.

However, as soon as you introduce mutation, those benefits disappear. The reason for the else clause of the excerpt above is to undo side-effects of match(), and the only way to know what those side-effects may be is to read the source code of match(). To understand any part of your solution, you must understand all of it. That's a huge mental burden for any code maintainer, and it also means that your code is fragile.

Interface

The SimpleMatch(String pattern, String matchStr) interface is cumbersome, in my opinion. A programmer using your library might get the order of the arguments confused, unless he/she has good documentation or a good IDE.

Instead, I suggest dividing the responsibilities:

new SimplePattern(pattern).match(matchStr);

This makes the parameters foolproof, and also simplifies the constructor.

All you need for the pattern and matchStr is .length() and .charAt(). Therefore you shouldn't require a String, considering that any String

Validation

Why shouldn't an empty pattern legally match an empty string?

Dubious optimization

The following optimization relies in the fact that every character in the pattern must consume at least one character of the string.

if (ptnOutBound > strOutBound) {
    return false;
}

Even if it is accurate for your current behaviour of * in the pattern, but it would fail if * meant "zero or more characters" — as it customarily does with shell globs. Therefore, if you use that optimization, it's worth an explanatory comment.

Suggested implementation

Notice that the object barely carries state:

public class SimplePattern {

    //constants
    private static final char MATCH_ALL = '*';
    private static final char MATCH_ONE = '?';

    private final CharSequence pattern;
    private final int ptnPosition;

    public SimplePattern(CharSequence pattern) {
        this(pattern, 0);
    }

    private SimplePattern(CharSequence pattern, int ptnPosition) {
        if (pattern == null) {
            throw new IllegalArgumentException("Pattern must not be null");
        }

        this.pattern = pattern;
        this.ptnPosition = ptnPosition;
    }

    /**
     * Match and return result
     *
     * @return true if match
     */
    public boolean match(CharSequence string) {
        return this.match(string, 0);
    }

    public boolean match(CharSequence string, int startPosition) {
        if (ptnPosition == this.pattern.length()) {
            return startPosition == string.length();
        }
        if (startPosition >= string.length()) {
            return false;
        }
        SimplePattern nextPattern = new SimplePattern(pattern, ptnPosition + 1);
        char patternChar = this.pattern.charAt(this.ptnPosition);
        switch (patternChar) {
          case MATCH_ONE:
            return nextPattern.match(string, startPosition + 1);
          case MATCH_ALL:
            for (int i = startPosition + 1; i <= string.length(); i++) {
                if (nextPattern.match(string, i)) {
                    return true;
                }
            }
            return false;
          default:
            return string.charAt(startPosition) == patternChar &&
                   nextPattern.match(string, startPosition + 1);
        }
    }

    /**
     * Match and return result
     *
     * @param pattern pattern
     * @param matchStr string to match
     * @return true if match
     * @throws IllegalArgumentException
     */
    public static boolean match(CharSequence pattern, CharSequence matchStr) {
        return new SimplePattern(pattern).match(matchStr);
    }

}

Acceptable use of mutation with recursion

Recursion is discouraged in Java, due to performance concerns and stack size limitations. Therefore, you may want to reintroduce some mutation (looping) in the solution. Here is a replacement for the match(string, startPosition) method above that illustrates how you can do so responsibly:

public boolean match(CharSequence string, int startPosition) {
    int ptnPos;
    for (ptnPos = this.ptnPosition; ptnPos < this.pattern.length(); ptnPos++) {
        if (startPosition >= string.length()) {
            return ptnPos == this.pattern.length();
        }

        char patternChar = this.pattern.charAt(ptnPos);
        switch (patternChar) {
          case MATCH_ONE:
            startPosition++;
            break;
          case MATCH_ALL:
            SimplePattern nextPattern = new SimplePattern(pattern, ptnPos + 1);
            for (int i = startPosition + 1; i <= string.length(); i++) {
                if (nextPattern.match(string, i)) {
                    return true;
                }
            }
            return false;
          default:
            if (string.charAt(startPosition++) != patternChar) {
                return false;
            }
        }
    }
    assert ptnPos == this.pattern.length();
    return startPosition == string.length();
}

Now, instead of making a recursive call for each character in the pattern, you only need to make a recursive call for each * in the pattern.

Notice that this version only mutates local variables, so that it has no side-effects outside the current stack frame. The use of final in the declarations of instance variables pattern and ptnPosition helps enforce that discipline.

Answer 2

I don't have a comment regarding the algorithm right now, just the general code structure.

Comments

Some comments are unnecessary and those make it harder to find the actually useful comments. After a while, people will just ignore all you comments. For example:

private final String pattern; // pattern
private boolean matchFound = false; // is match
private State state = State.JUST_STARTED; // state

Some comments should be changed so they better describe what you mean. For example:

private final int ptnOutBound; // pattern out bound

Ok, so ptn stands for pattern, that's good to know. But what exactly is out bound? From the code, I'm assuming upper bound (or length - 1)?

Another example is State and it's values.

And most methods don't have any comments. The code would be faster to understand if at least eat had a comment. Or if you described how your algorithm approximately works in the class comment.

But even a method like matchOne should be commented. Right now, I have to look up MATCH_ONE, matchStrChar and patternChar to see what it does. If you comment something like true if current character matches * or current pattern I know right away what it does.

Constructor

I would pull up all checks to the very beginning. Also, I wouldn't save the length in a variable if it is only used twice. Constructors are generally not called that often.

Number of Fields

As was mentioned in your last question, you have a lot of fields. I would just get rid of ptnOutBound and strOutBound. You can use pattern.length() and matchString.length(). In most cases, you would just need to change <= to <.

If you still want to keep them, I would rename them to patternUpperBound and stringUpperBound so it is clear that they relate to pattern and matchString (or length instead of upperBound and use < instead of <=, it's easier to understand). Same with ptnPosition and strPosition (patternPosition isn't all that long and easier to read).

Number of Methods

You still have too many methods. I would get rid of patternChar, matchStrChar, patternCheckBound, patternNextCheckBound and matchStrCheckBound. These really make the code harder to read.