Simple wildcard pattern matcher in Java

Question

I have built a simple wild card pattern matcher algorithm.

I am concerned where it can be improved.

• 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 {

    private static enum State {

        JUST_STARTED, NORMAL, EAGER, END
    }

    private final int pl; // pattern length
    private final int pob; // pattern out bound
    private final int sl; // string length
    private final int sob; // string out bound
    private final String p; // pattern
    private final String s; // string to match

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

    private int pp; // position of pattern
    private int ps; // position of string
    private State z; // state
    private boolean m = false; // is match

    public SimpleMatch(String p, String s) {

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

        this.p = p;
        this.s = s;
        pl = p.length();
        sl = s.length();
        if (pl == 0 || sl == 0) {
            throw new IllegalArgumentException(
                    "Pattern and String must have at least one character");
        }
        pob = pl - 1;
        sob = sl - 1;
        pp = 0;
        ps = 0;
        z = State.JUST_STARTED;

    }

    private SimpleMatch(String p, String s, int pp, int ps) {

        this(p, s);
        this.pp = pp;
        this.ps = ps;
    }

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

        if (!psafe() || !ssafe()) {
            z = State.END;
        } else if (pc() == MATCH_ALL) {
            if (!pnsafe()) {
                z = State.END;
                m = true;
            } else {
                z = State.EAGER;
            }
        } else {
            z = State.NORMAL;
        }
    }

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

        m = false;

        if (z == State.EAGER) {
            SimpleMatch smo = new SimpleMatch(p, s, pp + 1, ps + 1);
            if (smo.match()) {
                z = State.END;
                m = true;
                return;
            }
            ips();
        } else if (z == State.NORMAL) {
            if (mo()) {
                ips();
                ipp();
                m = true;
            } else {
                z = State.END;
                m = false;
            }
        }
    }

    private boolean mo() {
        // match one
        char pc = pc();
        return (pc == MATCH_ONE || pc == sc());
    }

    private char pc() {
        // pattern current char
        return p.charAt(pp);
    }

    private char sc() {
        // str current char
        return s.charAt(ps);
    }

    private boolean psafe() {
        //pattern position bound check
        return pp <= pob;
    }

    private boolean pnsafe() {
        //pattern next position bound check
        return (pp + 1) <= pob;
    }

    private boolean ssafe() {
        //string bound check
        return ps <= sob;
    }

    private void ipp() {
        //increase position of pattern
        pp++;
    }

    private void ips() {
        //increate position of string
        ps++;
    }

    /**
     * Match and return result
     * @return true if match
     */        
    public boolean match() {
        if (pob > sob) {
            return false;
        }
        while (z != State.END) {
            calcState();
            eat();
        }
        return m;
    }

    /**
     * Match and return result
     * @param p pattern
     * @param s string to match
     * @return true if match
     * @throws IllegalArgumentException 
     */
    public static boolean match(String p, String s) throws
            IllegalArgumentException {
        return new SimpleMatch(p, s).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 m1 = new SimpleMatch("a*", "bb");
        Assert.assertFalse(m1.match());
    }

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

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

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

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

    }

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

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

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

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

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

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

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

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

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

}

Related Links:

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

Answer 1

private final int pl; // pattern length
private final int pob; // pattern out bound
private final int sl; // string length
private final int sob; // string out bound
private final String p; // pattern
private final String s; // string to match

private int pp; // position of pattern
private int ps; // position of string
private State z; // state
private boolean m = false; // is match

Instead of writing a comment, why don't you use the complete name?

private final int length; // pattern length
private final int outbound; // pattern out bound
private final int stringLength; // string length
private final int stringOutBound; // string out bound
private final String pattern; // pattern
private final String matchString; // string to match

private int position; // position of pattern
private int stringPos; // position of string
private State state; // state
private boolean matchFound = false; // is match

Some examples, I used length instead of pattern because I think in this class pattern is obvious (or at least, I think.)

But why you have so much fields? Do you really need all them or we can convert them to variables?

And, if I don't remember wrong, the static final fields should go to the top of the class.

---

In your constructor, move the check conditions at top

public SimpleMatch(String p, String s) {

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

    pl = p.length();
    sl = s.length();

    if (pl == 0 || sl == 0) {
        throw new IllegalArgumentException(
                "Pattern and String must have at least one character");
    }

    this.p = p;
    this.s = s;
    pob = pl - 1;
    sob = sl - 1;
    pp = 0;
    ps = 0;
}

And use better names! Even for params variables (who uses your class need to check the code / or documentation to understand what p and s are!)

I prefer to have all conditions in the top of the constructor so you (and who uses it) can see why the code thrown an exception without surfing between the constructor.

You can just do

private State z = State.JUST_STARTED; // state

and avoid

z = State.JUST_STARTED;

The same for others constructor, really what means pp, ps!

pl and sl are used inside constructor only, so convert to local variables:

int pl = p.length();
int sl = s.length();

You could use Guava Preconditions to improve the constructor style but whatever.

---

Method names, maybe:

mo -> matchOne
pc -> patternChar
sc -> stringChar
psafe -> hasNextPositionPattern (i really like the hasNext but it could be a bit strange like name anyway)
pnsafe -> hasNextPositionString (same)
ssafe -> checkStringPosition
ipp -> nextCharPattern
ips -> nextCharString

Now, you really need this methods?

nextCharString()
nextCharPattern()

Why not directly

stringPos++;
position++;

?

The same for other methods like patternChar.

---

SimpleMatch smo = new SimpleMatch(pattern, matchString, position + 1, stringPos + 1);

if (smo.match()) {
    state = State.END;
    matchFound = true;
    return;
}

Here you create another SimpleMatch instance, you can't alter the current instance?

Something like:

position++;
stringPos++;

if (match()) {
    state = State.END;
    matchFound = true;
    return;
}

Maybe you want to keep the original instance to the position because you want to return the match position?

What about

if (match()) {
    stringPos--;
    position--;

    state = State.END;
    matchFound = true;
    return;
}

But I don't see where you return there info... anyway, it still works (or at least, your test cases)

} else if (state == State.NORMAL) {
    if (matchOne()) {
        nextCharString();
        nextCharPattern();

        matchFound = true;
    } else {
        state = State.END;
        matchFound = false;
    }
}

The matchFound = false; is useless, it's already false. (you marked it false at method start matchFound = false;)

---

It's how it could look

public class SimpleMatch {

    private static enum State {
        JUST_STARTED, NORMAL, EAGER, END
    }

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

    private final int outbound;
    private final int stringOutbound;
    private final String pattern;
    private final String matchString;

    private int position;
    private int stringPos;
    private State state = State.JUST_STARTED;
    private boolean matchFound = false;

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

        int patternLength = pattern.length();
        int stringLength = matchString.length();

        if (patternLength == 0 || stringLength == 0) {
            throw new IllegalArgumentException(
                    "Pattern and String must have at least one character");
        }

        this.pattern = pattern;
        this.matchString = matchString;

        outbound = patternLength - 1;
        stringOutbound = stringLength - 1;

        position = 0;
        stringPos = 0;
    }

    private SimpleMatch(String pattern, String matchString, int position, int stringPos) {
        this(pattern, matchString);

        this.position = position;
        this.stringPos = stringPos;
    }

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

        if (!hasNextPositionPattern() || !checkStringPosition()) {
            state = State.END;
        } else if (patternChar() == MATCH_ALL) {
            if (!hasNextPositionString()) {
                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) {
            position++;
            stringPos++;

            if (match()) {
                stringPos--;
                position--;

                state = State.END;
                matchFound = true;
                return;
            }

            nextCharString();
        } else if (state == State.NORMAL) {
            if (matchOne()) {
                nextCharString();
                nextCharPattern();

                matchFound = true;
            } else {
                state = State.END;
            }
        }
    }

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

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

    private char stringChar() {
        // str current char
        return matchString.charAt(stringPos);
    }

    private boolean hasNextPositionPattern() {
        //pattern position bound check
        return position <= outbound;
    }

    private boolean hasNextPositionString() {
        //pattern next position bound check
        return (position + 1) <= outbound;
    }

    private boolean checkStringPosition() {
        //string bound check
        return stringPos <= stringOutbound;
    }

    private void nextCharPattern() {
        //increase position of pattern
        position++;
    }

    private void nextCharString() {
        //increate position of string
        stringPos++;
    }

    /**
     * Match and return result
     * @return true if match
     */
    public boolean match() {
        if (outbound > stringOutbound) {
            return false;
        }

        while (state != State.END) {
            calcState();
            eat();
        }

        return matchFound;
    }

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

}

In this post I used my variables names, if you think it's confused I will edit it!