#!/usr/bin/env python

# Only support * and ?

def fnmatch(name, pat):
    if not pat:
        return not name

    namelen = len(name)
    patlen = len(pat)

    name_idx = 0
    pat_idx = 0
    while name_idx < namelen and pat_idx < patlen:
        if pat[pat_idx] == '?':
            pat_idx += 1
            name_idx += 1
        elif pat[pat_idx] == '*':
            nextchar_pat = None if pat_idx + 1 == len(pat) else pat[pat_idx + 1]
            if nextchar_pat is None:
                return True
            if nextchar_pat == name[name_idx]:
                pat_idx += 2
            name_idx += 1
        elif name[name_idx] == pat[pat_idx]:
            name_idx += 1
            pat_idx += 1
        else:
            return False
    return name_idx == namelen

def fnmatch_r(name, pat):
    if not name:
        return True
    if not pat:
        return not name
    if pat[0] == '*':
        nextchar_pat = None if len(pat) == 1 else pat[1]
        if nextchar_pat is None:
            return True
        if nextchar_pat == name[0]:
            pat = pat[2:]
        return fnmatch_r(name[1:], pat)
    if pat[0] == '?' or name[0] == pat[0]:
        return fnmatch_r(name[1:], pat[1:])
    return False

if __name__ == "__main__":
    assert fnmatch("toto.py", "*")
    print('assert fnmatch("toto.py", "*") → ok')
    assert fnmatch("toto.py", "*.py")
    print('assert fnmatch("toto.py", "*.py") → ok')
    assert not fnmatch("ab.pya", "*.py")
    print('assert not fnmatch("ab.pya", "*.py") → ok')
    assert not fnmatch("toto.py", "*.c")
    print('assert not fnmatch("toto.py", "*.c") → ok')
    assert fnmatch("toto.py", "toto.*")
    print('assert fnmatch("toto.py", "toto.*") → ok')
    assert fnmatch("/dev/sda1", "/dev/sda?")
    print('assert fnmatch("/dev/sda1", "/dev/sda?") → ok')
    assert fnmatch("/dev/sdb1", "/dev/sd?1")
    print('assert fnmatch("/dev/sdb1", "/dev/sd?1") → ok')
    assert fnmatch("aaa", "???")
    print('assert fnmatch("aaa", "???") → ok')
    assert fnmatch("aaa", "?*")
    print('assert fnmatch("aaa", "?*") → ok')
    assert fnmatch("aaa", "???*")
    print('assert fnmatch("aaa", "???*") → ok')
    assert not fnmatch("aaa", "bbb")
    print('assert not fnmatch("aaa", "bbb") → ok')
    assert fnmatch("", "")
    print('assert fnmatch("", "") → ok')
    assert not fnmatch("toto", "")
    print('assert not fnmatch("toto", "") → ok')

    assert fnmatch_r("toto.py", "*")
    print('assert fnmatch_r("toto.py", "*") → ok')
    assert fnmatch_r("toto.py", "*.py")
    print('assert fnmatch_r("toto.py", "*.py") → ok')
    assert not fnmatch("ab.pya", "*.py")
    print('assert not fnmatch("ab.pya", "*.py") → ok')
    assert not fnmatch_r("toto.py", "*.c")
    print('assert not fnmatch_r("toto.py", "*.c") → ok')
    assert fnmatch_r("toto.py", "toto.*")
    print('assert fnmatch_r("toto.py", "toto.*") → ok')
    assert fnmatch_r("/dev/sda1", "/dev/sda?")
    print('assert fnmatch_r("/dev/sda1", "/dev/sda?") → ok')
    assert fnmatch_r("/dev/sdb1", "/dev/sd?1")
    print('assert fnmatch_r("/dev/sdb1", "/dev/sd?1") → ok')
    assert fnmatch_r("aaa", "???")
    print('assert fnmatch_r("aaa", "???") → ok')
    assert fnmatch_r("aaa", "?*")
    print('assert fnmatch_r("aaa", "?*") → ok')
    assert fnmatch_r("aaa", "???*")
    print('assert fnmatch_r("aaa", "???*") → ok')
    assert not fnmatch_r("aaa", "bbb")
    print('assert not fnmatch_r("aaa", "bbb") → ok')
    assert fnmatch_r("", "")
    print('assert fnmatch("", "") → ok')
    assert not fnmatch_r("toto", "")
    print('assert not fnmatch("toto", "") → ok')