Cacher is the code snippet organizer for pro developers

run();

function run() {
    const test = [ { p: 'hello world', q: 'hello world', t: true },
        { p: 'hello', q: 'helle', t: false },
        { p: 'aaaaa', q: 'a', t: false },
        { p: 'a', q: 'aaaaa', t: false },
        { p: '*a', q: 'bbbabba', t: true },
        { p: 'a*', q: 'abcd', t: true },
        { p: 'a*a', q: 'abbbaaba', t: true },
        { p: '*a*', q: 'a', t: true },
        { p: '*a*', q: 'aa', t: true},
        { p: '*a*', q: 'aaa', t: true},
        { p: '?*', q: 'ab', t: true },
        { p: '?*', q: 'a', t: true },
        { p: '?*', q: '', t: false },
        { p: '*?', q: '', t: false },
        { p: '?', q: '', t: false },
        { p: '?', q: 'a', t: true },
        { p: 'a*a*ab', q: 'aaaab', t: true },
        { p: '*c***d?f*', q: 'cacbcdef', t: true},
        { p: '*??c?c', q: 'aacdcfc', t: true},
        { p: '*c**d*', q: 'acdbcdef', t: true},
        { p: '*ab?d*', q: 'wabdabad', t: true},
        { p: '??*', q: 'aab', t: true},
        { p: 'a*d?f', q: 'abcdef', t: true},
        { p: 'a****d?f', q: 'abc', t: false},
        { p: 'd?f*z*d?f', q: 'deffdefzzdef', t: true},
        { p: '*?a*a*', q: 'aaa', t: true},
        // P'Nitch test
        { p: 'aa', q: 'aa', t: true },
        { p: 'a?', q: 'ab', t: true },
        { p: 'a?a', q: 'aba', t: true },
        { p: 'a', q: 'aa', t: false },
        { p: '*', q: 'aa', t: true },
        { p: 'a*', q: 'aa', t: true },
        { p: 'a*a', q: 'aaa', t: true },
        { p: 'a*b', q: 'aaa', t: false },
        { p: 'a*f', q: 'abcdef', t: true },
        { p: 'a*d?f', q: 'abcdef', t: true },
        { p: 'a****d?f', q: 'abcdef', t: true },
        { p: 'a****d?x', q: 'abcdef', t: false },
        { p: 'c***d?f*', q: 'abcdef', t: false },
        { p: '?*', q: 'ab', t: true },
        { p: 'c*a*b', q: 'aab', t: false },
    ];
    let success = true;
    test.forEach((ts, i) => {
        const r = regexMatch(ts.p, ts.q);
        if(r !== ts.t) {
            success = false;
            console.log(`${i+1}. p: ${ts.p}, q: ${ts.q}, expected: ${ts.t}, actual: ${r}`);
        }
    });
    console.log(`success: ${success}`);
}

function normalizeAsterisk(pattern){
    if  (pattern.length === 0) return pattern;

    let newPattern = pattern[0];
    for(let x = 1, lastCh = pattern[0]; x < pattern.length; lastCh = pattern[x], x++){
        if (lastCh !== '*' || pattern[x] !== lastCh) {
            newPattern += pattern[x];
        }
    }
    return newPattern;
}
function regexMatch (pattern, q) {
    pattern = normalizeAsterisk(pattern);
    let i = 0;
    let j;

    if (pattern[0] !== '*') {
        while (i < pattern.length && pattern[i] !== '*') {
            if ((pattern[i] === '?' && q[i]) || pattern[i] === q[i]) {
                i++;
            } else {
                return false;
            }
        }
        if (i === pattern.length && i === q.length) {
            return true;
        }
        pattern = pattern.slice(i);
        q = q.slice(i);
    }

    if (pattern[pattern.length-1] !== '*') {
        i = pattern.length-1;
        j = q.length-1;
        while (i >= 0 && j >= 0 && pattern[i] !== '*') {
            if ((pattern[i] === '?' && q[j]) || pattern[i] === q[j]) {
                i--;
                j--;
            } else {
                return false;
            }
        }
        if (i === 0 && j === 0 && pattern[i] !== '*') {
            return true;
        }

        pattern = pattern.slice(0, i + 1);
        q = q.slice(0, j + 1);
    }

    if (pattern.length === 1) {
        return true;
    }

    let a = 1, b = 0;
    while (a < pattern.length && b < q.length) {
        if (pattern[a] === q[b] || pattern[a] === '?') {
            let match = true;
            let aa = a + 1;
            let bb = b + 1;
            while (aa < pattern.length && bb < q.length) {
                if (pattern[aa] === '?' || pattern[aa] === q[bb]) {
                    aa++;
                    bb++;
                    continue;
                } else if (pattern[aa] === '*') {
                    break;
                } else {
                    match = false;
                    break;
                }
            }

            if (match) {
                const pl = pattern[0];
                const pr = pattern.slice(aa, pattern.length);
                const ql = q.slice(0, b);
                const qr = q.slice(bb, q.length);

                if (pl.length === 0 && ql.length > 0) return false;
                if (pr.length === 0 && qr.length > 0) return false;

                return regexMatch(pl, ql) && regexMatch(pr, qr);
            } else {
                b++;
            }
        } else {
            b++;
        }
    }

    return false;
}