#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <optional>
#include <cassert>
#include <future>
//? Любой отдельный символ
//* Ноль или более символов
//# Любая однозначная цифра (0-9)
//[charlist] Любой отдельный символ в charlist
//[!charlist] Любой отдельный символ, отсутствующий в charlist
//Symbol Meaning
//LIKE '5[*]' 5*
//LIKE '[?]n' ?n
//LIKE '[a-cdf]' a, b, c, d, or f
//LIKE '[-acdf]' -, a, c, d, or f
//LIKE '[ [ ]' [
//LIKE ']' ]
//LIKE 'abc[_]d*' abc_d and abc_de
//LIKE 'abc[def]' abcd, abce, and abcf
constexpr bool MatchWildcardAndText_showDebugOutput = !true;
constexpr std::wstring_view MatchWildcardAndText_DebugPrefix = L" dbg: ";
bool MatchWildcardAndText(const std::wstring_view text, const std::wstring_view wc)
{
auto wc_cur = wc.cbegin();
auto wc_end = wc.cend();
auto text_cur = text.cbegin();
auto text_end = text.cend();
//информация о пропарсенных квадратных скобках
struct s_SquareBracketsInfo
{
private:
//#todo - для оптимизации можно попробовать заменить строку массивом, тогда уберётся работа с кучей
std::wstring m_CharsList;//список символов, раскрытый из квадратных скобой
size_t m_ClosingBracketPos{};//позиция закрывающей скобки
bool m_Inverted{};//флаг инверсии из начала скобок
private:
//для оптимизации: предыдущий распарсенный текст.
//Если он такой же, то заново парсить не нужно, всё уже готово
std::optional<std::wstring_view> m_lastParsedText;
public:
bool TestChar(const char c)const noexcept
{
const bool contains = (m_CharsList.find(c) != m_CharsList.npos);
if (m_Inverted)
{
return !contains;
}
else
{
return contains;
}
}
bool Parse(const std::wstring_view text)
{
if (m_lastParsedText)
{
if (m_lastParsedText->size() == text.size())
{
if (m_lastParsedText->data() == text.data())
{
if constexpr (MatchWildcardAndText_showDebugOutput)std::wcout << MatchWildcardAndText_DebugPrefix << L"m_lastParsedText reused\n";
return true;
}
}
}
auto res = Parse__(text);
if (res)
{
//запоминаем последний парсённый текст
m_lastParsedText = text;
//if constexpr(MatchWildcardAndText_showDebugOutput)std::wcout<<MatchWildcardAndText_DebugPrefix<<L"m_lastParsedText saved\n";
assert(m_lastParsedText);
assert(!m_lastParsedText->empty());
assert(m_lastParsedText->size() > m_ClosingBracketPos);
assert((*m_lastParsedText)[m_ClosingBracketPos] == L']');
}
else
{
//поскольку состояние могло меняться, забываем последний текст
m_lastParsedText.reset();
if constexpr (MatchWildcardAndText_showDebugOutput)std::wcout << MatchWildcardAndText_DebugPrefix << L"m_lastParsedText reset\n";
}
return res;
}
size_t PosOfClosingBracket()const noexcept
{
return m_ClosingBracketPos;
}
private:
//заполнение списка символов из квадратных скобок
//text - начинается с первого символа после открывающей L'['
bool Parse__(std::wstring_view text)
{
//тут не производится оптимизация по удалению повторов [ababa].
//Предполагается, что юзер сам себе не враг, а если добавлять алгоритм
//удаления повторов - это будет постоянная дополнительная нагрузка
m_CharsList.clear();
m_ClosingBracketPos = {};
m_Inverted = {};
m_CharsList.reserve(256);
if (text.empty())return false;
//справа ограничиваемся по закрывающей скобке
{
const auto pos = text.find_first_of(L']');
if (pos == text.npos)return false;
text = text.substr(0, pos);
m_ClosingBracketPos = pos;
}
//флаг инверсии
if (!text.empty() && text.front() == L'!')
{
m_Inverted = true;
text.remove_prefix(1);
}
//сейчас text такой:
//begin,front - первый символ после L'[' или L"[!"
//back - символ перед L']'
//end - L']'
auto text_cur = text.cbegin();
auto text_end = text.cend();
while (text_cur != text_end)
{
//text_cur - текущий символ
//если следующий символ это минус,
if (auto hyphen = text_cur + 1; hyphen != text_end && *hyphen == L'-')
{
//то после минуса тоже должен быть какой-то символ
if (auto second = hyphen + 1; second != text_end)
{
//обработка X-Z, сейчас находимся на X
char c1 = *text_cur;
char c2 = *second;
if (c1 > c2)std::swap(c1, c2);
for (char c = c1; c <= c2; ++c)m_CharsList.push_back(c);
//идём дальше
text_cur = second + 1;
continue;
}
}
//один символ кладём в список
m_CharsList.push_back(*text_cur);
text_cur++;
}
return true;
}
};
s_SquareBracketsInfo SBInfo;
while (wc_cur != wc_end)
{
if (text_cur == text_end)
{
//завершающие звёздочки игнорируем
if (*wc_cur == L'*')
{
++wc_cur;
continue;
}
return false;
}
switch (*wc_cur)
{
default:
{
//любой другой символ - должен совпасть с текстовым
if (*wc_cur == *text_cur)
{
++wc_cur;
++text_cur;
}
else
{
return false;
}
}break;
case L'?':
{
++wc_cur;
++text_cur;
}break;
case L'#':
{
if (L'0' <= *text_cur && *text_cur <= L'9')
{
++wc_cur;
++text_cur;
}
else
{
return false;
}
}break;
case L'*':
{
auto wc_next = wc_cur + 1;
bool done{};
do
{
if (wc_next != wc_end)
{
switch (*wc_next)
{
default:
{
//любой другой символ - должен совпасть с текстовым
if (*wc_next == *text_cur)
{
//совпал, поэтому звёздочку считаем завершённой
++wc_cur;
done = true;
}
else
{
//звёздочка забирает один символ из текста
++text_cur;
}
}break;
case L'?':
{
//звезда сматчилась с пустотой
++wc_cur;
done = true;
}break;
case L'#':
{
if (L'0' <= *text_cur && *text_cur <= L'9')
{
//звезда сматчилась с пустотой
++wc_cur;
done = true;
}
}break;
case L'*':
{
//звезда сматчилась с пустотой
++wc_cur;
//завершение не делаем, так как идём обрабатывать звезду
//done=true;
}break;
case L'[':
{
auto wc_past_next = wc_next + 1;
if (wc_past_next != wc_end && SBInfo.Parse({ &*wc_past_next, size_t(wc_end - wc_past_next) }))
{
//дальше лежат корректные квадратные скобки
++wc_cur;
done = true;
}
else
{
//считаем обычным символом
//любой другой символ - должен совпасть с текстовым
if (*wc_next == *text_cur)
{
++wc_cur;
done = true;
}
}
}break;
}
}
else
{
//следующего символа в маске нет, поэтому всё остальное - матчится
return true;
}
} while (!done && wc_cur != wc_end && text_cur != text_end);
}break;
case L'[':
{
auto wc_next = wc_cur + 1;
if (wc_next != wc_end && SBInfo.Parse({ &*wc_next, size_t(wc_end - wc_next) }))
{
//символ строки должен лежать в списке
if (SBInfo.TestChar(*text_cur))
{
wc_cur = wc_next + SBInfo.PosOfClosingBracket() + 1;
++text_cur;
}
else
{
return false;
}
}
else
{
//считаем обычным символом
//любой другой символ - должен совпасть с текстовым
if (*wc_cur == *text_cur)
{
++wc_cur;
++text_cur;
}
else
{
return false;
}
}
}break;
}
}
//#todo - эти три строки можно записать с одним return
if (wc_cur != wc_end) return false;
if (text_cur != text_end) return false;
return true;
}
bool check(wchar_t* s, wchar_t* p)
{
wchar_t* rs = 0, * rp=0;
while (1)
if (*p == L'*')
rs = s, rp = ++p;
else if (!*s)
return !*p;
else if (*s == *p || *p == L'?')
++s, ++p;
else if (rs)
s = ++rs, p = rp;
else
return false;
}
bool LikeVB(const wchar_t* s, const wchar_t* p)
{
const wchar_t* rs = 0, * rp = 0;
while (1) {
if (*p == L'[') {
bool b = false, res = false;
if (*(++p) == L'!') { b = true; ++p; }
while (*p != L']') {
if (*p == L'\0') { throw 93; }//если забыли закрывающую скобку//return false;
if (*(p + 1) == L'-' && *(p + 2) != L']')//если есть диапазон ... - ...
{
//if (*(p+2) == L'\0') { return false; }//если забыли закрывающую скобку
if (*s >= *p && *s <= *(p + 2))
{
if (b) { return false; }//если таких символов не должно быть
else { res = true; }//если нашли//break;
}
p += 2;
}
else { //если отдельный символ
if (*s == *p) {
if (b) { return false; }//если таких символов не должно быть
else { res = true; }//если нашли// res=true;
}
++p;
}
}
if (b == res) return false;
++p;//закрывающая скобка
++s;
}
else if (*p == L'*') {
rs = s, rp = ++p;
}
else if (!*s) {
return !*p;
}
else if (*p == L'#') {
if (*s <= L'9' && *s >= L'0') {
++s, ++p;
}
else {
return false; //++p;//or return false????
}
}
else if (*s == *p || *p == L'?') {
++s, ++p;
}
else if (rs) {
s = ++rs, p = rp;
}
else {
return false;
}
}
}
int main()
{
try {
int iMax = 1600000;// 16000000;
std::chrono::steady_clock::time_point timeStart;
std::chrono::steady_clock::time_point timeStop;
std::vector < std::vector<const wchar_t* >> testArr =
{
{L"XYXZZXY", L"*X*X?",L"True"}, //' Speed test
{L"aBBBa", L"a*a",L"True"},
{L"F" , L"[A-Z]" ,L"True"},
{L"F" , L"[!A-Z]",NULL},
{L"a2a" , L"a#a", L"True"},
{L"aM5b" , L"a[L-P]#[!c-e]", L"True"},
{L"BAT123khg" , L"B?T*", L"True"},
{L"CAT123khg" , L"B?T*",NULL},
{L"ab" , L"a*b",L"True"},
{L"a*b" , L"a [*]b", NULL},
{L"axxxxxb" , L"a [*]b",NULL},
{L"a [xyz" , L"a [[]*", L"True"},
{L"aM5b" , L"a*?b", L"True"},
//{L"aM5b" , L"a*[1-4-9][!c-e]", L"True"},
//{L"aM55b" , L"a*[1-4-9][!c-e]", L"True"},
//{L"aM5b" , L"*#[!c-e]", L"True"},
//{L"" , L"[]", L"True"},
//{L"", L"*", L"True"},
//{L"", L"", L"True"},
//{L"*", L"", NULL},
//{L"5*", L"5[*]", L"True"},
//{L"?n", L"[?]n", L"True"},
//{L"a", L"[a-cdf]", L"True"},
//{L"b", L"[a-cdf]", L"True"},
//{L"c", L"[a-cdf]", L"True"},
//{L"d", L"[a-cdf]", L"True"},
//{L"f", L"[a-cdf]", L"True"},
//{L"-", L"[-acdf]", L"True"},
//{L"a", L"[-acdf]", L"True"},
//{L"c", L"[-acdf]", L"True"},
//{L"d", L"[-acdf]", L"True"},
//{L"f", L"[-acdf]", L"True"},
//{L"[", L"[ [ ]", L"True"},
//{L"]", L"]", L"True"},
//{L"abc_d", L"abc[_]d*", L"True"},
//{L"abc_de", L"abc[_]d*", L"True"},
//{L"abcd", L"abc[def]", L"True"},
//{L"abce", L"abc[def]", L"True"},
//{L"abcf", L"abc[def]", L"True"},
//{L"abcdef", L"abc*[de]ef", L"True"},
//{L"abcyef", L"abc[xz]ef", NULL},
//{L"abcxef", L"abc[xz]ef", L"True"},
//{L"abcyef", L"abc[!xz]ef", L"True"},
//{L"abcxef", L"abc[!xz]ef", NULL},
{L"ac5c5b", L"a*[1-56-9][!c-e]", L"True"}
//{L"a [xyz" , L"a [*", NULL} //' Throws Error 93 (invalid pattern string).
};
std::wcout << L"Test pattern...";
std::wcout << L"\n\ncheck...";
for (int i = 0; i < testArr.size(); i++) {
if (check((wchar_t*)testArr[i][0], (wchar_t*)testArr[i][1]) != (bool)testArr[i][2]) {
std::wcout << std::wstring(L"\nERR: string, pattern-> '") + testArr[i][0] + L"', '" + testArr[i][1] + L"'";
}
}
std::wcout << L"\n\nLikeVB...";
for (int i = 0; i < testArr.size(); i++) {
if (LikeVB(testArr[i][0], testArr[i][1]) != (bool)testArr[i][2]) {
std::wcout << std::wstring(L"\nERR: string, pattern-> '") + testArr[i][0] + L"', '" + testArr[i][1] + L"'";
}
}
std::wcout << L"\n\nMatchWildcardAndText...";
for (int i = 0; i < testArr.size(); i++) {
if (MatchWildcardAndText(testArr[i][0], testArr[i][1]) != (bool)testArr[i][2]) {
std::wcout << std::wstring(L"\nERR: string-> ") + testArr[i][0] + L" pattern-> " + testArr[i][1];
}
}
std::wcout << L"\n\nSpeed test...";
timeStart = std::chrono::steady_clock::now();
for (int i = 0; i < iMax; i++) {
check((wchar_t*)testArr[0][0], (wchar_t*)testArr[0][1]);
}
timeStop = std::chrono::steady_clock::now();
std::wcout << L"\n\ncheck, ms: " + std::to_wstring(std::chrono::duration_cast<std::chrono::milliseconds> (timeStop - timeStart).count());
timeStart = std::chrono::steady_clock::now();
for (int i = 0; i < iMax; i++) {
LikeVB(testArr[0][0], testArr[0][1]);
}
timeStop = std::chrono::steady_clock::now();
std::wcout << L"\n\nLikeVB, ms: " + std::to_wstring(std::chrono::duration_cast<std::chrono::milliseconds> (timeStop - timeStart).count());
timeStart = std::chrono::steady_clock::now();
for (int i = 0; i < iMax; i++) {
MatchWildcardAndText(testArr[0][0], testArr[0][1]);
}
timeStop = std::chrono::steady_clock::now();
std::wcout << L"\n\nMatchWildcardAndText, ms: " + std::to_wstring(std::chrono::duration_cast<std::chrono::milliseconds> (timeStop - timeStart).count());
std::wcout << L"\n\n";
system("pause");
return 0;
}
catch (int& e) { system("pause"); return e; }
catch (...) { system("pause"); return -1; }
}
