Compiler Explorer

Source code

#include <iostream>
#include <vector>
#include <string_view>
//#include <stack>
//#include <cmath>
//#include <charconv> // from_chars
//#include <bit>
//#include <bitset>
#include <cstdint>

struct scoped_endl
{
    ~scoped_endl() { std::cout << '\n'; }
};
struct wchelper
{
    // *?aaa*?*bbb?*
    // ?*aaa?*bbb?*
    // [?][*][aaa?][*][bbb?][*]
    // the above means that basically the first char from the text is ignored
    // "a?c?d" <- this should turn into a single token, hm..
    //

std::string_view meat; // no ? chars here
    //size_t m = 0;
    size_t q = 0; // ? chars after the meat
    inline constexpr size_t mlen() const noexcept { return meat.size(); }
    inline constexpr size_t tlen() const noexcept { return mlen()+q; }
    inline constexpr bool is_q() const noexcept { return ((mlen() == 0) && (q)); }
    inline constexpr bool is_v() const noexcept { return (tlen() == 0); }
};
struct wchelper2
{
    // *?aaa*?*bbb?*
    // ?*aaa?*bbb?*
    // [?][*][aaa?][*][bbb?][*]
    // the above means that basically the first char from the text is ignored
    // a?c?d <- this should turn into a single token, hm..
    // ?*a?c??*wot?*
    // [?][*][a?c??][*][wot?][*]

std::string_view qmeat; // no * chars here
    //size_t m = 0;
    size_t q = 0; // number of ? chars
    inline constexpr void calc() noexcept
    {
        q = 0;
        size_t i = 0;
        const size_t n = qmeat.size();
        while (i < n) { q += (qmeat[i] == '?'); ++i; }
    }
    inline constexpr bool compare(const std::string_view text) const noexcept
    {
        //if (text.empty()) { return false; }
        const size_t n = tlen();
        if (text.size() < n) { return false; }
        size_t i = 0;
        while (i < n)
        {
            const char c = qmeat[i];
            if      (c == '?') {}
            else if (c != text[i]) { return false; }
            ++i;
        }
        return true;
    }
    //inline constexpr size_t mlen() const noexcept { return tlen()-q; }
    inline constexpr size_t tlen() const noexcept { return qmeat.size(); }
    inline constexpr bool is_q() const noexcept { return (q == tlen()); }
    inline constexpr bool is_m() const noexcept { return ((!is_v()) && (q == 0)); }
    inline constexpr bool is_v() const noexcept { return qmeat.empty(); }
};
constexpr bool _wc_match_rt(const std::string_view _s, const std::string_view text) noexcept
{
    std::string s;// { _s };
    s.reserve(_s.size());
    //std::cout << "_rt ";
    size_t n = _s.size();
    // optimize the search phrase:
    // a thing like [*?*?**] turns into [??*]
    size_t i = 0;
    //size_t min_len = 0;
    {
        char prev_c = 0;
        size_t q = 0;
        bool v = false;
        while (i < n)
        {
            const char c = _s[i];
            char this_c = 0;
            if      (c == '?')  { this_c = c; ++q; }
            else if (c == '*')  { this_c = c; v = true; }
            else
            {
                this_c = 'm';
                if (prev_c != 'm')
                {
                    if (q) { s += std::string(q, '?'); }
                    if (v) { s += '*'; }
                    q = 0; v = false;
                }
                s += c;
            }

prev_c = this_c;
            ++i;
        }
        if (prev_c != 'm')
        {
            if (q) { s += std::string(q, '?'); }
            if (v) { s += '*'; }
            q = 0; v = false;
        }
    }
    if (_s != s) { std::cout << "[" << _s << "] -> [" << s << "] "; }
    n = s.size();
    // tokenize the search phrase with the helper thing
    // don't store the * at all
    // in other words, only store the actual tokens with meat and/or ?
    // but remember if there's a * at the start and the end
    // "???*one*???"
    bool flex_s = false;
    bool flex_e = false;
    size_t min_len = 0;
    std::vector<wchelper2> stok;
    i = 0;
    {
        wchelper2 tmp;
        char prev_c = 0;
        size_t m = 0; //, q = 0;
        //while (true)
        size_t moff = 0;
        while (i < n)
        {
            const char c = s[i];
            char this_c = c;
            if (prev_c == '*') { moff = i; }
            if      (c == '*')
            {
                if (m)
                {
                    tmp.qmeat = { s.data()+moff, m };
                    tmp.calc();
                    stok.push_back(tmp);
                    min_len += m;
                    m = 0;
                }
                //flex_s = (stok.empty());
                //flex_s = (nq == 0);
                if (stok.empty()) { flex_s = true; }
                else { flex_s = (stok[0].is_q()); }
            }
            else { ++m; }
            prev_c = this_c;
            ++i;
        }
        if (m)
        {
            tmp.qmeat = { s.data()+moff, m };
            tmp.calc();
            stok.push_back(tmp);
            min_len += m;
        }
        flex_e = (prev_c == '*');
    }

// okay, gotta search now
    n = stok.size();
    if (n < 3)
    {
        std::cout << "**WTF**";
        return false;
    }

//size_t tn2 = text.size()-min_len;

std::string_view text2 = text;
    std::cout << "\n    text: " << text2 << '\n';
    std::string mon;
    // i think when a token matches at a given offset - there is no reason
    // to try to match it at any other offset
    // so perhaps, start from first token and "consume" the text
    size_t toki = 0;
    while (toki < n)
    {
        //std::cout << text << '\n';
        const wchelper2& tok = stok[toki];
        size_t j = 0;
        bool found = false;
        while (!text2.empty())
        {
            if (tok.compare(text2))
            {
                std::cout << "    ####: " << mon << tok.qmeat << '\n';
                found = true;
                text2.remove_prefix(tok.tlen());
                mon += tok.qmeat;
                break;
            }
            text2.remove_prefix(1);
            mon += ' ';
            ++j;
        }
        if (!found) { return false; }
        ++toki;
    }
    return true;

#if 0
    std::cout << "\n";
    if (flex_s) { std::cout << "<*<"; }
    i = 0;
    while (i < stok.size())
    {
        const wchelper2& tmp = stok[i];
        //if (tmp.is_v()) { std::cout << i << " <*>\n"; }
        //else { std::cout << i << " [" << tmp.qmeat << "] q=" << tmp.q << "\n"; }
        if (tmp.is_v()) { std::cout << "<*>"; }
        else { std::cout << "[" << tmp.qmeat << "]"; }
        ++i;
    }
    if (flex_e) { std::cout << ">*>"; }
    std::cout << " min=" << min_len << " tlen=" << text.size() << " tn2=" << tn2 << ", ";

return false;
    #endif
}
constexpr bool wildcard_match(const std::string_view s, const std::string_view text) noexcept
{
    //scoped_endl meh;
    //std::cout << '[' << s << "][" << text << "]:\t";
    size_t n = s.size();
    if (n == 0) { return false; }
    size_t min_len = 0;
    bool fixed_size = true;
    bool no_wc = true;
    bool meat = false; // meat is actual chars that are neither ? nor *
    uint8_t prev_type = 0;
    size_t flips = 0;
    size_t nmtok = 0; // number of "meat" tokens (?*??*? doesn't count as meat)
    size_t prev_tok = 0;
    bool s_has_var = false;
    bool e_has_var = false;
    bool t_has_var = false;
    size_t i = 0;
    // basic analysis of the search phrase:
    while (i < n)
    {
        const char c = s[i];
        uint8_t this_type = 0;
        switch (c)
        {
            case '?':
                this_type = 1;
                no_wc = false;
                ++min_len;
                break;
            case '*':
                this_type = 1;
                t_has_var = true;
                no_wc = false;
                fixed_size = false;
                break;
            default:
                this_type = 2;
                t_has_var = false; // hm
                meat = true;
                ++min_len;
                break;
        };
        if (this_type != prev_type)
        {
            prev_tok = flips; //nmtok;
            ++flips;
            if (this_type == 2)
            {
                ++nmtok;
            }
            if (prev_tok == 0)  { s_has_var = t_has_var; }
            e_has_var = t_has_var;
            //t_has_var = false;
        }
        prev_type = this_type;
        ++i;
    }
    if (prev_type == 1) { e_has_var = t_has_var; }
    //if (no_wc)
    if (!meat)
    {
        // no actual chars, only ? or *
        if (fixed_size) { return (s.size() == text.size()); }
        if (!no_wc) { return (text.size() >= min_len); }
    }
    else
    {
        // there's some meat
        if (text.size() < min_len) { return false; }
    }
    if (no_wc) { return (s == text); } // no actual ? and *, compare the strings
    i = 0;
    if (fixed_size)
    {
        // only ? chars, no *
        if (s.size() != text.size()) { return false; }
        while (i < n)
        {
            const char c = s[i];
            if      (c == '?') {}
            else if (c != text[i]) { return false; }
            ++i;
        }
        return true;
    }
    if (flips == 2)
    {
        // search phrase has a chunk of meat and a chunk of wildcards
        const bool from_start = (prev_type == 1+0);
        if (from_start)
        {
            while (i < n)
            {
                const char c = s[i];
                if      (c == '?') { break; }
                else if (c == '*') { break; }
                else if (c != text[i]) { return false; }
                ++i;
            }
            return true;
        }
        else
        {
            i = n;
            size_t j = text.size();
            while (i)
            {
                --i;
                --j;
                const char c = s[i];
                if      (c == '?') { break; }
                else if (c == '*') { break; }
                else if (c != text[i]) { return false; }
            }
            return true;
        }
    }
    if (flips == 3)
    {
        // search phrase has either 1 meat token  and 2 wildcard tokens
        // .....................or  2 meat tokens and 1 wildcard token
        if (nmtok == 1)
        {
            //std::cout << "! " ;
            // token in the middle
            if (!s_has_var)
            {
                // ???a*
                //std::cout << ">s> ";
                while (i < n)
                {
                    const char c = s[i];
                    if      (c == '?') {}
                    else if (c == '*') {} // this shouldn't happen here
                    else if (c != text[i]) { break; }
                    ++i;
                }
                while (i < n)
                {
                    const char c = s[i];
                    if      (c == '?') {} // this shouldn't happen here
                    else if (c == '*') { break; }
                    else if (c != text[i]) { return false; }
                    ++i;
                }
                return true;
            }
            if (!e_has_var)
            {
                // *a???
                //std::cout << ">e> ";
                i = n;
                size_t q = 0;
                while (i)
                {
                    --i;
                    const char c = s[i];
                    if      (c == '?') { ++q; }
                    else if (c == '*') { ++i; break; }
                }
                size_t d = n-i;
                i = text.size()-d;
                const size_t n2 = d-q;
                while (i < n2)
                {
                    const char c = s[i];
                    if (c != text[i]) { return false; }
                    ++i;
                }
                return true;
            }

// *a*
            // ?*a*?
            // count the number of ? before and after the token
            // s_count = number of ? before token
            // e_count = number of ? after token
            // start searching for the text after s_count
            // if a match is found there should be e_count chars left after it
            //std::cout << "<!> ";
            size_t s_count = 0;
            size_t e_count = 0;
            size_t moff = 0; // offset to the meat in s
            size_t mlen = 0; // meat length (not including ? chars)
            while (i < n)
            {
                if (mlen == 0) { moff = i; }
                const char c = s[i];
                if      (c == '?') { if (mlen == 0) { ++s_count; } else { ++e_count; } }
                else if (c == '*') {}
                else { ++mlen; }
                ++i;
            }
            std::string_view themeat = s.substr(moff, mlen);
            const size_t n2 = 1 + text.size() - (mlen + e_count);
            //std::cout << s_count << "^" << e_count << " >" << moff << "." << mlen << "< [" << themeat << "] " << n2 << " ";
            // searching.. start offset is s_count, number of tries should be..
            // 1 + text.size() - (mlen+e_count)
            size_t j = s_count;
            //std::cout << "\n";
            while (j < n2)
            {
                i = 0;
                while (i < mlen)
                {
                    //std::cout << themeat[i] << " " << text[j+i] << "\n";
                    if (themeat[i] != text[j+i]) { break; }
                    ++i;
                }
                if (i == mlen) { return true; }
                ++j;
            }
            return false;
        }
        
        if (nmtok == 2)
        {
            //std::cout << "<x*x> ";
            // abc*xyz
            // ab?*?yz
            // a hole in the middle
            // potential problem:
            // "aa*aa"   "aa"
            // "a?*?b"   "a...b"
            // "a?*?*?b" "a...b"
            // count how many ? we got in the middle
            // count how many meat chars there are on both sides
            size_t q = 0;
            size_t s_m = 0;
            size_t e_m = 0;
            bool mid = false;
            while (i < n)
            {
                const char c = s[i];
                if      (c == '?') { mid = true; ++q; }
                else if (c == '*') { mid = true; }
                else if (!mid)  { ++s_m; if (c != text[i]) { return false; } }
                else            { ++e_m; }
                ++i;
            }
            //std::cout << s_m << "^" << e_m << " q=" << q << ", ";
            i = 0;
            const size_t n2 = text.size();
            i = n - e_m;
            size_t k = n2-e_m;
            while (i < n2)
            {
                if (s[i] != text[k]) { return false; }
                ++k;
                ++i;
            }
            return true;
        }
    }
    std::cout << "min_len=" << min_len << ", meat=" << (int)(meat) << ", nmtok=" << nmtok << ", flips=" << flips << ", ";
    return _wc_match_rt(s, text);
    std::cout << "i don't know. ";
    return false;
}
void test(const std::string_view s, const std::string_view text) noexcept
{
    std::cout << '[' << s << "][" << text << "]:\t";
    bool res = wildcard_match(s, text);
    std::cout << (res ? "true" : "false");
    std::cout << '\n';
}
static_assert(wildcard_match("a?", "ab") == true);
static_assert(wildcard_match("a?b?c", "a.b.c") == true);
//static_assert(wildcard_match("a*b*c", "a.b.c") == true);
int main()
{

#if 0
    #endif
    test("","abc");
    test("*","abc");
    test("?*","abc");
    test("?*?","abc");
    test("?*??","abc");
    test("???*?","abc");
    test("?","abc");
    test("abc","abc");
    test("aaa","abc");
    test("a?c","abc");
    test("a?=","abc");
    test("a?*","a");
    test("a?*","abc");
    test("?*c","abc");
    test("a*c","abc");
    test("*b*","abc");
    test("a*e","abcde");
    test("a?*?e","abcde");
    test("aa*aa","aaaa");
    test("*bcd*","abcde");
    test("*bc?*","abcde");
    test("?bc*","abcde");
    test("??c*","abcde");
    test("*cd?","abcde");
    test("*c??","abcde");
    test("??c??","abcde");
    test("a??*?b", "a...b");
    test("da*da*da*", "daaadabadmanda");
    test("?*?six***?five*", "__six^^_five");
    test("a?*?six***?fiv?", "__six^^_five");
    test("*?one*two*three*?", "++one+++twothree++");
    test("*?one*two*five*?", "++onetwothree++");
    //test("one*two*three*", "__onetwothree__");
    return 0;
}