// What:  Lightweight, regular-expression matching expressed in STL form
// How:   Refactored from C code that worked on null-terminated char arrays,
//        by Kernighan and Pike in the Practice of Programming
// Where: Published in Application Development Advisor, "The Next Best String"
// When:  October 2002 (updated February 2006)
// Who:   Kevlin Henney

#ifndef REGEX_LITE_INCLUDED
#define REGEX_LITE_INCLUDED

// published regex-matching interface

template<typename text_iterator, typename regex_iterator>
bool regex_match(
    text_iterator text_begin, text_iterator text_end,
    regex_iterator regex_begin, regex_iterator regex_end);

template<typename text_iterator, typename regex_char>
bool regex_match(
    text_iterator text_begin, text_iterator text_end,
    const regex_char *regex);

// utility class that defines regex-matching functionality

class regex
{
public:
    template<typename text_iterator, typename regex_iterator>
    static bool match(
        text_iterator text_begin, text_iterator text_end,
        regex_iterator regex_begin, regex_iterator regex_end)
    {
        if(regex_begin != regex_end && *regex_begin == '^')
            return match_here(text_begin, text_end,
                              ++regex_begin, regex_end);
        for(;;)
        {
            if(match_here(text_begin, text_end,
                          regex_begin, regex_end))
                return true;
            if(text_begin != text_end)
                ++text_begin;
            else
                return false;
        }
    }
private:
    template<typename text_iterator, typename regex_iterator>
    static bool match_here(
        text_iterator text_begin, text_iterator text_end,
        regex_iterator regex_begin, regex_iterator regex_end)
    {
        if(regex_begin == regex_end)
            return true;
        regex_iterator regex_next = regex_begin;
        if(++regex_next != regex_end && *regex_next == '*')
            return match_many(text_begin, text_end,
                              ++regex_next, regex_end,
                              *regex_begin);
        if(*regex_begin == '$' && regex_next == regex_end)
            return text_begin == text_end;
        if(text_begin != text_end &&
           (*regex_begin == '.' ||
            *regex_begin == *text_begin))
            return match_here(++text_begin, text_end,
                              regex_next, regex_end);
        return false;
    }

    template<
        typename text_iterator, typename regex_iterator,
        typename value_type>
    static bool match_many(
        text_iterator text_begin, text_iterator text_end,
        regex_iterator regex_begin, regex_iterator regex_end,
        const value_type &value)
    {
        do
        {
            if(match_here(text_begin, text_end,
                          regex_begin, regex_end))
                return true;
        }
        while(text_begin != text_end &&
              (*text_begin++ == value || value == '.'));
        return false;
    }
};

// implementation of published regex-matching function templates

template<typename input_iterator, typename value_type>
input_iterator unguarded_find(
    input_iterator begin, const value_type &value)
{
    while(*begin != value)
        ++begin;
    return begin;
}

template<typename text_iterator, typename regex_iterator>
bool regex_match(
    text_iterator text_begin, text_iterator text_end,
    regex_iterator regex_begin, regex_iterator regex_end)
{
    return regex::match(text_begin, text_end,
                        regex_begin, regex_end);
}

template<typename text_iterator, typename regex_char>
bool regex_match(
    text_iterator text_begin, text_iterator text_end,
    const regex_char *regex)
{
    return regex::match(text_begin, text_end,
                        regex, unguarded_find(regex, '\0'));
}

#endif