deelx.h

// deelx.h
//
// DEELX Regular Expression Engine (v1.2)
//
// Copyright 2006 ~ 2012 (c) RegExLab.com
// All Rights Reserved.
//
// http://www.regexlab.com/deelx/
//
// Author: Ê·ÊÙΰ (sswater shi)
// sswater@gmail.com
//
// $Revision: 864 $
//

#ifndef __DEELX_REGEXP__H__
#define __DEELX_REGEXP__H__

#include <memory.h>
#include <ctype.h>
#include <limits.h>
#include <string.h>
#include <stdlib.h>

extern "C" {
  typedef int (*POSIX_FUNC)(int);
  int isblunk(int c);
}

//
// Data Reference
//
template <class ELT> class CBufferRefT
{
public:
  CBufferRefT(const ELT * pcsz, int length);
  CBufferRefT(const ELT * pcsz);

public:
  int nCompare      (const ELT * pcsz) const;
  int nCompareNoCase(const ELT * pcsz) const;
  int  Compare      (const ELT * pcsz) const;
  int  CompareNoCase(const ELT * pcsz) const;
  int  Compare      (const CBufferRefT <ELT> &) const;
  int  CompareNoCase(const CBufferRefT <ELT> &) const;

  ELT At          (int nIndex, ELT def = 0) const;
  ELT operator [] (int nIndex) const;

  const ELT * GetBuffer() const;
  int GetSize() const;

public:
  virtual ~CBufferRefT();

// Content
protected:
  ELT * m_pBuffer;
  int         m_nSize;
};

//
// Implemenation
//
template <class ELT> CBufferRefT <ELT> :: CBufferRefT(const ELT * pcsz, int length)
{
  m_pBuffer  = (ELT *)pcsz;
  m_nSize = length;
}

template <class ELT> CBufferRefT <ELT> :: CBufferRefT(const ELT * pcsz)
{
  m_pBuffer  = (ELT *)pcsz;
  m_nSize = 0;

  if(pcsz != 0) while(m_pBuffer[m_nSize] != 0) m_nSize ++;
}

template <class ELT> int CBufferRefT <ELT> :: nCompare(const ELT * pcsz) const
{
  for(int i=0; i<m_nSize; i++)
  {
    if(m_pBuffer[i] != pcsz[i])
      return m_pBuffer[i] - pcsz[i];
  }

  return 0;
}

template <class ELT> int CBufferRefT <ELT> :: nCompareNoCase(const ELT * pcsz) const
{
  for(int i=0; i<m_nSize; i++)
  {
    if(m_pBuffer[i] != pcsz[i])
    {
      if(toupper((int)m_pBuffer[i]) != toupper((int)pcsz[i]))
        return m_pBuffer[i] - pcsz[i];
    }
  }

  return 0;
}

template <class ELT> inline int CBufferRefT <ELT> :: Compare(const ELT * pcsz) const
{
  return nCompare(pcsz) ? 1 : (int)pcsz[m_nSize];
}

template <class ELT> inline int CBufferRefT <ELT> :: CompareNoCase(const ELT * pcsz) const
{
  return nCompareNoCase(pcsz) ? 1 : (int)pcsz[m_nSize];
}

template <class ELT> inline int CBufferRefT <ELT> :: Compare(const CBufferRefT <ELT> & cref) const
{
  return m_nSize == cref.m_nSize ? nCompare(cref.GetBuffer()) : 1;
}

template <class ELT> inline int CBufferRefT <ELT> :: CompareNoCase(const CBufferRefT <ELT> & cref) const
{
  return m_nSize == cref.m_nSize ? nCompareNoCase(cref.GetBuffer()) : 1;
}

template <class ELT> inline ELT CBufferRefT <ELT> :: At(int nIndex, ELT def) const
{
  return nIndex >= m_nSize ? def : m_pBuffer[nIndex];
}

template <class ELT> inline ELT CBufferRefT <ELT> :: operator [] (int nIndex) const
{
  return nIndex >= m_nSize ? 0 : m_pBuffer[nIndex];
}

template <class ELT> const ELT * CBufferRefT <ELT> :: GetBuffer() const
{
  static const ELT _def[] = {0}; return m_pBuffer ? m_pBuffer : _def;
}

template <class ELT> inline int CBufferRefT <ELT> :: GetSize() const
{
  return m_nSize;
}

template <class ELT> CBufferRefT <ELT> :: ~CBufferRefT()
{
}

//
// Data Buffer
//
template <class ELT> class CBufferT : public CBufferRefT <ELT>
{
public:
  CBufferT(const ELT * pcsz, int length);
  CBufferT(const ELT * pcsz);
  CBufferT();

public:
  ELT & operator [] (int nIndex);
  const ELT & operator [] (int nIndex) const;
  void  Append(const ELT * pcsz, int length, int eol = 0);
  void  Append(ELT el, int eol = 0);

public:
  void  Push(ELT   el);
  void  Push(const CBufferRefT<ELT> & buf);
  int   Pop (ELT & el);
  int   Pop (CBufferT<ELT> & buf);
  int   Peek(ELT & el) const;

public:
  const ELT * GetBuffer() const;
  ELT * GetBuffer();
  ELT * Detach();
  void  Release();
  void  Prepare(int index, int fill = 0);
  void  Restore(int size);

  ELT * PrepareInsert(int nPos, int nSize)
  {
    int nOldSize = CBufferRefT<ELT>::m_nSize;
    Restore(nPos > CBufferRefT<ELT>::m_nSize ? nPos : CBufferRefT<ELT>::m_nSize + nSize);

    if( nPos < nOldSize )
    {
      ELT * from = CBufferRefT<ELT>::m_pBuffer + nPos, * to = CBufferRefT<ELT>::m_pBuffer + nPos + nSize;
      memmove(to, from, sizeof(ELT) * (nOldSize - nPos));
    }

    return CBufferRefT<ELT>::m_pBuffer + nPos;
  }

  void Insert(int nIndex, const ELT & rT)
  {
    Insert(nIndex, &rT, 1);
  }

  void Insert(int nIndex, const ELT * pT, int nSize)
  {
    memcpy(PrepareInsert(nIndex, nSize), pT, sizeof(ELT) * nSize);
  }

  void Remove(int nIndex)
  {
    Remove(nIndex, 1);
  }

  void Remove(int nIndex, int nSize)
  {
    if( nIndex < CBufferRefT <ELT> :: m_nSize )
    {
      if( nIndex + nSize >= CBufferRefT <ELT> :: m_nSize )
      {
        Restore(nIndex);
      }
      else
      {
        memmove(CBufferRefT <ELT> :: m_pBuffer + nIndex, CBufferRefT <ELT> :: m_pBuffer + nIndex + nSize, sizeof(ELT) * (CBufferRefT <ELT> :: m_nSize - nIndex - nSize));
        Restore(CBufferRefT <ELT> :: m_nSize - nSize);
      }
    }
  }

  void SetMaxLength(int nSize)
  {
    if( nSize > m_nMaxLength )
    {
      if( m_nMaxLength < 8 )
        m_nMaxLength = 8;

      if( nSize > m_nMaxLength )
        m_nMaxLength *= 2;

      if( nSize > m_nMaxLength )
      {
        m_nMaxLength  = nSize + 11;
        m_nMaxLength -= m_nMaxLength & 0x07;
      }

      CBufferRefT <ELT> :: m_pBuffer = (ELT *) realloc(CBufferRefT <ELT> :: m_pBuffer, sizeof(ELT) * m_nMaxLength);
    }
  }

public:
  virtual ~CBufferT();

// Content
protected:
  int   m_nMaxLength;
};

//
// Implemenation
//
template <class ELT> CBufferT <ELT> :: CBufferT(const ELT * pcsz, int length) : CBufferRefT <ELT> (0, length)
{
  m_nMaxLength = CBufferRefT <ELT> :: m_nSize + 1;

  CBufferRefT <ELT> :: m_pBuffer = (ELT *) malloc(sizeof(ELT) * m_nMaxLength);
  memcpy(CBufferRefT<ELT>::m_pBuffer, pcsz, sizeof(ELT) * CBufferRefT <ELT> :: m_nSize);
  CBufferRefT<ELT>::m_pBuffer[CBufferRefT <ELT> :: m_nSize] = 0;
}

template <class ELT> CBufferT <ELT> :: CBufferT(const ELT * pcsz) : CBufferRefT <ELT> (pcsz)
{
  m_nMaxLength = CBufferRefT <ELT> :: m_nSize + 1;

  CBufferRefT <ELT> :: m_pBuffer = (ELT *) malloc(sizeof(ELT) * m_nMaxLength);
  memcpy(CBufferRefT<ELT>::m_pBuffer, pcsz, sizeof(ELT) * CBufferRefT <ELT> :: m_nSize);
  CBufferRefT<ELT>::m_pBuffer[CBufferRefT <ELT> :: m_nSize] = 0;
}

template <class ELT> CBufferT <ELT> :: CBufferT() : CBufferRefT <ELT> (0, 0)
{
  m_nMaxLength = 0;
  CBufferRefT<ELT>::m_pBuffer    = 0;
}

template <class ELT> inline ELT & CBufferT <ELT> :: operator [] (int nIndex)
{
  return CBufferRefT<ELT>::m_pBuffer[nIndex];
}

template <class ELT> inline const ELT & CBufferT <ELT> :: operator [] (int nIndex) const
{
  return CBufferRefT<ELT>::m_pBuffer[nIndex];
}

template <class ELT> void CBufferT <ELT> :: Append(const ELT * pcsz, int length, int eol)
{
  int nNewLength = m_nMaxLength;

  // Check length
  if(nNewLength < 8)
    nNewLength = 8;

  if(CBufferRefT <ELT> :: m_nSize + length + eol > nNewLength)
    nNewLength *= 2;

  if(CBufferRefT <ELT> :: m_nSize + length + eol > nNewLength)
  {
    nNewLength  = CBufferRefT <ELT> :: m_nSize + length + eol + 11;
    nNewLength -= nNewLength % 8;
  }

  // Realloc
  if(nNewLength > m_nMaxLength)
  {
    CBufferRefT <ELT> :: m_pBuffer = (ELT *) realloc(CBufferRefT<ELT>::m_pBuffer, sizeof(ELT) * nNewLength);
    m_nMaxLength = nNewLength;
  }

  // Append
  memcpy(CBufferRefT<ELT>::m_pBuffer + CBufferRefT <ELT> :: m_nSize, pcsz, sizeof(ELT) * length);
  CBufferRefT <ELT> :: m_nSize += length;

  if(eol > 0) CBufferRefT<ELT>::m_pBuffer[CBufferRefT <ELT> :: m_nSize] = 0;
}

template <class ELT> inline void CBufferT <ELT> :: Append(ELT el, int eol)
{
  Append(&el, 1, eol);
}

template <class ELT> void CBufferT <ELT> :: Push(ELT el)
{
  // Realloc
  if(CBufferRefT <ELT> :: m_nSize >= m_nMaxLength)
  {
    int nNewLength = m_nMaxLength * 2;
    if( nNewLength < 8 ) nNewLength = 8;

    CBufferRefT <ELT> :: m_pBuffer = (ELT *) realloc(CBufferRefT<ELT>::m_pBuffer, sizeof(ELT) * nNewLength);
    m_nMaxLength = nNewLength;
  }

  // Append
  CBufferRefT<ELT>::m_pBuffer[CBufferRefT <ELT> :: m_nSize++] = el;
}

template <class ELT> void CBufferT <ELT> :: Push(const CBufferRefT<ELT> & buf)
{
  for(int i=0; i<buf.GetSize(); i++)
  {
    Push(buf[i]);
  }

  Push((ELT)buf.GetSize());
}

template <class ELT> inline int CBufferT <ELT> :: Pop(ELT & el)
{
  if(CBufferRefT <ELT> :: m_nSize > 0)
  {
    el = CBufferRefT<ELT>::m_pBuffer[--CBufferRefT <ELT> :: m_nSize];
    return 1;
  }
  else
  {
    return 0;
  }
}

template <class ELT> int CBufferT <ELT> :: Pop (CBufferT<ELT> & buf)
{
  int size, res = 1;
  res = res && Pop(*(ELT*)&size);
  buf.Restore(size);

  for(int i=size-1; i>=0; i--)
  {
    res = res && Pop(buf[i]);
  }

  return res;
}

template <class ELT> inline int CBufferT <ELT> :: Peek(ELT & el) const
{
  if(CBufferRefT <ELT> :: m_nSize > 0)
  {
    el = CBufferRefT<ELT>::m_pBuffer[CBufferRefT <ELT> :: m_nSize - 1];
    return 1;
  }
  else
  {
    return 0;
  }
}

template <class ELT> const ELT * CBufferT <ELT> :: GetBuffer() const
{
  static const ELT _def[] = {0}; return CBufferRefT<ELT>::m_pBuffer ? CBufferRefT<ELT>::m_pBuffer : _def;
}

template <class ELT> ELT * CBufferT <ELT> :: GetBuffer()
{
  static const ELT _def[] = {0}; return CBufferRefT<ELT>::m_pBuffer ? CBufferRefT<ELT>::m_pBuffer : (ELT *)_def;
}

template <class ELT> ELT * CBufferT <ELT> :: Detach()
{
  ELT * pBuffer = CBufferRefT<ELT>::m_pBuffer;

  CBufferRefT <ELT> :: m_pBuffer = 0;
  CBufferRefT <ELT> :: m_nSize = m_nMaxLength = 0;

  return pBuffer;
}

template <class ELT> void CBufferT <ELT> :: Release()
{
  ELT * pBuffer = Detach();

  if(pBuffer != 0) free(pBuffer);
}

template <class ELT> void CBufferT <ELT> :: Prepare(int index, int fill)
{
  int nNewSize = index + 1;

  // Realloc
  if(nNewSize > m_nMaxLength)
  {
    int nNewLength = m_nMaxLength;

    if( nNewLength < 8 )
      nNewLength = 8;

    if( nNewSize > nNewLength )
      nNewLength *= 2;

    if( nNewSize > nNewLength )
    {
      nNewLength  = nNewSize + 11;
      nNewLength -= nNewLength % 8;
    }

    CBufferRefT <ELT> :: m_pBuffer = (ELT *) realloc(CBufferRefT<ELT>::m_pBuffer, sizeof(ELT) * nNewLength);
    m_nMaxLength = nNewLength;
  }

  // size
  if( CBufferRefT <ELT> :: m_nSize < nNewSize )
  {
    memset(CBufferRefT<ELT>::m_pBuffer + CBufferRefT <ELT> :: m_nSize, fill, sizeof(ELT) * (nNewSize - CBufferRefT <ELT> :: m_nSize));
    CBufferRefT <ELT> :: m_nSize = nNewSize;
  }
}

template <class ELT> inline void CBufferT <ELT> :: Restore(int size)
{
  SetMaxLength(size);
  CBufferRefT <ELT> :: m_nSize = size;
}

template <class ELT> CBufferT <ELT> :: ~CBufferT()
{
  if(CBufferRefT<ELT>::m_pBuffer != 0) free(CBufferRefT<ELT>::m_pBuffer);
}

template <class T> class CSortedBufferT : public CBufferT <T>
{
public:
  CSortedBufferT(int reverse = 0);
  CSortedBufferT(int(*)(const void *, const void *));

public:
  void Add(const T & rT);
  void Add(const T * pT, int nSize);
  int  Remove(const T & rT);
  void RemoveAll();

  void SortFreeze() { m_bSortFreezed = 1; }
  void SortUnFreeze();

public:
  int  Find(const T & rT, int(* compare)(const void *, const void *) = 0) { return FindAs(*(T*)&rT, compare); }
  int  FindAs(const T & rT, int(*)(const void *, const void *) = 0);
  int  GetSize() const { return CBufferRefT<T>::m_nSize; }
  T & operator [] (int nIndex) { return CBufferT <T> :: operator [] (nIndex); }

protected:
  int (* m_fncompare)(const void *, const void *);
  static int compareT(const void *, const void *);
  static int compareReverseT(const void *, const void *);

  int  m_bSortFreezed;
};

template <class T> CSortedBufferT <T> :: CSortedBufferT(int reverse)
{
  m_fncompare = reverse ? compareReverseT : compareT;
  m_bSortFreezed = 0;
}

template <class T> CSortedBufferT <T> :: CSortedBufferT(int (* compare)(const void *, const void *))
{
  m_fncompare = compare;
  m_bSortFreezed = 0;
}

template <class T> void CSortedBufferT <T> :: Add(const T & rT)
{
  if(m_bSortFreezed != 0)
  {
    this->Append(rT);
    return;
  }

  int a = 0, b = CBufferRefT<T>::m_nSize - 1, c = CBufferRefT<T>::m_nSize / 2;

  while(a <= b)
  {
    int r = m_fncompare(&rT, &CBufferRefT<T>::m_pBuffer[c]);

    if     ( r < 0 ) b = c - 1;
    else if( r > 0 ) a = c + 1;
    else break;

    c = (a + b + 1) / 2;
  }

  this->Insert(c, rT);
}

template <class T> void CSortedBufferT <T> :: Add(const T * pT, int nSize)
{
  Append(pT, nSize);

  if(m_bSortFreezed == 0)
  {
    qsort(CBufferRefT<T>::m_pBuffer, CBufferRefT<T>::m_nSize, sizeof(T), m_fncompare);
  }
}

template <class T> int CSortedBufferT <T> :: FindAs(const T & rT, int(* compare)(const void *, const void *))
{
  const T * pT = (const T *)bsearch(&rT, CBufferRefT<T>::m_pBuffer, CBufferRefT<T>::m_nSize, sizeof(T), compare == 0 ? m_fncompare : compare);

  if( pT != NULL )
    return pT - CBufferRefT<T>::m_pBuffer;
  else
    return -1;
}

template <class T> int CSortedBufferT <T> :: Remove(const T & rT)
{
  int pos = Find(rT);
  if( pos >= 0 ) CBufferT <T> :: Remove(pos);
  return pos;
}

template <class T> inline void CSortedBufferT <T> :: RemoveAll()
{
  CBufferT<T>::Restore(0);
}

template <class T> void CSortedBufferT <T> :: SortUnFreeze()
{
  if(m_bSortFreezed != 0)
  {
    m_bSortFreezed = 0;
    qsort(CBufferRefT<T>::m_pBuffer, CBufferRefT<T>::m_nSize, sizeof(T), m_fncompare);
  }
}

template <class T> int CSortedBufferT <T> :: compareT(const void * elem1, const void * elem2)
{
  if( *(const T *)elem1 == *(const T *)elem2 )
    return 0;
  else if( *(const T *)elem1 < *(const T *)elem2 )
    return -1;
  else
    return 1;
}

template <class T> int CSortedBufferT <T> :: compareReverseT(const void * elem1, const void * elem2)
{
  if( *(const T *)elem1 == *(const T *)elem2 )
    return 0;
  else if( *(const T *)elem1 > *(const T *)elem2 )
    return -1;
  else
    return 1;
}

//
// Context
//
class CContext
{
public:
  CBufferT <int> m_stack;
  CBufferT <int> m_capturestack, m_captureindex;

public:
  int    m_nCurrentPos;
  int    m_nBeginPos;
  int    m_nLastBeginPos;
  int    m_nParenZindex;
  int    m_nCursiveLimit;

  void * m_pMatchString;
  int    m_pMatchStringLength;
};

class CContextShot
{
public:
  CContextShot(CContext * pContext)
  {
    m_nCurrentPos = pContext->m_nCurrentPos;
    nsize  = pContext->m_stack.GetSize();
    ncsize = pContext->m_capturestack.GetSize();
  }

  void Restore(CContext * pContext)
  {
    pContext->m_stack.Restore(nsize);
    pContext->m_capturestack.Restore(ncsize);
    pContext->m_nCurrentPos = m_nCurrentPos;
  }

public:
  int m_nCurrentPos;
  int nsize ;
  int ncsize;
};

//
// Interface
//
class ElxInterface
{
public:
  virtual int Match    (CContext * pContext) const = 0;
  virtual int MatchNext(CContext * pContext) const = 0;

public:
  virtual ~ElxInterface() {};
};

//
// Alternative
//
template <int x> class CAlternativeElxT : public ElxInterface
{
public:
  int Match    (CContext * pContext) const;
  int MatchNext(CContext * pContext) const;

public:
  CAlternativeElxT();

public:
  CBufferT <ElxInterface *> m_elxlist;
};

typedef CAlternativeElxT <0> CAlternativeElx;

//
// Assert
//
template <int x> class CAssertElxT : public ElxInterface
{
public:
  int Match    (CContext * pContext) const;
  int MatchNext(CContext * pContext) const;

public:
  CAssertElxT(ElxInterface * pelx, int byes = 1);

public:
  ElxInterface * m_pelx;
  int m_byes;
};

typedef CAssertElxT <0> CAssertElx;

//
// Back reference elx
//
template <class CHART> class CBackrefElxT : public ElxInterface
{
public:
  int Match    (CContext * pContext) const;
  int MatchNext(CContext * pContext) const;

public:
  CBackrefElxT(int nnumber, int brightleft, int bignorecase);

public:
  int m_nnumber;
  int m_brightleft;
  int m_bignorecase;

  CBufferT <CHART> m_szNamed;
};

//
// Implementation
//
template <class CHART> CBackrefElxT <CHART> :: CBackrefElxT(int nnumber, int brightleft, int bignorecase)
{
  m_nnumber     = nnumber;
  m_brightleft  = brightleft;
  m_bignorecase = bignorecase;
}

template <class CHART> int CBackrefElxT <CHART> :: Match(CContext * pContext) const
{
  // check number, for named
  if( m_nnumber < 0 || m_nnumber >= pContext->m_captureindex.GetSize() ) return 0;

  int index = pContext->m_captureindex[m_nnumber];
  if( index < 0 ) return 0;

  // check enclosed
  int pos1 = pContext->m_capturestack[index + 1];
  int pos2 = pContext->m_capturestack[index + 2];

  if( pos2 < 0 ) pos2 = pContext->m_nCurrentPos;

  // info
  int lpos = pos1 < pos2 ? pos1 : pos2;
  int rpos = pos1 < pos2 ? pos2 : pos1;
  int slen = rpos - lpos;

  const CHART * pcsz = (const CHART *)pContext->m_pMatchString;
  int npos = pContext->m_nCurrentPos;
  int tlen = pContext->m_pMatchStringLength;

  // compare
  int bsucc;
  CBufferRefT <CHART> refstr(pcsz + lpos, slen);

  if( m_brightleft )
  {
    if(npos < slen)
      return 0;

    if(m_bignorecase)
      bsucc = ! refstr.nCompareNoCase(pcsz + (npos - slen));
    else
      bsucc = ! refstr.nCompare      (pcsz + (npos - slen));

    if( bsucc )
    {
      pContext->m_stack.Push(npos);
      pContext->m_nCurrentPos -= slen;
    }
  }
  else
  {
    if(npos + slen > tlen)
      return 0;

    if(m_bignorecase)
      bsucc = ! refstr.nCompareNoCase(pcsz + npos);
    else
      bsucc = ! refstr.nCompare      (pcsz + npos);

    if( bsucc )
    {
      pContext->m_stack.Push(npos);
      pContext->m_nCurrentPos += slen;
    }
  }

  return bsucc;
}

template <class CHART> int CBackrefElxT <CHART> :: MatchNext(CContext * pContext) const
{
  int npos = 0;

  pContext->m_stack.Pop(npos);
  pContext->m_nCurrentPos = npos;

  return 0;
}

// RCHART
#ifndef RCHART
  #define RCHART(ch) ((CHART)ch)
#endif

// BOUNDARY_TYPE
enum BOUNDARY_TYPE
{
  BOUNDARY_FILE_BEGIN, // begin of whole text
  BOUNDARY_FILE_END  , // end of whole text
  BOUNDARY_FILE_END_N, // end of whole text, or before newline at the end
  BOUNDARY_LINE_BEGIN, // begin of line
  BOUNDARY_LINE_END  , // end of line
  BOUNDARY_WORD_BEGIN, // begin of word
  BOUNDARY_WORD_END  , // end of word
  BOUNDARY_WORD_EDGE
};

//
// Boundary Elx
//
template <class CHART> class CBoundaryElxT : public ElxInterface
{
public:
  int Match    (CContext * pContext) const;
  int MatchNext(CContext * pContext) const;

public:
  CBoundaryElxT(int ntype, int byes = 1);

protected:
  static int IsWordChar(CHART ch);

public:
  int m_ntype;
  int m_byes;
};

//
// Implementation
//
template <class CHART> CBoundaryElxT <CHART> :: CBoundaryElxT(int ntype, int byes)
{
  m_ntype = ntype;
  m_byes  = byes;
}

template <class CHART> int CBoundaryElxT <CHART> :: Match(CContext * pContext) const
{
  const CHART * pcsz  = (const CHART *)pContext->m_pMatchString;
  int npos = pContext->m_nCurrentPos;
  int tlen = pContext->m_pMatchStringLength;

  CHART chL = npos > 0    ? pcsz[npos - 1] : 0;
  CHART chR = npos < tlen ? pcsz[npos    ] : 0;

  int bsucc = 0;

  switch(m_ntype)
  {
  case BOUNDARY_FILE_BEGIN:
    bsucc = (npos <= 0);
    break;

  case BOUNDARY_FILE_END:
    bsucc = (npos >= tlen);
    break;

  case BOUNDARY_FILE_END_N:
    bsucc = (npos >= tlen) || (pcsz[tlen-1] == RCHART('\n') && (npos == tlen-1 || (pcsz[tlen-2] == RCHART('\r') && npos == tlen-2)));
    break;

  case BOUNDARY_LINE_BEGIN:
    bsucc = (npos <= 0   ) || (chL == RCHART('\n')) || ((chL == RCHART('\r')) && (chR != RCHART('\n')));
    break;

  case BOUNDARY_LINE_END:
    bsucc = (npos >= tlen) || (chR == RCHART('\r')) || ((chR == RCHART('\n')) && (chL != RCHART('\r')));
    break;

  case BOUNDARY_WORD_BEGIN:
    bsucc = ! IsWordChar(chL) &&   IsWordChar(chR);
    break;

  case BOUNDARY_WORD_END:
    bsucc =   IsWordChar(chL) && ! IsWordChar(chR);
    break;

  case BOUNDARY_WORD_EDGE:
    bsucc =   IsWordChar(chL) ?  ! IsWordChar(chR) : IsWordChar(chR);
    break;
  }

  return m_byes ? bsucc : ! bsucc;
}

template <class CHART> int CBoundaryElxT <CHART> :: MatchNext(CContext *) const
{
  return 0;
}

template <class CHART> inline int CBoundaryElxT <CHART> :: IsWordChar(CHART ch)
{
  return (ch >= RCHART('A') && ch <= RCHART('Z')) || (ch >= RCHART('a') && ch <= RCHART('z')) || (ch >= RCHART('0') && ch <= RCHART('9')) || (ch == RCHART('_'));
}

//
// Bracket
//
template <class CHART> class CBracketElxT : public ElxInterface  
{
public:
  int Match    (CContext * pContext) const;
  int MatchNext(CContext * pContext) const;

public:
  CBracketElxT(int nnumber, int bright);
  static int CheckCaptureIndex(int & index, CContext * pContext, int number);

public:
  int m_nnumber;
  int m_bright;

  CBufferT <CHART> m_szNamed;
};

template <class CHART> CBracketElxT <CHART> :: CBracketElxT(int nnumber, int bright)
{
  m_nnumber = nnumber;
  m_bright  = bright;
}

template <class CHART> inline int CBracketElxT <CHART> :: CheckCaptureIndex(int & index, CContext * pContext, int number)
{
  if( index >= pContext->m_capturestack.GetSize() )
    index  = pContext->m_capturestack.GetSize() - 4;

  while(index >= 0)
  {
    if(pContext->m_capturestack[index] == number)
    {
      return 1;
    }

    index -= 4;
  }


  return 0;
}

//
// capturestack[index+0] => Group number
// capturestack[index+1] => Capture start pos
// capturestack[index+2] => Capture end pos
// capturestack[index+3] => Capture enclose z-index, zindex<0 means inner group with same name
//
template <class CHART> int CBracketElxT <CHART> :: Match(CContext * pContext) const
{
  // check, for named
  if(m_nnumber < 0) return 0;

  if( ! m_bright )
  {
    pContext->m_captureindex.Prepare(m_nnumber, -1);
    int index = pContext->m_captureindex[m_nnumber];

    // check
    if(CheckCaptureIndex(index, pContext, m_nnumber) && pContext->m_capturestack[index+2] < 0)
    {
      pContext->m_capturestack[index+3] --;
      return 1;
    }

    // save
    pContext->m_captureindex[m_nnumber] = pContext->m_capturestack.GetSize();

    pContext->m_capturestack.Push(m_nnumber);
    pContext->m_capturestack.Push(pContext->m_nCurrentPos);
    pContext->m_capturestack.Push(-1);
    pContext->m_capturestack.Push( 0); // z-index
  }
  else
  {
    // check
    int index = pContext->m_captureindex[m_nnumber];

    if(CheckCaptureIndex(index, pContext, m_nnumber))
    {
      if(pContext->m_capturestack[index + 3] < 0) // check inner group with same name
      {
        pContext->m_capturestack[index + 3] ++;
        return 1;
      }

      // save
      pContext->m_capturestack[index + 2] = pContext->m_nCurrentPos;
      pContext->m_capturestack[index + 3] = pContext->m_nParenZindex ++;
    }
  }

  return 1;
}

template <class CHART> int CBracketElxT <CHART> :: MatchNext(CContext * pContext) const
{
  int index = pContext->m_captureindex[m_nnumber];
  if( ! CheckCaptureIndex(index, pContext, m_nnumber) )
  {
    return 0;
  }

  if( ! m_bright )
  {
    if(pContext->m_capturestack[index + 3] < 0)
    {
      pContext->m_capturestack[index + 3] ++;
      return 0;
    }

    pContext->m_capturestack.Restore(pContext->m_capturestack.GetSize() - 4);

    // to find
    CheckCaptureIndex(index, pContext, m_nnumber);

    // new index
    pContext->m_captureindex[m_nnumber] = index;
  }
  else
  {
    if( pContext->m_capturestack[index + 2] >= 0 )
    {
      pContext->m_capturestack[index + 2] = -1;
      pContext->m_capturestack[index + 3] =  0;
    }
    else
    {
      pContext->m_capturestack[index + 3] --;
    }
  }

  return 0;
}

//
// Deletage
//
template <class CHART> class CDelegateElxT : public ElxInterface  
{
public:
  int Match    (CContext * pContext) const;
  int MatchNext(CContext * pContext) const;

public:
  CDelegateElxT(int ndata = 0);

public:
  ElxInterface * m_pelx;
  int m_ndata; // +0 : recursive to
               // -3 : named recursive

  CBufferT <CHART> m_szNamed;
};

template <class CHART> CDelegateElxT <CHART> :: CDelegateElxT(int ndata)
{
  m_pelx  = 0;
  m_ndata = ndata;
}

template <class CHART> int CDelegateElxT <CHART> :: Match(CContext * pContext) const
{
  if(m_pelx != 0)
  {
    if(pContext->m_nCursiveLimit > 0)
    {
      pContext->m_nCursiveLimit --;
      int result = m_pelx->Match(pContext);
      pContext->m_nCursiveLimit ++;
      return result;
    }
    else
      return 0;
  }
  else
    return 1;
}

template <class CHART> int CDelegateElxT <CHART> :: MatchNext(CContext * pContext) const
{
  if(m_pelx != 0)
    return m_pelx->MatchNext(pContext);
  else
    return 0;
}

//
// Empty
//
template <int x> class CEmptyElxT : public ElxInterface
{
public:
  int Match    (CContext * pContext) const;
  int MatchNext(CContext * pContext) const;

public:
  CEmptyElxT();
};

typedef CEmptyElxT <0> CEmptyElx;

//
// Global
//
template <int x> class CGlobalElxT : public ElxInterface
{
public:
  int Match    (CContext * pContext) const;
  int MatchNext(CContext * pContext) const;

public:
  CGlobalElxT();
};

typedef CGlobalElxT <0> CGlobalElx;

//
// Repeat
//
template <int x> class CRepeatElxT : public ElxInterface
{
public:
  int Match    (CContext * pContext) const;
  int MatchNext(CContext * pContext) const;

public:
  CRepeatElxT(ElxInterface * pelx, int ntimes);

protected:
  int MatchFixed    (CContext * pContext) const;
  int MatchNextFixed(CContext * pContext) const;
  int MatchForward  (CContext * pContext) const
  {
    CContextShot shot(pContext);
    
    if( ! m_pelx->Match(pContext) )
      return 0;

    if(pContext->m_nCurrentPos != shot.m_nCurrentPos)
      return 1;

    if( ! m_pelx->MatchNext(pContext) )
      return 0;

    if(pContext->m_nCurrentPos != shot.m_nCurrentPos)
      return 1;

    shot.Restore(pContext);
    return 0;
  }

public:
  ElxInterface * m_pelx;
  int m_nfixed;
};

typedef CRepeatElxT <0> CRepeatElx;

//
// Greedy
//
template <int x> class CGreedyElxT : public CRepeatElxT <x>
{
public:
  int Match    (CContext * pContext) const;
  int MatchNext(CContext * pContext) const;

public:
  CGreedyElxT(ElxInterface * pelx, int nmin = 0, int nmax = INT_MAX);

protected:
  int MatchVart    (CContext * pContext) const;
  int MatchNextVart(CContext * pContext) const;

public:
  int m_nvart;
};

typedef CGreedyElxT <0> CGreedyElx;

//
// Independent
//
template <int x> class CIndependentElxT : public ElxInterface
{
public:
  int Match    (CContext * pContext) const;
  int MatchNext(CContext * pContext) const;

public:
  CIndependentElxT(ElxInterface * pelx);

public:
  ElxInterface * m_pelx;
};

typedef CIndependentElxT <0> CIndependentElx;

//
// List
//
template <int x> class CListElxT : public ElxInterface
{
public:
  int Match    (CContext * pContext) const;
  int MatchNext(CContext * pContext) const;

public:
  CListElxT(int brightleft);

public:
  CBufferT <ElxInterface *> m_elxlist;
  int m_brightleft;
};

typedef CListElxT <0> CListElx;

//
// Posix Elx
//
template <class CHART> class CPosixElxT : public ElxInterface
{
public:
  int Match    (CContext * pContext) const;
  int MatchNext(CContext * pContext) const;

public:
  CPosixElxT(const char * posix, int brightleft);

public:
  POSIX_FUNC m_posixfun;
  int m_brightleft;
  int m_byes;
};

//
// Implementation
//
template <class CHART> CPosixElxT <CHART> :: CPosixElxT(const char * posix, int brightleft)
{
  m_brightleft = brightleft;

  if(posix[1] == '^')
  {
    m_byes = 0;
    posix += 2;
  }
  else
  {
    m_byes = 1;
    posix += 1;
  }

  if     (!strncmp(posix, "alnum:", 6)) m_posixfun = ::isalnum ;
  else if(!strncmp(posix, "alpha:", 6)) m_posixfun = ::isalpha ;
  else if(!strncmp(posix, "ascii:", 6)) m_posixfun = ::isascii ;
  else if(!strncmp(posix, "cntrl:", 6)) m_posixfun = ::iscntrl ;
  else if(!strncmp(posix, "digit:", 6)) m_posixfun = ::isdigit ;
  else if(!strncmp(posix, "graph:", 6)) m_posixfun = ::isgraph ;
  else if(!strncmp(posix, "lower:", 6)) m_posixfun = ::islower ;
  else if(!strncmp(posix, "print:", 6)) m_posixfun = ::isprint ;
  else if(!strncmp(posix, "punct:", 6)) m_posixfun = ::ispunct ;
  else if(!strncmp(posix, "space:", 6)) m_posixfun = ::isspace ;
  else if(!strncmp(posix, "upper:", 6)) m_posixfun = ::isupper ;
  else if(!strncmp(posix, "xdigit:",7)) m_posixfun = ::isxdigit;
  else if(!strncmp(posix, "blank:", 6)) m_posixfun =   isblunk ;
  else                                  m_posixfun = 0         ;
}

inline int isblunk(int c)
{
  return c == 0x20 || c == '\t';
}

template <class CHART> int CPosixElxT <CHART> :: Match(CContext * pContext) const
{
  if(m_posixfun == 0) return 0;

  int tlen = pContext->m_pMatchStringLength;
  int npos = pContext->m_nCurrentPos;

  // check
  int at   = m_brightleft ? npos - 1 : npos;
  if( at < 0 || at >= tlen )
    return 0;

  CHART ch = ((const CHART *)pContext->m_pMatchString)[at];

  int bsucc = (*m_posixfun)(ch);

  if( ! m_byes )
    bsucc = ! bsucc;

  if( bsucc )
    pContext->m_nCurrentPos += m_brightleft ? -1 : 1;

  return bsucc;
}

template <class CHART> int CPosixElxT <CHART> :: MatchNext(CContext * pContext) const
{
  pContext->m_nCurrentPos -= m_brightleft ? -1 : 1;
  return 0;
}

//
// Possessive
//
template <int x> class CPossessiveElxT : public CGreedyElxT <x>
{
public:
  int Match    (CContext * pContext) const;
  int MatchNext(CContext * pContext) const;

public:
  CPossessiveElxT(ElxInterface * pelx, int nmin = 0, int nmax = INT_MAX);
};

typedef CPossessiveElxT <0> CPossessiveElx;

//
// Range Elx
//
template <class CHART> class CRangeElxT : public ElxInterface
{
public:
  int Match    (CContext * pContext) const;
  int MatchNext(CContext * pContext) const;

public:
  CRangeElxT(int brightleft, int byes);

public:
  int IsContainChar(CHART ch) const;

public:
  CBufferT <CHART> m_ranges;
  CBufferT <CHART> m_chars;
  CBufferT <ElxInterface *> m_embeds;

public:
  int m_brightleft;
  int m_byes;
};

//
// Implementation
//
template <class CHART> CRangeElxT <CHART> :: CRangeElxT(int brightleft, int byes)
{
  m_brightleft = brightleft;
  m_byes       = byes;
}

template <class CHART> int CRangeElxT <CHART> :: Match(CContext * pContext) const
{
  int tlen = pContext->m_pMatchStringLength;
  int npos = pContext->m_nCurrentPos;

  // check
  int at   = m_brightleft ? npos - 1 : npos;
  if( at < 0 || at >= tlen )
    return 0;

  CHART ch = ((const CHART *)pContext->m_pMatchString)[at];
  int bsucc = 0, i;

  // compare
  for(i=0; !bsucc && i<m_ranges.GetSize(); i+=2)
  {
    if(m_ranges[i] <= ch && ch <= m_ranges[i+1]) bsucc = 1;
  }

  for(i=0; !bsucc && i<m_chars.GetSize(); i++)
  {
    if(m_chars[i] == ch) bsucc = 1;
  }

  for(i=0; !bsucc && i<m_embeds.GetSize(); i++)
  {
    if(m_embeds[i]->Match(pContext))
    {
      pContext->m_nCurrentPos = npos;
      bsucc = 1;
    }
  }

  if( ! m_byes )
    bsucc = ! bsucc;

  if( bsucc )
    pContext->m_nCurrentPos += m_brightleft ? -1 : 1;

  return bsucc;
}

template <class CHART> int CRangeElxT <CHART> :: IsContainChar(CHART ch) const
{
  int bsucc = 0, i;

  // compare
  for(i=0; !bsucc && i<m_ranges.GetSize(); i+=2)
  {
    if(m_ranges[i] <= ch && ch <= m_ranges[i+1]) bsucc = 1;
  }

  for(i=0; !bsucc && i<m_chars.GetSize(); i++)
  {
    if(m_chars[i] == ch) bsucc = 1;
  }

  return bsucc;
}

template <class CHART> int CRangeElxT <CHART> :: MatchNext(CContext * pContext) const
{
  pContext->m_nCurrentPos -= m_brightleft ? -1 : 1;
  return 0;
}

//
// Reluctant
//
template <int x> class CReluctantElxT : public CRepeatElxT <x>
{
public:
  int Match    (CContext * pContext) const;
  int MatchNext(CContext * pContext) const;

public:
  CReluctantElxT(ElxInterface * pelx, int nmin = 0, int nmax = INT_MAX);

protected:
  int MatchVart    (CContext * pContext) const;
  int MatchNextVart(CContext * pContext) const;

public:
  int m_nvart;
};

typedef CReluctantElxT <0> CReluctantElx;

//
// String Elx
//
template <class CHART> class CStringElxT : public ElxInterface
{
public:
  int Match    (CContext * pContext) const;
  int MatchNext(CContext * pContext) const;

public:
  CStringElxT(const CHART * fixed, int nlength, int brightleft, int bignorecase);

public:
  CBufferT <CHART> m_szPattern;
  int m_brightleft;
  int m_bignorecase;
};

//
// Implementation
//
template <class CHART> CStringElxT <CHART> :: CStringElxT(const CHART * fixed, int nlength, int brightleft, int bignorecase) : m_szPattern(fixed, nlength)
{
  m_brightleft  = brightleft;
  m_bignorecase = bignorecase;
}

template <class CHART> int CStringElxT <CHART> :: Match(CContext * pContext) const
{
  const CHART * pcsz  = (const CHART *)pContext->m_pMatchString;
  int npos = pContext->m_nCurrentPos;
  int tlen = pContext->m_pMatchStringLength;
  int slen = m_szPattern.GetSize();

  int bsucc;

  if(m_brightleft)
  {
    if(npos < slen)
      return 0;

    if(m_bignorecase)
      bsucc = ! m_szPattern.nCompareNoCase(pcsz + (npos - slen));
    else
      bsucc = ! m_szPattern.nCompare      (pcsz + (npos - slen));

    if( bsucc )
      pContext->m_nCurrentPos -= slen;
  }
  else
  {
    if(npos + slen > tlen)
      return 0;

    if(m_bignorecase)
      bsucc = ! m_szPattern.nCompareNoCase(pcsz + npos);
    else
      bsucc = ! m_szPattern.nCompare      (pcsz + npos);

    if( bsucc )
      pContext->m_nCurrentPos += slen;
  }

  return bsucc;
}

template <class CHART> int CStringElxT <CHART> :: MatchNext(CContext * pContext) const
{
  int slen = m_szPattern.GetSize();

  if(m_brightleft)
    pContext->m_nCurrentPos += slen;
  else
    pContext->m_nCurrentPos -= slen;

  return 0;
}

//
// CConditionElx
//
template <class CHART> class CConditionElxT : public ElxInterface
{
public:
  int Match    (CContext * pContext) const;
  int MatchNext(CContext * pContext) const;

public:
  CConditionElxT();

public:
  // backref condition
  int m_nnumber;
  CBufferT <CHART> m_szNamed;

  // elx condition
  ElxInterface * m_pelxask;

  // selection
  ElxInterface * m_pelxyes, * m_pelxno;
};

template <class CHART> CConditionElxT <CHART> :: CConditionElxT()
{
  m_nnumber = -1;
}

template <class CHART> int CConditionElxT <CHART> :: Match(CContext * pContext) const
{
  // status
  int nbegin = pContext->m_nCurrentPos;
  int nsize  = pContext->m_stack.GetSize();
  int ncsize = pContext->m_capturestack.GetSize();

  // condition result
  int condition_yes = 0;

  // backref type
  if( m_nnumber >= 0 )
  {
    do
    {
      if(m_nnumber >= pContext->m_captureindex.GetSize()) break;

      int index = pContext->m_captureindex[m_nnumber];
      if( index < 0) break;

      // else valid
      condition_yes = 1;
    }
    while(0);
  }
  else
  {
    if( m_pelxask == 0 )
      condition_yes = 1;
    else
      condition_yes = m_pelxask->Match(pContext);

    pContext->m_stack.Restore(nsize);
    pContext->m_nCurrentPos = nbegin;
  }

  // elx result
  int bsucc;
  if( condition_yes )
    bsucc = m_pelxyes == 0 ? 1 : m_pelxyes->Match(pContext);
  else
    bsucc = m_pelxno  == 0 ? 1 : m_pelxno ->Match(pContext);

  if( bsucc )
  {
    pContext->m_stack.Push(ncsize);
    pContext->m_stack.Push(condition_yes);
  }
  else
  {
    pContext->m_capturestack.Restore(ncsize);
  }

  return bsucc;
}

template <class CHART> int CConditionElxT <CHART> :: MatchNext(CContext * pContext) const
{
  // pop
  int ncsize, condition_yes;

  pContext->m_stack.Pop(condition_yes);
  pContext->m_stack.Pop(ncsize);

  // elx result
  int bsucc;
  if( condition_yes )
    bsucc = m_pelxyes == 0 ? 0 : m_pelxyes->MatchNext(pContext);
  else
    bsucc = m_pelxno  == 0 ? 0 : m_pelxno ->MatchNext(pContext);

  if( bsucc )
  {
    pContext->m_stack.Push(ncsize);
    pContext->m_stack.Push(condition_yes);
  }
  else
  {
    pContext->m_capturestack.Restore(ncsize);
  }

  return bsucc;
}

//
// MatchResult
//
template <int x> class MatchResultT
{
public:
  int IsMatched() const;

public:
  int GetStart() const;
  int GetEnd  () const;

public:
  int MaxGroupNumber() const;
  int GetGroupStart(int nGroupNumber) const;
  int GetGroupEnd  (int nGroupNumber) const;

public:
  MatchResultT(const MatchResultT <x> & from) { *this = from; }
  MatchResultT(CContext * pContext = 0, int nMaxNumber = -1);
  MatchResultT <x> & operator = (const MatchResultT <x> &);
  inline operator int() const { return IsMatched(); }

public:
  CBufferT <int> m_result;
};

typedef MatchResultT <0> MatchResult;

// Stocked Elx IDs
enum STOCKELX_ID_DEFINES
{
  STOCKELX_EMPTY = 0,

  ///////////////////////

  STOCKELX_DOT_ALL,
  STOCKELX_DOT_NOT_ALL,

  STOCKELX_WORD,
  STOCKELX_WORD_NOT,

  STOCKELX_SPACE,
  STOCKELX_SPACE_NOT,

  STOCKELX_DIGITAL,
  STOCKELX_DIGITAL_NOT,

  //////////////////////

  STOCKELX_DOT_ALL_RIGHTLEFT,
  STOCKELX_DOT_NOT_ALL_RIGHTLEFT,

  STOCKELX_WORD_RIGHTLEFT,
  STOCKELX_WORD_RIGHTLEFT_NOT,

  STOCKELX_SPACE_RIGHTLEFT,
  STOCKELX_SPACE_RIGHTLEFT_NOT,

  STOCKELX_DIGITAL_RIGHTLEFT,
  STOCKELX_DIGITAL_RIGHTLEFT_NOT,

  /////////////////////

  STOCKELX_COUNT
};

// REGEX_FLAGS
#ifndef _REGEX_FLAGS_DEFINED
  enum REGEX_FLAGS
  {
    NO_FLAG        = 0,
    SINGLELINE     = 0x01,
    MULTILINE      = 0x02,
    GLOBAL         = 0x04,
    IGNORECASE     = 0x08,
    RIGHTTOLEFT    = 0x10,
    EXTENDED       = 0x20
  };
  #define _REGEX_FLAGS_DEFINED
#endif

//
// Builder T
//
template <class CHART> class CBuilderT
{
public:
  typedef CDelegateElxT  <CHART> CDelegateElx;
  typedef CBracketElxT   <CHART> CBracketElx;
  typedef CBackrefElxT   <CHART> CBackrefElx;
  typedef CConditionElxT <CHART> CConditionElx;

// Methods
public:
  ElxInterface * Build(const CBufferRefT <CHART> & pattern, int flags);
  int GetNamedNumber(const CBufferRefT <CHART> & named) const;
  void Clear();

public:
   CBuilderT();
  ~CBuilderT();

// Public Attributes
public:
  ElxInterface * m_pTopElx;
  int            m_nFlags;
  int            m_nMaxNumber;
  int            m_nNextNamed;
  int            m_nGroupCount;

  CBufferT <ElxInterface  *> m_objlist;
  CBufferT <ElxInterface  *> m_grouplist;
  CBufferT <CDelegateElx  *> m_recursivelist;
  CBufferT <CListElx      *> m_namedlist;
  CBufferT <CBackrefElx   *> m_namedbackreflist;
  CBufferT <CConditionElx *> m_namedconditionlist;

// CHART_INFO
protected:
  struct CHART_INFO
  {
  public:
    CHART ch;
    int   type;
    int   pos;
    int   len;

  public:
    CHART_INFO(CHART c, int t, int p = 0, int l = 0) { ch = c; type = t; pos = p; len = l;    }
    inline int operator == (const CHART_INFO & ci)   { return ch == ci.ch && type == ci.type; }
    inline int operator != (const CHART_INFO & ci)   { return ! operator == (ci);             }
  };

protected:
  static unsigned int Hex2Int(const CHART * pcsz, int length, int & used);
  static int ReadDec(char * & str, unsigned int & dec);
  void MoveNext();
  int  GetNext2();

  ElxInterface * BuildAlternative(int vaflags);
  ElxInterface * BuildList       (int & flags);
  ElxInterface * BuildRepeat     (int & flags);
  ElxInterface * BuildSimple     (int & flags);
  ElxInterface * BuildCharset    (int & flags);
  ElxInterface * BuildRecursive  (int & flags);
  ElxInterface * BuildBoundary   (int & flags);
  ElxInterface * BuildBackref    (int & flags);

  ElxInterface * GetStockElx     (int nStockId);
  ElxInterface * Keep(ElxInterface * pElx);

// Private Attributes
protected:
  CBufferRefT <CHART> m_pattern;
  CHART_INFO prev, curr, next, nex2;
  int m_nNextPos;
  int m_nCharsetDepth;
  int m_bQuoted;
  POSIX_FUNC m_quote_fun;

  // Backup current pos
  struct Snapshot
  {
    CHART_INFO prev, curr, next, nex2;
    int m_nNextPos;
    int m_nCharsetDepth;
    int m_bQuoted;
    POSIX_FUNC m_quote_fun;
    Snapshot():prev(0,0),curr(0,0),next(0,0),nex2(0,0) {}
  };
  void Backup (Snapshot * pdata) { memcpy(pdata, &prev, sizeof(Snapshot)); }
  void Restore(Snapshot * pdata) { memcpy(&prev, pdata, sizeof(Snapshot)); }

  ElxInterface * m_pStockElxs[STOCKELX_COUNT];
};

//
// Implementation
//
template <class CHART> CBuilderT <CHART> :: CBuilderT() : m_pattern(0, 0), prev(0, 0), curr(0, 0), next(0, 0), nex2(0, 0)
{
  Clear();
}

template <class CHART> CBuilderT <CHART> :: ~CBuilderT()
{
  Clear();
}

template <class CHART> int CBuilderT <CHART> :: GetNamedNumber(const CBufferRefT <CHART> & named) const
{
  for(int i=0; i<m_namedlist.GetSize(); i++)
  {
    if( ! ((CBracketElx *)m_namedlist[i]->m_elxlist[0])->m_szNamed.CompareNoCase(named) )
      return ((CBracketElx *)m_namedlist[i]->m_elxlist[0])->m_nnumber;
  }

  return -3;
}

template <class CHART> ElxInterface * CBuilderT <CHART> :: Build(const CBufferRefT <CHART> & pattern, int flags)
{
  // init
  m_pattern       = pattern;
  m_nNextPos      = 0;
  m_nCharsetDepth = 0;
  m_nMaxNumber    = 0;
  m_nNextNamed    = 0;
  m_nFlags        = flags;
  m_bQuoted       = 0;
  m_quote_fun     = 0;

  m_grouplist         .Restore(0);
  m_recursivelist     .Restore(0);
  m_namedlist         .Restore(0);
  m_namedbackreflist  .Restore(0);
  m_namedconditionlist.Restore(0);

  int i;
  for(i=0; i<3; i++) MoveNext();

  // build
  m_pTopElx = BuildAlternative(flags);

  // group 0
  m_grouplist.Prepare(0);
  m_grouplist[0] = m_pTopElx;

  // append named to unnamed
  m_nGroupCount = m_grouplist.GetSize();

  m_grouplist.Prepare(m_nMaxNumber + m_namedlist.GetSize());

  for(i=0; i<m_namedlist.GetSize(); i++)
  {
    CBracketElx * pleft  = (CBracketElx *)m_namedlist[i]->m_elxlist[0];
    CBracketElx * pright = (CBracketElx *)m_namedlist[i]->m_elxlist[2];

    // append
    m_grouplist[m_nGroupCount ++] = m_namedlist[i];

    if( pleft->m_nnumber > 0 )
      continue;

    // same name
    int find_same_name = GetNamedNumber(pleft->m_szNamed);
    if( find_same_name >= 0 )
    {
      pleft ->m_nnumber = find_same_name;
      pright->m_nnumber = find_same_name;
    }
    else
    {
      m_nMaxNumber ++;

      pleft ->m_nnumber = m_nMaxNumber;
      pright->m_nnumber = m_nMaxNumber;
    }
  }

  for(i=1; i<m_nGroupCount; i++)
  {
    CBracketElx * pleft = (CBracketElx *)((CListElx*)m_grouplist[i])->m_elxlist[0];

    if( pleft->m_nnumber > m_nMaxNumber )
      m_nMaxNumber = pleft->m_nnumber;
  }

  // connect recursive
  for(i=0; i<m_recursivelist.GetSize(); i++)
  {
    if( m_recursivelist[i]->m_ndata == -3 )
      m_recursivelist[i]->m_ndata = GetNamedNumber(m_recursivelist[i]->m_szNamed);

    if( m_recursivelist[i]->m_ndata >= 0 && m_recursivelist[i]->m_ndata <= m_nMaxNumber )
    {
      if( m_recursivelist[i]->m_ndata == 0 )
        m_recursivelist[i]->m_pelx = m_pTopElx;
      else for(int j=1; j<m_grouplist.GetSize(); j++)
      {
        if(m_recursivelist[i]->m_ndata == ((CBracketElx *)((CListElx*)m_grouplist[j])->m_elxlist[0])->m_nnumber)
        {
          m_recursivelist[i]->m_pelx = m_grouplist[j];
          break;
        }
      }
    }
  }

  // named backref
  for(i=0; i<m_namedbackreflist.GetSize(); i++)
  {
    m_namedbackreflist[i]->m_nnumber = GetNamedNumber(m_namedbackreflist[i]->m_szNamed);
  }

  // named condition
  for(i=0; i<m_namedconditionlist.GetSize(); i++)
  {
    int nn = GetNamedNumber(m_namedconditionlist[i]->m_szNamed);
    if( nn >= 0 )
    {
      m_namedconditionlist[i]->m_nnumber = nn;
      m_namedconditionlist[i]->m_pelxask = 0;
    }
  }

  return m_pTopElx;
}

template <class CHART> void CBuilderT <CHART> :: Clear()
{
  for(int i=0; i<m_objlist.GetSize(); i++)
  {
    delete m_objlist[i];
  }

  m_objlist.Restore(0);
  m_pTopElx = 0;
  m_nMaxNumber = 0;

  memset(m_pStockElxs, 0, sizeof(m_pStockElxs));
}

//
// hex to int
//
template <class CHART> unsigned int CBuilderT <CHART> :: Hex2Int(const CHART * pcsz, int length, int & used)
{
  unsigned int result = 0;
  int & i = used;

  for(i=0; i<length; i++)
  {
    if(pcsz[i] >= RCHART('0') && pcsz[i] <= RCHART('9'))
      result = (result << 4) + (pcsz[i] - RCHART('0'));
    else if(pcsz[i] >= RCHART('A') && pcsz[i] <= RCHART('F'))
      result = (result << 4) + (0x0A + (pcsz[i] - RCHART('A')));
    else if(pcsz[i] >= RCHART('a') && pcsz[i] <= RCHART('f'))
      result = (result << 4) + (0x0A + (pcsz[i] - RCHART('a')));
    else
      break;
  }

  return result;
}

template <class CHART> inline ElxInterface * CBuilderT <CHART> :: Keep(ElxInterface * pelx)
{
  m_objlist.Push(pelx);
  return pelx;
}

template <class CHART> void CBuilderT <CHART> :: MoveNext()
{
  // forwards
  prev = curr;
  curr = next;
  next = nex2;

  // get nex2
  while( ! GetNext2() ) {};
}

template <class CHART> int CBuilderT <CHART> :: GetNext2()
{
  // check length
  if(m_nNextPos >= m_pattern.GetSize())
  {
    nex2 = CHART_INFO(0, 1, m_nNextPos, 0);
    return 1;
  }

  int   delta = 1;
  CHART ch    = m_pattern[m_nNextPos];

  // if quoted
  if(m_bQuoted)
  {
    if(ch == RCHART('\\'))
    {
      if(m_pattern[m_nNextPos + 1] == RCHART('E'))
      {
        m_quote_fun = 0;
        m_bQuoted   = 0;
        m_nNextPos += 2;
        return 0;
      }
    }

    if(m_quote_fun != 0)
      nex2 = CHART_INFO((CHART)(*m_quote_fun)((int)ch), 0, m_nNextPos, delta);
    else
      nex2 = CHART_INFO(ch, 0, m_nNextPos, delta);

    m_nNextPos += delta;

    return 1;
  }

  // common
  switch(ch)
  {
  case RCHART('\\'):
    {
      CHART ch1 = m_pattern[m_nNextPos+1];

      // backref
      if(ch1 >= RCHART('0') && ch1 <= RCHART('9'))
      {
        nex2 = CHART_INFO(ch, 1, m_nNextPos, delta);
        break;
      }

      // escape
      delta     = 2;

      switch(ch1)
      {
      case RCHART('A'):
      case RCHART('Z'):
      case RCHART('z'):
      case RCHART('w'):
      case RCHART('W'):
      case RCHART('s'):
      case RCHART('S'):
      case RCHART('B'):
      case RCHART('d'):
      case RCHART('D'):
      case RCHART('k'):
      case RCHART('g'):
        nex2 = CHART_INFO(ch1, 1, m_nNextPos, delta);
        break;

      case RCHART('b'):
        if(m_nCharsetDepth > 0)
          nex2 = CHART_INFO('\b', 0, m_nNextPos, delta);
        else
          nex2 = CHART_INFO(ch1, 1, m_nNextPos, delta);
        break;

      /*
      case RCHART('<'):
      case RCHART('>'):
        if(m_nCharsetDepth > 0)
          nex2 = CHART_INFO(ch1, 0, m_nNextPos, delta);
        else
          nex2 = CHART_INFO(ch1, 1, m_nNextPos, delta);
        break;
      */

      case RCHART('x'):
        if(m_pattern[m_nNextPos+2] != '{')
        {
          int red = 0;
          unsigned int ch2 = Hex2Int(m_pattern.GetBuffer() + m_nNextPos + 2, 2, red);

          delta += red;

          if(red > 0)
            nex2 = CHART_INFO(RCHART(ch2), 0, m_nNextPos, delta);
          else
            nex2 = CHART_INFO(ch1, 0, m_nNextPos, delta);

          break;
        }

      case RCHART('u'):
        if(m_pattern[m_nNextPos+2] != '{')
        {
          int red = 0;
          unsigned int ch2 = Hex2Int(m_pattern.GetBuffer() + m_nNextPos + 2, 4, red);

          delta += red;

          if(red > 0)
            nex2 = CHART_INFO(RCHART(ch2), 0, m_nNextPos, delta);
          else
            nex2 = CHART_INFO(ch1, 0, m_nNextPos, delta);
        }
        else
        {
          int red = 0;
          unsigned int ch2 = Hex2Int(m_pattern.GetBuffer() + m_nNextPos + 3, sizeof(int) * 2, red);

          delta += red;

          while(m_nNextPos + delta < m_pattern.GetSize() && m_pattern.At(m_nNextPos + delta) != RCHART('}'))
            delta ++;

          delta ++; // skip '}'

          nex2 = CHART_INFO(RCHART(ch2), 0, m_nNextPos, delta);
        }
        break;

      case RCHART('a'): nex2 = CHART_INFO(RCHART('\a'), 0, m_nNextPos, delta); break;
      case RCHART('f'): nex2 = CHART_INFO(RCHART('\f'), 0, m_nNextPos, delta); break;
      case RCHART('n'): nex2 = CHART_INFO(RCHART('\n'), 0, m_nNextPos, delta); break;
      case RCHART('r'): nex2 = CHART_INFO(RCHART('\r'), 0, m_nNextPos, delta); break;
      case RCHART('t'): nex2 = CHART_INFO(RCHART('\t'), 0, m_nNextPos, delta); break;
      case RCHART('v'): nex2 = CHART_INFO(RCHART('\v'), 0, m_nNextPos, delta); break;
      case RCHART('e'): nex2 = CHART_INFO(RCHART( 27 ), 0, m_nNextPos, delta); break;

      case RCHART('G'):  // skip '\G'
        if(m_nCharsetDepth > 0)
        {
          m_nNextPos += 2;
          return 0;
        }
        else
        {
          nex2 = CHART_INFO(ch1, 1, m_nNextPos, delta);
          break;
        }

      case RCHART('L'):
        if( ! m_quote_fun ) m_quote_fun = ::tolower;

      case RCHART('U'):
        if( ! m_quote_fun ) m_quote_fun = ::toupper;

      case RCHART('Q'):
        {
          m_bQuoted   = 1;
          m_nNextPos += 2;
          return 0;
        }

      case RCHART('E'):
        {
          m_quote_fun = 0;
          m_bQuoted   = 0;
          m_nNextPos += 2;
          return 0;
        }

      case 0:
        if(m_nNextPos+1 >= m_pattern.GetSize())
        {
          delta = 1;
          nex2 = CHART_INFO(ch , 0, m_nNextPos, delta);
        }
        else
          nex2 = CHART_INFO(ch1, 0, m_nNextPos, delta); // common '\0' char
        break;

      default:
        nex2 = CHART_INFO(ch1, 0, m_nNextPos, delta);
        break;
      }
    }
    break;

  case RCHART('*'):
  case RCHART('+'):
  case RCHART('?'):
  case RCHART('.'):
  case RCHART('{'):
  case RCHART('}'):
  case RCHART(')'):
  case RCHART('|'):
  case RCHART('$'):
    if(m_nCharsetDepth > 0)
      nex2 = CHART_INFO(ch, 0, m_nNextPos, delta);
    else
      nex2 = CHART_INFO(ch, 1, m_nNextPos, delta);
    break;

  case RCHART('-'):
    if(m_nCharsetDepth > 0)
      nex2 = CHART_INFO(ch, 1, m_nNextPos, delta);
    else
      nex2 = CHART_INFO(ch, 0, m_nNextPos, delta);
    break;

  case RCHART('('):
    {
      CHART ch1 = m_pattern[m_nNextPos+1];
      CHART ch2 = m_pattern[m_nNextPos+2];

      // skip remark
      if(ch1 == RCHART('?') && ch2 == RCHART('#'))
      {
        m_nNextPos += 2;
        while(m_nNextPos < m_pattern.GetSize())
        {
          if(m_pattern[m_nNextPos] == RCHART(')'))
            break;

          m_nNextPos ++;
        }

        if(m_pattern[m_nNextPos] == RCHART(')'))
        {
          m_nNextPos ++;

          // get next nex2
          return 0;
        }
      }
      else
      {
        if(m_nCharsetDepth > 0)
          nex2 = CHART_INFO(ch, 0, m_nNextPos, delta);
        else
          nex2 = CHART_INFO(ch, 1, m_nNextPos, delta);
      }
    }
    break;

  case RCHART('#'):
    if(m_nFlags & EXTENDED)
    {
      // skip remark
      m_nNextPos ++;

      while(m_nNextPos < m_pattern.GetSize())
      {
        if(m_pattern[m_nNextPos] == RCHART('\n') || m_pattern[m_nNextPos] == RCHART('\r'))
          break;

        m_nNextPos ++;
      }

      // get next nex2
      return 0;
    }
    else
    {
      nex2 = CHART_INFO(ch, 0, m_nNextPos, delta);
    }
    break;

  case RCHART(' '):
  case RCHART('\f'):
  case RCHART('\n'):
  case RCHART('\r'):
  case RCHART('\t'):
  case RCHART('\v'):
    if(m_nFlags & EXTENDED)
    {
      m_nNextPos ++;

      // get next nex2
      return 0;
    }
    else
    {
      nex2 = CHART_INFO(ch, 0, m_nNextPos, delta);
    }
    break;

  case RCHART('['):
    if( m_nCharsetDepth == 0 || m_pattern.At(m_nNextPos + 1, 0) == RCHART(':') )
    {
      m_nCharsetDepth ++;
      nex2 = CHART_INFO(ch, 1, m_nNextPos, delta);
    }
    else
    {
      nex2 = CHART_INFO(ch, 0, m_nNextPos, delta);
    }
    break;

  case RCHART(']'):
    if(m_nCharsetDepth > 0)
    {
      m_nCharsetDepth --;
      nex2 = CHART_INFO(ch, 1, m_nNextPos, delta);
    }
    else
    {
      nex2 = CHART_INFO(ch, 0, m_nNextPos, delta);
    }
    break;

  case RCHART(':'):
    if(next == CHART_INFO(RCHART('['), 1))
      nex2 = CHART_INFO(ch, 1, m_nNextPos, delta);
    else
      nex2 = CHART_INFO(ch, 0, m_nNextPos, delta);
    break;

  case RCHART('^'):
    if(m_nCharsetDepth == 0 || next == CHART_INFO(RCHART('['), 1) || (curr == CHART_INFO(RCHART('['), 1) && next == CHART_INFO(RCHART(':'), 1)))
      nex2 = CHART_INFO(ch, 1, m_nNextPos, delta);
    else
      nex2 = CHART_INFO(ch, 0, m_nNextPos, delta);
    break;

  case 0:
    if(m_nNextPos >= m_pattern.GetSize())
      nex2 = CHART_INFO(ch, 1, m_nNextPos, delta); // end of string
    else
      nex2 = CHART_INFO(ch, 0, m_nNextPos, delta); // common '\0' char
    break;

  default:
    nex2 = CHART_INFO(ch, 0, m_nNextPos, delta);
    break;
  }

  m_nNextPos += delta;

  return 1;
}

template <class CHART> ElxInterface * CBuilderT <CHART> :: GetStockElx(int nStockId)
{
  ElxInterface ** pStockElxs = m_pStockElxs;

  // check
  if(nStockId < 0 || nStockId >= STOCKELX_COUNT)
    return GetStockElx(0);

  // create if no
  if(pStockElxs[nStockId] == 0)
  {
    switch(nStockId)
    {
    case STOCKELX_EMPTY:
      pStockElxs[nStockId] = Keep(new CEmptyElx());
      break;

    case STOCKELX_WORD:
      {
        CRangeElxT <CHART> * pRange = (CRangeElxT <CHART> *)Keep(new CRangeElxT <CHART> (0, 1));

        pRange->m_ranges.Push(RCHART('A')); pRange->m_ranges.Push(RCHART('Z'));
        pRange->m_ranges.Push(RCHART('a')); pRange->m_ranges.Push(RCHART('z'));
        pRange->m_ranges.Push(RCHART('0')); pRange->m_ranges.Push(RCHART('9'));
        pRange->m_chars .Push(RCHART('_'));

        pStockElxs[nStockId] = pRange;
      }
      break;

    case STOCKELX_WORD_NOT:
      {
        CRangeElxT <CHART> * pRange = (CRangeElxT <CHART> *)Keep(new CRangeElxT <CHART> (0, 0));

        pRange->m_ranges.Push(RCHART('A')); pRange->m_ranges.Push(RCHART('Z'));
        pRange->m_ranges.Push(RCHART('a')); pRange->m_ranges.Push(RCHART('z'));
        pRange->m_ranges.Push(RCHART('0')); pRange->m_ranges.Push(RCHART('9'));
        pRange->m_chars .Push(RCHART('_'));

        pStockElxs[nStockId] = pRange;
      }
      break;

    case STOCKELX_DOT_ALL:
      pStockElxs[nStockId] = Keep(new CRangeElxT <CHART> (0, 0));
      break;

    case STOCKELX_DOT_NOT_ALL:
      {
        CRangeElxT <CHART> * pRange = (CRangeElxT <CHART> *)Keep(new CRangeElxT <CHART> (0, 0));

        pRange->m_chars .Push(RCHART('\n'));

        pStockElxs[nStockId] = pRange;
      }
      break;

    case STOCKELX_SPACE:
      {
        CRangeElxT <CHART> * pRange = (CRangeElxT <CHART> *)Keep(new CRangeElxT <CHART> (0, 1));

        pRange->m_chars .Push(RCHART(' '));
        pRange->m_chars .Push(RCHART('\t'));
        pRange->m_chars .Push(RCHART('\r'));
        pRange->m_chars .Push(RCHART('\n'));

        pStockElxs[nStockId] = pRange;
      }
      break;

    case STOCKELX_SPACE_NOT:
      {
        CRangeElxT <CHART> * pRange = (CRangeElxT <CHART> *)Keep(new CRangeElxT <CHART> (0, 0));

        pRange->m_chars .Push(RCHART(' '));
        pRange->m_chars .Push(RCHART('\t'));
        pRange->m_chars .Push(RCHART('\r'));
        pRange->m_chars .Push(RCHART('\n'));

        pStockElxs[nStockId] = pRange;
      }
      break;

    case STOCKELX_DIGITAL:
      {
        CRangeElxT <CHART> * pRange = (CRangeElxT <CHART> *)Keep(new CRangeElxT <CHART> (0, 1));

        pRange->m_ranges.Push(RCHART('0')); pRange->m_ranges.Push(RCHART('9'));

        pStockElxs[nStockId] = pRange;
      }
      break;

    case STOCKELX_DIGITAL_NOT:
      {
        CRangeElxT <CHART> * pRange = (CRangeElxT <CHART> *)Keep(new CRangeElxT <CHART> (0, 0));

        pRange->m_ranges.Push(RCHART('0')); pRange->m_ranges.Push(RCHART('9'));

        pStockElxs[nStockId] = pRange;
      }
      break;

    case STOCKELX_WORD_RIGHTLEFT:
      {
        CRangeElxT <CHART> * pRange = (CRangeElxT <CHART> *)Keep(new CRangeElxT <CHART> (1, 1));

        pRange->m_ranges.Push(RCHART('A')); pRange->m_ranges.Push(RCHART('Z'));
        pRange->m_ranges.Push(RCHART('a')); pRange->m_ranges.Push(RCHART('z'));
        pRange->m_ranges.Push(RCHART('0')); pRange->m_ranges.Push(RCHART('9'));
        pRange->m_chars .Push(RCHART('_'));

        pStockElxs[nStockId] = pRange;
      }
      break;

    case STOCKELX_WORD_RIGHTLEFT_NOT:
      {
        CRangeElxT <CHART> * pRange = (CRangeElxT <CHART> *)Keep(new CRangeElxT <CHART> (1, 0));

        pRange->m_ranges.Push(RCHART('A')); pRange->m_ranges.Push(RCHART('Z'));
        pRange->m_ranges.Push(RCHART('a')); pRange->m_ranges.Push(RCHART('z'));
        pRange->m_ranges.Push(RCHART('0')); pRange->m_ranges.Push(RCHART('9'));
        pRange->m_chars .Push(RCHART('_'));

        pStockElxs[nStockId] = pRange;
      }
      break;

    case STOCKELX_DOT_ALL_RIGHTLEFT:
      pStockElxs[nStockId] = Keep(new CRangeElxT <CHART> (1, 0));
      break;

    case STOCKELX_DOT_NOT_ALL_RIGHTLEFT:
      {
        CRangeElxT <CHART> * pRange = (CRangeElxT <CHART> *)Keep(new CRangeElxT <CHART> (1, 0));

        pRange->m_chars .Push(RCHART('\n'));

        pStockElxs[nStockId] = pRange;
      }
      break;

    case STOCKELX_SPACE_RIGHTLEFT:
      {
        CRangeElxT <CHART> * pRange = (CRangeElxT <CHART> *)Keep(new CRangeElxT <CHART> (1, 1));

        pRange->m_chars .Push(RCHART(' '));
        pRange->m_chars .Push(RCHART('\t'));
        pRange->m_chars .Push(RCHART('\r'));
        pRange->m_chars .Push(RCHART('\n'));
        pRange->m_chars .Push(RCHART('\f'));
        pRange->m_chars .Push(RCHART('\v'));

        pStockElxs[nStockId] = pRange;
      }
      break;

    case STOCKELX_SPACE_RIGHTLEFT_NOT:
      {
        CRangeElxT <CHART> * pRange = (CRangeElxT <CHART> *)Keep(new CRangeElxT <CHART> (1, 0));

        pRange->m_chars .Push(RCHART(' '));
        pRange->m_chars .Push(RCHART('\t'));
        pRange->m_chars .Push(RCHART('\r'));
        pRange->m_chars .Push(RCHART('\n'));
        pRange->m_chars .Push(RCHART('\f'));
        pRange->m_chars .Push(RCHART('\v'));

        pStockElxs[nStockId] = pRange;
      }
      break;

    case STOCKELX_DIGITAL_RIGHTLEFT:
      {
        CRangeElxT <CHART> * pRange = (CRangeElxT <CHART> *)Keep(new CRangeElxT <CHART> (1, 1));

        pRange->m_ranges.Push(RCHART('0')); pRange->m_ranges.Push(RCHART('9'));

        pStockElxs[nStockId] = pRange;
      }
      break;

    case STOCKELX_DIGITAL_RIGHTLEFT_NOT:
      {
        CRangeElxT <CHART> * pRange = (CRangeElxT <CHART> *)Keep(new CRangeElxT <CHART> (1, 0));

        pRange->m_ranges.Push(RCHART('0')); pRange->m_ranges.Push(RCHART('9'));

        pStockElxs[nStockId] = pRange;
      }
      break;
    }
  }

  // return
  return pStockElxs[nStockId];
}

template <class CHART> ElxInterface * CBuilderT <CHART> :: BuildAlternative(int vaflags)
{
  if(curr == CHART_INFO(0, 1))
    return GetStockElx(STOCKELX_EMPTY);

  // flag instance
  int flags = vaflags;

  // first part
  ElxInterface * pAlternativeOne = BuildList(flags);

  // check alternative
  if(curr == CHART_INFO(RCHART('|'), 1))
  {
    CAlternativeElx * pAlternative = (CAlternativeElx *)Keep(new CAlternativeElx());
    pAlternative->m_elxlist.Push(pAlternativeOne);

    // loop
    while(curr == CHART_INFO(RCHART('|'), 1))
    {
      // skip '|' itself
      MoveNext();

      pAlternativeOne = BuildList(flags);
      pAlternative->m_elxlist.Push(pAlternativeOne);
    }

    return pAlternative;
  }

  return pAlternativeOne;
}

template <class CHART> ElxInterface * CBuilderT <CHART> :: BuildList(int & flags)
{
  if(curr == CHART_INFO(0, 1) || curr == CHART_INFO(RCHART('|'), 1) || curr == CHART_INFO(RCHART(')'), 1))
    return GetStockElx(STOCKELX_EMPTY);

  // first
  ElxInterface * pListOne = BuildRepeat(flags);

  if(curr != CHART_INFO(0, 1) && curr != CHART_INFO(RCHART('|'), 1) && curr != CHART_INFO(RCHART(')'), 1))
  {
    CListElx * pList = (CListElx *)Keep(new CListElx(flags & RIGHTTOLEFT));
    pList->m_elxlist.Push(pListOne);

    while(curr != CHART_INFO(0, 1) && curr != CHART_INFO(RCHART('|'), 1) && curr != CHART_INFO(RCHART(')'), 1))
    {
      pListOne = BuildRepeat(flags);

      // add
      pList->m_elxlist.Push(pListOne);
    }

    return pList;
  }

  return pListOne;
}

template <class CHART> ElxInterface * CBuilderT <CHART> :: BuildRepeat(int & flags)
{
  // simple
  ElxInterface * pSimple = BuildSimple(flags);

  if(curr.type == 0) return pSimple;

  // is quantifier or not
  int bIsQuantifier = 1;

  // quantifier range
  unsigned int nMin = 0, nMax = 0;

  switch(curr.ch)
  {
  case RCHART('{'):
    {
      CBufferT <char> re;

      // skip '{'
      MoveNext();

      // copy
      while(curr != CHART_INFO(0, 1) && curr != CHART_INFO(RCHART('}'), 1))
      {
        re.Append(((curr.ch & (CHART)0xff) == curr.ch) ? (char)curr.ch : 0, 1);
        MoveNext();
      }

      // skip '}'
      MoveNext();

      // read
      int red;
      char * str = re.GetBuffer();

      if( ! ReadDec(str, nMin) )
        red = 0;
      else if( *str != ',' )
        red = 1;
      else
      {
        str ++;

        if( ! ReadDec(str, nMax) )
          red = 2;
        else
          red = 3;
      }

      // check
      if(red  <=  1 ) nMax = nMin;
      if(red  ==  2 ) nMax = INT_MAX;
      if(nMax < nMin) nMax = nMin;
    }
    break;

  case RCHART('?'):
    nMin = 0;
    nMax = 1;

    // skip '?'
    MoveNext();
    break;

  case RCHART('*'):
    nMin = 0;
    nMax = INT_MAX;

    // skip '*'
    MoveNext();
    break;

  case RCHART('+'):
    nMin = 1;
    nMax = INT_MAX;

    // skip '+'
    MoveNext();
    break;

  default:
    bIsQuantifier = 0;
    break;
  }

  // do quantify
  if(bIsQuantifier)
  {
    // 0 times
    if(nMax == 0)
      return GetStockElx(STOCKELX_EMPTY);

    // fixed times
    if(nMin == nMax)
    {
      if(curr == CHART_INFO(RCHART('?'), 1) || curr == CHART_INFO(RCHART('+'), 1))
        MoveNext();

      return Keep(new CRepeatElx(pSimple, nMin));
    }

    // range times
    if(curr == CHART_INFO(RCHART('?'), 1))
    {
      MoveNext();
      return Keep(new CReluctantElx(pSimple, nMin, nMax));
    }
    else if(curr == CHART_INFO(RCHART('+'), 1))
    {
      MoveNext();
      return Keep(new CPossessiveElx(pSimple, nMin, nMax));
    }
    else
    {
      return Keep(new CGreedyElx(pSimple, nMin, nMax));
    }
  }

  return pSimple;
}

template <class CHART> ElxInterface * CBuilderT <CHART> :: BuildSimple(int & flags)
{
  CBufferT <CHART> fixed;

  while(curr != CHART_INFO(0, 1))
  {
    if(curr.type == 0)
    {
      if(next == CHART_INFO(RCHART('{'), 1) || next == CHART_INFO(RCHART('?'), 1) || next == CHART_INFO(RCHART('*'), 1) || next == CHART_INFO(RCHART('+'), 1))
      {
        if(fixed.GetSize() == 0)
        {
          fixed.Append(curr.ch, 1);
          MoveNext();
        }

        break;
      }
      else
      {
        fixed.Append(curr.ch, 1);
        MoveNext();
      }
    }
    else if(curr.type == 1)
    {
      CHART vch = curr.ch;

      // end of simple
      if(vch == RCHART(')') || vch == RCHART('|'))
        break;

      // has fixed already
      if(fixed.GetSize() > 0)
        break;

      // left parentheses
      if(vch == RCHART('('))
      {
        return BuildRecursive(flags);
      }

      // char set
      if( vch == RCHART('[') || vch == RCHART('.') || vch == RCHART('w') || vch == RCHART('W') ||
        vch == RCHART('s') || vch == RCHART('S') || vch == RCHART('d') || vch == RCHART('D')
      )
      {
        return BuildCharset(flags);
      }

      // boundary
      if( vch == RCHART('^') || vch == RCHART('$') || vch == RCHART('A') || vch == RCHART('Z') || vch == RCHART('z') ||
        vch == RCHART('b') || vch == RCHART('B') || vch == RCHART('G') // vch == RCHART('<') || vch == RCHART('>')
      )
      {
        return BuildBoundary(flags);
      }

      // backref
      if(vch == RCHART('\\') || vch == RCHART('k') || vch == RCHART('g'))
      {
        return BuildBackref(flags);
      }

      // treat vchar as char
      fixed.Append(curr.ch, 1);
      MoveNext();
    }
  }

  if(fixed.GetSize() > 0)
    return Keep(new CStringElxT <CHART> (fixed.GetBuffer(), fixed.GetSize(), flags & RIGHTTOLEFT, flags & IGNORECASE));
  else
    return GetStockElx(STOCKELX_EMPTY);
}

#ifndef max
#define max(a, b)  (((a) > (b)) ? (a) : (b))
#endif
#ifndef min
#define min(a, b)  (((a) < (b)) ? (a) : (b))
#endif

template <class CHART> ElxInterface * CBuilderT <CHART> :: BuildCharset(int & flags)
{
  // char
  CHART ch = curr.ch;

  // skip
  MoveNext();

  switch(ch)
  {
  case RCHART('.'):
    return GetStockElx(
      flags & RIGHTTOLEFT ?
      ((flags & SINGLELINE) ? STOCKELX_DOT_ALL_RIGHTLEFT : STOCKELX_DOT_NOT_ALL_RIGHTLEFT) :
      ((flags & SINGLELINE) ? STOCKELX_DOT_ALL : STOCKELX_DOT_NOT_ALL)
    );

  case RCHART('w'):
    return GetStockElx(flags & RIGHTTOLEFT ? STOCKELX_WORD_RIGHTLEFT : STOCKELX_WORD);

  case RCHART('W'):
    return GetStockElx(flags & RIGHTTOLEFT ? STOCKELX_WORD_RIGHTLEFT_NOT : STOCKELX_WORD_NOT);

  case RCHART('s'):
    return GetStockElx(flags & RIGHTTOLEFT ? STOCKELX_SPACE_RIGHTLEFT : STOCKELX_SPACE);

  case RCHART('S'):
    return GetStockElx(flags & RIGHTTOLEFT ? STOCKELX_SPACE_RIGHTLEFT_NOT : STOCKELX_SPACE_NOT);

  case RCHART('d'):
    return GetStockElx(flags & RIGHTTOLEFT ? STOCKELX_DIGITAL_RIGHTLEFT : STOCKELX_DIGITAL);

  case RCHART('D'):
    return GetStockElx(flags & RIGHTTOLEFT ? STOCKELX_DIGITAL_RIGHTLEFT_NOT : STOCKELX_DIGITAL_NOT);

  case RCHART('['):
    {
      CRangeElxT <CHART> * pRange;

      // create
      if(curr == CHART_INFO(RCHART(':'), 1))
      {
        // Backup before posix
        Snapshot shot;
        Backup(&shot);

        CBufferT <char> posix;

        do {
          posix.Append(((curr.ch & (CHART)0xff) == curr.ch) ? (char)curr.ch : 0, 1);
          MoveNext();
        }
        while(curr.ch != RCHART(0) && curr != CHART_INFO(RCHART(']'), 1));

        MoveNext(); // skip ']'

        // posix
        CPosixElxT<CHART> * pposix = (CPosixElxT<CHART> *) Keep(new CPosixElxT <CHART> (posix.GetBuffer(), flags & RIGHTTOLEFT));
        if(pposix->m_posixfun != 0)
        {
          return pposix;
        }

        // restore if not posix
        Restore(&shot);
      }

      if(curr == CHART_INFO(RCHART('^'), 1))
      {
        MoveNext(); // skip '^'
        pRange = (CRangeElxT <CHART> *)Keep(new CRangeElxT <CHART> (flags & RIGHTTOLEFT, 0));
      }
      else
      {
        pRange = (CRangeElxT <CHART> *)Keep(new CRangeElxT <CHART> (flags & RIGHTTOLEFT, 1));
      }

      // parse
      while(curr != CHART_INFO(0, 1) && curr != CHART_INFO(RCHART(']'), 1))
      {
        ch = curr.ch;

        if(curr.type == 1 && (
          ch == RCHART('.') || ch == RCHART('w') || ch == RCHART('W') || ch == RCHART('s') || ch == RCHART('S') || ch == RCHART('d') || ch == RCHART('D') ||
          (ch == RCHART('[') && next == CHART_INFO(RCHART(':'), 1))
        ))
        {
          pRange->m_embeds.Push(BuildCharset(flags));
        }
        else if(next == CHART_INFO(RCHART('-'), 1) && nex2.type == 0)
        {
          pRange->m_ranges.Push(ch); pRange->m_ranges.Push(nex2.ch);

          // next
          MoveNext();
          MoveNext();
          MoveNext();
        }
        else
        {
          pRange->m_chars.Push(ch);

          // next
          MoveNext();
        }
      }

      // skip ']'
      MoveNext();

      if( flags & IGNORECASE )
      {
        CBufferT <CHART> & ranges = pRange->m_ranges;
        int i, oldcount = ranges.GetSize() / 2;

        for(i=0; i<oldcount; i++)
        {
          CHART newmin, newmax;

          if( ranges[i*2] <= RCHART('Z') && ranges[i*2+1] >= RCHART('A') )
          {
            newmin = tolower( max(RCHART('A'), ranges[i*2  ]) );
            newmax = tolower( min(RCHART('Z'), ranges[i*2+1]) );

            if( newmin < ranges[i*2] || newmax > ranges[i*2+1] )
            {
              ranges.Push(newmin);
              ranges.Push(newmax);
            }
          }

          if( ranges[i*2] <= RCHART('z') && ranges[i*2+1] >= RCHART('a') )
          {
            newmin = toupper( max(RCHART('a'), ranges[i*2  ]) );
            newmax = toupper( min(RCHART('z'), ranges[i*2+1]) );

            if( newmin < ranges[i*2] || newmax > ranges[i*2+1] )
            {
              ranges.Push(newmin);
              ranges.Push(newmax);
            }
          }
        }

        CBufferT <CHART> & chars = pRange->m_chars;
        oldcount = chars.GetSize();
        for(i=0; i<oldcount; i++)
        {
          if( isupper(chars[i]) && ! pRange->IsContainChar(tolower(chars[i])) )
            chars.Push(tolower(chars[i]));

          if( islower(chars[i]) && ! pRange->IsContainChar(toupper(chars[i])) )
            chars.Push(toupper(chars[i]));
        }
      }

      return pRange;
    }
  }

  return GetStockElx(STOCKELX_EMPTY);
}

template <class CHART> ElxInterface * CBuilderT <CHART> :: BuildRecursive(int & flags)
{
  // skip '('
  MoveNext();

  if(curr == CHART_INFO(RCHART('?'), 1))
  {
    ElxInterface * pElx = 0;

    // skip '?'
    MoveNext();

    int bNegative = 0;
    CHART named_end = RCHART('>');

    switch(curr.ch)
    {
    case RCHART('!'):
      bNegative = 1;

    case RCHART('='):
      {
        MoveNext(); // skip '!' or '='
        pElx = Keep(new CAssertElx(BuildAlternative(flags & ~RIGHTTOLEFT), !bNegative));
      }
      break;

    case RCHART('<'):
      switch(next.ch)
      {
      case RCHART('!'):
        bNegative = 1;

      case RCHART('='):
        MoveNext(); // skip '<'
        MoveNext(); // skip '!' or '='
        {
          pElx = Keep(new CAssertElx(BuildAlternative(flags | RIGHTTOLEFT), !bNegative));
        }
        break;

      default: // named group
        break;
      }
      // break if assertion // else named
      if(pElx != 0) break;

    case RCHART('P'):
      if(curr.ch == RCHART('P')) MoveNext(); // skip 'P'

    case RCHART('\''):
      if     (curr.ch == RCHART('<' )) named_end = RCHART('>' );
      else if(curr.ch == RCHART('\'')) named_end = RCHART('\'');
      MoveNext(); // skip '<' or '\''
      {
        // named number
        int nThisBackref = m_nNextNamed ++;

        CListElx    * pList  = (CListElx    *)Keep(new CListElx(flags & RIGHTTOLEFT));
        CBracketElx * pleft  = (CBracketElx *)Keep(new CBracketElx(-1, flags & RIGHTTOLEFT ? 1 : 0));
        CBracketElx * pright = (CBracketElx *)Keep(new CBracketElx(-1, flags & RIGHTTOLEFT ? 0 : 1));

        // save name
        CBufferT <CHART> & name = pleft->m_szNamed;
        CBufferT <char> num;

        while(curr.ch != RCHART(0) && curr.ch != named_end)
        {
          name.Append(curr.ch, 1);
          num .Append(((curr.ch & (CHART)0xff) == curr.ch) ? (char)curr.ch : 0, 1);
          MoveNext();
        }
        MoveNext(); // skip '>' or '\''

        // check <num>
        unsigned int number;
        char * str = num.GetBuffer();

        if( ReadDec(str, number) ? ( *str == '\0') : 0 )
        {
          pleft ->m_nnumber = number;
          pright->m_nnumber = number;

          name.Release();
        }

        // left, center, right
        pList->m_elxlist.Push(pleft);
        pList->m_elxlist.Push(BuildAlternative(flags));
        pList->m_elxlist.Push(pright);

        // for recursive
        m_namedlist.Prepare(nThisBackref);
        m_namedlist[nThisBackref] = pList;

        pElx = pList;
      }
      break;

    case RCHART('>'):
      {
        MoveNext(); // skip '>'
        pElx = Keep(new CIndependentElx(BuildAlternative(flags)));
      }
      break;

    case RCHART('R'):
      MoveNext(); // skip 'R'
      while(curr.ch != RCHART(0) && isspace(curr.ch)) MoveNext(); // skip space

      if(curr.ch == RCHART('<') || curr.ch == RCHART('\''))
      {
        named_end = curr.ch == RCHART('<') ? RCHART('>') : RCHART('\'');
        CDelegateElx * pDelegate = (CDelegateElx *)Keep(new CDelegateElx(-3));

        MoveNext(); // skip '<' or '\\'

        // save name
        CBufferT <CHART> & name = pDelegate->m_szNamed;
        CBufferT <char> num;

        while(curr.ch != RCHART(0) && curr.ch != named_end)
        {
          name.Append(curr.ch, 1);
          num .Append(((curr.ch & (CHART)0xff) == curr.ch) ? (char)curr.ch : 0, 1);
          MoveNext();
        }
        MoveNext(); // skip '>' or '\''

        // check <num>
        unsigned int number;
        char * str = num.GetBuffer();

        if( ReadDec(str, number) ? ( *str == '\0') : 0 )
        {
          pDelegate->m_ndata = number;
          name.Release();
        }

        m_recursivelist.Push(pDelegate);
        pElx = pDelegate;
      }
      else
      {
        CBufferT <char> rto;
        while(curr.ch != RCHART(0) && curr.ch != RCHART(')'))
        {
          rto.Append(((curr.ch & (CHART)0xff) == curr.ch) ? (char)curr.ch : 0, 1);
          MoveNext();
        }

        unsigned int rtono = 0;
        char * str = rto.GetBuffer();
        ReadDec(str, rtono);

        CDelegateElx * pDelegate = (CDelegateElx *)Keep(new CDelegateElx(rtono));

        m_recursivelist.Push(pDelegate);
        pElx = pDelegate;
      }
      break;

    case RCHART('('):
      {
        CConditionElx * pConditionElx = (CConditionElx *)Keep(new CConditionElx());

        // condition
        ElxInterface * & pCondition = pConditionElx->m_pelxask;

        if(next == CHART_INFO(RCHART('?'), 1))
        {
          pCondition = BuildRecursive(flags);
        }
        else // named, assert or number
        {
          MoveNext(); // skip '('
          int pos0 = curr.pos;

          // save elx condition
          pCondition = Keep(new CAssertElx(BuildAlternative(flags), 1));

          // save name
          pConditionElx->m_szNamed.Append(m_pattern.GetBuffer() + pos0, curr.pos - pos0, 1);

          // save number
          CBufferT <char> numstr;
          while(pos0 < curr.pos)
          {
            CHART ch = m_pattern[pos0];
            numstr.Append(((ch & (CHART)0xff) == ch) ? (char)ch : 0, 1);
            pos0 ++;
          }

          unsigned int number;
          char * str = numstr.GetBuffer();

          // valid group number
          if( ReadDec(str, number) ? ( *str == '\0') : 0 )
          {
            pConditionElx->m_nnumber = number;
            pCondition = 0;
          }
          else // maybe elx, maybe named
          {
            pConditionElx->m_nnumber = -1;
            m_namedconditionlist.Push(pConditionElx);
          }

          MoveNext(); // skip ')'
        }

        // alternative
        {
          int newflags = flags;

          pConditionElx->m_pelxyes = BuildList(newflags);
        }

        if(curr.ch == RCHART('|'))
        {
          MoveNext(); // skip '|'

          pConditionElx->m_pelxno = BuildAlternative(flags);
        }
        else
        {
          pConditionElx->m_pelxno = 0;
        }

        pElx = pConditionElx;
      }
      break;

    default:
      while(curr.ch != RCHART(0) && isspace(curr.ch)) MoveNext(); // skip space

      if(curr.ch >= RCHART('0') && curr.ch <= RCHART('9')) // recursive (?1) => (?R1)
      {
        CBufferT <char> rto;
        while(curr.ch != RCHART(0) && curr.ch != RCHART(')'))
        {
          rto.Append(((curr.ch & (CHART)0xff) == curr.ch) ? (char)curr.ch : 0, 1);
          MoveNext();
        }

        unsigned int rtono = 0;
        char * str = rto.GetBuffer();
        ReadDec(str, rtono);

        CDelegateElx * pDelegate = (CDelegateElx *)Keep(new CDelegateElx(rtono));

        m_recursivelist.Push(pDelegate);
        pElx = pDelegate;
      }
      else
      {
        // flag
        int newflags = flags;
        while(curr != CHART_INFO(0, 1) && curr.ch != RCHART(':') && curr.ch != RCHART(')') && curr != CHART_INFO(RCHART('('), 1))
        {
          int tochange = 0;

          switch(curr.ch)
          {
          case RCHART('i'):
          case RCHART('I'):
            tochange = IGNORECASE;
            break;

          case RCHART('s'):
          case RCHART('S'):
            tochange = SINGLELINE;
            break;

          case RCHART('m'):
          case RCHART('M'):
            tochange = MULTILINE;
            break;

          case RCHART('g'):
          case RCHART('G'):
            tochange = GLOBAL;
            break;

          case RCHART('-'):
            bNegative = 1;
            break;
          }

          if(bNegative)
            newflags &= ~tochange;
          else
            newflags |=  tochange;

          // move to next char
          MoveNext();
        }

        if(curr.ch == RCHART(':') || curr == CHART_INFO(RCHART('('), 1))
        {
          // skip ':'
          if(curr.ch == RCHART(':')) MoveNext();

          pElx = BuildAlternative(newflags);
        }
        else
        {
          // change parent flags
          flags = newflags;

          pElx = GetStockElx(STOCKELX_EMPTY);
        }
      }
      break;
    }

    MoveNext(); // skip ')'

    return pElx;
  }
  else
  {
    // group and number
    CListElx * pList = (CListElx *)Keep(new CListElx(flags & RIGHTTOLEFT));
    int nThisBackref = ++ m_nMaxNumber;

    // left, center, right
    pList->m_elxlist.Push(Keep(new CBracketElx(nThisBackref, flags & RIGHTTOLEFT ? 1 : 0)));
    pList->m_elxlist.Push(BuildAlternative(flags));
    pList->m_elxlist.Push(Keep(new CBracketElx(nThisBackref, flags & RIGHTTOLEFT ? 0 : 1)));

    // for recursive
    m_grouplist.Prepare(nThisBackref);
    m_grouplist[nThisBackref] = pList;

    // right
    MoveNext(); // skip ')' 

    return pList;
  }
}

template <class CHART> ElxInterface * CBuilderT <CHART> :: BuildBoundary(int & flags)
{
  // char
  CHART ch = curr.ch;

  // skip
  MoveNext();

  switch(ch)
  {
  case RCHART('^'):
    return Keep(new CBoundaryElxT <CHART> ((flags & MULTILINE) ? BOUNDARY_LINE_BEGIN : BOUNDARY_FILE_BEGIN));

  case RCHART('$'):
    return Keep(new CBoundaryElxT <CHART> ((flags & MULTILINE) ? BOUNDARY_LINE_END : BOUNDARY_FILE_END));

  case RCHART('b'):
    return Keep(new CBoundaryElxT <CHART> (BOUNDARY_WORD_EDGE));

  case RCHART('B'):
    return Keep(new CBoundaryElxT <CHART> (BOUNDARY_WORD_EDGE, 0));

  case RCHART('A'):
    return Keep(new CBoundaryElxT <CHART> (BOUNDARY_FILE_BEGIN));

  case RCHART('Z'):
    return Keep(new CBoundaryElxT <CHART> (BOUNDARY_FILE_END_N));

  case RCHART('z'):
    return Keep(new CBoundaryElxT <CHART> (BOUNDARY_FILE_END));

  case RCHART('G'):
    if(flags & GLOBAL)
      return Keep(new CGlobalElx());
    else
      return GetStockElx(STOCKELX_EMPTY);

  default:
    return GetStockElx(STOCKELX_EMPTY);
  }
}

template <class CHART> ElxInterface * CBuilderT <CHART> :: BuildBackref(int & flags)
{
  // skip '\\' or '\k' or '\g'
  MoveNext();

  if(curr.ch == RCHART('<') || curr.ch == RCHART('\''))
  {
    CHART named_end = curr.ch == RCHART('<') ? RCHART('>') : RCHART('\'');
    CBackrefElxT <CHART> * pbackref = (CBackrefElxT <CHART> *)Keep(new CBackrefElxT <CHART> (-1, flags & RIGHTTOLEFT, flags & IGNORECASE));

    MoveNext(); // skip '<' or '\''

    // save name
    CBufferT <CHART> & name = pbackref->m_szNamed;
    CBufferT <char> num;

    while(curr.ch != RCHART(0) && curr.ch != named_end)
    {
      name.Append(curr.ch, 1);
      num .Append(((curr.ch & (CHART)0xff) == curr.ch) ? (char)curr.ch : 0, 1);
      MoveNext();
    }
    MoveNext(); // skip '>' or '\''

    // check <num>
    unsigned int number;
    char * str = num.GetBuffer();

    if( ReadDec(str, number) ? ( *str == '\0') : 0 )
    {
      pbackref->m_nnumber = number;
      name.Release();
    }
    else
    {
      m_namedbackreflist.Push(pbackref);
    }

    return pbackref;
  }
  else
  {
    unsigned int nbackref = 0;

    for(int i=0; i<3; i++)
    {
      if(curr.ch >= RCHART('0') && curr.ch <= RCHART('9'))
        nbackref = nbackref * 10 + (curr.ch - RCHART('0'));
      else
        break;

      MoveNext();
    }

    return Keep(new CBackrefElxT <CHART> (nbackref, flags & RIGHTTOLEFT, flags & IGNORECASE));
  }
}

template <class CHART> int CBuilderT <CHART> :: ReadDec(char * & str, unsigned int & dec)
{
  int s = 0;
  while(str[s] != 0 && isspace(str[s])) s++;

  if(str[s] < '0' || str[s] > '9') return 0;

  dec = 0;
  unsigned int i;

  for(i = s; i<sizeof(CHART)*3 + s; i++)
  {
    if(str[i] >= '0' && str[i] <= '9')
      dec = dec * 10 + (str[i] - '0');
    else
      break;
  }

  while(str[i] != 0 && isspace(str[i])) i++;
  str += i;

  return 1;
}

//
// Regexp
//
template <class CHART> class CRegexpT
{
public:
  CRegexpT(const CHART * pattern = 0, int flags = 0);
  CRegexpT(const CHART * pattern, int length, int flags);
  void Compile(const CHART * pattern, int flags = 0);
  void Compile(const CHART * pattern, int length, int flags);

public:
  MatchResult MatchExact(const CHART * tstring, CContext * pContext = 0) const;
  MatchResult MatchExact(const CHART * tstring, int length, CContext * pContext = 0) const;
  MatchResult Match(const CHART * tstring, int start = -1, CContext * pContext = 0) const;
  MatchResult Match(const CHART * tstring, int length, int start, CContext * pContext = 0) const;
  MatchResult Match(CContext * pContext) const;
  CContext * PrepareMatch(const CHART * tstring, int start = -1, CContext * pContext = 0) const;
  CContext * PrepareMatch(const CHART * tstring, int length, int start, CContext * pContext = 0) const;
  CHART * Replace(const CHART * tstring, const CHART * replaceto, int start = -1, int ntimes = -1, MatchResult * result = 0, CContext * pContext = 0) const;
  CHART * Replace(const CHART * tstring, int string_length, const CHART * replaceto, int to_length, int & result_length, int start = -1, int ntimes = -1, MatchResult * result = 0, CContext * pContext = 0) const;
  int GetNamedGroupNumber(const CHART * group_name) const;

public:
  static void ReleaseString (CHART    * tstring );
  static void ReleaseContext(CContext * pContext);

public:
  CBuilderT <CHART> m_builder;
};

//
// Implementation
//
template <class CHART> CRegexpT <CHART> :: CRegexpT(const CHART * pattern, int flags)
{
  Compile(pattern, CBufferRefT<CHART>(pattern).GetSize(), flags);
}

template <class CHART> CRegexpT <CHART> :: CRegexpT(const CHART * pattern, int length, int flags)
{
  Compile(pattern, length, flags);
}

template <class CHART> inline void CRegexpT <CHART> :: Compile(const CHART * pattern, int flags)
{
  Compile(pattern, CBufferRefT<CHART>(pattern).GetSize(), flags);
}

template <class CHART> void CRegexpT <CHART> :: Compile(const CHART * pattern, int length, int flags)
{
  m_builder.Clear();
  if(pattern != 0) m_builder.Build(CBufferRefT<CHART>(pattern, length), flags);
}

template <class CHART> inline MatchResult CRegexpT <CHART> :: MatchExact(const CHART * tstring, CContext * pContext) const
{
  return MatchExact(tstring, CBufferRefT<CHART>(tstring).GetSize(), pContext);
}

template <class CHART> MatchResult CRegexpT <CHART> :: MatchExact(const CHART * tstring, int length, CContext * pContext) const
{
  if(m_builder.m_pTopElx == 0)
    return 0;

  // info
  int endpos = 0;

  CContext context;
  if(pContext == 0) pContext = &context;

  pContext->m_stack.Restore(0);
  pContext->m_capturestack.Restore(0);
  pContext->m_captureindex.Restore(0);

  pContext->m_nParenZindex  = 0;
  pContext->m_nLastBeginPos = -1;
  pContext->m_pMatchString  = (void*)tstring;
  pContext->m_pMatchStringLength = length;
  pContext->m_nCursiveLimit = 100;

  if(m_builder.m_nFlags & RIGHTTOLEFT)
  {
    pContext->m_nBeginPos   = length;
    pContext->m_nCurrentPos = length;
    endpos = 0;
  }
  else
  {
    pContext->m_nBeginPos   = 0;
    pContext->m_nCurrentPos = 0;
    endpos = length;
  }

  pContext->m_captureindex.Prepare(m_builder.m_nMaxNumber, -1);
  pContext->m_captureindex[0] = 0;
  pContext->m_capturestack.Push(0);
  pContext->m_capturestack.Push(pContext->m_nCurrentPos);
  pContext->m_capturestack.Push(-1);
  pContext->m_capturestack.Push(-1);

  // match
  if( ! m_builder.m_pTopElx->Match( pContext ) )
    return 0;
  else
  {
    while( pContext->m_nCurrentPos != endpos )
    {
      if( ! m_builder.m_pTopElx->MatchNext( pContext ) )
        return 0;
      else
      {
        if( pContext->m_nLastBeginPos == pContext->m_nBeginPos && pContext->m_nBeginPos == pContext->m_nCurrentPos )
          return 0;
        else
          pContext->m_nLastBeginPos = pContext->m_nCurrentPos;
      }
    }

    // end pos
    pContext->m_capturestack[2] = pContext->m_nCurrentPos;

    return MatchResult( pContext, m_builder.m_nMaxNumber );
  }
}

template <class CHART> MatchResult CRegexpT <CHART> :: Match(const CHART * tstring, int start, CContext * pContext) const
{
  return Match(tstring, CBufferRefT<CHART>(tstring).GetSize(), start, pContext);
}

template <class CHART> MatchResult CRegexpT <CHART> :: Match(const CHART * tstring, int length, int start, CContext * pContext) const
{
  if(m_builder.m_pTopElx == 0)
    return 0;

  CContext context;
  if(pContext == 0) pContext = &context;

  PrepareMatch(tstring, length, start, pContext);

  return Match( pContext );
}

template <class CHART> MatchResult CRegexpT <CHART> :: Match(CContext * pContext) const
{
  if(m_builder.m_pTopElx == 0)
    return 0;

  int endpos, delta;

  if(m_builder.m_nFlags & RIGHTTOLEFT)
  {
    endpos = -1;
    delta  = -1;
  }
  else
  {
    endpos = pContext->m_pMatchStringLength + 1;
    delta  = 1;
  }

  while(pContext->m_nCurrentPos != endpos)
  {
    pContext->m_captureindex.Restore(0);
    pContext->m_stack       .Restore(0);
    pContext->m_capturestack.Restore(0);

    pContext->m_captureindex.Prepare(m_builder.m_nMaxNumber, -1);
    pContext->m_captureindex[0] = 0;
    pContext->m_capturestack.Push(0);
    pContext->m_capturestack.Push(pContext->m_nCurrentPos);
    pContext->m_capturestack.Push(-1);
    pContext->m_capturestack.Push(-1);

    if( m_builder.m_pTopElx->Match( pContext ) )
    {
      pContext->m_capturestack[2] = pContext->m_nCurrentPos;

      // zero width
      if( pContext->m_capturestack[1] == pContext->m_nCurrentPos )
      {
        pContext->m_nCurrentPos += delta;
      }

      // save pos
      pContext->m_nLastBeginPos   = pContext->m_nBeginPos;
      pContext->m_nBeginPos       = pContext->m_nCurrentPos;

      // return
      return MatchResult( pContext, m_builder.m_nMaxNumber );
    }
    else
    {
      pContext->m_nCurrentPos += delta;
    }
  }

  return 0;
}

template <class CHART> inline CContext * CRegexpT <CHART> :: PrepareMatch(const CHART * tstring, int start, CContext * pContext) const
{
  return PrepareMatch(tstring, CBufferRefT<CHART>(tstring).GetSize(), start, pContext);
}

template <class CHART> CContext * CRegexpT <CHART> :: PrepareMatch(const CHART * tstring, int length, int start, CContext * pContext) const
{
  if(m_builder.m_pTopElx == 0)
    return 0;

  if(pContext == 0) pContext = new CContext();

  pContext->m_nParenZindex  =  0;
  pContext->m_nLastBeginPos = -1;
  pContext->m_pMatchString  = (void*)tstring;
  pContext->m_pMatchStringLength = length;
  pContext->m_nCursiveLimit = 100;

  if(start < 0)
  {
    if(m_builder.m_nFlags & RIGHTTOLEFT)
    {
      pContext->m_nBeginPos   = length;
      pContext->m_nCurrentPos = length;
    }
    else
    {
      pContext->m_nBeginPos   = 0;
      pContext->m_nCurrentPos = 0;
    }
  }
  else
  {
    if(start > length) start = length + ((m_builder.m_nFlags & RIGHTTOLEFT)?0:1);

    pContext->m_nBeginPos   = start;
    pContext->m_nCurrentPos = start;
  }

  return pContext;
}

template <class CHART> inline int CRegexpT <CHART> :: GetNamedGroupNumber(const CHART * group_name) const
{
  return m_builder.GetNamedNumber(group_name);
}

template <class CHART> CHART * CRegexpT <CHART> :: Replace(const CHART * tstring, const CHART * replaceto, int start, int ntimes, MatchResult * result, CContext * pContext) const
{
  int result_length = 0;
  return Replace(tstring, CBufferRefT<CHART>(tstring).GetSize(), replaceto, CBufferRefT<CHART>(replaceto).GetSize(), result_length, start, ntimes, result, pContext);
}

template <class CHART> CHART * CRegexpT <CHART> :: Replace(const CHART * tstring, int string_length, const CHART * replaceto, int to_length, int & result_length, int start, int ntimes, MatchResult * remote_result, CContext * oContext) const
{
  if(m_builder.m_pTopElx == 0) return 0;

  // --- compile replace to ---

  CBufferT <int> compiledto;

  static const CHART rtoptn[] = { RCHART('\\'), RCHART('$' ), RCHART('('), RCHART('?'), RCHART(':'), RCHART('[' ), RCHART('$' ), RCHART('&' ), RCHART('`' ), RCHART('\''), RCHART('+'), RCHART('_' ), RCHART('\\'), RCHART('d'), RCHART(']'), RCHART('|'), RCHART('\\'), RCHART('{'), RCHART('.'), RCHART('*'), RCHART('?'), RCHART('\\'), RCHART('}'), RCHART(')' ), RCHART('\0') };
  static CRegexpT <CHART> rtoreg(rtoptn);

  MatchResult local_result(0), * result = remote_result ? remote_result : & local_result;

  // prepare
  CContext * pContext = rtoreg.PrepareMatch(replaceto, to_length, -1, oContext);
  int lastIndex = 0, nmatch = 0;

  while( ((*result) = rtoreg.Match(pContext)).IsMatched() )
  {
    int delta = result->GetStart() - lastIndex;
    if( delta > 0 )
    {
      compiledto.Push(lastIndex);
      compiledto.Push(delta);
    }

    lastIndex = result->GetStart();
    delta     = 2;

    switch(replaceto[lastIndex + 1])
    {
    case RCHART('$'):
      compiledto.Push(lastIndex);
      compiledto.Push(1);
      break;

    case RCHART('&'):
    case RCHART('`'):
    case RCHART('\''):
    case RCHART('+'):
    case RCHART('_'):
      compiledto.Push(-1);
      compiledto.Push((int)replaceto[lastIndex + 1]);
      break;

    case RCHART('{'):
      delta  = result->GetEnd() - result->GetStart();
      nmatch = m_builder.GetNamedNumber(CBufferRefT <CHART> (replaceto + (lastIndex + 2), delta - 3));

      if(nmatch > 0 && nmatch <= m_builder.m_nMaxNumber)
      {
        compiledto.Push(-2);
        compiledto.Push(nmatch);
      }
      else
      {
        compiledto.Push(lastIndex);
        compiledto.Push(delta);
      }
      break;

    default:
      nmatch = 0;
      for(delta=1; delta<=3; delta++)
      {
        CHART ch = replaceto[lastIndex + delta];

        if(ch < RCHART('0') || ch > RCHART('9'))
          break;

        nmatch = nmatch * 10 + (ch - RCHART('0'));
      }

      if(nmatch > m_builder.m_nMaxNumber)
      {
        while(nmatch > m_builder.m_nMaxNumber)
        {
          nmatch /= 10;
          delta --;
        }

        if(nmatch == 0)
        {
          delta = 1;
        }
      }

      if(delta == 1)
      {
        compiledto.Push(lastIndex);
        compiledto.Push(1);
      }
      else
      {
        compiledto.Push(-2);
        compiledto.Push(nmatch);
      }
      break;
    }

    lastIndex += delta;
  }

  if(lastIndex < to_length)
  {
    compiledto.Push(lastIndex);
    compiledto.Push(to_length - lastIndex);
  }

  int rightleft = m_builder.m_nFlags & RIGHTTOLEFT;

  int tb = rightleft ? compiledto.GetSize() - 2 : 0;
  int te = rightleft ? -2 : compiledto.GetSize();
  int ts = rightleft ? -2 : 2;

  // --- compile complete ---

  int beginpos  = rightleft ? string_length : 0;
  int endpos    = rightleft ? 0 : string_length;

  int toIndex0  = 0;
  int toIndex1  = 0;
  int i, ntime;

  CBufferT <const CHART *> buffer;

  // prepare
  pContext  = PrepareMatch(tstring, string_length, start, pContext);
  lastIndex = beginpos;

  // Match
  for(ntime = 0; ntimes < 0 || ntime < ntimes; ntime ++)
  {
    (*result) = Match(pContext);

    if( ! result->IsMatched() )
      break;

    // before
    if( rightleft )
    {
      int distance = lastIndex - result->GetEnd();
      if( distance )
      {
        buffer.Push(tstring + result->GetEnd());
        buffer.Push((const CHART *)distance);

        toIndex1 -= distance;
      }
      lastIndex = result->GetStart();
    }
    else
    {
      int distance = result->GetStart() - lastIndex;
      if( distance )
      {
        buffer.Push(tstring + lastIndex);
        buffer.Push((const CHART *)distance);

        toIndex1 += distance;
      }
      lastIndex = result->GetEnd();
    }

    toIndex0 = toIndex1;

    // middle
    for(i=tb; i!=te; i+=ts)
    {
      int off = compiledto[i];
      int len = compiledto[i + 1];

      const CHART * sub = replaceto + off;

      if( off == -1 )
      {
        switch(RCHART(len))
        {
        case RCHART('&'):
          sub = tstring + result->GetStart();
          len = result->GetEnd() - result->GetStart();
          break;

        case RCHART('`'):
          sub = tstring;
          len = result->GetStart();
          break;

        case RCHART('\''):
          sub = tstring + result->GetEnd();
          len = string_length - result->GetEnd();
          break;

        case RCHART('+'):
          for(nmatch = result->MaxGroupNumber(); nmatch >= 0; nmatch --)
          {
            if(result->GetGroupStart(nmatch) >= 0) break;
          }
          sub = tstring + result->GetGroupStart(nmatch);
          len = result->GetGroupEnd(nmatch) - result->GetGroupStart(nmatch);
          break;

        case RCHART('_'):
          sub = tstring;
          len = string_length;
          break;
        }
      }
      else if( off == -2 )
      {
        sub = tstring + result->GetGroupStart(len);
        len = result->GetGroupEnd(len) - result->GetGroupStart(len);
      }

      buffer.Push(sub);
      buffer.Push((const CHART *)len);

      toIndex1 += rightleft ? (-len) : len;
    }
  }

  // after
  if(rightleft)
  {
    if(endpos < lastIndex)
    {
      buffer.Push(tstring + endpos);
      buffer.Push((const CHART *)(lastIndex - endpos));
    }
  }
  else
  {
    if(lastIndex < endpos)
    {
      buffer.Push(tstring + lastIndex);
      buffer.Push((const CHART *)(endpos - lastIndex));
    }
  }

  if(oContext == 0) ReleaseContext(pContext);

  // join string
  result_length = 0;
  for(i=0; i<buffer.GetSize(); i+=2)
  {
    result_length += (int)buffer[i+1];
  }

  CBufferT <CHART> result_string;
  result_string.Prepare(result_length);
  result_string.Restore(0);

  if(rightleft)
  {
    for(i=buffer.GetSize()-2; i>=0; i-=2)
    {
      result_string.Append(buffer[i], (int)buffer[i+1]);
    }
  }
  else
  {
    for(i=0; i<buffer.GetSize(); i+=2)
    {
      result_string.Append(buffer[i], (int)buffer[i+1]);
    }
  }

  result_string.Append(0);

  result->m_result.Append(result_length, 3);
  result->m_result.Append(ntime);

  if(rightleft)
  {
    result->m_result.Append(result_length - toIndex1);
    result->m_result.Append(result_length - toIndex0);
  }
  else
  {
    result->m_result.Append(toIndex0);
    result->m_result.Append(toIndex1);
  }

  return result_string.Detach();
}

template <class CHART> inline void CRegexpT <CHART> :: ReleaseString(CHART * tstring)
{
  if(tstring != 0) free(tstring);
}

template <class CHART> inline void CRegexpT <CHART> :: ReleaseContext(CContext * pContext)
{
  if(pContext != 0) delete pContext;
}

//
// All implementations
//
template <int x> CAlternativeElxT <x> :: CAlternativeElxT()
{
}

template <int x> int CAlternativeElxT <x> :: Match(CContext * pContext) const
{
  if(m_elxlist.GetSize() == 0)
    return 1;

  // try all
  for(int n = 0; n < m_elxlist.GetSize(); n++)
  {
    if(m_elxlist[n]->Match(pContext))
    {
      pContext->m_stack.Push(n);
      return 1;
    }
  }

  return 0;
}

template <int x> int CAlternativeElxT <x> :: MatchNext(CContext * pContext) const
{
  if(m_elxlist.GetSize() == 0)
    return 0;

  int n = 0;

  // recall prev
  pContext->m_stack.Pop(n);

  // prev
  if(m_elxlist[n]->MatchNext(pContext))
  {
    pContext->m_stack.Push(n);
    return 1;
  }
  else
  {
    // try rest
    for(n++; n < m_elxlist.GetSize(); n++)
    {
      if(m_elxlist[n]->Match(pContext))
      {
        pContext->m_stack.Push(n);
        return 1;
      }
    }

    return 0;
  }
}

// assertx.cpp: implementation of the CAssertElx class.
//
template <int x> CAssertElxT <x> :: CAssertElxT(ElxInterface * pelx, int byes)
{
  m_pelx = pelx;
  m_byes = byes;
}

template <int x> int CAssertElxT <x> :: Match(CContext * pContext) const
{
  int nbegin = pContext->m_nCurrentPos;
  int nsize  = pContext->m_stack.GetSize();
  int ncsize = pContext->m_capturestack.GetSize();
  int bsucc;

  // match
  if( m_byes )
    bsucc =   m_pelx->Match(pContext);
  else
    bsucc = ! m_pelx->Match(pContext);

  // status
  pContext->m_stack.Restore(nsize);
  pContext->m_nCurrentPos = nbegin;

  if( bsucc )
    pContext->m_stack.Push(ncsize);
  else
    pContext->m_capturestack.Restore(ncsize);

  return bsucc;
}

template <int x> int CAssertElxT <x> :: MatchNext(CContext * pContext) const
{
  int ncsize = 0;

  pContext->m_stack.Pop(ncsize);
  pContext->m_capturestack.Restore(ncsize);

  return 0;
}

// emptyelx.cpp: implementation of the CEmptyElx class.
//
template <int x> CEmptyElxT <x> :: CEmptyElxT()
{
}

template <int x> int CEmptyElxT <x> :: Match(CContext *) const
{
  return 1;
}

template <int x> int CEmptyElxT <x> :: MatchNext(CContext *) const
{
  return 0;
}

// globalx.cpp: implementation of the CGlobalElx class.
//
template <int x> CGlobalElxT <x> ::CGlobalElxT()
{
}

template <int x> int CGlobalElxT <x> :: Match(CContext * pContext) const
{
  return pContext->m_nCurrentPos == pContext->m_nBeginPos;
}

template <int x> int CGlobalElxT <x> :: MatchNext(CContext *) const
{
  return 0;
}

// greedelx.cpp: implementation of the CGreedyElx class.
//
template <int x> CGreedyElxT <x> :: CGreedyElxT(ElxInterface * pelx, int nmin, int nmax) : CRepeatElxT <x> (pelx, nmin)
{
  m_nvart = nmax - nmin;
}

template <int x> int CGreedyElxT <x> :: Match(CContext * pContext) const
{
  if( ! CRepeatElxT <x> :: MatchFixed(pContext) )
    return 0;

  while( ! MatchVart(pContext) )
  {
    if( ! CRepeatElxT <x> :: MatchNextFixed(pContext) )
      return 0;
  }

  return 1;
}

template <int x> int CGreedyElxT <x> :: MatchNext(CContext * pContext) const
{
  if( MatchNextVart(pContext) )
    return 1;

  if( ! CRepeatElxT <x> :: MatchNextFixed(pContext) )
    return 0;

  while( ! MatchVart(pContext) )
  {
    if( ! CRepeatElxT <x> :: MatchNextFixed(pContext) )
      return 0;
  }

  return 1;
}

template <int x> int CGreedyElxT <x> :: MatchVart(CContext * pContext) const
{
  int n      = 0;
  int nbegin00 = pContext->m_nCurrentPos;
  int nsize    = pContext->m_stack.GetSize();
  int ncsize   = pContext->m_capturestack.GetSize();

  while(n < m_nvart && CRepeatElx::MatchForward(pContext))
  {
    n ++;
  }

  pContext->m_stack.Push(ncsize);
  pContext->m_stack.Push(nsize);
  pContext->m_stack.Push(pContext->m_nCurrentPos);
  pContext->m_stack.Push(1);
  pContext->m_stack.Push(nbegin00);
  pContext->m_stack.Push(n);

  return 1;
}

template <int x> int CGreedyElxT <x> :: MatchNextVart(CContext * pContext) const
{
  int n, nbegin00, nsize, ncsize;
  CSortedBufferT <int> nbegin99;
  pContext->m_stack.Pop(n);
  pContext->m_stack.Pop(nbegin00);
  pContext->m_stack.Pop(nbegin99);
  pContext->m_stack.Pop(nsize);
  pContext->m_stack.Pop(ncsize);

  if(n == 0) return 0;

  int n0 = n;

  if( ! CRepeatElxT<x>::m_pelx->MatchNext(pContext) )
  {
    n --;
  }

  // not to re-match
  else if(pContext->m_nCurrentPos == nbegin00)
  {
    pContext->m_stack.Restore(nsize);
    pContext->m_capturestack.Restore(ncsize);
    pContext->m_nCurrentPos = nbegin00;

    return 0;
  }

  // fix 2012-10-26, thanks to chenlx01@sohu.com
  else
  {
    CContextShot shot(pContext);

    while(n < m_nvart && CRepeatElx::MatchForward(pContext))
    {
      n ++;
    }

    if(nbegin99.Find(pContext->m_nCurrentPos) >= 0)
    {
      shot.Restore(pContext);
      n = n0;
    }
    else
    {
      nbegin99.Add(pContext->m_nCurrentPos);
    }
  }

  pContext->m_stack.Push(ncsize);
  pContext->m_stack.Push(nsize);
  pContext->m_stack.Push(nbegin99);
  pContext->m_stack.Push(nbegin00);
  pContext->m_stack.Push(n);

  return 1;
}

// indepelx.cpp: implementation of the CIndependentElx class.
//
template <int x> CIndependentElxT <x> :: CIndependentElxT(ElxInterface * pelx)
{
  m_pelx = pelx;
}

template <int x> int CIndependentElxT <x> :: Match(CContext * pContext) const
{
  int nbegin = pContext->m_nCurrentPos;
  int nsize  = pContext->m_stack.GetSize();
  int ncsize = pContext->m_capturestack.GetSize();

  // match
  int bsucc  = m_pelx->Match(pContext);

  // status
  pContext->m_stack.Restore(nsize);

  if( bsucc )
  {
    pContext->m_stack.Push(nbegin);
    pContext->m_stack.Push(ncsize);
  }

  return bsucc;
}

template <int x> int CIndependentElxT <x> :: MatchNext(CContext * pContext) const
{
  int nbegin = 0, ncsize = 0;

  pContext->m_stack.Pop(ncsize);
  pContext->m_stack.Pop(nbegin);

  pContext->m_capturestack.Restore(ncsize);
  pContext->m_nCurrentPos = nbegin;

  return 0;
}

// listelx.cpp: implementation of the CListElx class.
//
template <int x> CListElxT <x> :: CListElxT(int brightleft)
{
  m_brightleft = brightleft;
}

template <int x> int CListElxT <x> :: Match(CContext * pContext) const
{
  if(m_elxlist.GetSize() == 0)
    return 1;

  // prepare
  int bol = m_brightleft ? m_elxlist.GetSize() : -1;
  int stp = m_brightleft ? -1 : 1;
  int eol = m_brightleft ? -1 : m_elxlist.GetSize();

  // from first
  int n = bol + stp;

  // match all
  while(n != eol)
  {
    if(m_elxlist[n]->Match(pContext))
    {
      n += stp;
    }
    else
    {
      n -= stp;

      while(n != bol && ! m_elxlist[n]->MatchNext(pContext))
        n -= stp;

      if(n != bol)
        n += stp;
      else
        return 0;
    }
  }

  return 1;
}

template <int x> int CListElxT <x> :: MatchNext(CContext * pContext) const
{
  if(m_elxlist.GetSize() == 0)
    return 0;

  // prepare
  int bol = m_brightleft ? m_elxlist.GetSize() : -1;
  int stp = m_brightleft ? -1 : 1;
  int eol = m_brightleft ? -1 : m_elxlist.GetSize();

  // from last
  int n = eol - stp;

  while(n != bol && ! m_elxlist[n]->MatchNext(pContext))
    n -= stp;

  if(n != bol)
    n += stp;
  else
    return 0;

  // match rest
  while(n != eol)
  {
    if(m_elxlist[n]->Match(pContext))
    {
      n += stp;
    }
    else
    {
      n -= stp;

      while(n != bol && ! m_elxlist[n]->MatchNext(pContext))
        n -= stp;

      if(n != bol)
        n += stp;
      else
        return 0;
    }
  }

  return 1;
}

// mresult.cpp: implementation of the MatchResult class.
//
template <int x> MatchResultT <x> :: MatchResultT(CContext * pContext, int nMaxNumber)
{
  if(pContext != 0)
  {
    m_result.Prepare(nMaxNumber * 2 + 3, -1);

    // matched
    m_result[0] = 1;
    m_result[1] = nMaxNumber;

    for(int n = 0; n <= nMaxNumber; n++)
    {
      int index = pContext->m_captureindex[n];
      //if( index < 0 ) continue;
      if( ! CBracketElxT<char>::CheckCaptureIndex(index, pContext, n) ) continue;

      // check enclosed
      int pos1 = pContext->m_capturestack[index + 1];
      int pos2 = pContext->m_capturestack[index + 2];

      // info
      m_result[n*2 + 2] = pos1 < pos2 ? pos1 : pos2;
      m_result[n*2 + 3] = pos1 < pos2 ? pos2 : pos1;
    }
  }
}

template <int x> inline int MatchResultT <x> :: IsMatched() const
{
  return m_result.At(0, 0);
}

template <int x> inline int MatchResultT <x> :: MaxGroupNumber() const
{
  return m_result.At(1, 0);
}

template <int x> inline int MatchResultT <x> :: GetStart() const
{
  return m_result.At(2, -1);
}

template <int x> inline int MatchResultT <x> :: GetEnd() const
{
  return m_result.At(3, -1);
}

template <int x> inline int MatchResultT <x> :: GetGroupStart(int nGroupNumber) const
{
  return m_result.At(2 + nGroupNumber * 2, -1);
}

template <int x> inline int MatchResultT <x> :: GetGroupEnd(int nGroupNumber) const
{
  return m_result.At(2 + nGroupNumber * 2 + 1, -1);
}

template <int x> MatchResultT <x> & MatchResultT <x> :: operator = (const MatchResultT <x> & result)
{
  m_result.Restore(0);
  if(result.m_result.GetSize() > 0) m_result.Append(result.m_result.GetBuffer(), result.m_result.GetSize());

  return *this;
}

// posselx.cpp: implementation of the CPossessiveElx class.
//
template <int x> CPossessiveElxT <x> :: CPossessiveElxT(ElxInterface * pelx, int nmin, int nmax) : CGreedyElxT <x> (pelx, nmin, nmax)
{
}

template <int x> int CPossessiveElxT <x> :: Match(CContext * pContext) const
{
  int nbegin = pContext->m_nCurrentPos;
  int nsize  = pContext->m_stack.GetSize();
  int ncsize = pContext->m_capturestack.GetSize();
  int bsucc  = 1;

  // match
  if( ! CRepeatElxT <x> :: MatchFixed(pContext) )
  {
    bsucc = 0;
  }
  else
  {
    while( ! CGreedyElxT <x> :: MatchVart(pContext) )
    {
      if( ! CRepeatElxT <x> :: MatchNextFixed(pContext) )
      {
        bsucc = 0;
        break;
      }
    }
  }

  // status
  pContext->m_stack.Restore(nsize);

  if( bsucc )
  {
    pContext->m_stack.Push(nbegin);
    pContext->m_stack.Push(ncsize);
  }

  return bsucc;
}

template <int x> int CPossessiveElxT <x> :: MatchNext(CContext * pContext) const
{
  int nbegin = 0, ncsize = 0;

  pContext->m_stack.Pop(ncsize);
  pContext->m_stack.Pop(nbegin);

  pContext->m_capturestack.Restore(ncsize);
  pContext->m_nCurrentPos = nbegin;

  return 0;
}

// reluctx.cpp: implementation of the CReluctantElx class.
//
template <int x> CReluctantElxT <x> :: CReluctantElxT(ElxInterface * pelx, int nmin, int nmax) : CRepeatElxT <x> (pelx, nmin)
{
  m_nvart = nmax - nmin;
}

template <int x> int CReluctantElxT <x> :: Match(CContext * pContext) const
{
  if( ! CRepeatElxT <x> :: MatchFixed(pContext) )
    return 0;

  while( ! MatchVart(pContext) )
  {
    if( ! CRepeatElxT <x> :: MatchNextFixed(pContext) )
      return 0;
  }

  return 1;
}

template <int x> int CReluctantElxT <x> :: MatchNext(CContext * pContext) const
{
  if( MatchNextVart(pContext) )
    return 1;

  if( ! CRepeatElxT <x> :: MatchNextFixed(pContext) )
    return 0;

  while( ! MatchVart(pContext) )
  {
    if( ! CRepeatElxT <x> :: MatchNextFixed(pContext) )
      return 0;
  }

  return 1;
}

template <int x> int CReluctantElxT <x> :: MatchVart(CContext * pContext) const
{
  pContext->m_stack.Push(0);

  return 1;
}

template <int x> int CReluctantElxT <x> :: MatchNextVart(CContext * pContext) const
{
  int n = 0, nbegin = pContext->m_nCurrentPos;

  pContext->m_stack.Pop(n);

  if(n < m_nvart && CRepeatElxT <x> :: m_pelx->Match(pContext))
  {
    while(pContext->m_nCurrentPos == nbegin)
    {
      if( ! CRepeatElxT <x> :: m_pelx->MatchNext(pContext) ) break;
    }

    if(pContext->m_nCurrentPos != nbegin)
    {
      n ++;

      pContext->m_stack.Push(nbegin);
      pContext->m_stack.Push(n);

      return 1;
    }
  }

  while(n > 0)
  {
    pContext->m_stack.Pop(nbegin);

    while( CRepeatElxT <x> :: m_pelx->MatchNext(pContext) )
    {
      if(pContext->m_nCurrentPos != nbegin)
      {
        pContext->m_stack.Push(nbegin);
        pContext->m_stack.Push(n);

        return 1;
      }
    }

    n --;
  }

  return 0;
}

// repeatx.cpp: implementation of the CRepeatElx class.
//
template <int x> CRepeatElxT <x> :: CRepeatElxT(ElxInterface * pelx, int ntimes)
{
  m_pelx   = pelx;
  m_nfixed = ntimes;
}

template <int x> int CRepeatElxT <x> :: Match(CContext * pContext) const
{
  return MatchFixed(pContext);
}

template <int x> int CRepeatElxT <x> :: MatchNext(CContext * pContext) const
{
  return MatchNextFixed(pContext);
}

template <int x> int CRepeatElxT <x> :: MatchFixed(CContext * pContext) const
{
  if(m_nfixed == 0)
    return 1;

  int n = 0;

  while(n < m_nfixed)
  {
    if(m_pelx->Match(pContext))
    {
      n ++;
    }
    else
    {
      n --;

      while(n >= 0 && ! m_pelx->MatchNext(pContext))
        n --;

      if(n >= 0)
        n ++;
      else
        return 0;
    }
  }

  return 1;
}

template <int x> int CRepeatElxT <x> :: MatchNextFixed(CContext * pContext) const
{
  if(m_nfixed == 0)
    return 0;

  // from last
  int n = m_nfixed - 1;

  while(n >= 0 && ! m_pelx->MatchNext(pContext))
    n --;

  if(n >= 0)
    n ++;
  else
    return 0;

  // match rest
  while(n < m_nfixed)
  {
    if(m_pelx->Match(pContext))
    {
      n ++;
    }
    else
    {
      n --;

      while(n >= 0 && ! m_pelx->MatchNext(pContext))
        n --;

      if(n >= 0)
        n ++;
      else
        return 0;
    }
  }

  return 1;
}

// Regexp
typedef CRegexpT <char> CRegexpA;
typedef CRegexpT <unsigned short> CRegexpW;

#if defined(_UNICODE) || defined(UNICODE)
  typedef CRegexpW CRegexp;
#else
  typedef CRegexpA CRegexp;
#endif

#endif//__DEELX_REGEXP__H__