#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <optional>
#include <cassert>
#include <future>
struct WildCardParser
{
//? Любой отдельный символ
//* Ноль или более символов
//# Любая однозначная цифра (0-9)
//[charlist] Любой отдельный символ в charlist
//[!charlist] Любой отдельный символ, отсутствующий в charlist
//To match the special characters left bracket ([), question mark (?), number sign (#)
//and asterisk (*), enclose them in brackets. The right bracket (])
//can't be used within a group to match itself, but it can be used outside a group as an individual character.
constexpr static bool ShowDebugOutput = !true;
constexpr static std::wstring_view DebugPrefix = L" dbg: ";
constexpr static wchar_t WCHAR_exclamation{ L'!' };
constexpr static wchar_t WCHAR_openbrace{ L'[' };
constexpr static wchar_t WCHAR_closebrace{ L']' };
constexpr static wchar_t WCHAR_hyphen{ L'-' };
constexpr static wchar_t WCHAR_numbersign{ L'#' };
constexpr static wchar_t WCHAR_asterisk{ L'*' };
constexpr static wchar_t WCHAR_question{ L'?' };
constexpr static wchar_t WCHAR_zero{ L'0' };
constexpr static wchar_t WCHAR_nine{ L'9' };
//информация о пропарсенных квадратных скобках
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 IsSetEmpty()const noexcept
{
return m_CharsList.empty();
}
bool TestChar(const wchar_t 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 (ShowDebugOutput)std::wcout << DebugPrefix << L"m_lastParsedText reused\n";
return true;
}
}
}
const auto res = Parse__(text);
if (res)
{
//запоминаем последний парсённый текст
m_lastParsedText = text;
//if constexpr(ShowDebugOutput)std::wcout<<DebugPrefix<<L"m_lastParsedText saved\n";
assert(m_lastParsedText);
assert(!m_lastParsedText->empty());
assert(m_lastParsedText->size() > m_ClosingBracketPos);
assert((*m_lastParsedText)[m_ClosingBracketPos] == WCHAR_closebrace);
}
else
{
//поскольку состояние могло меняться, забываем последний текст
m_lastParsedText.reset();
if constexpr (ShowDebugOutput)std::wcout << DebugPrefix << L"m_lastParsedText reset\n";
}
return res;
}
size_t PosOfClosingBracket()const noexcept
{
return m_ClosingBracketPos;
}
private:
//заполнение списка символов из квадратных скобок
//text - начинается с первого символа после открывающей скобки
bool Parse__(std::wstring_view text)
{
//тут не производится оптимизация по удалению повторов [ababa].
//Предполагается, что юзер сам себе не враг, а если добавлять алгоритм
//удаления повторов - это будет постоянная дополнительная нагрузка
if (text.empty())return false;
m_CharsList.clear();
m_ClosingBracketPos = {};
m_Inverted = {};
//справа ограничиваемся по закрывающей скобке
{
const auto pos = text.find_first_of(WCHAR_closebrace);
if (pos == text.npos)return false;
text = text.substr(0, pos);
m_ClosingBracketPos = pos;
}
//флаг инверсии
if (!text.empty() && text.front() == WCHAR_exclamation)
{
//проверка на одинокий восклицательный знак
if (text.size() == 1)
{
m_CharsList.push_back(WCHAR_exclamation);
return true;
}
m_Inverted = true;
text.remove_prefix(1);
}
//сейчас text такой:
//begin,front - первый символ после открывающей скобки или инвертирующего знака
//back - символ перед закрывающей скобкой
//end - закрывающая скобка
auto text_cur = text.cbegin();
auto const text_end = text.cend();
while (text_cur != text_end)
{
//text_cur - текущий символ
//если следующий символ это минус,
if (const auto hyphen = text_cur + 1; hyphen != text_end && *hyphen == WCHAR_hyphen)
{
//то после минуса тоже должен быть какой-то символ
if (const auto second = hyphen + 1; second != text_end)
{
//обработка X-Z, сейчас находимся на X
auto c1 = *text_cur;
auto c2 = *second;
if (c1 > c2)std::swap(c1, c2);
for (auto c = c1; c <= c2; ++c)m_CharsList.push_back(c);
//идём дальше
//обрабатываем ситуацию с трамваем a-b-c
//если после second лежит минус
const auto next_after_second = second + 1;
if (next_after_second != text_end && *next_after_second == WCHAR_hyphen)
{
text_cur = second;
}
else
{
text_cur = second + 1;
}
continue;
}
}
//один символ кладём в список
m_CharsList.push_back(*text_cur);
text_cur++;
}
return true;
}
};
static bool Match(const std::wstring_view text, const std::wstring_view wc)
{
//информация о пропарсенных квадратных скобках
s_SquareBracketsInfo SBInfo;
return Match_recursed(text, wc, SBInfo);
}
private:
static bool Match_recursed(const std::wstring_view text, const std::wstring_view wc, s_SquareBracketsInfo& SBInfo)
{
auto wc_cur = wc.cbegin();
auto const wc_end = wc.cend();
auto text_cur = text.cbegin();
auto const text_end = text.cend();
while (wc_cur != wc_end)
{
if (text_cur == text_end)
{
//завершающие звёздочки игнорируем
if (*wc_cur == WCHAR_asterisk)
{
++wc_cur;
continue;
}
//завершающие пустые квадратные скобки игнорируем
if (*wc_cur == WCHAR_openbrace && (wc_cur + 1) != wc_end && *(wc_cur + 1) == WCHAR_closebrace)
{
wc_cur += 2;
continue;
}
return false;
}
switch (*wc_cur)
{
default:
{
//любой другой символ - должен совпасть с текстовым
if (*wc_cur == *text_cur)
{
++wc_cur;
++text_cur;
}
else
{
return false;
}
}break;
case WCHAR_question:
{
++wc_cur;
++text_cur;
}break;
case WCHAR_numbersign:
{
if (WCHAR_zero <= *text_cur && *text_cur <= WCHAR_nine)
{
++wc_cur;
++text_cur;
}
else
{
return false;
}
}break;
case WCHAR_openbrace:
{
const auto wc_next = wc_cur + 1;
if (!SBInfo.Parse({ &*wc_next, size_t(wc_end - wc_next) }))
{
//ошибка парсинга квадратных скобок
return false;
}
if (SBInfo.IsSetEmpty())
{
//[]
wc_cur = wc_next + SBInfo.PosOfClosingBracket() + 1;
}
else if (SBInfo.TestChar(*text_cur))
{
//символ строки есть в списке
wc_cur = wc_next + SBInfo.PosOfClosingBracket() + 1;
++text_cur;
}
else
{
return false;
}
}break;
case WCHAR_asterisk:
{
const auto wc_next = wc_cur + 1;
if (wc_next == wc_end)
{
//следующего символа в маске нет, поэтому всё остальное - матчится
return true;
}
//нужно выяснить, сколько символов возьмёт звёздочка из последующей строки.
//Используем для этого рекурсию
auto text_lef = text_end;
while (1)
{
//предполагаем, что звёздочка забирает [text_lef...text_end).
//Тогда эта часть строки должна сматчится с оставшейся частью маски
if (Match_recursed({ &*text_lef, size_t(text_end - text_lef) }, { &*wc_next, size_t(wc_end - wc_next) }, SBInfo))
{
return true;
}
if (text_lef == text_cur)
{
return false;
}
text_lef--;
}
}break;
}
}
//строка и маска должны быть дочитаны полностью
return wc_cur == wc_end && text_cur == text_end;
}
};
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;
//https://ru.stackoverflow.com/questions/483723/%d0%9a%d0%b0%d0%ba-%d0%bf%d1%80%d0%be%d0%b2%d0%b5%d1%80%d0%b8%d1%82%d1%8c-%d1%81%d0%be%d0%be%d1%82%d0%b2%d0%b5%d1%82%d1%81%d1%82%d0%b2%d0%b8%d0%b5-%d0%b8%d0%bc%d0%b5%d0%bd%d0%b8-%d1%84%d0%b0%d0%b9%d0%bb%d0%b0-%d0%bc%d0%b0%d1%81%d0%ba%d0%b5/483724#483724
}
bool LikeVB(const wchar_t* s, const wchar_t* p)
{
const wchar_t* rs = 0, * rp = 0;
bool res = 0;//result [...]
while (1) {
if (*p == L'[') {
if (*(p + 1) == L']') { p += 2; continue; }// ""=="[]"
bool b = false, match = false;
const wchar_t* pt = p; //p_temp
if (*(++pt) == L'!' && *(pt + 1) != L']') { b = true; ++pt; }//[!...] not [!]
while (*pt != L']') {
if (*pt == L'\0') { throw 93; }//если забыли закрывающую скобку//' Throws Error 93 (invalid pattern string).
if (*(pt + 1) == L'-' && *(pt + 2) != L']')//если есть диапазон ... - ...
{
if (*s >= *pt && *s <= *(pt + 2))
{
if (b) {
res = false; break;
}//если таких символов не должно быть
else {
match = true;
}//если нашли
}
pt += 2; //for [1-4-9]
}
else { //если отдельный символ
if (*s == *pt) {
if (b) {
res = false; break;
}//если таких символов не должно быть
else {
match = true;
}//если нашли
}
++pt;
}
}
if (b == match) {
res = false;
}
else {
res = true;
++s; p = ++pt;//закрывающая скобка
}
}
if (res) {
res = false;
}
else if (*p == L'#' && *s <= L'9' && *s >= L'0') {
++s, ++p;
}
else if (*p == L'*') {
rs = s, rp = ++p;
}
else if (!*s) {
return !*p;
}
else if (*p == L'?' || *s == *p && *p != L'[' && *p != L'#') {
++s, ++p;
}
else if (rs) {
s = ++rs, p = rp;
}
else {
return false;
}
}
}
int main()
{
try {
int iMax = 16000000;// 16000000;
std::chrono::steady_clock::time_point timeStart;
std::chrono::steady_clock::time_point timeStop;
std::vector < std::vector<const wchar_t* >> testArr =
{
{L"XYXZZXYXYXZZXY", L"*X*X?*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"aM55b" , L"a*[1-45-9][!c-e]", L"True"},
{L"aM5b" , L"*#[!c-e]", L"True"},
{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"", L"", L"True"},
{L"", L"*", L"True"},
{L"", L"[]", L"True"},
{L"", L"[!]", NULL},
{L"", L"[]*", L"True"},
{L"", L"[!]*", NULL},
{L"1", L"[!]*", NULL},
{L"1", L"[]*", L"True"},
{L"1", L"[!]*", NULL},
{L"1", L"[!]", NULL},
{L"1", L"*[!]", NULL},
{L"1", L"*[]", L"True"},
{L"1", L"#[]", L"True"},
{L"1", L"#[!]", NULL},
{L"12", L"#[!]", NULL},
{L"12", L"#[!]*", NULL},
{L"123", L"*[!]*", NULL},
{L"1!3", L"*[!]*", L"True"},
{L"!", L"*[!]*", L"True"},
{L"!", L"[!]", L"True"},
{L"!a", L"*[!a]*", L"True"},
{L"!a", L"[!a]*", L"True"},
{L"!a", L"*[!a]", NULL},
{L"!a", L"[!a]", NULL},
{L"a", L"[!a]", NULL},
{L"b", L"[!a]", L"True"},
{L"2", L"#[]", L"True"},
{L"*", L"[*]", L"True"},
{L"1", L"[*]", NULL},
{L"!", L"[!-!]", NULL},
{L"1", L"[!-!]", L"True"},
{L"!", L"[-!]", L"True"},
{L"!", L"[!-]", L"True"},
{L"-", L"[!-]", NULL},
{L"-", L"[-]", L"True"},
{L"***", L"*[*]*", L"True"},
{L"???", L"?[?]?", L"True"},
{L"###", L"#[#]#", NULL},
{L"[[[[[", L"[[]?*[[]", L"True"},
//{L"a [xyz" , L"a [*", NULL} //' Throws Error 93 (invalid pattern string).
};
std::wcout << L"Test pattern...";
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"'" + L"', ";
std::wcout << (bool)testArr[i][2];
}
}
std::wcout << L"\n\nWildCardParser::Match...";
for (int i = 0; i < testArr.size(); i++) {
if (WildCardParser::Match(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"'" + L"', ";
std::wcout << (bool)testArr[i][2];
}
}
bool result = 0;
std::wcout << L"\n\nSpeed test...";
timeStart = std::chrono::steady_clock::now();
for (int i = 0; i < iMax; i++) {
result = 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()) + L"\n";
std::wcout << result;
timeStart = std::chrono::steady_clock::now();
for (int i = 0; i < iMax; i++) {
result = 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()) + L"\n";
std::wcout << result;
timeStart = std::chrono::steady_clock::now();
for (int i = 0; i < iMax; i++) {
result = WildCardParser::Match(testArr[0][0], testArr[0][1]);
}
timeStop = std::chrono::steady_clock::now();
std::wcout << L"\n\nWildCardParser::Match, ms: " + std::to_wstring(std::chrono::duration_cast<std::chrono::milliseconds> (timeStop - timeStart).count()) + L"\n";
std::wcout << result;
std::wcout << L"\n\n";
system("pause");
return 0;
}
catch (int& e) { system("pause"); return e; }
catch (...) { system("pause"); return -1; }
}
