include/regex

// -*- C++ -*-
//===--------------------------- regex ------------------------------------===//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//

#ifndef _LIBCPP_REGEX
#define _LIBCPP_REGEX

/*
 regex synopsis

#include <initializer_list>

namespace std
{

namespace regex_constants
{

emum syntax_option_type
{
 icase = unspecified,
 nosubs = unspecified,
 optimize = unspecified,
 collate = unspecified,
 ECMAScript = unspecified,
 basic = unspecified,
 extended = unspecified,
 awk = unspecified,
 grep = unspecified,
 egrep = unspecified
};

constexpr syntax_option_type operator~(syntax_option_type f);
constexpr syntax_option_type operator&(syntax_option_type lhs, syntax_option_type rhs);
constexpr syntax_option_type operator|(syntax_option_type lhs, syntax_option_type rhs);

enum match_flag_type
{
 match_default = 0,
 match_not_bol = unspecified,
 match_not_eol = unspecified,
 match_not_bow = unspecified,
 match_not_eow = unspecified,
 match_any = unspecified,
 match_not_null = unspecified,
 match_continuous = unspecified,
 match_prev_avail = unspecified,
 format_default = 0,
 format_sed = unspecified,
 format_no_copy = unspecified,
 format_first_only = unspecified
};

constexpr match_flag_type operator~(match_flag_type f);
constexpr match_flag_type operator&(match_flag_type lhs, match_flag_type rhs);
constexpr match_flag_type operator|(match_flag_type lhs, match_flag_type rhs);

enum error_type
{
 error_collate = unspecified,
 error_ctype = unspecified,
 error_escape = unspecified,
 error_backref = unspecified,
 error_brack = unspecified,
 error_paren = unspecified,
 error_brace = unspecified,
 error_badbrace = unspecified,
 error_range = unspecified,
 error_space = unspecified,
 error_badrepeat = unspecified,
 error_complexity = unspecified,
 error_stack = unspecified
};

} // regex_constants

class regex_error
 : public runtime_error
{
public:
 explicit regex_error(regex_constants::error_type ecode);
 regex_constants::error_type code() const;
};

template <class charT>
struct regex_traits
{
public:
 typedef charT char_type;
 typedef basic_string<char_type> string_type;
 typedef locale locale_type;
 typedef /bitmask_type/ char_class_type;

 regex_traits();

 static size_t length(const char_type* p);
 charT translate(charT c) const;
 charT translate_nocase(charT c) const;
 template <class ForwardIterator>
 string_type
 transform(ForwardIterator first, ForwardIterator last) const;
 template <class ForwardIterator>
 string_type
 transform_primary( ForwardIterator first, ForwardIterator last) const;
 template <class ForwardIterator>
 string_type
 lookup_collatename(ForwardIterator first, ForwardIterator last) const;
 template <class ForwardIterator>
 char_class_type
 lookup_classname(ForwardIterator first, ForwardIterator last,
 bool icase = false) const;
 bool isctype(charT c, char_class_type f) const;
 int value(charT ch, int radix) const;
 locale_type imbue(locale_type l);
 locale_type getloc()const;
};

template <class charT, class traits = regex_traits<charT>>
class basic_regex
{
public:
 // types:
 typedef charT value_type;
 typedef regex_constants::syntax_option_type flag_type;
 typedef typename traits::locale_type locale_type;

 // constants:
 static constexpr regex_constants::syntax_option_type icase = regex_constants::icase;
 static constexpr regex_constants::syntax_option_type nosubs = regex_constants::nosubs;
 static constexpr regex_constants::syntax_option_type optimize = regex_constants::optimize;
 static constexpr regex_constants::syntax_option_type collate = regex_constants::collate;
 static constexpr regex_constants::syntax_option_type ECMAScript = regex_constants::ECMAScript;
 static constexpr regex_constants::syntax_option_type basic = regex_constants::basic;
 static constexpr regex_constants::syntax_option_type extended = regex_constants::extended;
 static constexpr regex_constants::syntax_option_type awk = regex_constants::awk;
 static constexpr regex_constants::syntax_option_type grep = regex_constants::grep;
 static constexpr regex_constants::syntax_option_type egrep = regex_constants::egrep;

 // construct/copy/destroy:
 basic_regex();
 explicit basic_regex(const charT* p, flag_type f = regex_constants::ECMAScript);
 basic_regex(const charT* p, size_t len, flag_type f);
 basic_regex(const basic_regex&);
 basic_regex(basic_regex&&);
 template <class ST, class SA>
 explicit basic_regex(const basic_string<charT, ST, SA>& p,
 flag_type f = regex_constants::ECMAScript);
 template <class ForwardIterator>
 basic_regex(ForwardIterator first, ForwardIterator last,
 flag_type f = regex_constants::ECMAScript);
 basic_regex(initializer_list<charT>, flag_type = regex_constants::ECMAScript);

 ~basic_regex();

 basic_regex& operator=(const basic_regex&);
 basic_regex& operator=(basic_regex&&);
 basic_regex& operator=(const charT* ptr);
 basic_regex& operator=(initializer_list<charT> il);
 template <class ST, class SA>
 basic_regex& operator=(const basic_string<charT, ST, SA>& p);

 // assign:
 basic_regex& assign(const basic_regex& that);
 basic_regex& assign(basic_regex&& that);
 basic_regex& assign(const charT* ptr, flag_type f = regex_constants::ECMAScript);
 basic_regex& assign(const charT* p, size_t len, flag_type f);
 template <class string_traits, class A>
 basic_regex& assign(const basic_string<charT, string_traits, A>& s,
 flag_type f = regex_constants::ECMAScript);
 template <class InputIterator>
 basic_regex& assign(InputIterator first, InputIterator last,
 flag_type f = regex_constants::ECMAScript);
 basic_regex& assign(initializer_list<charT>, flag_type = regex_constants::ECMAScript);

 // const operations:
 unsigned mark_count() const;
 flag_type flags() const;

 // locale:
 locale_type imbue(locale_type loc);
 locale_type getloc() const;

 // swap:
 void swap(basic_regex&);
};

typedef basic_regex<char> regex;
typedef basic_regex<wchar_t> wregex;

template <class charT, class traits>
 void swap(basic_regex<charT, traits>& e1, basic_regex<charT, traits>& e2);

template <class BidirectionalIterator>
class sub_match
 : public pair<BidirectionalIterator, BidirectionalIterator>
{
public:
 typedef typename iterator_traits<BidirectionalIterator>::value_type value_type;
 typedef typename iterator_traits<BidirectionalIterator>::difference_type difference_type;
 typedef BidirectionalIterator iterator;
 typedef basic_string<value_type> string_type;

 bool matched;

 difference_type length() const;
 operator string_type() const;
 string_type str() const;

 int compare(const sub_match& s) const;
 int compare(const string_type& s) const;
 int compare(const value_type* s) const;
};

typedef sub_match<const char*> csub_match;
typedef sub_match<const wchar_t*> wcsub_match;
typedef sub_match<string::const_iterator> ssub_match;
typedef sub_match<wstring::const_iterator> wssub_match;

template <class BiIter>
 bool
 operator==(const sub_match<BiIter>& lhs, const sub_match<BiIter>& rhs);

template <class BiIter>
 bool
 operator!=(const sub_match<BiIter>& lhs, const sub_match<BiIter>& rhs);

template <class BiIter>
 bool
 operator<(const sub_match<BiIter>& lhs, const sub_match<BiIter>& rhs);

template <class BiIter>
 bool
 operator<=(const sub_match<BiIter>& lhs, const sub_match<BiIter>& rhs);

template <class BiIter>
 bool
 operator>=(const sub_match<BiIter>& lhs, const sub_match<BiIter>& rhs);

template <class BiIter>
 bool
 operator>(const sub_match<BiIter>& lhs, const sub_match<BiIter>& rhs);

template <class BiIter, class ST, class SA>
 bool
 operator==(const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& lhs,
 const sub_match<BiIter>& rhs);

template <class BiIter, class ST, class SA>
 bool
 operator!=(const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& lhs,
 const sub_match<BiIter>& rhs);

template <class BiIter, class ST, class SA>
 bool
 operator<(const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& lhs,
 const sub_match<BiIter>& rhs);

template <class BiIter, class ST, class SA>
 bool
 operator>(const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& lhs,
 const sub_match<BiIter>& rhs);

template <class BiIter, class ST, class SA>
 bool operator>=(const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& lhs,
 const sub_match<BiIter>& rhs);

template <class BiIter, class ST, class SA>
 bool
 operator<=(const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& lhs,
 const sub_match<BiIter>& rhs);

template <class BiIter, class ST, class SA>
 bool
 operator==(const sub_match<BiIter>& lhs,
 const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& rhs);

template <class BiIter, class ST, class SA>
 bool
 operator!=(const sub_match<BiIter>& lhs,
 const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& rhs);

template <class BiIter, class ST, class SA>
 bool
 operator<(const sub_match<BiIter>& lhs,
 const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& rhs);

template <class BiIter, class ST, class SA>
 bool operator>(const sub_match<BiIter>& lhs,
 const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& rhs);

template <class BiIter, class ST, class SA>
 bool
 operator>=(const sub_match<BiIter>& lhs,
 const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& rhs);

template <class BiIter, class ST, class SA>
 bool
 operator<=(const sub_match<BiIter>& lhs,
 const basic_string<typename iterator_traits<BiIter>::value_type, ST, SA>& rhs);

template <class BiIter>
 bool
 operator==(typename iterator_traits<BiIter>::value_type const* lhs,
 const sub_match<BiIter>& rhs);

template <class BiIter>
 bool
 operator!=(typename iterator_traits<BiIter>::value_type const* lhs,
 const sub_match<BiIter>& rhs);

template <class BiIter>
 bool
 operator<(typename iterator_traits<BiIter>::value_type const* lhs,
 const sub_match<BiIter>& rhs);

template <class BiIter>
 bool
 operator>(typename iterator_traits<BiIter>::value_type const* lhs,
 const sub_match<BiIter>& rhs);

template <class BiIter>
 bool
 operator>=(typename iterator_traits<BiIter>::value_type const* lhs,
 const sub_match<BiIter>& rhs);

template <class BiIter>
 bool
 operator<=(typename iterator_traits<BiIter>::value_type const* lhs,
 const sub_match<BiIter>& rhs);

template <class BiIter>
 bool
 operator==(const sub_match<BiIter>& lhs,
 typename iterator_traits<BiIter>::value_type const* rhs);

template <class BiIter>
 bool
 operator!=(const sub_match<BiIter>& lhs,
 typename iterator_traits<BiIter>::value_type const* rhs);

template <class BiIter>
 bool
 operator<(const sub_match<BiIter>& lhs,
 typename iterator_traits<BiIter>::value_type const* rhs);

template <class BiIter>
 bool
 operator>(const sub_match<BiIter>& lhs,
 typename iterator_traits<BiIter>::value_type const* rhs);

template <class BiIter>
 bool
 operator>=(const sub_match<BiIter>& lhs,
 typename iterator_traits<BiIter>::value_type const* rhs);

template <class BiIter>
 bool
 operator<=(const sub_match<BiIter>& lhs,
 typename iterator_traits<BiIter>::value_type const* rhs);

template <class BiIter>
 bool
 operator==(typename iterator_traits<BiIter>::value_type const& lhs,
 const sub_match<BiIter>& rhs);

template <class BiIter>
 bool
 operator!=(typename iterator_traits<BiIter>::value_type const& lhs,
 const sub_match<BiIter>& rhs);

template <class BiIter>
 bool
 operator<(typename iterator_traits<BiIter>::value_type const& lhs,
 const sub_match<BiIter>& rhs);

template <class BiIter>
 bool
 operator>(typename iterator_traits<BiIter>::value_type const& lhs,
 const sub_match<BiIter>& rhs);

template <class BiIter>
 bool
 operator>=(typename iterator_traits<BiIter>::value_type const& lhs,
 const sub_match<BiIter>& rhs);

template <class BiIter>
 bool
 operator<=(typename iterator_traits<BiIter>::value_type const& lhs,
 const sub_match<BiIter>& rhs);

template <class BiIter>
 bool
 operator==(const sub_match<BiIter>& lhs,
 typename iterator_traits<BiIter>::value_type const& rhs);

template <class BiIter>
 bool
 operator!=(const sub_match<BiIter>& lhs,
 typename iterator_traits<BiIter>::value_type const& rhs);

template <class BiIter>
 bool
 operator<(const sub_match<BiIter>& lhs,
 typename iterator_traits<BiIter>::value_type const& rhs);

template <class BiIter>
 bool
 operator>(const sub_match<BiIter>& lhs,
 typename iterator_traits<BiIter>::value_type const& rhs);

template <class BiIter>
 bool
 operator>=(const sub_match<BiIter>& lhs,
 typename iterator_traits<BiIter>::value_type const& rhs);

template <class BiIter>
 bool
 operator<=(const sub_match<BiIter>& lhs,
 typename iterator_traits<BiIter>::value_type const& rhs);

template <class charT, class ST, class BiIter>
 basic_ostream<charT, ST>&
 operator<<(basic_ostream<charT, ST>& os, const sub_match<BiIter>& m);

template <class BidirectionalIterator,
 class Allocator = allocator<sub_match<BidirectionalIterator>>>
class match_results
{
public:
 typedef sub_match<BidirectionalIterator> value_type;
 typedef const value_type& const_reference;
 typedef const_reference reference;
 typedef /implementation-defined/ const_iterator;
 typedef const_iterator iterator;
 typedef typename iterator_traits<BidirectionalIterator>::difference_type difference_type;
 typedef typename allocator_traits<Allocator>::size_type size_type;
 typedef Allocator allocator_type;
 typedef typename iterator_traits<BidirectionalIterator>::value_type char_type;
 typedef basic_string<char_type> string_type;

 // construct/copy/destroy:
 explicit match_results(const Allocator& a = Allocator());
 match_results(const match_results& m);
 match_results(match_results&& m);
 match_results& operator=(const match_results& m);
 match_results& operator=(match_results&& m);
 ~match_results();

 // size:
 size_type size() const;
 size_type max_size() const;
 bool empty() const;

 // element access:
 difference_type length(size_type sub = 0) const;
 difference_type position(size_type sub = 0) const;
 string_type str(size_type sub = 0) const;
 const_reference operator[](size_type n) const;

 const_reference prefix() const;
 const_reference suffix() const;

 const_iterator begin() const;
 const_iterator end() const;
 const_iterator cbegin() const;
 const_iterator cend() const;

 // format:
 template <class OutputIter>
 OutputIter
 format(OutputIter out, const char_type* fmt_first,
 const char_type* fmt_last,
 regex_constants::match_flag_type flags = regex_constants::format_default) const;
 template <class OutputIter, class ST, class SA>
 OutputIter
 format(OutputIter out, const basic_string<char_type, ST, SA>& fmt,
 regex_constants::match_flag_type flags = regex_constants::format_default) const;
 template <class ST, class SA>
 basic_string<char_type, ST, SA>
 format(const basic_string<char_type, ST, SA>& fmt,
 regex_constants::match_flag_type flags = regex_constants::format_default) const;
 string_type
 format(const char_type* fmt,
 regex_constants::match_flag_type flags = regex_constants::format_default) const;

 // allocator:
 allocator_type get_allocator() const;

 // swap:
 void swap(match_results& that);
};

typedef match_results<const char*> cmatch;
typedef match_results<const wchar_t*> wcmatch;
typedef match_results<string::const_iterator> smatch;
typedef match_results<wstring::const_iterator> wsmatch;

template <class BidirectionalIterator, class Allocator>
 bool
 operator==(const match_results<BidirectionalIterator, Allocator>& m1,
 const match_results<BidirectionalIterator, Allocator>& m2);

template <class BidirectionalIterator, class Allocator>
 bool
 operator!=(const match_results<BidirectionalIterator, Allocator>& m1,
 const match_results<BidirectionalIterator, Allocator>& m2);

template <class BidirectionalIterator, class Allocator>
 void
 swap(match_results<BidirectionalIterator, Allocator>& m1,
 match_results<BidirectionalIterator, Allocator>& m2);

template <class BidirectionalIterator, class Allocator, class charT, class traits>
 bool
 regex_match(BidirectionalIterator first, BidirectionalIterator last,
 match_results<BidirectionalIterator, Allocator>& m,
 const basic_regex<charT, traits>& e,
 regex_constants::match_flag_type flags = regex_constants::match_default);

template <class BidirectionalIterator, class charT, class traits>
 bool
 regex_match(BidirectionalIterator first, BidirectionalIterator last,
 const basic_regex<charT, traits>& e,
 regex_constants::match_flag_type flags = regex_constants::match_default);

template <class charT, class Allocator, class traits>
 bool
 regex_match(const charT* str, match_results<const charT*, Allocator>& m,
 const basic_regex<charT, traits>& e,
 regex_constants::match_flag_type flags = regex_constants::match_default);

template <class ST, class SA, class Allocator, class charT, class traits>
 bool
 regex_match(const basic_string<charT, ST, SA>& s,
 match_results<typename basic_string<charT, ST, SA>::const_iterator, Allocator>& m,
 const basic_regex<charT, traits>& e,
 regex_constants::match_flag_type flags = regex_constants::match_default);

template <class charT, class traits>
 bool
 regex_match(const charT* str, const basic_regex<charT, traits>& e,
 regex_constants::match_flag_type flags = regex_constants::match_default);

template <class ST, class SA, class charT, class traits>
 bool
 regex_match(const basic_string<charT, ST, SA>& s,
 const basic_regex<charT, traits>& e,
 regex_constants::match_flag_type flags = regex_constants::match_default);

template <class BidirectionalIterator, class Allocator, class charT, class traits>
 bool
 regex_search(BidirectionalIterator first, BidirectionalIterator last,
 match_results<BidirectionalIterator, Allocator>& m,
 const basic_regex<charT, traits>& e,
 regex_constants::match_flag_type flags = regex_constants::match_default);

template <class BidirectionalIterator, class charT, class traits>
 bool
 regex_search(BidirectionalIterator first, BidirectionalIterator last,
 const basic_regex<charT, traits>& e,
 regex_constants::match_flag_type flags = regex_constants::match_default);

template <class charT, class Allocator, class traits>
 bool
 regex_search(const charT* str, match_results<const charT*, Allocator>& m,
 const basic_regex<charT, traits>& e,
 regex_constants::match_flag_type flags = regex_constants::match_default);

template <class charT, class traits>
 bool
 regex_search(const charT* str, const basic_regex<charT, traits>& e,
 regex_constants::match_flag_type flags = regex_constants::match_default);

template <class ST, class SA, class charT, class traits>
 bool
 regex_search(const basic_string<charT, ST, SA>& s,
 const basic_regex<charT, traits>& e,
 regex_constants::match_flag_type flags = regex_constants::match_default);

template <class ST, class SA, class Allocator, class charT, class traits>
 bool
 regex_search(const basic_string<charT, ST, SA>& s,
 match_results<typename basic_string<charT, ST, SA>::const_iterator, Allocator>& m,
 const basic_regex<charT, traits>& e,
 regex_constants::match_flag_type flags = regex_constants::match_default);

template <class OutputIterator, class BidirectionalIterator,
 class traits, class charT, class ST, class SA>
 OutputIterator
 regex_replace(OutputIterator out,
 BidirectionalIterator first, BidirectionalIterator last,
 const basic_regex<charT, traits>& e,
 const basic_string<charT, ST, SA>& fmt,
 regex_constants::match_flag_type flags = regex_constants::match_default);

template <class OutputIterator, class BidirectionalIterator,
 class traits, class charT>
 OutputIterator
 regex_replace(OutputIterator out,
 BidirectionalIterator first, BidirectionalIterator last,
 const basic_regex<charT, traits>& e, const charT* fmt,
 regex_constants::match_flag_type flags = regex_constants::match_default);

template <class traits, class charT, class ST, class SA, class FST, class FSA>>
 basic_string<charT, ST, SA>
 regex_replace(const basic_string<charT, ST, SA>& s,
 const basic_regex<charT, traits>& e,
 const basic_string<charT, FST, FSA>& fmt,
 regex_constants::match_flag_type flags = regex_constants::match_default);

template <class traits, class charT, class ST, class SA>
 basic_string<charT, ST, SA>
 regex_replace(const basic_string<charT, ST, SA>& s,
 const basic_regex<charT, traits>& e, const charT* fmt,
 regex_constants::match_flag_type flags = regex_constants::match_default);

template <class traits, class charT, class ST, class SA>
 basic_string<charT>
 regex_replace(const charT* s,
 const basic_regex<charT, traits>& e,
 const basic_string<charT, ST, SA>& fmt,
 regex_constants::match_flag_type flags = regex_constants::match_default);

template <class traits, class charT>
 basic_string<charT>
 regex_replace(const charT* s,
 const basic_regex<charT, traits>& e,
 const charT* fmt,
 regex_constants::match_flag_type flags = regex_constants::match_default);

template <class BidirectionalIterator,
 class charT = typename iterator_traits< BidirectionalIterator>::value_type,
 class traits = regex_traits<charT>>
class regex_iterator
{
public:
 typedef basic_regex<charT, traits> regex_type;
 typedef match_results<BidirectionalIterator> value_type;
 typedef ptrdiff_t difference_type;
 typedef const value_type* pointer;
 typedef const value_type& reference;
 typedef forward_iterator_tag iterator_category;

 regex_iterator();
 regex_iterator(BidirectionalIterator a, BidirectionalIterator b,
 const regex_type& re,
 regex_constants::match_flag_type m = regex_constants::match_default);
 regex_iterator(const regex_iterator&);
 regex_iterator& operator=(const regex_iterator&);

 bool operator==(const regex_iterator&) const;
 bool operator!=(const regex_iterator&) const;

 const value_type& operator*() const;
 const value_type* operator->() const;

 regex_iterator& operator++();
 regex_iterator operator++(int);
};

typedef regex_iterator<const char*> cregex_iterator;
typedef regex_iterator<const wchar_t*> wcregex_iterator;
typedef regex_iterator<string::const_iterator> sregex_iterator;
typedef regex_iterator<wstring::const_iterator> wsregex_iterator;

template <class BidirectionalIterator,
 class charT = typename iterator_traits< BidirectionalIterator>::value_type,
 class traits = regex_traits<charT>>
class regex_token_iterator
{
public:
 typedef basic_regex<charT, traits> regex_type;
 typedef sub_match<BidirectionalIterator> value_type;
 typedef ptrdiff_t difference_type;
 typedef const value_type* pointer;
 typedef const value_type& reference;
 typedef forward_iterator_tag iterator_category;

 regex_token_iterator();
 regex_token_iterator(BidirectionalIterator a, BidirectionalIterator b,
 const regex_type& re, int submatch = 0,
 regex_constants::match_flag_type m = regex_constants::match_default);
 regex_token_iterator(BidirectionalIterator a, BidirectionalIterator b,
 const regex_type& re, const vector<int>& submatches,
 regex_constants::match_flag_type m = regex_constants::match_default);
 regex_token_iterator(BidirectionalIterator a, BidirectionalIterator b,
 const regex_type& re, initializer_list<int> submatches,
 regex_constants::match_flag_type m = regex_constants::match_default);
 template <size_t N>
 regex_token_iterator(BidirectionalIterator a, BidirectionalIterator b,
 const regex_type& re, const int (&submatches)[N],
 regex_constants::match_flag_type m = regex_constants::match_default);
 regex_token_iterator(const regex_token_iterator&);
 regex_token_iterator& operator=(const regex_token_iterator&);

 bool operator==(const regex_token_iterator&) const;
 bool operator!=(const regex_token_iterator&) const;

 const value_type& operator*() const;
 const value_type* operator->() const;

 regex_token_iterator& operator++();
 regex_token_iterator operator++(int);
};

typedef regex_token_iterator<const char*> cregex_token_iterator;
typedef regex_token_iterator<const wchar_t*> wcregex_token_iterator;
typedef regex_token_iterator<string::const_iterator> sregex_token_iterator;
typedef regex_token_iterator<wstring::const_iterator> wsregex_token_iterator;

} // std
*/

#include <__config>
#include <stdexcept>
#include <__locale>
#include <initializer_list>
#include <utility>
#include <iterator>
#include <string>

#pragma GCC system_header

_LIBCPP_BEGIN_NAMESPACE_STD

namespace regex_constants
{

// syntax_option_type

enum syntax_option_type
{
 icase = 1 << 0,
 nosubs = 1 << 1,
 optimize = 1 << 2,
 collate = 1 << 3,
 ECMAScript = 1 << 4,
 basic = 1 << 5,
 extended = 1 << 6,
 awk = 1 << 7,
 grep = 1 << 8,
 egrep = 1 << 9
};

inline
/*constexpr*/
syntax_option_type
operator~(syntax_option_type __x)
{
 return syntax_option_type(~int(__x));
}

inline
/*constexpr*/
syntax_option_type
operator&(syntax_option_type __x, syntax_option_type __y)
{
 return syntax_option_type(int(__x) & int(__y));
}

inline
/*constexpr*/
syntax_option_type
operator|(syntax_option_type __x, syntax_option_type __y)
{
 return syntax_option_type(int(__x) | int(__y));
}

inline
/*constexpr*/
syntax_option_type
operator^(syntax_option_type __x, syntax_option_type __y)
{
 return syntax_option_type(int(__x) ^ int(__y));
}

inline
/*constexpr*/
syntax_option_type&
operator&=(syntax_option_type& __x, syntax_option_type __y)
{
 __x = __x & __y;
 return __x;
}

inline
/*constexpr*/
syntax_option_type&
operator|=(syntax_option_type& __x, syntax_option_type __y)
{
 __x = __x | __y;
 return __x;
}

inline
/*constexpr*/
syntax_option_type&
operator^=(syntax_option_type& __x, syntax_option_type __y)
{
 __x = __x ^ __y;
 return __x;
}

// match_flag_type

enum match_flag_type
{
 match_default = 0,
 match_not_bol = 1 << 0,
 match_not_eol = 1 << 1,
 match_not_bow = 1 << 2,
 match_not_eow = 1 << 3,
 match_any = 1 << 4,
 match_not_null = 1 << 5,
 match_continuous = 1 << 6,
 match_prev_avail = 1 << 7,
 format_default = 0,
 format_sed = 1 << 8,
 format_no_copy = 1 << 9,
 format_first_only = 1 << 10
};

inline
/*constexpr*/
match_flag_type
operator~(match_flag_type __x)
{
 return match_flag_type(~int(__x));
}

inline
/*constexpr*/
match_flag_type
operator&(match_flag_type __x, match_flag_type __y)
{
 return match_flag_type(int(__x) & int(__y));
}

inline
/*constexpr*/
match_flag_type
operator|(match_flag_type __x, match_flag_type __y)
{
 return match_flag_type(int(__x) | int(__y));
}

inline
/*constexpr*/
match_flag_type
operator^(match_flag_type __x, match_flag_type __y)
{
 return match_flag_type(int(__x) ^ int(__y));
}

inline
/*constexpr*/
match_flag_type&
operator&=(match_flag_type& __x, match_flag_type __y)
{
 __x = __x & __y;
 return __x;
}

inline
/*constexpr*/
match_flag_type&
operator|=(match_flag_type& __x, match_flag_type __y)
{
 __x = __x | __y;
 return __x;
}

inline
/*constexpr*/
match_flag_type&
operator^=(match_flag_type& __x, match_flag_type __y)
{
 __x = __x ^ __y;
 return __x;
}

enum error_type
{
 error_collate = 1,
 error_ctype,
 error_escape,
 error_backref,
 error_brack,
 error_paren,
 error_brace,
 error_badbrace,
 error_range,
 error_space,
 error_badrepeat,
 error_complexity,
 error_stack,
 error_temp
};

} // regex_constants

class _LIBCPP_EXCEPTION_ABI regex_error
 : public runtime_error
{
 regex_constants::error_type __code_;
public:
 explicit regex_error(regex_constants::error_type __ecode);
 virtual ~regex_error() throw();
 regex_constants::error_type code() const {return __code_;}
};

template <class _CharT>
struct regex_traits
{
public:
 typedef _CharT char_type;
 typedef basic_string<char_type> string_type;
 typedef locale locale_type;
 typedef ctype_base::mask char_class_type;

 static const char_class_type __regex_word = 0x80;
private:
 locale __loc_;
 const ctype<char_type>* __ct_;
 const collate<char_type>* __col_;

public:
 regex_traits();

 static size_t length(const char_type* __p)
 {return char_traits<char_type>::length(__p);}
 char_type translate(char_type __c) const {return __c;}
 char_type translate_nocase(char_type __c) const;
 template <class _ForwardIterator>
 string_type
 transform(_ForwardIterator __f, _ForwardIterator __l) const;
 template <class _ForwardIterator>
 string_type
 transform_primary( _ForwardIterator __f, _ForwardIterator __l) const
 {return __transform_primary(__f, __l, char_type());}
 template <class _ForwardIterator>
 string_type
 lookup_collatename(_ForwardIterator __f, _ForwardIterator __l) const
 {return __lookup_collatename(__f, __l, char_type());}
 template <class _ForwardIterator>
 char_class_type
 lookup_classname(_ForwardIterator __f, _ForwardIterator __l,
 bool __icase = false) const
 {return __lookup_classname(__f, __l, __icase, char_type());}
 bool isctype(char_type __c, char_class_type __m) const;
 int value(char_type __ch, int __radix) const
 {return __value(__ch, __radix);}
 locale_type imbue(locale_type __l);
 locale_type getloc()const {return __loc_;}

private:
 void __init();

 template <class _ForwardIterator>
 string_type
 __transform_primary(_ForwardIterator __f, _ForwardIterator __l, char) const;
 template <class _ForwardIterator>
 string_type
 __transform_primary(_ForwardIterator __f, _ForwardIterator __l, wchar_t) const;

 template <class _ForwardIterator>
 string_type
 __lookup_collatename(_ForwardIterator __f, _ForwardIterator __l, char) const;
 template <class _ForwardIterator>
 string_type
 __lookup_collatename(_ForwardIterator __f, _ForwardIterator __l, wchar_t) const;

 template <class _ForwardIterator>
 char_class_type
 __lookup_classname(_ForwardIterator __f, _ForwardIterator __l,
 bool __icase, char) const;
 template <class _ForwardIterator>
 char_class_type
 __lookup_classname(_ForwardIterator __f, _ForwardIterator __l,
 bool __icase, wchar_t) const;

 static int __value(unsigned char __ch, int __radix);
 int __value(char __ch, int __radix) const
 {return __value(static_cast<unsigned char>(__ch), __radix);}
 int __value(wchar_t __ch, int __radix) const;
};

template <class _CharT>
regex_traits<_CharT>::regex_traits()
{
 __init();
}

template <class _CharT>
typename regex_traits<_CharT>::char_type
regex_traits<_CharT>::translate_nocase(char_type __c) const
{
 return __ct_->tolower(__c);
}

template <class _CharT>
template <class _ForwardIterator>
typename regex_traits<_CharT>::string_type
regex_traits<_CharT>::transform(_ForwardIterator __f, _ForwardIterator __l) const
{
 string_type __s(__f, __l);
 return __col_->transform(__s.data(), __s.data() + __s.size());
}

template <class _CharT>
void
regex_traits<_CharT>::__init()
{
 __ct_ = &use_facet<ctype<char_type> >(__loc_);
 __col_ = &use_facet<collate<char_type> >(__loc_);
}

template <class _CharT>
typename regex_traits<_CharT>::locale_type
regex_traits<_CharT>::imbue(locale_type __l)
{
 locale __r = __loc_;
 __loc_ = __l;
 __init();
 return __r;
}

// transform_primary is very FreeBSD-specific

template <class _CharT>
template <class _ForwardIterator>
typename regex_traits<_CharT>::string_type
regex_traits<_CharT>::__transform_primary(_ForwardIterator __f,
 _ForwardIterator __l, char) const
{
 const string_type __s(__f, __l);
 string_type __d = __col_->transform(__s.data(), __s.data() + __s.size());
 switch (__d.size())
 {
 case 1:
 break;
 case 12:
 __d[11] = __d[3];
 break;
 default:
 __d.clear();
 break;
 }
 return __d;
}

template <class _CharT>
template <class _ForwardIterator>
typename regex_traits<_CharT>::string_type
regex_traits<_CharT>::__transform_primary(_ForwardIterator __f,
 _ForwardIterator __l, wchar_t) const
{
 const string_type __s(__f, __l);
 string_type __d = __col_->transform(__s.data(), __s.data() + __s.size());
 switch (__d.size())
 {
 case 1:
 break;
 case 3:
 __d[2] = __d[0];
 break;
 default:
 __d.clear();
 break;
 }
 return __d;
}

// lookup_collatename is very FreeBSD-specific

string __get_collation_name(const char* __s);

template <class _CharT>
template <class _ForwardIterator>
typename regex_traits<_CharT>::string_type
regex_traits<_CharT>::__lookup_collatename(_ForwardIterator __f,
 _ForwardIterator __l, char) const
{
 string_type __s(__f, __l);
 string_type __r;
 if (!__s.empty())
 {
 __r = __get_collation_name(__s.c_str());
 if (__r.empty() && __s.size() <= 2)
 {
 __r = __col_->transform(__s.data(), __s.data() + __s.size());
 if (__r.size() == 1 || __r.size() == 12)
 __r = __s;
 else
 __r.clear();
 }
 }
 return __r;
}

template <class _CharT>
template <class _ForwardIterator>
typename regex_traits<_CharT>::string_type
regex_traits<_CharT>::__lookup_collatename(_ForwardIterator __f,
 _ForwardIterator __l, wchar_t) const
{
 string_type __s(__f, __l);
 string __n;
 __n.reserve(__s.size());
 for (typename string_type::const_iterator __i = __s.begin(), __e = __s.end();
 __i != __e; ++__i)
 {
 if (static_cast<unsigned>(*__i) >= 127)
 return string_type();
 __n.push_back(char(*__i));
 }
 string_type __r;
 if (!__s.empty())
 {
 __n = __get_collation_name(__n.c_str());
 if (!__n.empty())
 __r.assign(__n.begin(), __n.end());
 else if (__s.size() <= 2)
 {
 __r = __col_->transform(__s.data(), __s.data() + __s.size());
 if (__r.size() == 1 || __r.size() == 3)
 __r = __s;
 else
 __r.clear();
 }
 }
 return __r;
}

// lookup_classname

ctype_base::mask __get_classname(const char* __s, bool __icase);

template <class _CharT>
template <class _ForwardIterator>
typename regex_traits<_CharT>::char_class_type
regex_traits<_CharT>::__lookup_classname(_ForwardIterator __f,
 _ForwardIterator __l,
 bool __icase, char) const
{
 string_type __s(__f, __l);
 __ct_->tolower(&__s[0], &__s[0] + __s.size());
 return __get_classname(__s.c_str(), __icase);
}

template <class _CharT>
template <class _ForwardIterator>
typename regex_traits<_CharT>::char_class_type
regex_traits<_CharT>::__lookup_classname(_ForwardIterator __f,
 _ForwardIterator __l,
 bool __icase, wchar_t) const
{
 string_type __s(__f, __l);
 __ct_->tolower(&__s[0], &__s[0] + __s.size());
 string __n;
 __n.reserve(__s.size());
 for (typename string_type::const_iterator __i = __s.begin(), __e = __s.end();
 __i != __e; ++__i)
 {
 if (static_cast<unsigned>(*__i) >= 127)
 return char_class_type();
 __n.push_back(char(*__i));
 }
 return __get_classname(__n.c_str(), __icase);
}

template <class _CharT>
bool
regex_traits<_CharT>::isctype(char_type __c, char_class_type __m) const
{
 if (__ct_->is(__m, __c))
 return true;
 return (__c == '_' && (__m & __regex_word));
}

template <class _CharT>
int
regex_traits<_CharT>::__value(unsigned char __ch, int __radix)
{
 if ((__ch & 0xF8u) == 0x30) // '0' <= __ch && __ch <= '7'
 return __ch - '0';
 if (__radix != 8)
 {
 if ((__ch & 0xFEu) == 0x38) // '8' <= __ch && __ch <= '9'
 return __ch - '0';
 if (__radix == 16)
 {
 __ch |= 0x20; // tolower
 if ('a' <= __ch && __ch <= 'f')
 return __ch - ('a' - 10);
 }
 }
 return -1;
}

template <class _CharT>
inline
int
regex_traits<_CharT>::__value(wchar_t __ch, int __radix) const
{
 return __value(static_cast<unsigned char>(__ct_->narrow(__ch, char_type())), __radix);
}

template <class _CharT> class __transition;

template <class _CharT>
class __state
{
 typedef __transition<_CharT> __transition;
 __transition* __t1_;
 __transition* __t2_;
 int __state_;
 enum
 {
 __1_not_tried = 0,
 __1_succeded = 1,
 __1_failed = 2,
 __2_not_tried = 0,
 __2_succeded = 4,
 __2_failed = 8
 };

 __state(const __state&);
 __state& operator=(const __state&);
public:
 __state()
 : __t1_(), __t2_(), __state_() {}
 ~__state();

 const __state* operator()(_CharT __c);

 void __add_one(__transition* __t) {__t1_ = __t;}
};

template <class _CharT>
__state<_CharT>::~__state()
{
 delete __t1_;
 delete __t2_;
}

template <class _CharT>
const __state<_CharT>*
__state<_CharT>::operator()(_CharT __c)
{
 const __state* __r = nullptr;
 if ((__state_ & 3) == 0)
 {
 if (__t1_)
 {
 __r = (*__t1_)(__c);
 if (__r)
 __state_ |= __1_succeded;
 else
 __state_ |= __1_failed;
 }
 else
 __state_ |= __1_failed;
 }
 else if ((__state_ & 0xC) == 0)
 {
 if (__t2_)
 {
 __r = (*__t2_)(__c);
 if (__r)
 __state_ |= __2_succeded;
 else
 __state_ |= __2_failed;
 }
 else
 __state_ |= __2_failed;
 }
 return __r;
}

template <class _CharT>
class __transition
{
 __transition(const __transition&);
 __transition& operator=(const __transition&);

 typedef __state<_CharT> __state;
 typedef unique_ptr<__state, void(*)(__state*)> __sptr;

 static void __delete_state(__state* __p) {delete __p;}
 static void __ignore_state(__state*) {}

protected:
 __sptr __sptr_;
public:
 __transition(bool __owns, __state* __st)
 : __sptr_(__st, __owns ? &__delete_state : &__ignore_state) {}
 virtual ~__transition() {}

 virtual const __state* operator()(_CharT) const {return __sptr_.get();}
};

template <class _CharT>
class __match_char
 : public __transition<_CharT>
{
 typedef __transition<_CharT> base;
 _CharT __c_;
public:
 __match_char(_CharT __c, bool __owns, __state<_CharT>* __st)
 : base(__owns, __st), __c_(__c) {}

 virtual const __state<_CharT>* operator()(_CharT __c) const
 {return __c == __c_ ? base::__sptr_.get() : nullptr;}
};

template <class _CharT, class _Traits = regex_traits<_CharT> >
class basic_regex
{
public:
 // types:
 typedef _CharT value_type;
 typedef regex_constants::syntax_option_type flag_type;
 typedef typename _Traits::locale_type locale_type;

private:
 _Traits __traits_;
 flag_type __flags_;
 unsigned __marked_count_;
 int __open_count_;
 shared_ptr<__state<_CharT> > __start_;
 __state<_CharT>* __end_;

public:
 // constants:
 static const/*expr*/ regex_constants::syntax_option_type icase = regex_constants::icase;
 static const/*expr*/ regex_constants::syntax_option_type nosubs = regex_constants::nosubs;
 static const/*expr*/ regex_constants::syntax_option_type optimize = regex_constants::optimize;
 static const/*expr*/ regex_constants::syntax_option_type collate = regex_constants::collate;
 static const/*expr*/ regex_constants::syntax_option_type ECMAScript = regex_constants::ECMAScript;
 static const/*expr*/ regex_constants::syntax_option_type basic = regex_constants::basic;
 static const/*expr*/ regex_constants::syntax_option_type extended = regex_constants::extended;
 static const/*expr*/ regex_constants::syntax_option_type awk = regex_constants::awk;
 static const/*expr*/ regex_constants::syntax_option_type grep = regex_constants::grep;
 static const/*expr*/ regex_constants::syntax_option_type egrep = regex_constants::egrep;

 // construct/copy/destroy:
 basic_regex();
 explicit basic_regex(const value_type* __p, flag_type __f = regex_constants::ECMAScript)
 : __flags_(__f), __marked_count_(0), __open_count_(0), __end_(0)
 {__parse(__p, __p + __traits_.length(__p));}
 basic_regex(const value_type* __p, size_t __len, flag_type __f)
 : __flags_(__f), __marked_count_(0), __open_count_(0), __end_(0)
 {__parse(__p, __p + __len);}
 basic_regex(const basic_regex&);
#ifdef _LIBCPP_MOVE
 basic_regex(basic_regex&&);
#endif
 template <class _ST, class _SA>
 explicit basic_regex(const basic_string<value_type, _ST, _SA>& __p,
 flag_type __f = regex_constants::ECMAScript)
 : __flags_(__f), __marked_count_(0), __open_count_(0), __end_(0)
 {__parse(__p.begin(), __p.end());}
 template <class _ForwardIterator>
 basic_regex(_ForwardIterator __first, _ForwardIterator __last,
 flag_type __f = regex_constants::ECMAScript)
 : __flags_(__f), __marked_count_(0), __open_count_(0), __end_(0)
 {__parse(__first, __last);}
 basic_regex(initializer_list<value_type> __il,
 flag_type __f = regex_constants::ECMAScript)
 : __flags_(__f), __marked_count_(0), __open_count_(0), __end_(0)
 {__parse(__il.begin(), __il.end());}

 ~basic_regex();

 basic_regex& operator=(const basic_regex&);
#ifdef _LIBCPP_MOVE
 basic_regex& operator=(basic_regex&&);
#endif
 basic_regex& operator=(const value_type* __p);
 basic_regex& operator=(initializer_list<value_type> __il);
 template <class _ST, class _SA>
 basic_regex& operator=(const basic_string<value_type, _ST, _SA>& __p);

 // assign:
 basic_regex& assign(const basic_regex& __that);
#ifdef _LIBCPP_MOVE
 basic_regex& assign(basic_regex&& __that);
#endif
 basic_regex& assign(const value_type* __p, flag_type __f = regex_constants::ECMAScript);
 basic_regex& assign(const value_type* __p, size_t __len, flag_type __f);
 template <class _ST, class _SA>
 basic_regex& assign(const basic_string<value_type, _ST, _SA>& __s,
 flag_type __f = regex_constants::ECMAScript);
 template <class _InputIterator>
 basic_regex& assign(_InputIterator __first, _InputIterator __last,
 flag_type __f = regex_constants::ECMAScript);
 basic_regex& assign(initializer_list<value_type> __il,
 flag_type = regex_constants::ECMAScript);

 // const operations:
 unsigned mark_count() const {return __marked_count_;}
 flag_type flags() const {return __flags_;}

 // locale:
 locale_type imbue(locale_type __loc) {return __traits_.imbue(__loc);}
 locale_type getloc() const {return __traits_.getloc();}

 // swap:
 void swap(basic_regex&);

private:
 template <class _ForwardIterator>
 void __parse(_ForwardIterator __first, _ForwardIterator __last);
 template <class _ForwardIterator>
 _ForwardIterator
 __parse_basic_reg_exp(_ForwardIterator __first, _ForwardIterator __last);
 template <class _ForwardIterator>
 _ForwardIterator
 __parse_RE_expression(_ForwardIterator __first, _ForwardIterator __last);
 template <class _ForwardIterator>
 _ForwardIterator
 __parse_simple_RE(_ForwardIterator __first, _ForwardIterator __last);
 template <class _ForwardIterator>
 _ForwardIterator
 __parse_nondupl_RE(_ForwardIterator __first, _ForwardIterator __last);
 template <class _ForwardIterator>
 _ForwardIterator
 __parse_one_char_or_coll_elem_RE(_ForwardIterator __first, _ForwardIterator __last);
 template <class _ForwardIterator>
 _ForwardIterator
 __parse_Back_open_paren(_ForwardIterator __first, _ForwardIterator __last);
 template <class _ForwardIterator>
 _ForwardIterator
 __parse_Back_close_paren(_ForwardIterator __first, _ForwardIterator __last);
 template <class _ForwardIterator>
 _ForwardIterator
 __parse_Back_open_brace(_ForwardIterator __first, _ForwardIterator __last);
 template <class _ForwardIterator>
 _ForwardIterator
 __parse_Back_close_brace(_ForwardIterator __first, _ForwardIterator __last);
 template <class _ForwardIterator>
 _ForwardIterator
 __parse_BACKREF(_ForwardIterator __first, _ForwardIterator __last);
 template <class _ForwardIterator>
 _ForwardIterator
 __parse_ORD_CHAR(_ForwardIterator __first, _ForwardIterator __last);
 template <class _ForwardIterator>
 _ForwardIterator
 __parse_QUOTED_CHAR(_ForwardIterator __first, _ForwardIterator __last);
 template <class _ForwardIterator>
 _ForwardIterator
 __parse_RE_dupl_symbol(_ForwardIterator __first, _ForwardIterator __last);
 template <class _ForwardIterator>
 _ForwardIterator
 __parse_ERE_dupl_symbol(_ForwardIterator __first, _ForwardIterator __last);
 template <class _ForwardIterator>
 _ForwardIterator
 __parse_bracket_expression(_ForwardIterator __first, _ForwardIterator __last);
 template <class _ForwardIterator>
 _ForwardIterator
 __parse_follow_list(_ForwardIterator __first, _ForwardIterator __last);
 template <class _ForwardIterator>
 _ForwardIterator
 __parse_expression_term(_ForwardIterator __first, _ForwardIterator __last);
 template <class _ForwardIterator>
 _ForwardIterator
 __parse_equivalence_class(_ForwardIterator __first, _ForwardIterator __last);
 template <class _ForwardIterator>
 _ForwardIterator
 __parse_character_class(_ForwardIterator __first, _ForwardIterator __last);
 template <class _ForwardIterator>
 _ForwardIterator
 __parse_collating_symbol(_ForwardIterator __first, _ForwardIterator __last);
 template <class _ForwardIterator>
 _ForwardIterator
 __parse_DUP_COUNT(_ForwardIterator __first, _ForwardIterator __last, int& __c);
 template <class _ForwardIterator>
 _ForwardIterator
 __parse_extended_reg_exp(_ForwardIterator __first, _ForwardIterator __last);
 template <class _ForwardIterator>
 _ForwardIterator
 __parse_ERE_branch(_ForwardIterator __first, _ForwardIterator __last);
 template <class _ForwardIterator>
 _ForwardIterator
 __parse_ERE_expression(_ForwardIterator __first, _ForwardIterator __last);
 template <class _ForwardIterator>
 _ForwardIterator
 __parse_one_char_or_coll_elem_ERE(_ForwardIterator __first, _ForwardIterator __last);
 template <class _ForwardIterator>
 _ForwardIterator
 __parse_ORD_CHAR_ERE(_ForwardIterator __first, _ForwardIterator __last);
 template <class _ForwardIterator>
 _ForwardIterator
 __parse_QUOTED_CHAR_ERE(_ForwardIterator __first, _ForwardIterator __last);

 void __push_l_anchor() {}
 void __push_r_anchor() {}
 void __push_match_any() {}
 void __push_greedy_inf_repeat(int __min) {}
 void __push_exact_repeat(int __count) {}
 void __push_repeat(int __min, int __max) {}
 void __start_nonmatching_list() {}
 void __start_matching_list() {}
 void __end_nonmatching_list() {}
 void __end_matching_list() {}
 void __push_char(value_type __c);
 void __push_char(const typename _Traits::string_type& __c) {}
 void __push_range() {}
 void __push_class_type(typename _Traits::char_class_type) {}
 void __push_back_ref(int __i) {}
 void __push_alternation() {}
};

template <class _CharT, class _Traits>
inline
basic_regex<_CharT, _Traits>::basic_regex()
 : __traits_(), __flags_(), __marked_count_(0)
{
}

template <class _CharT, class _Traits>
basic_regex<_CharT, _Traits>::~basic_regex()
{
}

template <class _CharT, class _Traits>
template <class _ForwardIterator>
void
basic_regex<_CharT, _Traits>::__parse(_ForwardIterator __first,
 _ForwardIterator __last)
{
 switch (__flags_ & 0x3F0)
 {
 case ECMAScript:
 break;
 case basic:
 __parse_basic_reg_exp(__first, __last);
 break;
 case extended:
 __parse_extended_reg_exp(__first, __last);
 break;
 case awk:
 break;
 case grep:
 break;
 case egrep:
 break;
 default:
 throw regex_error(regex_constants::error_temp);
 }
}

template <class _CharT, class _Traits>
template <class _ForwardIterator>
_ForwardIterator
basic_regex<_CharT, _Traits>::__parse_basic_reg_exp(_ForwardIterator __first,
 _ForwardIterator __last)
{
 if (__first != __last)
 {
 if (*__first == '^')
 {
 __push_l_anchor();
 ++__first;
 }
 if (__first != __last)
 {
 __first = __parse_RE_expression(__first, __last);
 if (__first != __last)
 {
 _ForwardIterator __temp = next(__first);
 if (__temp == __last && *__first == '$')
 {
 __push_r_anchor();
 ++__first;
 }
 }
 }
 if (__first != __last)
 throw regex_error(regex_constants::error_temp);
 }
 return __first;
}

template <class _CharT, class _Traits>
template <class _ForwardIterator>
_ForwardIterator
basic_regex<_CharT, _Traits>::__parse_extended_reg_exp(_ForwardIterator __first,
 _ForwardIterator __last)
{
 while (true)
 {
 _ForwardIterator __temp = __parse_ERE_branch(__first, __last);
 if (__temp == __first)
 throw regex_error(regex_constants::error_temp);
 __first = __temp;
 if (__first == __last)
 break;
 if (*__first != '|')
 throw regex_error(regex_constants::error_temp);
 __push_alternation();
 ++__first;
 }
 return __first;
}

template <class _CharT, class _Traits>
template <class _ForwardIterator>
_ForwardIterator
basic_regex<_CharT, _Traits>::__parse_ERE_branch(_ForwardIterator __first,
 _ForwardIterator __last)
{
 _ForwardIterator __temp = __parse_ERE_expression(__first, __last);
 if (__temp == __first)
 throw regex_error(regex_constants::error_temp);
 do
 {
 __first = __temp;
 __temp = __parse_ERE_expression(__first, __last);
 } while (__temp != __first);
 return __first;
}

template <class _CharT, class _Traits>
template <class _ForwardIterator>
_ForwardIterator
basic_regex<_CharT, _Traits>::__parse_ERE_expression(_ForwardIterator __first,
 _ForwardIterator __last)
{
 _ForwardIterator __temp = __parse_one_char_or_coll_elem_ERE(__first, __last);
 if (__temp == __first && __temp != __last)
 {
 switch (*__temp)
 {
 case '^':
 __push_l_anchor();
 ++__temp;
 break;
 case '$':
 __push_r_anchor();
 ++__temp;
 break;
 case '(':
 ++__marked_count_;
 ++__open_count_;
 __temp = __parse_extended_reg_exp(++__temp, __last);
 if (__temp == __last || *__temp != ')')
 throw regex_error(regex_constants::error_paren);
 --__open_count_;
 ++__temp;
 break;
 }
 }
 if (__temp != __first)
 __temp = __parse_ERE_dupl_symbol(__temp, __last);
 __first = __temp;
 return __first;
}

template <class _CharT, class _Traits>
template <class _ForwardIterator>
_ForwardIterator
basic_regex<_CharT, _Traits>::__parse_RE_expression(_ForwardIterator __first,
 _ForwardIterator __last)
{
 while (true)
 {
 _ForwardIterator __temp = __parse_simple_RE(__first, __last);
 if (__temp == __first)
 break;
 __first = __temp;
 }
 return __first;
}

template <class _CharT, class _Traits>
template <class _ForwardIterator>
_ForwardIterator
basic_regex<_CharT, _Traits>::__parse_simple_RE(_ForwardIterator __first,
 _ForwardIterator __last)
{
 if (__first != __last)
 {
 _ForwardIterator __temp = __parse_nondupl_RE(__first, __last);
 if (__temp != __first)
 {
 __first = __temp;
 __first = __parse_RE_dupl_symbol(__first, __last);
 }
 }
 return __first;
}

template <class _CharT, class _Traits>
template <class _ForwardIterator>
_ForwardIterator
basic_regex<_CharT, _Traits>::__parse_nondupl_RE(_ForwardIterator __first,
 _ForwardIterator __last)
{
 _ForwardIterator __temp = __first;
 __first = __parse_one_char_or_coll_elem_RE(__first, __last);
 if (__temp == __first)
 {
 __temp = __parse_Back_open_paren(__first, __last);
 if (__temp != __first)
 {
 ++__marked_count_;
 __first = __parse_RE_expression(__temp, __last);
 __temp = __parse_Back_close_paren(__first, __last);
 if (__temp == __first)
 throw regex_error(regex_constants::error_paren);
 __first = __temp;
 }
 else
 __first = __parse_BACKREF(__first, __last);
 }
 return __first;
}

template <class _CharT, class _Traits>
template <class _ForwardIterator>
_ForwardIterator
basic_regex<_CharT, _Traits>::__parse_one_char_or_coll_elem_RE(
 _ForwardIterator __first,
 _ForwardIterator __last)
{
 _ForwardIterator __temp = __parse_ORD_CHAR(__first, __last);
 if (__temp == __first)
 {
 __temp = __parse_QUOTED_CHAR(__first, __last);
 if (__temp == __first)
 {
 if (__temp != __last && *__temp == '.')
 {
 __push_match_any();
 ++__temp;
 }
 else
 __temp = __parse_bracket_expression(__first, __last);
 }
 }
 __first = __temp;
 return __first;
}

template <class _CharT, class _Traits>
template <class _ForwardIterator>
_ForwardIterator
basic_regex<_CharT, _Traits>::__parse_one_char_or_coll_elem_ERE(
 _ForwardIterator __first,
 _ForwardIterator __last)
{
 _ForwardIterator __temp = __parse_ORD_CHAR_ERE(__first, __last);
 if (__temp == __first)
 {
 __temp = __parse_QUOTED_CHAR_ERE(__first, __last);
 if (__temp == __first)
 {
 if (__temp != __last && *__temp == '.')
 {
 __push_match_any();
 ++__temp;
 }
 else
 __temp = __parse_bracket_expression(__first, __last);
 }
 }
 __first = __temp;
 return __first;
}

template <class _CharT, class _Traits>
template <class _ForwardIterator>
_ForwardIterator
basic_regex<_CharT, _Traits>::__parse_Back_open_paren(_ForwardIterator __first,
 _ForwardIterator __last)
{
 if (__first != __last)
 {
 _ForwardIterator __temp = next(__first);
 if (__temp != __last)
 {
 if (*__first == '\\' && *__temp == '(')
 __first = ++__temp;
 }
 }
 return __first;
}

template <class _CharT, class _Traits>
template <class _ForwardIterator>
_ForwardIterator
basic_regex<_CharT, _Traits>::__parse_Back_close_paren(_ForwardIterator __first,
 _ForwardIterator __last)
{
 if (__first != __last)
 {
 _ForwardIterator __temp = next(__first);
 if (__temp != __last)
 {
 if (*__first == '\\' && *__temp == ')')
 __first = ++__temp;
 }
 }
 return __first;
}

template <class _CharT, class _Traits>
template <class _ForwardIterator>
_ForwardIterator
basic_regex<_CharT, _Traits>::__parse_Back_open_brace(_ForwardIterator __first,
 _ForwardIterator __last)
{
 if (__first != __last)
 {
 _ForwardIterator __temp = next(__first);
 if (__temp != __last)
 {
 if (*__first == '\\' && *__temp == '{')
 __first = ++__temp;
 }
 }
 return __first;
}

template <class _CharT, class _Traits>
template <class _ForwardIterator>
_ForwardIterator
basic_regex<_CharT, _Traits>::__parse_Back_close_brace(_ForwardIterator __first,
 _ForwardIterator __last)
{
 if (__first != __last)
 {
 _ForwardIterator __temp = next(__first);
 if (__temp != __last)
 {
 if (*__first == '\\' && *__temp == '}')
 __first = ++__temp;
 }
 }
 return __first;
}

template <class _CharT, class _Traits>
template <class _ForwardIterator>
_ForwardIterator
basic_regex<_CharT, _Traits>::__parse_BACKREF(_ForwardIterator __first,
 _ForwardIterator __last)
{
 if (__first != __last)
 {
 _ForwardIterator __temp = next(__first);
 if (__temp != __last)
 {
 if (*__first == '\\' && '1' <= *__temp && *__temp <= '9')
 {
 __push_back_ref(*__temp - '0');
 __first = ++__temp;
 }
 }
 }
 return __first;
}

template <class _CharT, class _Traits>
template <class _ForwardIterator>
_ForwardIterator
basic_regex<_CharT, _Traits>::__parse_ORD_CHAR(_ForwardIterator __first,
 _ForwardIterator __last)
{
 if (__first != __last)
 {
 _ForwardIterator __temp = next(__first);
 if (__temp == __last && *__first == '$')
 return __first;
 // Not called inside a bracket
 if (*__first == '.' || *__first == '\\' || *__first == '[')
 return __first;
 __push_char(*__first);
 ++__first;
 }
 return __first;
}

template <class _CharT, class _Traits>
template <class _ForwardIterator>
_ForwardIterator
basic_regex<_CharT, _Traits>::__parse_ORD_CHAR_ERE(_ForwardIterator __first,
 _ForwardIterator __last)
{
 if (__first != __last)
 {
 switch (*__first)
 {
 case '^':
 case '.':
 case '[':
 case '$':
 case '(':
 case '|':
 case '*':
 case '+':
 case '?':
 case '{':
 case '\\':
 break;
 case ')':
 if (__open_count_ == 0)
 {
 __push_char(*__first);
 ++__first;
 }
 break;
 default:
 __push_char(*__first);
 ++__first;
 break;
 }
 }
 return __first;
}

template <class _CharT, class _Traits>
template <class _ForwardIterator>
_ForwardIterator
basic_regex<_CharT, _Traits>::__parse_QUOTED_CHAR(_ForwardIterator __first,
 _ForwardIterator __last)
{
 if (__first != __last)
 {
 _ForwardIterator __temp = next(__first);
 if (__temp != __last)
 {
 if (*__first == '\\')
 {
 switch (*__temp)
 {
 case '^':
 case '.':
 case '*':
 case '[':
 case '$':
 case '\\':
 __push_char(*__temp);
 __first = ++__temp;
 break;
 }
 }
 }
 }
 return __first;
}

template <class _CharT, class _Traits>
template <class _ForwardIterator>
_ForwardIterator
basic_regex<_CharT, _Traits>::__parse_QUOTED_CHAR_ERE(_ForwardIterator __first,
 _ForwardIterator __last)
{
 if (__first != __last)
 {
 _ForwardIterator __temp = next(__first);
 if (__temp != __last)
 {
 if (*__first == '\\')
 {
 switch (*__temp)
 {
 case '^':
 case '.':
 case '*':
 case '[':
 case '$':
 case '\\':
 case '(':
 case ')':
 case '|':
 case '+':
 case '?':
 case '{':
 __push_char(*__temp);
 __first = ++__temp;
 break;
 }
 }
 }
 }
 return __first;
}

template <class _CharT, class _Traits>
template <class _ForwardIterator>
_ForwardIterator
basic_regex<_CharT, _Traits>::__parse_RE_dupl_symbol(_ForwardIterator __first,
 _ForwardIterator __last)
{
 if (__first != __last)
 {
 if (*__first == '*')
 {
 __push_greedy_inf_repeat(0);
 ++__first;
 }
 else
 {
 _ForwardIterator __temp = __parse_Back_open_brace(__first, __last);
 if (__temp != __first)
 {
 int __min = 0;
 __first = __temp;
 __temp = __parse_DUP_COUNT(__first, __last, __min);
 if (__temp == __first)
 throw regex_error(regex_constants::error_badbrace);
 __first = __temp;
 if (__first == __last)
 throw regex_error(regex_constants::error_brace);
 if (*__first != ',')
 {
 __temp = __parse_Back_close_brace(__first, __last);
 if (__temp == __first)
 throw regex_error(regex_constants::error_brace);
 __push_exact_repeat(__min);
 __first = __temp;
 }
 else
 {
 ++__first; // consume ','
 int __max = -1;
 __first = __parse_DUP_COUNT(__first, __last, __max);
 __temp = __parse_Back_close_brace(__first, __last);
 if (__temp == __first)
 throw regex_error(regex_constants::error_brace);
 if (__max == -1)
 __push_greedy_inf_repeat(__min);
 else
 {
 if (__max < __min)
 throw regex_error(regex_constants::error_badbrace);
 __push_repeat(__min, __max);
 }
 __first = __temp;
 }
 }
 }
 }
 return __first;
}

template <class _CharT, class _Traits>
template <class _ForwardIterator>
_ForwardIterator
basic_regex<_CharT, _Traits>::__parse_ERE_dupl_symbol(_ForwardIterator __first,
 _ForwardIterator __last)
{
 if (__first != __last)
 {
 switch (*__first)
 {
 case '*':
 __push_greedy_inf_repeat(0);
 ++__first;
 break;
 case '+':
 __push_greedy_inf_repeat(1);
 ++__first;
 break;
 case '?':
 __push_repeat(0, 1);
 ++__first;
 break;
 case '{':
 {
 int __min;
 _ForwardIterator __temp = __parse_DUP_COUNT(__first, __last, __min);
 if (__temp == __first)
 throw regex_error(regex_constants::error_badbrace);
 __first = __temp;
 if (__first == __last)
 throw regex_error(regex_constants::error_brace);
 switch (*__first)
 {
 case '}':
 __push_exact_repeat(__min);
 ++__first;
 break;
 case ',':
 if (++__first == __last)
 throw regex_error(regex_constants::error_badbrace);
 if (*__first == '}')
 {
 __push_greedy_inf_repeat(__min);
 ++__first;
 }
 else
 {
 int __max;
 __temp = __parse_DUP_COUNT(__first, __last, __max);
 if (__temp == __first)
 throw regex_error(regex_constants::error_brace);
 __first = __temp;
 if (__first == __last || *__first != '}')
 throw regex_error(regex_constants::error_brace);
 ++__first;
 if (__max < __min)
 throw regex_error(regex_constants::error_badbrace);
 __push_repeat(__min, __max);
 }
 default:
 throw regex_error(regex_constants::error_badbrace);
 }
 }
 break;
 }
 }
 return __first;
}

template <class _CharT, class _Traits>
template <class _ForwardIterator>
_ForwardIterator
basic_regex<_CharT, _Traits>::__parse_bracket_expression(_ForwardIterator __first,
 _ForwardIterator __last)
{
 if (__first != __last && *__first == '[')
 {
 if (++__first == __last)
 throw regex_error(regex_constants::error_brack);
 bool __non_matching = false;
 if (*__first == '^')
 {
 ++__first;
 __non_matching = true;
 __start_nonmatching_list();
 }
 else
 __start_matching_list();
 if (__first == __last)
 throw regex_error(regex_constants::error_brack);
 if (*__first == ']')
 {
 __push_char(']');
 ++__first;
 }
 __first = __parse_follow_list(__first, __last);
 if (__first == __last)
 throw regex_error(regex_constants::error_brack);
 if (*__first == '-')
 {
 __push_char('-');
 ++__first;
 }
 if (__first == __last || *__first != ']')
 throw regex_error(regex_constants::error_brack);
 if (__non_matching)
 __end_nonmatching_list();
 else
 __end_matching_list();
 ++__first;
 }
 return __first;
}

template <class _CharT, class _Traits>
template <class _ForwardIterator>
_ForwardIterator
basic_regex<_CharT, _Traits>::__parse_follow_list(_ForwardIterator __first,
 _ForwardIterator __last)
{
 if (__first != __last)
 {
 while (true)
 {
 _ForwardIterator __temp = __parse_expression_term(__first, __last);
 if (__temp == __first)
 break;
 __first = __temp;
 }
 }
 return __first;
}

template <class _CharT, class _Traits>
template <class _ForwardIterator>
_ForwardIterator
basic_regex<_CharT, _Traits>::__parse_expression_term(_ForwardIterator __first,
 _ForwardIterator __last)
{
 if (__first != __last && *__first != ']')
 {
 bool __parsed_one = false;
 _ForwardIterator __temp = next(__first);
 if (__temp != __last && *__first == '[')
 {
 if (*__temp == '=')
 return __parse_equivalence_class(++__temp, __last);
 else if (*__temp == ':')
 return __parse_character_class(++__temp, __last);
 else if (*__temp == '.')
 {
 __first = __parse_collating_symbol(++__temp, __last);
 __parsed_one = true;
 }
 }
 if (!__parsed_one)
 {
 __push_char(*__first);
 ++__first;
 }
 if (__first != __last && *__first != ']')
 {
 __temp = next(__first);
 if (__temp != __last && *__first == '-' && *__temp != ']')
 {
 // parse a range
 __first = __temp;
 ++__temp;
 if (__temp != __last && *__first == '[' && *__temp == '.')
 __first = __parse_collating_symbol(++__temp, __last);
 else
 {
 __push_char(*__first);
 ++__first;
 }
 __push_range();
 }
 }
 }
 return __first;
}

template <class _CharT, class _Traits>
template <class _ForwardIterator>
_ForwardIterator
basic_regex<_CharT, _Traits>::__parse_equivalence_class(_ForwardIterator __first,
 _ForwardIterator __last)
{
 // Found [=
 // This means =] must exist
 value_type _Equal_close[2] = {'=', ']'};
 _ForwardIterator __temp = _STD::search(__first, __last, _Equal_close,
 _Equal_close+2);
 if (__temp == __last)
 throw regex_error(regex_constants::error_brack);
 // [__first, __temp) contains all text in [= ... =]
 typedef typename _Traits::string_type string_type;
 string_type __collate_name =
 __traits_.lookup_collatename(__first, __temp);
 if (__collate_name.empty())
 throw regex_error(regex_constants::error_brack);
 string_type __equiv_name =
 __traits_.transform_primary(__collate_name.begin(),
 __collate_name.end());
 if (!__equiv_name.empty())
 __push_char(__equiv_name);
 else
 __push_char(__collate_name);
 __first = next(__temp, 2);
 return __first;
}

template <class _CharT, class _Traits>
template <class _ForwardIterator>
_ForwardIterator
basic_regex<_CharT, _Traits>::__parse_character_class(_ForwardIterator __first,
 _ForwardIterator __last)
{
 // Found [:
 // This means :] must exist
 value_type _Colon_close[2] = {':', ']'};
 _ForwardIterator __temp = _STD::search(__first, __last, _Colon_close,
 _Colon_close+2);
 if (__temp == __last)
 throw regex_error(regex_constants::error_brack);
 // [__first, __temp) contains all text in [: ... :]
 typedef typename _Traits::char_class_type char_class_type;
 char_class_type __class_type =
 __traits_.lookup_classname(__first, __temp, __flags_ & icase);
 if (__class_type == 0)
 throw regex_error(regex_constants::error_brack);
 __push_class_type(__class_type);
 __first = next(__temp, 2);
 return __first;
}

template <class _CharT, class _Traits>
template <class _ForwardIterator>
_ForwardIterator
basic_regex<_CharT, _Traits>::__parse_collating_symbol(_ForwardIterator __first,
 _ForwardIterator __last)
{
 // Found [.
 // This means .] must exist
 value_type _Dot_close[2] = {'.', ']'};
 _ForwardIterator __temp = _STD::search(__first, __last, _Dot_close,
 _Dot_close+2);
 if (__temp == __last)
 throw regex_error(regex_constants::error_brack);
 // [__first, __temp) contains all text in [. ... .]
 typedef typename _Traits::string_type string_type;
 string_type __collate_name =
 __traits_.lookup_collatename(__first, __temp);
 if (__collate_name.empty())
 throw regex_error(regex_constants::error_brack);
 __push_char(__collate_name);
 __first = next(__temp, 2);
 return __first;
}

template <class _CharT, class _Traits>
template <class _ForwardIterator>
_ForwardIterator
basic_regex<_CharT, _Traits>::__parse_DUP_COUNT(_ForwardIterator __first,
 _ForwardIterator __last,
 int& __c)
{
 if (__first != __last && '0' <= *__first && *__first <= '9')
 {
 __c = *__first - '0';
 for (++__first; __first != __last && '0' <= *__first && *__first <= '9';
 ++__first)
 {
 __c *= 10;
 __c += *__first - '0';
 }
 }
 return __first;
}

template <class _CharT, class _Traits>
void
basic_regex<_CharT, _Traits>::__push_char(value_type __c)
{
 unique_ptr<__state<_CharT> > __new_end(new __state<_CharT>);
 unique_ptr<__transition<_CharT> > __new_transition(
 new __match_char<_CharT>(__c, true, __new_end.get()));
 __state<_CharT>* __e = __new_end.release();
 if (__end_ == nullptr)
 {
 __start_.reset(new __state<_CharT>);
 __end_ = __start_.get();
 }
 __end_->__add_one(__new_transition.release());
 __end_ = __e;
}

typedef basic_regex<char> regex;
typedef basic_regex<wchar_t> wregex;

// sub_match

template <class _BidirectionalIterator>
class sub_match
 : public pair<_BidirectionalIterator, _BidirectionalIterator>
{
public:
 typedef _BidirectionalIterator iterator;
 typedef typename iterator_traits<iterator>::value_type value_type;
 typedef typename iterator_traits<iterator>::difference_type difference_type;
 typedef basic_string<value_type> string_type;

 bool matched;

 difference_type length() const
 {return matched ? _STD::distance(this->first, this->second) : 0;}
 string_type str() const
 {return matched ? string_type(this->first, this->second) : string_type();}
 operator string_type() const
 {return str();}

 int compare(const sub_match& __s) const
 {return str().compare(__s.str());}
 int compare(const string_type& __s) const
 {return str().compare(__s);}
 int compare(const value_type* __s) const
 {return str().compare(__s);}
};

typedef sub_match<const char*> csub_match;
typedef sub_match<const wchar_t*> wcsub_match;
typedef sub_match<string::const_iterator> ssub_match;
typedef sub_match<wstring::const_iterator> wssub_match;

template <class _BiIter>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator==(const sub_match<_BiIter>& __x, const sub_match<_BiIter>& __y)
{
 return __x.compare(__y) == 0;
}

template <class _BiIter>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator!=(const sub_match<_BiIter>& __x, const sub_match<_BiIter>& __y)
{
 return !(__x == __y);
}

template <class _BiIter>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator<(const sub_match<_BiIter>& __x, const sub_match<_BiIter>& __y)
{
 return __x.compare(__y) < 0;
}

template <class _BiIter>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator<=(const sub_match<_BiIter>& __x, const sub_match<_BiIter>& __y)
{
 return !(__y < __x);
}

template <class _BiIter>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator>=(const sub_match<_BiIter>& __x, const sub_match<_BiIter>& __y)
{
 return !(__x < __y);
}

template <class _BiIter>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator>(const sub_match<_BiIter>& __x, const sub_match<_BiIter>& __y)
{
 return __y < __x;
}

template <class _BiIter, class _ST, class _SA>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator==(const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __x,
 const sub_match<_BiIter>& __y)
{
 return __y.compare(__x.c_str()) == 0;
}

template <class _BiIter, class _ST, class _SA>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator!=(const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __x,
 const sub_match<_BiIter>& __y)
{
 return !(__x == __y);
}

template <class _BiIter, class _ST, class _SA>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator<(const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __x,
 const sub_match<_BiIter>& __y)
{
 return __y.compare(__x.c_str()) > 0;
}

template <class _BiIter, class _ST, class _SA>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator>(const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __x,
 const sub_match<_BiIter>& __y)
{
 return __y < __x;
}

template <class _BiIter, class _ST, class _SA>
inline _LIBCPP_INLINE_VISIBILITY
bool operator>=(const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __x,
 const sub_match<_BiIter>& __y)
{
 return !(__x < __y);
}

template <class _BiIter, class _ST, class _SA>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator<=(const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __x,
 const sub_match<_BiIter>& __y)
{
 return !(__y < __x);
}

template <class _BiIter, class _ST, class _SA>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator==(const sub_match<_BiIter>& __x,
 const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __y)
{
 return __x.compare(__y.c_str()) == 0;
}

template <class _BiIter, class _ST, class _SA>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator!=(const sub_match<_BiIter>& __x,
 const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __y)
{
 return !(__x == __y);
}

template <class _BiIter, class _ST, class _SA>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator<(const sub_match<_BiIter>& __x,
 const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __y)
{
 return __x.compare(__y.c_str()) < 0;
}

template <class _BiIter, class _ST, class _SA>
inline _LIBCPP_INLINE_VISIBILITY
bool operator>(const sub_match<_BiIter>& __x,
 const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __y)
{
 return __y < __x;
}

template <class _BiIter, class _ST, class _SA>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator>=(const sub_match<_BiIter>& __x,
 const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __y)
{
 return !(__x < __y);
}

template <class _BiIter, class _ST, class _SA>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator<=(const sub_match<_BiIter>& __x,
 const basic_string<typename iterator_traits<_BiIter>::value_type, _ST, _SA>& __y)
{
 return !(__y < __x);
}

template <class _BiIter>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator==(typename iterator_traits<_BiIter>::value_type const* __x,
 const sub_match<_BiIter>& __y)
{
 return __y.compare(__x) == 0;
}

template <class _BiIter>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator!=(typename iterator_traits<_BiIter>::value_type const* __x,
 const sub_match<_BiIter>& __y)
{
 return !(__x == __y);
}

template <class _BiIter>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator<(typename iterator_traits<_BiIter>::value_type const* __x,
 const sub_match<_BiIter>& __y)
{
 return __y.compare(__x) > 0;
}

template <class _BiIter>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator>(typename iterator_traits<_BiIter>::value_type const* __x,
 const sub_match<_BiIter>& __y)
{
 return __y < __x;
}

template <class _BiIter>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator>=(typename iterator_traits<_BiIter>::value_type const* __x,
 const sub_match<_BiIter>& __y)
{
 return !(__x < __y);
}

template <class _BiIter>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator<=(typename iterator_traits<_BiIter>::value_type const* __x,
 const sub_match<_BiIter>& __y)
{
 return !(__y < __x);
}

template <class _BiIter>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator==(const sub_match<_BiIter>& __x,
 typename iterator_traits<_BiIter>::value_type const* __y)
{
 return __x.compare(__y) == 0;
}

template <class _BiIter>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator!=(const sub_match<_BiIter>& __x,
 typename iterator_traits<_BiIter>::value_type const* __y)
{
 return !(__x == __y);
}

template <class _BiIter>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator<(const sub_match<_BiIter>& __x,
 typename iterator_traits<_BiIter>::value_type const* __y)
{
 return __x.compare(__y) < 0;
}

template <class _BiIter>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator>(const sub_match<_BiIter>& __x,
 typename iterator_traits<_BiIter>::value_type const* __y)
{
 return __y < __x;
}

template <class _BiIter>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator>=(const sub_match<_BiIter>& __x,
 typename iterator_traits<_BiIter>::value_type const* __y)
{
 return !(__x < __y);
}

template <class _BiIter>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator<=(const sub_match<_BiIter>& __x,
 typename iterator_traits<_BiIter>::value_type const* __y)
{
 return !(__y < __x);
}

template <class _BiIter>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator==(typename iterator_traits<_BiIter>::value_type const& __x,
 const sub_match<_BiIter>& __y)
{
 typedef basic_string<typename iterator_traits<_BiIter>::value_type> string_type;
 return __y.compare(string_type(1, __x)) == 0;
}

template <class _BiIter>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator!=(typename iterator_traits<_BiIter>::value_type const& __x,
 const sub_match<_BiIter>& __y)
{
 return !(__x == __y);
}

template <class _BiIter>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator<(typename iterator_traits<_BiIter>::value_type const& __x,
 const sub_match<_BiIter>& __y)
{
 typedef basic_string<typename iterator_traits<_BiIter>::value_type> string_type;
 return __y.compare(string_type(1, __x)) > 0;
}

template <class _BiIter>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator>(typename iterator_traits<_BiIter>::value_type const& __x,
 const sub_match<_BiIter>& __y)
{
 return __y < __x;
}

template <class _BiIter>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator>=(typename iterator_traits<_BiIter>::value_type const& __x,
 const sub_match<_BiIter>& __y)
{
 return !(__x < __y);
}

template <class _BiIter>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator<=(typename iterator_traits<_BiIter>::value_type const& __x,
 const sub_match<_BiIter>& __y)
{
 return !(__y < __x);
}

template <class _BiIter>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator==(const sub_match<_BiIter>& __x,
 typename iterator_traits<_BiIter>::value_type const& __y)
{
 typedef basic_string<typename iterator_traits<_BiIter>::value_type> string_type;
 return __x.compare(string_type(1, __y)) == 0;
}

template <class _BiIter>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator!=(const sub_match<_BiIter>& __x,
 typename iterator_traits<_BiIter>::value_type const& __y)
{
 return !(__x == __y);
}

template <class _BiIter>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator<(const sub_match<_BiIter>& __x,
 typename iterator_traits<_BiIter>::value_type const& __y)
{
 typedef basic_string<typename iterator_traits<_BiIter>::value_type> string_type;
 return __x.compare(string_type(1, __y)) < 0;
}

template <class _BiIter>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator>(const sub_match<_BiIter>& __x,
 typename iterator_traits<_BiIter>::value_type const& __y)
{
 return __y < __x;
}

template <class _BiIter>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator>=(const sub_match<_BiIter>& __x,
 typename iterator_traits<_BiIter>::value_type const& __y)
{
 return !(__x < __y);
}

template <class _BiIter>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator<=(const sub_match<_BiIter>& __x,
 typename iterator_traits<_BiIter>::value_type const& __y)
{
 return !(__y < __x);
}

template <class _CharT, class _ST, class _BiIter>
inline _LIBCPP_INLINE_VISIBILITY
basic_ostream<_CharT, _ST>&
operator<<(basic_ostream<_CharT, _ST>& __os, const sub_match<_BiIter>& __m)
{
 return __os << __m.str();
}

_LIBCPP_END_NAMESPACE_STD

#endif // _LIBCPP_REGEX