﻿ Thiago's website

## Pattern matching

Generic algorithms to find patterns similar to regular expressions

Operators:

```(Expression) * OneOrMore :
(Expression) * ZeroOrMore :
(Expression) * Optional :
! (Expression) : Not
(Left)&(Right) : And
(Left)|(Right) : Or
Val(iterator::value_type) : Matches this value
Range(begin, end) : Matches if the value is in the interval begin end
```

Sample

```int main()
{
std::string s = "a 123 b 45.67 c" ;
using namespace PatternMatching;

find_replace(s,
Range('0', '9') * OneOrMore & ('.' & Range('0', '9') * OneOrMore) * Optional,
std::string("NUMBER"));

using namespace PatternMatching;
std::wstring ss = L"121.54";

Result r;
//number :  digit+ ('.' digit+)?
std::wstring::iterator it = Match(ss.begin(), ss.end(),
Range(L'0', L'9') * OneOrMore & (L'.' & Range(L'0', L'9') * OneOrMore) * Optional, r);
if (r)
{
//        std::wcout << *it;
}

std::vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(2);
v.push_back(4);

//while not 2 walk...
std::vector<int>::iterator it2 = Match(v.begin(), v.end(), ! Val(2) * ZeroOrMore, r);
if (it2 != v.begin())
{
std::cout << *it2;
}

std::vector<int>::iterator it3 =  Find(v.begin(), v.end(), (Val(2) | Val(3)) * OneOrMore);

return 0;
}

```

Code

```

// Permission to copy, use, modify, sell and distribute this software
// is granted provided this copyright notice appears in all copies.
// This software is provided "as is" without express or implied
// warranty, and with no claim as to its suitability for any purpose.

namespace PatternMatching
{
enum Result
{
ResultFalse = 0,
ResultTrue,
ResultTrueOptional,
ResultFalseOptional
};

template<class Iterator, class Expression>
Iterator Match(const Iterator& begin,
const Iterator& end,
const Expression& expr,
Result& result)
{
return expr.Match(begin, end, result);
}

//especialization
template<class Iterator>
Iterator Match(const Iterator& begin,
const Iterator& end,
const typename Iterator::value_type& value,
Result& result)
{
result = ResultFalse;
std::cout << "Val" << std::endl;
if (begin == end)
return begin;
result = (*begin == value) ? ResultTrue : ResultFalse;
if (result)
{
return begin;// + 1;
}
return begin;
}

template<class T>
struct ValT
{
T ch;
ValT(const T& c) : ch(c) {}

template<class Iterator>
Iterator Match(const Iterator& begin,
const Iterator& end,
Result& result) const
{
std::cout << "ValT" << std::endl;
result = ResultFalse;
if (begin == end)
return begin;

result = (*begin == ch) ? ResultTrue : ResultFalse;
//if (result)
//{
//  return begin;// + 1;
//}
return begin;
}
};
template <class T>
ValT<T> Val(const T& v)
{
return v;
}

template<class T>
struct RangeT
{
T m_begin;
T m_end;
RangeT(T b, T e) : m_begin(b), m_end(e) {}

template<class Iterator>
Iterator Match(const Iterator& begin,
const Iterator& end,
Result& result) const
{
std::cout << "Range" << std::endl;
result = ResultFalse;
if (begin == end)
return begin;
if ((*begin >= m_begin) && (*begin <= m_end))
result = ResultTrue;
else
result = ResultFalse;
//if (result)
//{
//  return begin ;//+ 1;
//}
return begin;
}
};
template <class T>
RangeT<T> Range(const T& begin, const T& end)
{
return RangeT<T>(begin, end);
}

template<class Expr>
struct NotExpression
{
Expr exp;
NotExpression(const Expr& ll) : exp(ll) {}
template<class Iterator>
Iterator Match(const Iterator& begin,
const Iterator& end,
Result& result) const
{
std::cout << "Not" << std::endl;
if (begin == end)
return begin;
Iterator it = PatternMatching::Match(begin, end, exp, result);
if (result == ResultFalse)
{
result = ResultTrue;
return begin;
}
else
{
result = ResultFalse;
}
return it;
}
};

template<class Expr>
NotExpression<Expr> operator!(const Expr& a)
{
return NotExpression<Expr>(a);
}

enum ZeroOrMoreT {ZeroOrMore};
template <class Expr>
struct ZeroOrMoreExpression
{
Expr exp;
ZeroOrMoreExpression(const Expr& e) : exp(e) {}

template<class Iterator>
Iterator Match(const Iterator& begin,
const Iterator& end,
Result& result) const
{
std::cout << "ZeroOrMore" << std::endl;
result = ResultFalse;
if (begin == end)
return begin;
Iterator it(begin);
result = ResultTrue;
while (result == ResultTrue)
{
Result r;
Iterator it2 = PatternMatching::Match(it, end, exp, r);
if (r == ResultFalse)
break;
it++;//passa p frente
it = it2;
}
return it;
}
};

enum OneOrMoreT {OneOrMore};
template <class Expr>
struct OneOrMoreExpression
{
Expr exp;
OneOrMoreExpression(const Expr& e) : exp(e) {}

template<class Iterator>
Iterator Match(const Iterator& begin,
const Iterator& end,
Result& result) const
{
std::cout << "OneOrMore" << std::endl;

result = ResultFalse;
if (begin == end)
return begin;
Iterator it(begin);

it = PatternMatching::Match(begin, end, exp, result);
if (result == ResultFalse)
return begin;
result = ResultTrue;

Iterator it2 = it;
it2++;//passa p frente

for (;it2 != end;)
{
Result r2;
it2 = PatternMatching::Match(it2, end, exp, r2);
if (r2 == ResultFalse)
break;
result = ResultTrue;
it = it2;
if (it2 == end)
break;
it2++;//passa p frente
}
return it;
}
};

struct OptionalExpressionType {};

enum OptionalT {Optional};
template <class Expr>
struct OptionalExpression : public OptionalExpressionType
{
Expr exp;
OptionalExpression(const Expr& e) : exp(e) {}

template<class Iterator>
Iterator Match(const Iterator& begin,
const Iterator& end,
Result& result) const
{
std::cout << "Optional" << std::endl;
result = ResultFalse;

if (begin == end)
return begin;

Iterator it = PatternMatching::Match(begin, end, exp, result);
if (result == ResultFalse)
result = ResultFalseOptional;
else
result = ResultTrueOptional;

return it;
}
};

template<class left, class right>
struct AndExpression
{
left l;
right r;
AndExpression(const left& ll,
const right& rr) : r(rr), l(ll)
{
}

template<class Iterator>
Iterator Match(const Iterator& begin,
const Iterator& end,
Result& result) const
{
result = ResultFalse;
if (begin == end)
return begin;

std::cout << "And" << std::endl;

Iterator it = PatternMatching::Match(begin, end, l, result);
if (result == ResultFalse)
return begin;

Iterator it2 = it;
it2++; //passar 1 p frente

it2 = PatternMatching::Match(it2, end, r, result);
if (result == ResultFalse)
return begin;

if (result == ResultFalseOptional)
{
result = ResultTrue;
it = it;
}
else if (result == ResultTrueOptional)
{
result = ResultTrue;
it = it2; //commit
}
else
{
it = it2; //commit
}

return it;
}
};
template<class left, class right>
struct OrExpression
{
left l;
right r;
OrExpression(const left& ll,
const right& rr) : r(rr), l(ll)
{
}

template<class Iterator>
Iterator Match(const Iterator& begin,
const Iterator& end,
Result& result) const
{
std::cout << "Or" << std::endl;
Iterator it = PatternMatching::Match(begin, end, l, result);
if (result)
return it;
Iterator it2(it);
it2++;

it2 = PatternMatching::Match(it2, end, r, result);
if (result != ResultFalse)
{
it = it2; //comit
}
return it;
}
};

template<class Iterator>
struct FunctionExpression
{
typedef Iterator(*MatchFunction)(const Iterator& begin,
const Iterator& end,
Result& result);
MatchFunction m_f;

FunctionExpression(MatchFunction f): m_f(f) {}

template<class Iterator>
Iterator Match(const Iterator& begin,
const Iterator& end,
Result& result) const
{
std::cout << "F" << std::endl;
return (*m_f)(begin, end, result);
}
};

template<class Iterator>
FunctionExpression<Iterator> F(Iterator(*f)(const Iterator& begin,
const Iterator& end,
Result& result))
{
return FunctionExpression<Iterator>(f);
}

template<class Expr>
OptionalExpression<Expr> operator *(const Expr& a,  OptionalT)
{
return OptionalExpression<Expr>(a);
}

template<class Expr>
OneOrMoreExpression<Expr> operator *(const Expr& a,  OneOrMoreT)
{
return OneOrMoreExpression<Expr>(a);
}

template<class Expr>
ZeroOrMoreExpression<Expr> operator *(const Expr& a,  ZeroOrMoreT)
{
return ZeroOrMoreExpression<Expr>(a);
}

template<class left, class right>
AndExpression<left, right> operator & (const left& l, const right& r)
{
return AndExpression<left, right>(l, r);
}

template<class left, class right>
OrExpression<left, right> operator | (const left& l, const right& r)
{
return OrExpression<left, right>(l, r);
}
} //namespace PatternMatching

template<class  Exp>
inline void find_replace(std::string& in_this_string,
const Exp& e,
const std::string& replace)
{
using namespace PatternMatching;

std::string::iterator itbegin = in_this_string.begin();

for (; itbegin != in_this_string.end();)
{
Result r;
std::string::iterator it = PatternMatching::Match(itbegin, in_this_string.end(), e, r);
if (r == ResultTrue || r == ResultTrueOptional)
{
size_t pos = itbegin - in_this_string.begin();
in_this_string.replace(itbegin, it + 1, replace);

itbegin = in_this_string.begin() + pos + replace.length();
}
else
{
itbegin++;
}
}
}

template<class Iterator, class  Exp>
inline Iterator Find(const Iterator& begin,
const Iterator& end,
const Exp& e)
{
Iterator itbegin = begin;

for (; itbegin != end; itbegin++)
{
PatternMatching::Result r;
Iterator it = PatternMatching::Match(itbegin, end, e, r);
if (r != PatternMatching::ResultFalse)
{
return it;
}
}
}

```