Здравствуйте, TepMuHyc, Вы писали:
TMH>...запустил нижеприведенную програмку и просто офигел... TMH>Я, конечно ожидал, что инлайновый код быстрый, но чтобы настолько TMH>
Здравствуйте, TepMuHyc, Вы писали:
TMH>...запустил нижеприведенную програмку и просто офигел... TMH>Я, конечно ожидал, что инлайновый код быстрый, но чтобы настолько TMH>
Здравствуйте, TepMuHyc, Вы писали:
TMH>...запустил нижеприведенную програмку и просто офигел... TMH>Я, конечно ожидал, что инлайновый код быстрый, но чтобы настолько TMH>
Что впрочем предсказуемо.
Но, учитывая, что мой код не inline, а статическая либа,
думаю что неплохо
Если компилировать не с /O2 а /O1, то одинаковое время
Но всё равно впечатляет, возьму на заметку
Re[4]: Код: версия 0.00000003 - бенчмарки
От:
Аноним
Дата:
09.12.03 23:49
Оценка:
Здравствуйте, e-Xecutor, Вы писали:
(отвечает TepMuHyc которого задолбал РСДН)
EX>
Здравствуйте, TepMuHyc, Вы писали:
TMH>Здравствуйте, Кодт, Вы писали:
К>>Где-нибудь наверху определи константу -- enum или просто #define. Чтобы потом можно было по-быстрому править... TMH>...это и ежу понятно — писать 0xBAADC0DE 28 раз — можно и мозоли на пальчиках заработать — проще TMH>enum{ stopch = 0xBAADC0DE };
А я наверное заменю на 0xdeadbeef
Правда, Ложь — мне все одно — я имею свое мнение.
Если функция недокументированна — это не значит, что ее не используют все ваши конкуренты в своих продуктах.
Любой строй переходный и отрицать это значит быть закостенелым идиотом.
А>Что есть "skv" и с чем его можно покушать? Иными словами код в студию... А>...А то я к аутпуту могу что хошь приписать... даже отрицательные числа...
skv — это моя библиотечка regexp-ов.
точнее это мои инициалы
Кода там больше ста кил, так что студия треснет, если его в неё внести
Всё не соберусь доку написать да выложить куда-нить...
И попытаемся ответить на вопрос как отделить группы найденные первой альтернативой от групп второй?
Ответ — никак.
Чтобы решить эту проблему, предлагаю придерживаться следуюших правил:
1) Количество найденных групп = количеству select-ов в выражении.
2) Несовпавшая группа обнуляется.
3) star и plus запоминают последнюю найденную группу.
4) для star — пустое совпадение — оба итератора указывают на место этого совпадения.
При этом можно на этапе компиляции подсчитать размер массива, нужного для хранения групп.
А так же несколько оптимизировать вычисления (если известно что групп нет — вызываем версию не работаюшую с группами).
Ниже приводиться исходник, где всё это реализованно.
//http://www.rsdn.ru/Forum/Message.aspx?mid=456007&only=1
//0.00000003#ifndef __STATIC_REGEX_H_INCLUDED__
#define __STATIC_REGEX_H_INCLUDED__
namespace static_regex {
typedef wchar_t rx_char;
struct seqe {};
enum { stpc = 0xBAADC0DE };
template<bool> struct grp_present {};
template<rx_char E>
struct c {/* literal charachter */static bool char_match(rx_char ch)
{ return (E == ch); }
template<class InIt>
static bool match(InIt& it, const InIt& end)
{
bool res = (it != end) && (E == static_cast<rx_char>(*it));
if( res ) ++it;
return res;
}
template<class InIt>
static bool match(InIt& it, const InIt& end, InIt*, int&)
{
return match(it,end);
}
enum {sel_len = 0};
};
template<
int c0, int c1, int c2 =stpc, int c3 =stpc, int c4 =stpc, int c5 =stpc, int c6 =stpc, int c7 =stpc, int c8 =stpc, int c9 =stpc,
int c10=stpc, int c11=stpc, int c12=stpc, int c13=stpc, int c14=stpc, int c15=stpc, int c16=stpc, int c17=stpc, int c18=stpc, int c19=stpc,
int c20=stpc, int c21=stpc, int c22=stpc, int c23=stpc, int c24=stpc, int c25=stpc, int c26=stpc, int c27=stpc, int c28=stpc, int c29=stpc>
struct s {/* literal string - up to 30 symbols */typedef s<
c1, c2, c3, c4, c5, c6, c7, c8, c9, c10,
c11,c12,c13,c14,c15,c16,c17,c18,c19,c20,
c21,c22,c23,c24,c25,c26,c27,c28,c29,stpc
> tail;
enum { length = 1 + tail::length };
template<class InIt>
static bool do_match(InIt& it)
{
return (c0 == static_cast<rx_char>(*it)) && tail::do_match(++it);
}
template<class InIt>
static bool match(InIt& it, const InIt& end)
{
InIt tend( it + length );
if( !(tend < end || tend == end) )
return false;
InIt t(it);
bool res = do_match(it);
if( !res ) it = t;
return res;
}
template<class InIt>
static bool match(InIt& it, const InIt& end, InIt*, int&)
{
return match(it,end);
}
enum {sel_len = 0};
};
template<> struct s<
stpc, stpc, stpc, stpc, stpc, stpc, stpc, stpc, stpc, stpc,
stpc, stpc, stpc, stpc, stpc, stpc, stpc, stpc, stpc, stpc,
stpc, stpc, stpc, stpc, stpc, stpc, stpc, stpc, stpc, stpc>
{
enum { length = 0 };
template<class InIt>
static bool do_match(InIt&)
{ return true; }
};
template<
bool INCLUSIVE,
int c0, int c1, int c2 =stpc, int c3 =stpc, int c4 =stpc, int c5 =stpc, int c6 =stpc, int c7 =stpc, int c8 =stpc, int c9 =stpc,
int c10=stpc, int c11=stpc, int c12=stpc, int c13=stpc, int c14=stpc, int c15=stpc, int c16=stpc, int c17=stpc, int c18=stpc, int c19=stpc,
int c20=stpc, int c21=stpc, int c22=stpc, int c23=stpc, int c24=stpc, int c25=stpc, int c26=stpc, int c27=stpc, int c28=stpc, int c29=stpc>
struct cc_ /* charachter class - like "[abcdEF]" or "[^abcdEF]" */
{
typedef cc_<INCLUSIVE,
c1, c2, c3, c4, c5, c6, c7, c8, c9, c10,
c11,c12,c13,c14,c15,c16,c17,c18,c19,c20,
c21,c22,c23,c24,c25,c26,c27,c28,c29,stpc
> tail;
static bool char_match(rx_char ch)
{ return (c0 == ch) || tail::char_match(ch); }
template<bool> struct sel {};
static bool char_match(rx_char ch, sel<true>)
{ return char_match(ch); }
static bool char_match(rx_char ch, sel<false>)
{ return !char_match(ch); }
template<class InIt>
static bool match(InIt& it, const InIt& end)
{
bool res = (it != end) &&
char_match(static_cast<rx_char>(*it), sel<INCLUSIVE>());
if( res ) ++it;
return res;
}
template<class InIt>
static bool match(InIt& it, const InIt& end, InIt*, int&)
{
return match(it,end);
}
enum {sel_len = 0};
};
template<> struct cc_<true,
stpc, stpc, stpc, stpc, stpc, stpc, stpc, stpc, stpc, stpc,
stpc, stpc, stpc, stpc, stpc, stpc, stpc, stpc, stpc, stpc,
stpc, stpc, stpc, stpc, stpc, stpc, stpc, stpc, stpc, stpc>
{
static bool char_match(rx_char ch)
{ return false; }
};
template<> struct cc_<false,
stpc, stpc, stpc, stpc, stpc, stpc, stpc, stpc, stpc, stpc,
stpc, stpc, stpc, stpc, stpc, stpc, stpc, stpc, stpc, stpc,
stpc, stpc, stpc, stpc, stpc, stpc, stpc, stpc, stpc, stpc>
{
static bool char_match(rx_char ch)
{ return false; }
};
template<
int c0, int c1, int c2 =stpc, int c3 =stpc, int c4 =stpc, int c5 =stpc, int c6 =stpc, int c7 =stpc, int c8 =stpc, int c9 =stpc,
int c10=stpc, int c11=stpc, int c12=stpc, int c13=stpc, int c14=stpc, int c15=stpc, int c16=stpc, int c17=stpc, int c18=stpc, int c19=stpc,
int c20=stpc, int c21=stpc, int c22=stpc, int c23=stpc, int c24=stpc, int c25=stpc, int c26=stpc, int c27=stpc, int c28=stpc, int c29=stpc>
struct cc:cc_<true,c0,c1,c2,c3,c4,c5,c6,c7,c8,c9,c10,c11,c12,c13,c14,c15,c16,c17,c18,c19,c20,c21,c22,c23,c24,c25,c26,c27,c28,c29>
{};
template<
int c0, int c1, int c2 =stpc, int c3 =stpc, int c4 =stpc, int c5 =stpc, int c6 =stpc, int c7 =stpc, int c8 =stpc, int c9 =stpc,
int c10=stpc, int c11=stpc, int c12=stpc, int c13=stpc, int c14=stpc, int c15=stpc, int c16=stpc, int c17=stpc, int c18=stpc, int c19=stpc,
int c20=stpc, int c21=stpc, int c22=stpc, int c23=stpc, int c24=stpc, int c25=stpc, int c26=stpc, int c27=stpc, int c28=stpc, int c29=stpc>
struct not_cc:cc_<false,c0,c1,c2,c3,c4,c5,c6,c7,c8,c9,c10,c11,c12,c13,c14,c15,c16,c17,c18,c19,c20,c21,c22,c23,c24,c25,c26,c27,c28,c29>
{};
template<rx_char F, rx_char B, bool INCLUSIVE=true>
struct range /* charachter range - like "[a-d]" or "[^a-d]" */
{
static bool char_match(rx_char ch)
{
return (((F < B) ? F : B) <= ch) && (ch <= ((F < B) ? B : F));
}
template<bool> struct sel {};
static bool char_match(rx_char ch, sel<true>)
{ return char_match(ch); }
static bool char_match(rx_char ch, sel<false>)
{ return !char_match(ch); }
template<class InIt>
static bool match(InIt& it, const InIt& end)
{
bool res = (it != end) &&
char_match(static_cast<rx_char>(*it), sel<INCLUSIVE>());
if( res ) ++it;
return res;
}
template<class InIt>
static bool match(InIt& it, const InIt& end, InIt*, int&)
{
return match(it,end);
}
enum {sel_len = 0};
};
template<
class CC0, class CC1, class CC2=seqe, class CC3=seqe, class CC4=seqe,
class CC5=seqe, class CC6=seqe, class CC7=seqe, class CC8=seqe, class CC9=seqe>
struct set {/* charachter set */typedef set<CC1,CC2,CC3,CC4,CC5,CC6,CC7,CC8,CC9,seqe> tail;
static bool char_match(rx_char ch)
{
return CC0::char_match(ch) || tail::char_match(ch);
}
template<class InIt>
static bool match(InIt& it, const InIt& end)
{
bool res = (it != end) &&
char_match( static_cast<rx_char>(*it) );
if( res ) ++it;
return res;
}
template<class InIt>
static bool match(InIt& it, const InIt& end, InIt*, int&)
{
return match(it,end);
}
enum {sel_len = 0};
};
template<> struct set<seqe,seqe,seqe,seqe,seqe,seqe,seqe,seqe,seqe,seqe>
{
static bool char_match(rx_char)
{ return false; }
};
template<class RX>
struct star {/* zero or more occurences of RX - like "(abc)*" */template<class InIt>
static bool match(InIt& it, const InIt& end)
{
while( RX::match(it,end) );
return true;
}
template<class InIt>
static bool match(InIt& it, const InIt& end, InIt*, int&, grp_present<false>) {
return match(it, end);
}
template<class InIt>
static bool match(
InIt& it, const InIt& end, InIt* sel, int& nsel, grp_present<true>
) {
InIt _sel2[2*RX::sel_len];
int _nsel = 0, _nsel2 = 0;
while (RX::match(it, end, _sel2, _nsel)) {
for (int i = 0; i < 2*_nsel; ++i)
sel[i] = _sel2[i];
_nsel2 = _nsel;
_nsel = 0;
}
if (_nsel2)
nsel += _nsel2;
return true;
}
template<class InIt>
static bool match(InIt& it, const InIt& end, InIt* sel, int& nsel) {
return match(it,end, sel, nsel, grp_present<(!!sel_len)>());
}
enum {sel_len = RX::sel_len};
};
template<class RX>
struct plus {/* one or more occurences of RX - like "(abc)+" */template<class InIt>
static bool match(InIt& it, const InIt& end)
{
return RX::match(it, end) && star<RX>::match(it, end);
}
template<class InIt>
static bool match(InIt& it, const InIt& end, InIt*, int&, grp_present<false>) {
return match(it, end);
}
template<class InIt>
static bool match(
InIt& it, const InIt& end, InIt* sel, int& nsel, grp_present<true>
) {
int _nsel2 = 0;
InIt _sel2[2*RX::sel_len];
if (!RX::match(it, end, _sel2, _nsel2))
return false;
int _nsel = 0;
star<RX>::match(it, end, sel, _nsel);
if (!_nsel) {
for (int i = 0; i < _nsel2; ++i)
sel[i] = _sel2[i];
_nsel = _nsel2;
}
nsel += _nsel;
return true;
}
template<class InIt>
static bool match(InIt& it, const InIt& end, InIt* sel, int& nsel) {
return match(it, end, sel, nsel, grp_present<(!!sel_len)>());
}
enum {sel_len = RX::sel_len};
};
template<class RX>
struct opt {/* optional occurence of RX - like "(abc)?" */template<class InIt>
static bool match(InIt& it, const InIt& end)
{
RX::match(it, end);
return true;
}
template<class InIt>
static bool match(InIt& it, const InIt& end, InIt* sel, int& nsel)
{
RX::match(it, end, sel, nsel);
return true;
}
enum {sel_len = RX::sel_len};
};
template<
class RX0, class RX1, class RX2=seqe, class RX3=seqe, class RX4=seqe,
class RX5=seqe, class RX6=seqe, class RX7=seqe, class RX8=seqe, class RX9=seqe>
struct seq /* sequence of RX - like "(abc)(def)" */
{
typedef seq<RX1,RX2,RX3,RX4,RX5,RX6,RX7,RX8,RX9,seqe> tail;
template<class InIt>
static bool do_match(InIt& it, const InIt& end)
{
return RX0::match(it,end) && tail::do_match(it,end);
}
template<class InIt>
static bool do_match(InIt& it, const InIt& end, InIt* sel, int& nsel)
{
return RX0::match(it, end, sel, nsel)
&& tail::do_match(it, end, sel + RX0::sel_len, nsel);
}
template<class InIt>
static bool match(InIt& it, const InIt& end)
{
InIt itbk(it);
bool res = do_match(it, end);
if (!res)
it = itbk;
return res;
}
template<class InIt>
static bool match(InIt& it, const InIt& end, InIt* sel, int& nsel)
{
InIt itbk(it);
int nselbk = nsel;
bool res = do_match(it, end, sel, nsel);
if( !res ) {
it = itbk;
nsel = nselbk;
}
return res;
}
enum {sel_len = RX0::sel_len + tail::sel_len};
};
template<> struct seq<seqe,seqe,seqe,seqe,seqe,seqe,seqe,seqe,seqe,seqe>
{
template<class InIt>
static bool do_match(InIt& it, const InIt& end)
{ return true; }
template<class InIt>
static bool do_match(InIt& it, const InIt& end, InIt* sel, int& nsel)
{ return true; }
enum {sel_len = 0};
};
template<
class RX0, class RX1, class RX2=seqe, class RX3=seqe, class RX4=seqe,
class RX5=seqe, class RX6=seqe, class RX7=seqe, class RX8=seqe, class RX9=seqe>
struct alt /* alternative - like "(abc|def)" */
{
typedef alt<RX1,RX2,RX3,RX4,RX5,RX6,RX7,RX8,RX9,seqe> tail;
template<class InIt>
static bool match(InIt& it, const InIt& end)
{
if (RX0::match(it, end))
return true;
else
return tail::match(it, end);
}
template<class InIt>
static bool match(InIt& it, const InIt& end, InIt* sel, int& nsel) {
if (RX0::match(it, end, sel, nsel))
return true;
else
return tail::match(it, end, sel + RX0::sel_len, nsel);
}
enum {sel_len = RX0::sel_len + tail::sel_len};
};
template<> struct alt<seqe,seqe,seqe,seqe,seqe,seqe,seqe,seqe,seqe,seqe>
{
template<class InIt>
static bool match(InIt& it, const InIt& end)
{ return false; }
template<class InIt>
static bool match(InIt& it, const InIt& end, InIt*, int&)
{ return false; }
enum {sel_len = 0};
};
template<class RX>
struct select
{
template<class InIt>
static bool match(InIt& it, const InIt& end)
{
return RX::match(it, end);
}
template<class InIt>
static bool match(InIt& it, const InIt& end, InIt* sel, int& nsel) {
InIt first(it);
int _nsel = 0;
if (RX::match(it, end, sel + 2, _nsel)) {
sel[0] = first;
sel[1] = it;
nsel += 1 + _nsel;
return true;
} else {
sel[0] = sel[1] = InIt();
return false;
}
}
enum {sel_len = 1};
};
//-////////////////////////////////////////////////////////////////////////template<bool INCLUSIVE> struct ws_
:cc<INCLUSIVE, ' ', '\t'>
{};
typedef ws_<true> ws;
typedef ws_<false> not_ws;
template<bool INCLUSIVE> struct digit_
:range<'0','9',INCLUSIVE>
{};
typedef digit_<true> digit;
typedef digit_<false> not_digit;
template<bool INCLUSIVE> struct xdigit_
:set< range<'0','9',INCLUSIVE>, range<'A','F',INCLUSIVE>, range<'a','f',INCLUSIVE> >
{};
typedef digit_<true> xdigit;
typedef digit_<false> not_xdigit;
template<bool INCLUSIVE> struct alpha_
:set< range<'A','Z',INCLUSIVE>, range<'a','z',INCLUSIVE> >
{};
typedef alpha_<true> alpha;
typedef alpha_<false> not_alpha;
template<bool INCLUSIVE> struct alphanum_
:set< alpha_<INCLUSIVE>, digit_<INCLUSIVE> >
{};
typedef alphanum_<true> alphanum;
typedef alphanum_<false> not_alphanum;
struct endl:seq< opt< c<'\r'> >, c<'\n'> > {};
//Shura addedstruct dot {/*any character*/template<class InIt>
static bool match(InIt& it, const InIt& end)
{
bool res = (it != end);
if( res ) ++it;
return res;
}
template<class InIt>
static bool match(InIt& it, const InIt& end, InIt*, int&)
{
return match(it,end);
}
enum {sel_len = 0};
};//dot /*any character*/struct ends {/*end of input sequence*/template<class InIt>
static bool match(InIt& it, const InIt& end)
{
return it == end;
}
template<class InIt>
static bool match(InIt& it, const InIt& end, InIt*, int&)
{
return match(it, end);
}
enum {sel_len = 0};
};//ends /*end of input sequence*/
}//namespace static_regex#endif//__STATIC_REGEX_H_INCLUDED__
1) Может всёж-таки завести структурку для группировки — ато некошерно как-то получается...
К тому же требующийся размер массива можно теперь вычислить.
Не могут быть найдены — т.к. операторы повторения (star, plus, opt) реализованы как "неуступчивые". Т.е. заняв какой-либо символ, они не умеют отдать его назад.
К сожалению проблема не в коде этих операторов, а во взаимодействии их и последующих.
Т.е. эту проблему, предположительно, можно решить подправив код seq::match.
3) Завести перегруженные функции помощники, типа:
//Приверка последовательностиtemplate <class RX, class Iter>
bool test(RX, Iter first, Iter last);
//Приверка последовательности и заполнение группtemplate <class RX, class Iter>
bool match(RX, Iter first, Iter last, RX::groups&);
//Поиск в последовательностиtemplate <class RX, class Iter>
bool search(RX, Iter first, Iter last, RX::groups&);
Можно ещё для string перегрузить...
... << RSDN@Home 1.1.0 stable >>
Re: Предложения по дальнейшей разработке
От:
Аноним
Дата:
29.12.03 13:12
Оценка:
Здравствуйте, Tonal-, Вы писали:
T>Предложения по дальнейшей разработке:
T>1) Может всёж-таки завести структурку для группировки — ато некошерно как-то получается...
Пришел к аналогичному выводу. Скоро выложу.
T>2) Выражение типа "/.*\.cpp/" Не могут быть найдены.
Известная беда всех реализаций регулярных выражений.
Что же касается "нежадных" операторов, то у регулярного выражения есть задача: "найти наидлиннейшее совпадение". Чтобы решить ее с "нежадными" операторами, придется перепробовать все комбинаци их "жадности" — от "совсем нежадный" до "почти жадный". Задачка не для слабонервных. И сложность у нее полиномиальная, а то и (не приведи господь) экспоненциальная.
Так что увольте, "нежадные" операторы не будут реализованы никогда — проще потребовать от программиста
чтобы он писал выражения учитывающие "жадность".
например так:
/.*\.cpp/ <==> /[^.]*\.cpp/
T>3) Завести перегруженные функции помощники, типа:
Никто не мешает. Но это лучше отдать на откуп "прикладному программисту"
T>//Поиск в последовательности T>template <class RX, class Iter> T>bool search(RX, Iter first, Iter last, RX::groups&); T>[/ccode]
Это еще одна задача из разряда "и хочется и колется"..
"brute force" подход всегда открыт, но мне не нравится его сложность: O(length(rx) * length(string))
Думаю как притянуть сюда алгоритм Кнута-Морриса-Пратта, но в данной реализации это скорее всего нереализуемо (точнее, реализуемо, но компилируется ОЧЕНЬ долго)
T>Можно ещё для string перегрузить...
Опять-таки "прикладной программист" напишет этот костыль для себя гораздо лучше чем я для него.
Ура, я тут не один! ;-в
T>>2) Выражение типа "/.*\.cpp/" Не могут быть найдены. А>Известная беда всех реализаций регулярных выражений. А>Что же касается "нежадных" операторов, то у регулярного выражения есть задача: "найти наидлиннейшее совпадение". Чтобы решить ее с "нежадными" операторами, придется перепробовать все комбинаци их "жадности" — от "совсем нежадный" до "почти жадный". Задачка не для слабонервных. И сложность у нее полиномиальная, а то и (не приведи господь) экспоненциальная.
Мне кажется, ты немножко путаешь понятия:
Квалификатор повторения может быть "жадным" и "не жадным".
"Жадные" могут быть "уступчивым" и "неуступчивым".
Так что имеем 3 варианта.
Сейчас у нас "жадный неуступчивый", т.е. система не поддерживает откатов.
Это не даёт написать выражение типа "оканчивается на" в обшем виде. Например нельзя написать выражение для выделения доменов первого уровня в url-е, или для выделения имени файла (ведь "." — допустимый символ). Для обработки подобных выражений придётся прибегать к другой библиотеке, а не хочется.
А насчёт "наидлиннейшего" совпадения — для отыскания оного, надо перебрать все возможные варианты.
Пример
"abcc"
/(a*)(abc+|b)/
Тут "наидлиннейшее" бидет вся сторка по пустой первой группе и первой алтернативе во второй. Её и найдёт ДКА, или POSIX НКА. Ну а обычный НКА или интерпретатор найдёт только "ab".
Так что я предлагаю не очень напрягаться по этому поводу (Perl ведь не напрягаются). Лучше попытаться построить ДКА.
А на счёт нетривиальности задачки — всё это достаточно просто реализовать (код ниже).
Чтобы не слишком тормазило решения такие:
А) Для всех классов определить константу undoable — откатываемость.
А1) Для терминалов (c, cc, s...) — false.
А2) Для повторителей и альтернативы — true.
А3) Для контейнеров — вычисляется по или от содержимого.
Б) В последовательности разбираем разные варианты и пишем код.
В) Создаём класс контейнер noundo — который делает содержащееся в нём выражение неуступчивым (undoable = false).
Для моего бенчмарка эта версия даёт всего лишь 4-5 кратный выигрышь в скорости по сравнению с boost::regex.
Но, если переписать варажение с использованием noundo в разумнвх местах, то опять выигрыш примерно на 1,5-2 порядка!
Выражение вот:
typedef seq<
noundo< select< plus<digit> > >, //код ответа
noundo< select< alt<cc<'-',' '>, endl> > >, //символ переноса - если '-' - то ответ многострочный
select< star<not_cc<'\r','\n'> > >, //текст сообщения - все до конца строки
opt<endl> //необязательный перевод строки
>
rx_ftp2;
T>>3) Завести перегруженные функции помощники, типа: А>Никто не мешает. Но это лучше отдать на откуп "прикладному программисту"
Я всёж таки изобразил 2 перегруженных варианта test. Зачем плодить везде одинаковые куски, если можно их вставить в библиотеку не нарушая единства.
Остальные — подожду структурку для групп. ;-в
T>>//Поиск в последовательности
T>>template <class RX, class Iter>
T>>bool search(RX, Iter first, Iter last, RX::groups&);
T>>
А>Это еще одна задача из разряда "и хочется и колется".. А>"brute force" подход всегда открыт, но мне не нравится его сложность: O(length(rx) * length(string)) А>Думаю как притянуть сюда алгоритм Кнута-Морриса-Пратта, но в данной реализации это скорее всего нереализуемо (точнее, реализуемо, но компилируется ОЧЕНЬ долго)
Тут тоже есть много вариантов для оптимизации... хотя согласен, надо пока обдумать...
Таки код:
//http://www.rsdn.ru/Forum/Message.aspx?mid=456007&only=1
//0.00000003#ifndef __STATIC_REGEX_H_INCLUDED__
#define __STATIC_REGEX_H_INCLUDED__
namespace static_regex {
typedef wchar_t rx_char;
struct seqe {};
enum { stpc = 0xBAADC0DE };
template<bool> struct grp_present {};
template<rx_char E>
struct c {/* literal charachter */static bool char_match(rx_char ch)
{ return (E == ch); }
template<class InIt>
static bool match(InIt& it, const InIt& end)
{
bool res = (it != end) && (E == static_cast<rx_char>(*it));
if( res ) ++it;
return res;
}
template<class InIt>
static bool match(InIt& it, const InIt& end, InIt*, int&)
{
return match(it,end);
}
enum {sel_len = 0};
enum {undoable = 0};
};
template<
int c0, int c1, int c2 =stpc, int c3 =stpc, int c4 =stpc, int c5 =stpc, int c6 =stpc, int c7 =stpc, int c8 =stpc, int c9 =stpc,
int c10=stpc, int c11=stpc, int c12=stpc, int c13=stpc, int c14=stpc, int c15=stpc, int c16=stpc, int c17=stpc, int c18=stpc, int c19=stpc,
int c20=stpc, int c21=stpc, int c22=stpc, int c23=stpc, int c24=stpc, int c25=stpc, int c26=stpc, int c27=stpc, int c28=stpc, int c29=stpc>
struct s {/* literal string - up to 30 symbols */typedef s<
c1, c2, c3, c4, c5, c6, c7, c8, c9, c10,
c11,c12,c13,c14,c15,c16,c17,c18,c19,c20,
c21,c22,c23,c24,c25,c26,c27,c28,c29,stpc
> tail;
enum { length = 1 + tail::length };
template<class InIt>
static bool do_match(InIt& it)
{
return (c0 == static_cast<rx_char>(*it)) && tail::do_match(++it);
}
template<class InIt>
static bool match(InIt& it, const InIt& end)
{
InIt tend( it + length );
if( !(tend < end || tend == end) )
return false;
InIt t(it);
bool res = do_match(it);
if( !res ) it = t;
return res;
}
template<class InIt>
static bool match(InIt& it, const InIt& end, InIt*, int&)
{
return match(it,end);
}
enum {sel_len = 0};
enum {undoable = 0};
};
template<> struct s<
stpc, stpc, stpc, stpc, stpc, stpc, stpc, stpc, stpc, stpc,
stpc, stpc, stpc, stpc, stpc, stpc, stpc, stpc, stpc, stpc,
stpc, stpc, stpc, stpc, stpc, stpc, stpc, stpc, stpc, stpc>
{
enum { length = 0 };
template<class InIt>
static bool do_match(InIt&)
{ return true; }
};
template<
bool INCLUSIVE,
int c0, int c1, int c2 =stpc, int c3 =stpc, int c4 =stpc, int c5 =stpc, int c6 =stpc, int c7 =stpc, int c8 =stpc, int c9 =stpc,
int c10=stpc, int c11=stpc, int c12=stpc, int c13=stpc, int c14=stpc, int c15=stpc, int c16=stpc, int c17=stpc, int c18=stpc, int c19=stpc,
int c20=stpc, int c21=stpc, int c22=stpc, int c23=stpc, int c24=stpc, int c25=stpc, int c26=stpc, int c27=stpc, int c28=stpc, int c29=stpc>
struct cc_ /* charachter class - like "[abcdEF]" or "[^abcdEF]" */
{
typedef cc_<INCLUSIVE,
c1, c2, c3, c4, c5, c6, c7, c8, c9, c10,
c11,c12,c13,c14,c15,c16,c17,c18,c19,c20,
c21,c22,c23,c24,c25,c26,c27,c28,c29,stpc
> tail;
static bool char_match(rx_char ch)
{ return (c0 == ch) || tail::char_match(ch); }
template<bool> struct sel {};
static bool char_match(rx_char ch, sel<true>)
{ return char_match(ch); }
static bool char_match(rx_char ch, sel<false>)
{ return !char_match(ch); }
template<class InIt>
static bool match(InIt& it, const InIt& end)
{
bool res = (it != end) &&
char_match(static_cast<rx_char>(*it), sel<INCLUSIVE>());
if( res ) ++it;
return res;
}
template<class InIt>
static bool match(InIt& it, const InIt& end, InIt*, int&)
{
return match(it,end);
}
enum {sel_len = 0};
enum {undoable = 0};
};
template<> struct cc_<true,
stpc, stpc, stpc, stpc, stpc, stpc, stpc, stpc, stpc, stpc,
stpc, stpc, stpc, stpc, stpc, stpc, stpc, stpc, stpc, stpc,
stpc, stpc, stpc, stpc, stpc, stpc, stpc, stpc, stpc, stpc>
{
static bool char_match(rx_char ch)
{ return false; }
};
template<> struct cc_<false,
stpc, stpc, stpc, stpc, stpc, stpc, stpc, stpc, stpc, stpc,
stpc, stpc, stpc, stpc, stpc, stpc, stpc, stpc, stpc, stpc,
stpc, stpc, stpc, stpc, stpc, stpc, stpc, stpc, stpc, stpc>
{
static bool char_match(rx_char ch)
{ return false; }
};
template<
int c0, int c1, int c2 =stpc, int c3 =stpc, int c4 =stpc, int c5 =stpc, int c6 =stpc, int c7 =stpc, int c8 =stpc, int c9 =stpc,
int c10=stpc, int c11=stpc, int c12=stpc, int c13=stpc, int c14=stpc, int c15=stpc, int c16=stpc, int c17=stpc, int c18=stpc, int c19=stpc,
int c20=stpc, int c21=stpc, int c22=stpc, int c23=stpc, int c24=stpc, int c25=stpc, int c26=stpc, int c27=stpc, int c28=stpc, int c29=stpc>
struct cc:cc_<true,c0,c1,c2,c3,c4,c5,c6,c7,c8,c9,c10,c11,c12,c13,c14,c15,c16,c17,c18,c19,c20,c21,c22,c23,c24,c25,c26,c27,c28,c29>
{};
template<
int c0, int c1, int c2 =stpc, int c3 =stpc, int c4 =stpc, int c5 =stpc, int c6 =stpc, int c7 =stpc, int c8 =stpc, int c9 =stpc,
int c10=stpc, int c11=stpc, int c12=stpc, int c13=stpc, int c14=stpc, int c15=stpc, int c16=stpc, int c17=stpc, int c18=stpc, int c19=stpc,
int c20=stpc, int c21=stpc, int c22=stpc, int c23=stpc, int c24=stpc, int c25=stpc, int c26=stpc, int c27=stpc, int c28=stpc, int c29=stpc>
struct not_cc:cc_<false,c0,c1,c2,c3,c4,c5,c6,c7,c8,c9,c10,c11,c12,c13,c14,c15,c16,c17,c18,c19,c20,c21,c22,c23,c24,c25,c26,c27,c28,c29>
{};
template<rx_char F, rx_char B, bool INCLUSIVE=true>
struct range /* charachter range - like "[a-d]" or "[^a-d]" */
{
static bool char_match(rx_char ch)
{
return (((F < B) ? F : B) <= ch) && (ch <= ((F < B) ? B : F));
}
template<bool> struct sel {};
static bool char_match(rx_char ch, sel<true>)
{ return char_match(ch); }
static bool char_match(rx_char ch, sel<false>)
{ return !char_match(ch); }
template<class InIt>
static bool match(InIt& it, const InIt& end)
{
bool res = (it != end) &&
char_match(static_cast<rx_char>(*it), sel<INCLUSIVE>());
if( res ) ++it;
return res;
}
template<class InIt>
static bool match(InIt& it, const InIt& end, InIt*, int&)
{
return match(it,end);
}
enum {sel_len = 0};
enum {undoable = 0};
};
template<
class CC0, class CC1, class CC2=seqe, class CC3=seqe, class CC4=seqe,
class CC5=seqe, class CC6=seqe, class CC7=seqe, class CC8=seqe, class CC9=seqe>
struct set {/* charachter set */typedef set<CC1,CC2,CC3,CC4,CC5,CC6,CC7,CC8,CC9,seqe> tail;
static bool char_match(rx_char ch)
{
return CC0::char_match(ch) || tail::char_match(ch);
}
template<class InIt>
static bool match(InIt& it, const InIt& end)
{
bool res = (it != end) &&
char_match( static_cast<rx_char>(*it) );
if( res ) ++it;
return res;
}
template<class InIt>
static bool match(InIt& it, const InIt& end, InIt*, int&)
{
return match(it,end);
}
enum {sel_len = 0};
enum {undoable = 0};
};
template<> struct set<seqe,seqe,seqe,seqe,seqe,seqe,seqe,seqe,seqe,seqe>
{
static bool char_match(rx_char)
{ return false; }
};
template<class RX>
struct star {/* zero or more occurences of RX - like "(abc)*" */template<class InIt>
static bool match(InIt& it, const InIt& end)
{
while( RX::match(it,end) );
return true;
}
template<class InIt>
static bool match(InIt& it, const InIt& end, InIt*, int&, grp_present<false>) {
return match(it, end);
}
template<class InIt>
static bool match(
InIt& it, const InIt& end, InIt* sel, int& nsel, grp_present<true>
) {
InIt _sel2[2*RX::sel_len];
int _nsel = 0, _nsel2 = 0;
while (RX::match(it, end, _sel2, _nsel)) {
for (int i = 0; i < 2*_nsel; ++i)
sel[i] = _sel2[i];
_nsel2 = _nsel;
_nsel = 0;
}
if (_nsel2)
nsel += _nsel2;
return true;
}
template<class InIt>
static bool match(InIt& it, const InIt& end, InIt* sel, int& nsel) {
return match(it, end, sel, nsel, grp_present<(!!sel_len)>());
}
enum {sel_len = RX::sel_len};
enum {undoable = 1};
};
template<class RX>
struct plus {/* one or more occurences of RX - like "(abc)+" */template<class InIt>
static bool match(InIt& it, const InIt& end)
{
return RX::match(it, end) && star<RX>::match(it, end);
}
template<class InIt>
static bool match(InIt& it, const InIt& end, InIt*, int&, grp_present<false>) {
return match(it, end);
}
template<class InIt>
static bool match(
InIt& it, const InIt& end, InIt* sel, int& nsel, grp_present<true>
) {
int _nsel2 = 0;
InIt _sel2[2*RX::sel_len];
if (!RX::match(it, end, _sel2, _nsel2))
return false;
int _nsel = 0;
star<RX>::match(it, end, sel, _nsel);
if (!_nsel) {
for (int i = 0; i < _nsel2; ++i)
sel[i] = _sel2[i];
_nsel = _nsel2;
}
nsel += _nsel;
return true;
}
template<class InIt>
static bool match(InIt& it, const InIt& end, InIt* sel, int& nsel) {
return match(it, end, sel, nsel, grp_present<(!!sel_len)>());
}
enum {sel_len = RX::sel_len};
enum {undoable = 1};
};
template<class RX>
struct opt {/* optional occurence of RX - like "(abc)?" */template<class InIt>
static bool match(InIt& it, const InIt& end)
{
RX::match(it, end);
return true;
}
template<class InIt>
static bool match(InIt& it, const InIt& end, InIt* sel, int& nsel)
{
RX::match(it, end, sel, nsel);
return true;
}
enum {sel_len = RX::sel_len};
enum {undoable = 1};
};
template<
class RX0, class RX1, class RX2=seqe, class RX3=seqe, class RX4=seqe,
class RX5=seqe, class RX6=seqe, class RX7=seqe, class RX8=seqe, class RX9=seqe>
struct seq /* sequence of RX - like "(abc)(def)" */
{
typedef seq<RX1,RX2,RX3,RX4,RX5,RX6,RX7,RX8,RX9,seqe> tail;
template <bool> struct simple{};
template<class InIt>
static bool do_match(InIt& it, const InIt& end, simple<true>) {
return RX0::match(it, end) && tail::do_match(it, end);
}
template<class InIt>
static bool do_match(InIt& it, const InIt& end, simple<false>) {
for (InIt _end = end; it != _end; --_end) {
InIt _it = it;
if (!RX0::match(_it, _end))
return false;
if (tail::do_match(_it, end)) {
it = _it;
return true;
}
}
return false;
}
template<class InIt>
static bool do_match(InIt& it, const InIt& end) {
return do_match(
it, end, simple<(!RX0::undoable || tail::end_seq)>()
);
}
template<class InIt>
static bool do_match(
InIt& it, const InIt& end, InIt* sel, int& nsel, simple<true>
) {
return RX0::match(it, end, sel, nsel)
&& tail::do_match(it, end, sel + 2*RX0::sel_len, nsel);
}
template<class InIt>
static bool do_match(
InIt& it, const InIt& end, InIt* sel, int& nsel, grp_present<false>
) {
for (InIt _end = end; it != _end; --_end) {
InIt _it(it);
if (!RX0::match(_it, _end))
return false;
if (tail::do_match(_it, end, sel, nsel)) {
it = _it;
return true;
}
}
return false;
}
template<class InIt>
static bool do_match(
InIt& it, const InIt& end, InIt* sel, int& nsel, grp_present<true>
) {
for (InIt _end = end; it != _end; --_end) {
InIt _it(it);
InIt _sel[RX0::sel_len + 1];
int _nsel = 0;
if (!RX0::match(_it, _end, _sel, _nsel))
return false;
if (tail::do_match(_it, end, sel + 2*RX0::sel_len, nsel)) {
for (int i = 0; i < 2*_nsel; ++i)
sel[i] = _sel[i];
nsel += _nsel;
it = _it;
return true;
}
}
return false;
}
template<class InIt>
static bool do_match(
InIt& it, const InIt& end, InIt* sel, int& nsel, simple<false>
) {
return do_match(it, end, sel, nsel, grp_present<(!!RX0::sel_len)>());
}
template<class InIt>
static bool do_match(InIt& it, const InIt& end, InIt* sel, int& nsel) {
return do_match(
it, end, sel, nsel, simple<(!RX0::undoable || tail::end_seq)>()
);
}
template<class InIt>
static bool match(InIt& it, const InIt& end) {
InIt itbk(it);
bool res = do_match(it, end);
if (!res)
it = itbk;
return res;
}
template<class InIt>
static bool match(InIt& it, const InIt& end, InIt* sel, int& nsel) {
InIt itbk(it);
int nselbk = nsel;
bool res = do_match(it, end, sel, nsel);
if( !res ) {
it = itbk;
nsel = nselbk;
}
return res;
}
enum {sel_len = RX0::sel_len + tail::sel_len};
enum {undoable = RX0::undoable || tail::undoable};
enum {end_seq = 0};
};
template<> struct seq<seqe,seqe,seqe,seqe,seqe,seqe,seqe,seqe,seqe,seqe>
{
template<class InIt>
static bool do_match(InIt&, const InIt&)
{ return true; }
template<class InIt>
static bool do_match(InIt& it, const InIt& end, InIt* sel, int& nsel)
{ return true; }
enum {sel_len = 0};
enum {undoable = 0};
enum {end_seq = 1};
};
template<
class RX0, class RX1, class RX2=seqe, class RX3=seqe, class RX4=seqe,
class RX5=seqe, class RX6=seqe, class RX7=seqe, class RX8=seqe, class RX9=seqe>
struct alt /* alternative - like "(abc|def)" */
{
typedef alt<RX1,RX2,RX3,RX4,RX5,RX6,RX7,RX8,RX9,seqe> tail;
template<class InIt>
static bool match(InIt& it, const InIt& end)
{
if (RX0::match(it, end))
return true;
else
return tail::match(it, end);
}
template<class InIt>
static bool match(InIt& it, const InIt& end, InIt* sel, int& nsel) {
if (RX0::match(it, end, sel, nsel))
return true;
else
return tail::match(it, end, sel + 2*RX0::sel_len, nsel);
}
enum {sel_len = RX0::sel_len + tail::sel_len};
enum {undoable = 1};
};
template<> struct alt<seqe,seqe,seqe,seqe,seqe,seqe,seqe,seqe,seqe,seqe>
{
template<class InIt>
static bool match(InIt& it, const InIt& end)
{ return false; }
template<class InIt>
static bool match(InIt& it, const InIt& end, InIt*, int&)
{ return false; }
enum {sel_len = 0};
enum {undoable = 0};
};
template<class RX>
struct select
{
template<class InIt>
static bool match(InIt& it, const InIt& end)
{
return RX::match(it, end);
}
template<class InIt>
static bool match(InIt& it, const InIt& end, InIt* sel, int& nsel) {
InIt first(it);
int _nsel = 0;
if (RX::match(it, end, sel + 2, _nsel)) {
sel[0] = first;
sel[1] = it;
nsel += 1 + _nsel;
return true;
} else {
sel[0] = sel[1] = InIt();
return false;
}
}
enum {sel_len = 1};
enum {undoable = RX::undoable};
};
//-////////////////////////////////////////////////////////////////////////template<bool INCLUSIVE> struct ws_
:cc<INCLUSIVE, ' ', '\t'>
{};
typedef ws_<true> ws;
typedef ws_<false> not_ws;
template<bool INCLUSIVE> struct digit_
:range<'0','9',INCLUSIVE>
{};
typedef digit_<true> digit;
typedef digit_<false> not_digit;
template<bool INCLUSIVE> struct xdigit_
:set< range<'0','9',INCLUSIVE>, range<'A','F',INCLUSIVE>, range<'a','f',INCLUSIVE> >
{};
typedef digit_<true> xdigit;
typedef digit_<false> not_xdigit;
template<bool INCLUSIVE> struct alpha_
:set< range<'A','Z',INCLUSIVE>, range<'a','z',INCLUSIVE> >
{};
typedef alpha_<true> alpha;
typedef alpha_<false> not_alpha;
template<bool INCLUSIVE> struct alphanum_
:set< alpha_<INCLUSIVE>, digit_<INCLUSIVE> >
{};
typedef alphanum_<true> alphanum;
typedef alphanum_<false> not_alphanum;
struct endl:seq< opt< c<'\r'> >, c<'\n'> > {};
//Shura addedstruct dot {/*any character*/template<class InIt>
static bool match(InIt& it, const InIt& end)
{
bool res = (it != end);
if( res ) ++it;
return res;
}
template<class InIt>
static bool match(InIt& it, const InIt& end, InIt*, int&)
{
return match(it,end);
}
enum {sel_len = 0};
enum {undoable = 0};
};//dot /*any character*/struct ends {/*end of input sequence*/template<class InIt>
static bool match(InIt& it, const InIt& end)
{
return it == end;
}
template<class InIt>
static bool match(InIt& it, const InIt& end, InIt*, int&)
{
return match(it, end);
}
enum {sel_len = 0};
enum {undoable = 0};
};//ends /*end of input sequence*/template <class RX>
struct noundo {/*modifer for non undoable repeats*/template<class InIt>
static bool match(InIt& it, const InIt& end)
{
return RX::match(it, end);
}
template<class InIt>
static bool match(InIt& it, const InIt& end, InIt* sel, int& nsel)
{
return RX::match(it, end, sel, nsel);
}
enum {sel_len = RX::sel_len};
enum {undoable = 0};
};//noundo
//Приверка последовательностиtemplate <class RX, class Iter>
bool test(RX, Iter first, Iter last) {
return RX::match(first, last) && first == last;
}
template <class RX, class String>
bool test(RX, const String& str) {
typename str::const_iterator first = str.begin();
return RX::match(first, str.end()) && first == str.end();
}
}//namespace static_regex#endif//__STATIC_REGEX_H_INCLUDED__
-убраны операторы начинающиеся с "not_" — вместо них используйте "name_<false", где "name" — имя оператора. Например not_cc<A,B,C> == cc_<false,A,B,C>
-добавлены многоаргументные версии для всех нетерминальных операторов (т.е. star, plus, opt, и тд) — их имена также заканчиваются на "_"
-у оператора захвата подсовпадения mark<int ID, class RX> появился параметр ID — это произвольный числовой идентификатор подсовпадения.
-Нельзя пользоваться member-функцией RX::match() — она стала насколько мохнатой, что пришлось ввести глобальные функции match().
Их надо использовать так:
-Теперь библиотека использeт контейнеры для хранения подсовпадений. Доступно 2 вида контейнеров:
-- match_array<class InIt,int N> — контейнер основанный на статическом массиве размера N. Если подсовпадений больше чем размер контейнера, то "лишние" подсовпадения игнорируются.
-- match_array<class InIt> — контейнер основанный на std::vector<>.
-- более подробно, смотрите эти классы и класс submatch в исходниках.
Пример использования:
-Добавлен оператор "обратной ссылки" bk<int ID>
Пример использования (псевдокод)
typedef seq<mark<1,cc<'\'','"'>>, s<"HELLO">, bk<1>> myrx;
//myrx совпадет со строкой "HELLO" и со строкой 'HELLO'
-к ранее имевшимся "тупым" операторам-повторителям star<>, plus<>, rep<> добавлены следующие их модификации:
-- "нежадные": xstar<>, xplus<>, xrep<>
Пример использования (псевдокод)
typedef seq<mark<1,plus<dot>>, mark<2,s<".cpp">>> myrx1;
typedef seq<mark<1,xplus<dot>>, mark<2,s<".cpp">>> myrx2;
//myrx2 совпадет со строкой "file1.cpp", а myrx1 - нет,
//т.к. оператор plus<dot> сьест все до конца строки.
-- "жадные": xxstar<>, xxplus<>, xxrep<>
Пример использования (псевдокод)
typedef seq<mark<1,xxplus<dot>>, mark<2,s<".cpp">>> myrx3;
//при проверке строки "file1.cpp.cpp.cpp.cpp"
//myrx2 совпадет с подстрокой "file1.cpp", а myrx3 - с полной строкой,
Внимание: использование этих модификаций влечет за собой значительное падение производительности. "нежадных" — примерно в 2 раза, "жадных" — в десятки раз.
-Бенчмарки
Не улучшились, но и не ухудшились.
Был также проведен тест на производительность "жадных" операторов.
выражение "(.+)(\.cpp)" проверялось на строке "file.cpp.cpp.cpp.cpp" длиной 4 мегабайта. boost::regex оказалась хуже в 10 раз...
Наверное надо включить #include <vector> если есть элементы зависимые от std::vector.
Не совсем понятно назначение функций get_match_at и set_match_count. Почму нельзя просто воспользоваться методами operator[]() и resize(). Тогда не понадобятся friend объявления, которые во первых не совсем тривиальны для шаблонов, а во вторых разные компиляторы их по разному трактуют (Borland например требует полной спецификации шаблонных параметров.)
По моему operator[]() для match_vector и для match_array несколько расходятся. Если уж проверять выход за граници, то для обоих, или уж не проверять совсем. А так как-то не согласованно получается.
Я бы не проверял (по крайний мере в релизе).
Начитался давеча Саттера — он говорит что не следует применять наследование без вестких на то причин — это я о match_vector. Собственно если переименовать функцию reset() в clear() то вместо match_vector можно будет использовать и std::vector, и std::deque и boost::array. В общем непонятна суть ограничений.
Есть некоторый недостаток в ID к mark-у: непонятно как избежать совподения. Оно может случиться не только из за ошибок набивки, но и в случаи собирания выражения из разных частей. ;-с
По моему было бы очень удобно, если для любого вырожения можно было бы получить максимальное количество подсовпадений. Реализация — тривиальна: для символьных классов = 0, для mark = подвырожение + 1, для контейнеров = сумма подвырожений.
Может быть следует предоставить 2 формы alt — полный перебор (POSIX-like), или до первого совпадения (Perl-like) — некоторые выражения можно соптимизировать.
