template< typename T >
type_with_size<3> allocator_picker( arena_allocator<T> const &, int );

template<> struct rebind_helper<3>
{
	template< typename, typename ElemT>
	struct inner
	{
		typedef arena_allocator<ElemT> type;
	};
};

// --------------------------------------------------------------------------
//
// Class:       sub_expr_base
//
// Description: patterns are "compiled" into a directed graph of sub_expr_base
//              structs.  Matching is accomplished by traversing this graph.
//
// Methods:     ~sub_expr_base - virt dtor so cleanup happens correctly
//              recursive_match_all      - match this sub-expression and all following
//                               sub-expression
//
// History:     8/14/2000 - ericne - Created
//
// --------------------------------------------------------------------------
template< typename IterT >
struct sub_expr_base
{
    virtual bool recursive_match_all_s( match_param<IterT> &, IterT ) const = 0; //throw() (offset 0)
    virtual bool recursive_match_all_c( match_param<IterT> &, IterT ) const = 0; //throw() (offset 4)
    virtual bool iterative_match_this_s( match_param<IterT> & ) const = 0; //throw()       (offset 8)
    virtual bool iterative_match_this_c( match_param<IterT> & ) const = 0; //throw()       (offset 12)
    virtual bool iterative_rematch_this_s( match_param<IterT> & ) const = 0; //throw()     (offset 16)
    virtual bool iterative_rematch_this_c( match_param<IterT> & ) const = 0; //throw()     (offset 20)

    virtual ~sub_expr_base() = 0;                                                       // (offset 24)

    // Use the regex_arena for memory management
    static void * operator new( size_t size, regex_arena & arena )
    {
        return arena.allocate( size );
    }
    static void operator delete( void *, regex_arena & )
    {
    }

    // Invoke the d'tor, but don't bother freeing memory. That will
    // happen automatically when the arena object gets destroyed.
    static void operator delete( void * )
    {
    }

    // For choosing an appropriate virtual function based on a compile time constant
    bool recursive_match_all( match_param<IterT> & param, IterT icur, false_t ) const //throw()
    {
        return recursive_match_all_s( param, icur );
    }
    bool recursive_match_all( match_param<IterT> & param, IterT icur, true_t ) const //throw()
    {
        return recursive_match_all_c( param, icur );
    }
    bool iterative_match_this( match_param<IterT> & param, false_t ) const //throw()
    {
        return iterative_match_this_s( param );
    }
    bool iterative_match_this( match_param<IterT> & param, true_t ) const //throw()
    {
        return iterative_match_this_c( param );
    }
    bool iterative_rematch_this( match_param<IterT> & param, false_t ) const //throw()
    {
        return iterative_rematch_this_s( param );
    }
    bool iterative_rematch_this( match_param<IterT> & param, true_t ) const //throw()
    {
        return iterative_rematch_this_c( param );
    }
private:
    // don't allocate sub-expressions directly on the heap; they should
    // be allocated from an arena
    static void * operator new( size_t size ) throw( std::bad_alloc );
    // disable all the vector new's and delete's.
    static void * operator new[]( size_t size, regex_arena & arena ) throw( std::bad_alloc );
    static void operator delete[]( void *, regex_arena & );
    static void * operator new[]( size_t size ) throw( std::bad_alloc );
    static void operator delete[]( void * );
};

template< typename IterT >
inline sub_expr_base<IterT>::~sub_expr_base()
{
}

// --------------------------------------------------------------------------
//
// Class:       subst_node
//
// Description: Substitution strings are parsed into an array of these
//              structures in order to speed up subst operations.
//
// Members:     stype         - type of this struct
//              .m_subst_string  - do a string substitution
//             .m_subst_backref - do a bacref substitution
//              op            - execute an operation
//
// History:     8/14/2000 - ericne - Created
//
// --------------------------------------------------------------------------
struct subst_node
{
    enum
    {
        PREMATCH  = -1,
        POSTMATCH = -2
    };

    enum subst_type
    {
        SUBST_STRING,
        SUBST_BACKREF,
        SUBST_OP
    };

    enum op_type
    {
        UPPER_ON   = SUBST_UPPER_ON,
        UPPER_NEXT = SUBST_UPPER_NEXT,
        LOWER_ON   = SUBST_LOWER_ON,
        LOWER_NEXT = SUBST_LOWER_NEXT,
        ALL_OFF    = SUBST_ALL_OFF
    };

    struct string_offsets
    {
        ptrdiff_t       m_rstart;
        ptrdiff_t       m_rlength;
    };

    subst_type          m_stype;

    union
    {
        string_offsets  m_subst_string;
        size_t          m_subst_backref;
        op_type         m_op;
    };
};

typedef std::list<subst_node> subst_list_type;
size_t DEFAULT_BLOCK_SIZE();

template< typename IterT >
class boyer_moore;

// --------------------------------------------------------------------------
//
// Class:       basic_rpattern_base_impl
//
// Description:
//
// Methods:     basic_rpattern_base_impl - ctor
//              flags                   - get the state of the flags
//              uses_backrefs           - true if the backrefs are referenced
//              get_first_subexpression - return ptr to first sub_expr struct
//              get_width               - get min/max nbr chars this pattern can match
//              loops                   - if false, we only need to try to match at 1st position
//              cgroups                 - number of visible groups
//              _cgroups_total          - total number of groups, including hidden ( ?: ) groups
//              get_pat                 - get string representing the pattern
//              get_subst               - get string representing the substitution string
//              get_subst_list          - get the list of subst nodes
//              _normalize_string       - perform character escaping
//
// Members:     m_fuses_backrefs        - true if subst string refers to backrefs
//              m_floop                 - false if pat only needs to be matched in one place
//              m_cgroups               - total count of groups
//              m_cgroups_visible       - count of visible groups
//              m_flags                 - the flags
//              m_nwidth                - width of this pattern
//              m_pat                   - pattern string
//              m_subst                 - substitution string
//              m_subst_list            - list of substitution nodes
//              m_pfirst                - ptr to first subexpression to match
//
// Typedefs:    char_type               -
//              string_type             -
//              size_type               -
//
// History:     8/14/2000 - ericne - Created
//
// --------------------------------------------------------------------------
template< typename IterT >
class basic_rpattern_base_impl
{
    basic_rpattern_base_impl( basic_rpattern_base_impl<IterT> const & );
    basic_rpattern_base_impl & operator=( basic_rpattern_base_impl<IterT> const & );
protected:
    typedef typename std::iterator_traits<IterT>::value_type char_type;
    typedef std::char_traits<char_type>                   traits_type;

    typedef std::basic_string<char_type>                  string_type;
    typedef size_t                                        size_type;

    typedef backref_tag<IterT>                             backref_type;
    typedef std::vector<backref_type>                     backref_vector;

    friend struct regex_access<IterT>;

    explicit basic_rpattern_base_impl
    (
        REGEX_FLAGS         flags = NOFLAGS,
        REGEX_MODE          mode  = MODE_DEFAULT,
        string_type const & pat   = string_type(),
        string_type const & subst = string_type()
    )                                               //throw()
        : m_arena( DEFAULT_BLOCK_SIZE() )
        , m_fuses_backrefs( false )
        , m_floop( true )
        , m_fok_to_recurse( true )
        , m_cgroups( 0 )
        , m_cgroups_visible( 0 )
        , m_flags( flags )
        , m_mode( mode )
        , m_nwidth( uninit_width() )
        , m_pat( new string_type( pat ) )
        , m_subst( new string_type( subst ) )
        , m_subst_list()
        , m_pfirst( 0 )
        , m_invisible_groups()
        , m_search( 0 )
    {
    }

    virtual ~basic_rpattern_base_impl()
    {
        // We're not going to be calling destructors because all allocated
        // memory associated with the parsed pattern resides in the arena.
        // The memory will be freed when the arena gets destroyed.
        //delete m_pfirst;
        reset_auto_ptr( m_pat );
        reset_auto_ptr( m_subst );
        m_arena.finalize();
    }

    regex_arena m_arena;           // The sub_expr arena

    bool        m_fuses_backrefs;  // true if the substitution uses backrefs
    bool        m_floop;           // false if m_pfirst->recursive_match_all only needs to be called once
    bool        m_fok_to_recurse;  // false if the pattern would recurse too deeply
    size_t      m_cgroups;         // number of groups ( always at least one )
    size_t      m_cgroups_visible; // number of visible groups
    REGEX_FLAGS m_flags;           // flags used to customize search/replace
    REGEX_MODE  m_mode;            // Used to pick the fast or safe algorithm
    width_type  m_nwidth;          // width of the pattern

    std::auto_ptr<string_type>   m_pat;   // contains the unparsed pattern
    std::auto_ptr<string_type>   m_subst; // contains the unparsed substitution

    subst_list_type              m_subst_list; // used to speed up substitution
    sub_expr_base<IterT> const * m_pfirst;     // first subexpression in pattern

    std::list<size_t>           m_invisible_groups; // groups w/o backrefs

    boyer_moore<typename string_type::const_iterator>  * m_search;

    size_t _cgroups_total() const //throw()
    {
        return m_cgroups;
    }

    bool _loops() const //throw()
    {
        return m_floop;
    }

    size_t _get_next_group_nbr()
    {
        return m_cgroups++;
    }

    void _normalize_string( string_type & str ) const //throw()
    {
        if( NORMALIZE & flags() )
            process_escapes( str, true );
    }

    bool _save_backrefs() const //throw()
    {
        return m_fuses_backrefs || ! ( flags() & NOBACKREFS );
    }

    sub_expr_base<IterT> const * _get_first_subexpression() const //throw()
    {
        return m_pfirst;
    }

    REGEX_FLAGS flags() const //throw()
    {
        return m_flags;
    }

    REGEX_MODE mode() const // throw()
    {
        return m_mode;
    }

    width_type get_width() const //throw()
    {
        return m_nwidth;
    }

    size_t cgroups() const //throw()
    {
        return m_cgroups_visible;
    }

    string_type const & get_pat() const //throw()
    {
        return *m_pat;
    }

    string_type const & get_subst() const //throw()
    {
        return *m_subst;
    }

    bool _ok_to_recurse() const; //throw();

    void swap( basic_rpattern_base_impl<IterT> & that ); // throw();

    enum { npos = static_cast<size_type>( -1 ) };

    static instantiator instantiate()
    {
        typedef basic_rpattern_base_impl this_type;

        return instantiator_helper
        (
            &this_type::_ok_to_recurse,
            &this_type::swap
        );
    }
};

template< typename IterT >
struct regex_access
{
    typedef basic_rpattern_base_impl< IterT >    rpattern_type;
    typedef typename rpattern_type::size_type    size_type;
    typedef typename rpattern_type::char_type    char_type;
    typedef typename rpattern_type::traits_type  traits_type;
    typedef typename rpattern_type::backref_type backref_type;

    static bool _do_match_iterative_helper_s
    (
        sub_expr_base<IterT> const * expr,
        match_param<IterT> & param,
        IterT icur
    );

    static bool _do_match_iterative_helper_c
    (
        sub_expr_base<IterT> const * expr,
        match_param<IterT> & param,
        IterT icur
    );