text: // MarkupSTL.cpp: implementation of the CMarkupSTL class.
  //
  // Markup Release 6.3
  // Copyright (C) 1999-2002 First Objective Software, Inc. All rights reserved
  // Go to www.firstobject.com for the latest CMarkup and EDOM documentation
  // Use in commercial applications requires written permission
  // This software is provided "as is", with no warranty.
  
  #include "StdAfx.h"
  
  using namespace std;
  
  #ifdef _DEBUG
  #undef THIS_FILE
  static char THIS_FILE[]=__FILE__;
  #define new DEBUG_NEW
  #endif
  
  namespace StdUtils
  {
  
  void CMarkupSTL::operator=( const CMarkupSTL& markup )
  {
  	m_iPosParent = markup.m_iPosParent;
  	m_iPos = markup.m_iPos;
  	m_iPosChild = markup.m_iPosChild;
  	m_iPosFree = markup.m_iPosFree;
  	m_nNodeType = markup.m_nNodeType;
  	m_aPos = markup.m_aPos;
  	m_strDoc = markup.m_strDoc;
  	MARKUP_SETDEBUGSTATE;
  }
  
  bool CMarkupSTL::SetDoc( const char* szDoc )
  {
  	// Reset indexes
  	m_iPosFree = 1;
  	ResetPos();
  	m_mapSavedPos.clear();
  
  	// Set document text
  	if ( szDoc )
  		m_strDoc = szDoc;
  	else
  		m_strDoc.erase();
  
  	// Starting size of position array: 1 element per 64 bytes of document
  	// Tight fit when parsing small doc, only 0 to 2 reallocs when parsing large doc
  	// Start at 8 when creating new document
  	int nStartSize = m_strDoc.size() / 64 + 8;
  	if ( m_aPos.size() < nStartSize )
  		m_aPos.resize( nStartSize );
  
  	// Parse document
  	bool bWellFormed = false;
  	if ( m_strDoc.size() )
  	{
  		m_aPos[0].Clear();
  		int iPos = x_ParseElem( 0 );
  		if ( iPos > 0 )
  		{
  			m_aPos[0].iElemChild = iPos;
  			bWellFormed = true;
  		}
  	}
  
  	// Clear indexes if parse failed or empty document
  	if ( ! bWellFormed )
  	{
  		m_aPos[0].Clear();
  		m_iPosFree = 1;
  	}
  
  	ResetPos();
  	return bWellFormed;
  };
  
  bool CMarkupSTL::IsWellFormed()
  {
  	if ( m_aPos.size() && m_aPos[0].iElemChild )
  		return true;
  	return false;
  }
  
  bool CMarkupSTL::Load( const char* szFileName )
  {
  	// Load document from file
  	bool bResult = false;
  	FILE* fp = fopen( szFileName, "rb" );
  	if ( fp )
  	{
  		// Determine file length
  		fseek( fp, 0L, SEEK_END );
  		int nFileLen = ftell(fp);
  		fseek( fp, 0L, SEEK_SET );
  
  		// Load string
  		allocator<char> mem;
  		allocator<char>::pointer pBuffer = mem.allocate(nFileLen+1, NULL);
  		if ( fread( pBuffer, nFileLen, 1, fp ) == 1 )
  		{
  			pBuffer[nFileLen] = '\0';
  			bResult = SetDoc( pBuffer );
  		}
  		fclose(fp);
  		mem.deallocate(pBuffer,1);
  	}
  	if ( ! bResult )
  		SetDoc(NULL);
  	MARKUP_SETDEBUGSTATE;
  	return bResult;
  }
  
  bool CMarkupSTL::Save( const char* szFileName )
  {
  	// Save document to file
  	bool bResult = false;
  	FILE* fp = fopen( szFileName, "wb" );
  	if ( fp )
  	{
  		// Save string
  		int nFileLen = m_strDoc.size();
  		if ( ! nFileLen )
  			bResult = true;
  		else if ( fwrite( m_strDoc.c_str(), nFileLen, 1, fp ) == 1 )
  			bResult = true;
  		fclose(fp);
  	}
  	return bResult;
  }
  
  bool CMarkupSTL::FindElem( const char* szName )
  {
  	// Change current position only if found
  	//
  	if ( m_aPos.size() )
  	{
  		int iPos = x_FindElem( m_iPosParent, m_iPos, szName );
  		if ( iPos )
  		{
  			// Assign new position
  			x_SetPos( m_aPos[iPos].iElemParent, iPos, 0 );
  			return true;
  		}
  	}
  	return false;
  }
  
  bool CMarkupSTL::FindChildElem( const char* szName )
  {
  	// Change current child position only if found
  	//
  	// Shorthand: call this with no current main position
  	// means find child under root element
  	if ( ! m_iPos )
  		FindElem();
  
  	int iPosChild = x_FindElem( m_iPos, m_iPosChild, szName );
  	if ( iPosChild )
  	{
  		// Assign new position
  		int iPos = m_aPos[iPosChild].iElemParent;
  		x_SetPos( m_aPos[iPos].iElemParent, iPos, iPosChild );
  		return true;
  	}
  
  	return false;
  }
  
  std::string CMarkupSTL::GetTagName() const
  {
  	// Return the tag name at the current main position
  	std::string strTagName;
  
  	if ( m_iPos )
  		strTagName = x_GetTagName( m_iPos );
  	return strTagName;
  }
  
  bool CMarkupSTL::IntoElem()
  {
  	// If there is no child position and IntoElem is called it will succeed in release 6.3
  	// (A subsequent call to FindElem will find the first element)
  	// The following short-hand behavior was never part of EDOM and was misleading
  	// It would find a child element if there was no current child element position and go into it
  	// It is removed in release 6.3, this change is NOT backwards compatible!
  	// if ( ! m_iPosChild )
  	//	FindChildElem();
  
  	if ( m_iPos && m_nNodeType == MNT_ELEMENT )
  	{
  		x_SetPos( m_iPos, m_iPosChild, 0 );
  		return true;
  	}
  	return false;
  }
  
  bool CMarkupSTL::OutOfElem()
  {
  	// Go to parent element
  	if ( m_iPosParent )
  	{
  		x_SetPos( m_aPos[m_iPosParent].iElemParent, m_iPosParent, m_iPos );
  		return true;
  	}
  	return false;
  }
  
  std::string CMarkupSTL::GetAttribName( int n ) const
  {
  	// Return nth attribute name of main position
  	if ( ! m_iPos || m_nNodeType != MNT_ELEMENT )
  		return "";
  
  	TokenPos token( m_strDoc.c_str() );
  	token.nNext = m_aPos[m_iPos].nStartL + 1;
  	for ( int nAttrib=0; nAttrib<=n; ++nAttrib )
  		if ( ! x_FindAttrib(token) )
  			return "";
  
  	// Return substring of document
  	return x_GetToken( token );
  }
  
  bool CMarkupSTL::SavePos( const char* szPosName )
  {
  	// Save current element position in saved position map
  	if ( szPosName )
  	{
  		SavedPos savedpos;
  		savedpos.iPosParent = m_iPosParent;
  		savedpos.iPos = m_iPos;
  		savedpos.iPosChild = m_iPosChild;
  		string strPosName = szPosName;
  		m_mapSavedPos[strPosName] = savedpos;
  		return true;
  	}
  	return false;
  }
  
  bool CMarkupSTL::RestorePos( const char* szPosName )
  {
  	// Restore element position if found in saved position map
  	if ( szPosName )
  	{
  		std::string strPosName = szPosName;
  		mapSavedPosT::const_iterator iterSavePos = m_mapSavedPos.find( strPosName );
  		if ( iterSavePos != m_mapSavedPos.end() )
  		{
  			SavedPos savedpos = (*iterSavePos).second;
  			x_SetPos( savedpos.iPosParent, savedpos.iPos, savedpos.iPosChild );
  			return true;
  		}
  	}
  	return false;
  }
  
  bool CMarkupSTL::GetOffsets( int& nStart, int& nEnd ) const
  {
  	// Return document offsets of current main position element
  	// This is not part of EDOM but is used by the Markup project
  	if ( m_iPos )
  	{
  		nStart = m_aPos[m_iPos].nStartL;
  		nEnd = m_aPos[m_iPos].nEndR;
  		return true;
  	}
  	return false;
  }
  
  std::string CMarkupSTL::GetChildSubDoc() const
  {
  	if ( m_iPosChild )
  	{
  		int nL = m_aPos[m_iPosChild].nStartL;
  		int nR = m_aPos[m_iPosChild].nEndR + 1;
  		TokenPos token( m_strDoc.c_str() );
  		token.nNext = nR;
  		if ( ! x_FindToken(token) || m_strDoc[token.nL] == '<' )
  			nR = token.nL;
  		return m_strDoc.substr( nL, nR - nL );
  	}
  	return "";
  }
  
  bool CMarkupSTL::RemoveElem()
  {
  	// Remove current main position element
  	if ( m_iPos && m_nNodeType == MNT_ELEMENT )
  	{
  		int iPos = x_RemoveElem( m_iPos );
  		x_SetPos( m_iPosParent, iPos, 0 );
  		return true;
  	}
  	return false;
  }
  
  bool CMarkupSTL::RemoveChildElem()
  {
  	// Remove current child position element
  	if ( m_iPosChild )
  	{
  		int iPosChild = x_RemoveElem( m_iPosChild );
  		x_SetPos( m_iPosParent, m_iPos, iPosChild );
  		return true;
  	}
  	return false;
  }
  
  //////////////////////////////////////////////////////////////////////
  // Private Methods
  //////////////////////////////////////////////////////////////////////
  
  int CMarkupSTL::x_GetFreePos()
  {
  	//
  	// This returns the index of the next unused ElemPos in the array
  	//
  	if ( m_iPosFree == m_aPos.size() )
  		m_aPos.resize( m_iPosFree + m_iPosFree / 2 );
  	++m_iPosFree;
  	return m_iPosFree - 1;
  }
  
  int CMarkupSTL::x_ReleasePos()
  {
  	//
  	// This decrements the index of the next unused ElemPos in the array
  	// allowing the element index returned by GetFreePos() to be reused
  	//
  	--m_iPosFree;
  	return 0;
  }
  
  int CMarkupSTL::x_ParseError( const char* szError, const char* szName )
  {
  	if ( szName )
  	{
  		char szFormat[300];
  		sprintf( szFormat, szError, szName );
  		m_strError = szFormat;
  	}
  	else
  		m_strError = szError;
  	x_ReleasePos();
  	return -1;
  }
  
  int CMarkupSTL::x_ParseElem( int iPosParent )
  {
  	// This is either called by SetDoc, x_AddSubDoc, or itself recursively
  	// m_aPos[iPosParent].nEndL is where to start parsing for the child element
  	// This returns the new position if a tag is found, otherwise zero
  	// In all cases we need to get a new ElemPos, but release it if unused
  	//
  	int iPos = x_GetFreePos();
  	m_aPos[iPos].nStartL = m_aPos[iPosParent].nEndL;
  	m_aPos[iPos].iElemParent = iPosParent;
  	m_aPos[iPos].iElemChild = 0;
  	m_aPos[iPos].iElemNext = 0;
  
  	// Start Tag
  	// A loop is used to ignore all remarks tags and special tags
  	// i.e. <?xml version="1.0"?>, and <!-- comment here -->
  	// So any tag beginning with ? or ! is ignored
  	// Loop past ignored tags
  	TokenPos token( m_strDoc.c_str() );
  	token.nNext = m_aPos[iPosParent].nEndL;
  	std::string strName;
  	while ( strName.empty() )
  	{
  		// Look for left angle bracket of start tag
  		m_aPos[iPos].nStartL = token.nNext;
  		if ( ! x_FindChar( token.szDoc, m_aPos[iPos].nStartL, '<' ) )
  			return x_ParseError( "Element tag not found" );
  
  		// Set parent's End tag to start looking from here (or later)
  		m_aPos[iPosParent].nEndL = m_aPos[iPos].nStartL;
  
  		// Determine whether this is an element, or bypass other type of node
  		token.nNext = m_aPos[iPos].nStartL + 1;
  		if ( x_FindToken( token ) )
  		{
  			if ( token.bIsString )
  				return x_ParseError( "Tag starts with quote" );
  			char cFirstChar = m_strDoc[token.nL];
  			if ( cFirstChar == '?' || cFirstChar == '!' )
  			{
  				token.nNext = m_aPos[iPos].nStartL;
  				if ( ! x_ParseNode(token) )
  					return x_ParseError( "Invalid node" );
  			}
  			else if ( cFirstChar != '/' )
  			{
  				strName = x_GetToken( token );
  				// Look for end of tag
  				if ( ! x_FindChar(token.szDoc, token.nNext, '>') )
  					return x_ParseError( "End of tag not found" );
  			}
  			else
  				return x_ReleasePos(); // probably end tag of parent
  		}
  		else
  			return x_ParseError( "Abrupt end within tag" );
  	}
  	m_aPos[iPos].nStartR = token.nNext;
  
  	// Is ending mark within start tag, i.e. empty element?
  	if ( m_strDoc[m_aPos[iPos].nStartR-1] == '/' )
  	{
  		// Empty element
  		// Close tag left is set to ending mark, and right to open tag right
  		m_aPos[iPos].nEndL = m_aPos[iPos].nStartR-1;
  		m_aPos[iPos].nEndR = m_aPos[iPos].nStartR;
  	}
  	else // look for end tag
  	{
  		// Element probably has contents
  		// Determine where to start looking for left angle bracket of end tag
  		// This is done by recursively parsing the contents of this element
  		int iInner, iInnerPrev = 0;
  		m_aPos[iPos].nEndL = m_aPos[iPos].nStartR + 1;
  		while ( (iInner = x_ParseElem( iPos )) > 0 )
  		{
  			// Set links to iInner
  			if ( iInnerPrev )
  				m_aPos[iInnerPrev].iElemNext = iInner;
  			else
  				m_aPos[iPos].iElemChild = iInner;
  			iInnerPrev = iInner;
  
  			// Set offset to reflect child
  			m_aPos[iPos].nEndL = m_aPos[iInner].nEndR + 1;
  		}
  		if ( iInner == -1 )
  			return -1;
  
  		// Look for left angle bracket of end tag
  		if ( ! x_FindChar( token.szDoc, m_aPos[iPos].nEndL, '<' ) )
  			return x_ParseError( "End tag of %s element not found", strName.c_str() );
  
  		// Look through tokens of end tag
  		token.nNext = m_aPos[iPos].nEndL + 1;
  		int nTokenCount = 0;
  		while ( x_FindToken( token ) )
  		{
  			++nTokenCount;
  			if ( ! token.bIsString )
  			{
  				// Is first token not an end slash mark?
  				if ( nTokenCount == 1 && m_strDoc[token.nL] != '/' )
  					return x_ParseError( "Expecting end tag of element %s", strName.c_str() );
  
  				else if ( nTokenCount == 2 && ! token.Match(strName.c_str()) )
  					return x_ParseError( "End tag does not correspond to %s", strName.c_str() );
  
  				// Else is it a right angle bracket?
  				else if ( m_strDoc[token.nL] == '>' )
  					break;
  			}
  		}
  
  		// Was a right angle bracket not found?
  		if ( ! token.szDoc[token.nL] || nTokenCount < 2 )
  			return x_ParseError( "End tag not completed for element %s", strName.c_str() );
  		m_aPos[iPos].nEndR = token.nL;
  	}
  
  	// Successfully parsed element (and contained elements)
  	return iPos;
  }
  
  bool CMarkupSTL::x_FindChar( const char* szDoc, int& nChar, char c )
  {
  	// static function
  	const char* pChar = &szDoc[nChar];
  	while ( *pChar && *pChar != c )
  		pChar += 1;
  	nChar = pChar - szDoc;
  	if ( ! *pChar )
  		return false;
  	/*
  	while ( szDoc[nChar] && szDoc[nChar] != c )
  		nChar += _tclen( &szDoc[nChar] );
  	if ( ! szDoc[nChar] )
  		return false;
  	*/
  	return true;
  }
  
  bool CMarkupSTL::x_FindToken( CMarkupSTL::TokenPos& token )
  {
  	// Starting at token.nNext, bypass whitespace and find the next token
  	// returns true on success, members of token point to token
  	// returns false on end of document, members point to end of document
  	const char* szDoc = token.szDoc;
  	int nChar = token.nNext;
  	token.bIsString = false;
  
  	// By-pass leading whitespace
  	while ( szDoc[nChar] && strchr(" \t\n\r",szDoc[nChar]) )
  		++nChar;
  	if ( ! szDoc[nChar] )
  	{
  		// No token was found before end of document
  		token.nL = nChar;
  		token.nR = nChar;
  		token.nNext = nChar;
  		return false;
  	}
  
  	// Is it an opening quote?
  	char cFirstChar = szDoc[nChar];
  	if ( cFirstChar == '\"' || cFirstChar == '\'' )
  	{
  		token.bIsString = true;
  
  		// Move past opening quote
  		++nChar;
  		token.nL = nChar;
  
  		// Look for closing quote
  		x_FindChar( token.szDoc, nChar, cFirstChar );
  
  		// Set right to before closing quote
  		token.nR = nChar - 1;
  
  		// Set nChar past closing quote unless at end of document
  		if ( szDoc[nChar] )
  			++nChar;
  	}
  	else
  	{
  		// Go until special char or whitespace
  		token.nL = nChar;
  		while ( szDoc[nChar] && ! strchr(" \t\n\r<>=\\/?!",szDoc[nChar]) )
  			nChar += 1;
  
  		// Adjust end position if it is one special char
  		if ( nChar == token.nL )
  			++nChar; // it is a special char
  		token.nR = nChar - 1;
  	}
  
  	// nNext points to one past last char of token
  	token.nNext = nChar;
  	return true;
  }
  
  std::string CMarkupSTL::x_GetToken( const CMarkupSTL::TokenPos& token ) const
  {
  	// The token contains indexes into the document identifying a small substring
  	// Build the substring from those indexes and return it
  	if ( token.nL > token.nR )
  		return "";
  	return m_strDoc.substr( token.nL,
  		token.nR - token.nL + ((token.nR<m_strDoc.size())? 1:0) );
  }
  
  int CMarkupSTL::x_FindElem( int iPosParent, int iPos, const char* szPath )
  {
  	// If szPath is NULL or empty, go to next sibling element
  	// Otherwise go to next sibling element with matching path
  	//
  	if ( iPos )
  		iPos = m_aPos[iPos].iElemNext;
  	else
  		iPos = m_aPos[iPosParent].iElemChild;
  
  	// Finished here if szPath not specified
  	if ( szPath == NULL || !szPath[0] )
  		return iPos;
  
  	// Search
  	TokenPos token( m_strDoc.c_str() );
  	while ( iPos )
  	{
  		// Compare tag name
  		token.nNext = m_aPos[iPos].nStartL + 1;
  		x_FindToken( token ); // Locate tag name
  		if ( token.Match(szPath) )
  			return iPos;
  		iPos = m_aPos[iPos].iElemNext;
  	}
  	return 0;
  }
  
  int CMarkupSTL::x_ParseNode( CMarkupSTL::TokenPos& token )
  {
  	// Call this with token.nNext set to the start of the node
  	// This returns the node type and token.nNext set to the char after the node
  	// If the node is not found or an element, token.nR is not determined
  	// White space between elements is a text node
  	int nTypeFound = 0;
  	const char* szDoc = token.szDoc;
  	token.nL = token.nNext;
  	if ( szDoc[token.nL] == '<' )
  	{
  		// Started with <, could be:
  		// <!--...--> comment
  		// <!DOCTYPE ...> dtd
  		// <?target ...?> processing instruction
  		// <![CDATA[...]]> cdata section
  		// <NAME ...> element
  		//
  		if ( ! szDoc[token.nL+1] || ! szDoc[token.nL+2] )
  			return 0;
  		char cFirstChar = szDoc[token.nL+1];
  		const char* szEndOfNode = NULL;
  		if ( cFirstChar == '?' )
  		{
  			nTypeFound = MNT_PROCESSING_INSTRUCTION; // processing instruction
  			szEndOfNode = "?>";
  		}
  		else if ( cFirstChar == '!' )
  		{
  			char cSecondChar = szDoc[token.nL+2];
  			if ( cSecondChar == '[' )
  			{
  				nTypeFound = MNT_CDATA_SECTION;
  				szEndOfNode = "]]>";
  			}
  			else if ( cSecondChar == '-' )
  			{
  				nTypeFound = MNT_COMMENT;
  				szEndOfNode = "-->";
  			}
  			else
  			{
  				// Document type requires tokenizing because of strings and brackets
  				nTypeFound = 0;
  				int nBrackets = 0;
  				while ( x_FindToken(token) )
  				{
  					if ( ! token.bIsString )
  					{
  						char cChar = szDoc[token.nL];
  						if ( cChar == '[' )
  							++nBrackets;
  						else if ( cChar == ']' )
  							--nBrackets;
  						else if ( nBrackets == 0 && cChar == '>' )
  						{
  							nTypeFound = MNT_DOCUMENT_TYPE;
  							break;
  						}
  					}
  				}
  				if ( ! nTypeFound )
  					return 0;
  			}
  		}
  		else if ( cFirstChar == '/' )
  		{
  			// End tag means no node found within parent element
  			return 0;
  		}
  		else
  		{
  			nTypeFound = MNT_ELEMENT;
  		}
  
  		// Search for end of node if not found yet
  		if ( szEndOfNode )
  		{
  			const char* pEnd = strstr( &szDoc[token.nNext], szEndOfNode );
  			if ( ! pEnd )
  				return 0; // not well-formed
  			token.nNext = (pEnd - szDoc) + strlen(szEndOfNode);
  		}
  	}
  	else if ( szDoc[token.nL] )
  	{
  		// It is text or whitespace because it did not start with <
  		nTypeFound = MNT_WHITESPACE;
  		if ( x_FindToken(token) )
  		{
  			if ( szDoc[token.nL] == '<' )
  				token.nNext = token.nL;
  			else
  			{
  				nTypeFound = MNT_TEXT;
  				x_FindChar( token.szDoc, token.nNext, '<' );
  			}
  		}
  	}
  	return nTypeFound;
  }
  
  std::string CMarkupSTL::x_GetTagName( int iPos ) const
  {
  	// Return the tag name at specified element
  	TokenPos token( m_strDoc.c_str() );
  	token.nNext = m_aPos[iPos].nStartL + 1;
  	if ( ! iPos || ! x_FindToken( token ) )
  		return "";
  
  	// Return substring of document
  	return x_GetToken( token );
  }
  
  bool CMarkupSTL::x_FindAttrib( CMarkupSTL::TokenPos& token, const char* szAttrib ) const
  {
  	// If szAttrib is NULL find next attrib, otherwise find named attrib
  	// Return true if found
  	int nAttrib = 0;
  	for ( int nCount = 0; x_FindToken(token); ++nCount )
  	{
  		if ( ! token.bIsString )
  		{
  			// Is it the right angle bracket?
  			if ( m_strDoc[token.nL] == '>' || m_strDoc[token.nL] == '/' )
  				break; // attrib not found
  
  			// Equal sign
  			if ( m_strDoc[token.nL] == '=' )
  				continue;
  
  			// Potential attribute
  			if ( ! nAttrib && nCount )
  			{
  				// Attribute name search?
  				if ( ! szAttrib || ! szAttrib[0] )
  					return true; // return with token at attrib name
  
  				// Compare szAttrib
  				if ( token.Match(szAttrib) )
  					nAttrib = nCount;
  			}
  		}
  		else if ( nAttrib && nCount == nAttrib + 2 )
  		{
  			return true;
  		}
  	}
  
  	// Not found
  	return false;
  }
  
  std::string CMarkupSTL::x_GetAttrib( int iPos, const char* szAttrib ) const
  {
  	// Return the value of the attrib at specified element
  	if ( ! iPos || m_nNodeType != MNT_ELEMENT )
  		return "";
  
  	TokenPos token( m_strDoc.c_str() );
  	token.nNext = m_aPos[iPos].nStartL + 1;
  	if ( szAttrib && x_FindAttrib( token, szAttrib ) )
  		return x_TextFromDoc( token.nL, token.nR - ((token.nR<m_strDoc.size())?0:1) );
  	return "";
  }
  
  bool CMarkupSTL::x_SetAttrib( int iPos, const char* szAttrib, int nValue )
  {
  	// Convert integer to string and call SetChildAttrib
  	char szVal[25];
  	sprintf( szVal, "%d", nValue );
  	return x_SetAttrib( iPos, szAttrib, szVal );
  }
  
  bool CMarkupSTL::x_SetAttrib( int iPos, const char* szAttrib, const char* szValue )
  {
  	// Set attribute in iPos element
  	if ( ! iPos || m_nNodeType != MNT_ELEMENT )
  		return false;
  
  	TokenPos token( m_strDoc.c_str() );
  	token.nNext = m_aPos[iPos].nStartL + 1;
  	int nInsertAt, nReplace = 0;
  	std::string strInsert;
  	if ( x_FindAttrib( token, szAttrib ) )
  	{
  		// Decision: for empty value leaving attrib="" instead of removing attrib
  		// Replace value only
  		strInsert = x_TextToDoc( szValue, true );
  		nInsertAt = token.nL;
  		nReplace = token.nR-token.nL+1;
  	}
  	else
  	{
  		// Insert string name value pair
  		std::string strFormat;
  		strFormat = " ";
  		strFormat += szAttrib;
  		strFormat += "=\"";
  		strFormat += x_TextToDoc( szValue, true );
  		strFormat += "\"";
  		strInsert = strFormat;
  
  		// take into account whether it is an empty element
  		nInsertAt = m_aPos[iPos].nStartR - (m_aPos[iPos].IsEmptyElement()?1:0);
  	}
  
  	x_DocChange( nInsertAt, nReplace, strInsert );
  	int nAdjust = strInsert.size() - nReplace;
  	m_aPos[iPos].nStartR += nAdjust;
  	m_aPos[iPos].AdjustEnd( nAdjust );
  	x_Adjust( iPos, nAdjust );
  	MARKUP_SETDEBUGSTATE;
  	return true;
  }
  
  bool CMarkupSTL::x_CreateNode( std::string& strNode, int nNodeType, const char* szText )
  {
  	// Set strNode based on nNodeType and szText
  	// Return false if szText would jeopardize well-formed document
  	//
  	switch ( nNodeType )
  	{
  	case MNT_CDATA_SECTION:
  		if ( strstr(szText,"]]>") != NULL )
  			return false;
  		strNode = "<![CDATA[";
  		strNode += szText;
  		strNode += "]]>";
  		break;
  	}
  	return true;
  }
  
  bool CMarkupSTL::x_SetData( int iPos, const char* szData, int nCDATA )
  {
  	// Set data at specified position
  	// if nCDATA==1, set content of element to a CDATA Section
  	std::string strInsert;
  
  	// Set data in iPos element
  	if ( ! iPos || m_aPos[iPos].iElemChild )
  		return false;
  
  	// Build strInsert from szData based on nCDATA
  	// If CDATA section not valid, use parsed text (PCDATA) instead
  	if ( nCDATA != 0 )
  		if ( ! x_CreateNode(strInsert, MNT_CDATA_SECTION, szData) )
  			nCDATA = 0;
  	if ( nCDATA == 0 )
  		strInsert = x_TextToDoc( szData );
  
  	// Decide where to insert
  	int nInsertAt, nReplace;
  	if ( m_aPos[iPos].IsEmptyElement() )
  	{
  		nInsertAt = m_aPos[iPos].nEndL;
  		nReplace = 1;
  
  		// Pre-adjust since <NAME/> becomes <NAME>data</NAME>
  		std::string strTagName = x_GetTagName( iPos );
  		m_aPos[iPos].nStartR -= 1;
  		m_aPos[iPos].nEndL -= (1 + strTagName.size());
  		std::string strFormat;
  		strFormat = ">";
  		strFormat += strInsert;
  		strFormat += "</";
  		strFormat += strTagName;
  		strInsert = strFormat;
  	}
  	else
  	{
  		nInsertAt = m_aPos[iPos].nStartR+1;
  		nReplace = m_aPos[iPos].nEndL - m_aPos[iPos].nStartR - 1;
  	}
  	x_DocChange( nInsertAt, nReplace, strInsert );
  	int nAdjust = strInsert.size() - nReplace;
  	x_Adjust( iPos, nAdjust );
  	m_aPos[iPos].AdjustEnd( nAdjust );
  	MARKUP_SETDEBUGSTATE;
  	return true;
  }
  
  std::string CMarkupSTL::x_GetData( int iPos ) const
  {
  	// Return a string representing data between start and end tag
  	// Return empty string if there are any children elements
  	if ( ! m_aPos[iPos].iElemChild && ! m_aPos[iPos].IsEmptyElement() )
  	{
  		// See if it is a CDATA section
  		TokenPos token( m_strDoc.c_str() );
  		token.nNext = m_aPos[iPos].nStartR+1;
  		if ( x_FindToken( token ) && m_strDoc[token.nL] == '<'
  				&& token.nL + 11 < m_aPos[iPos].nEndL
  				&& strncmp( &token.szDoc[token.nL+1], "![CDATA[", 8 ) == 0 )
  		{
  			int nEndCDATA = m_strDoc.find( "]]>", token.nNext );
  			if ( nEndCDATA != std::string::npos && nEndCDATA < m_aPos[iPos].nEndL )
  			{
  				return m_strDoc.substr( token.nL+9, nEndCDATA-token.nL-9 );
  			}
  		}
  		return x_TextFromDoc( m_aPos[iPos].nStartR+1, m_aPos[iPos].nEndL-1 );
  	}
  	return "";
  }
  
  std::string CMarkupSTL::x_TextToDoc( const char* szText, bool bAttrib ) const
  {
  	//
  	// &lt;   less than
  	// &amp;  ampersand
  	// &gt;   greater than
  	//
  	// and for attributes:
  	//
  	// &apos; apostrophe or single quote
  	// &quot; double quote
  	//
  	static char* szaReplace[] = { "&lt;","&amp;","&gt;","&apos;","&quot;" };
  	const char* pFind = bAttrib?"<&>\'\"":"<&>";
  	const char* pSource = szText;
  	std::string strResult;
  	int nLen = strlen( szText );
  	strResult.reserve( nLen + nLen / 10 );
  	char cSource = *pSource;
  	char* pFound;
  	while ( cSource )
  	{
  		if ( (pFound=strchr((char *) pFind,cSource)) != NULL )
  		{
  			pFound = szaReplace[pFound-pFind];
  			strResult.append(pFound);
  		}
  		else
  		{
  			strResult += cSource;
  		}
  		cSource = *(++pSource);
  	}
  	return strResult;
  }
  
  std::string CMarkupSTL::x_TextFromDoc( int nLeft, int nRight ) const
  {
  	//
  	// Conveniently the result is always the same or shorter in length
  	//
  	static char* szaCode[] = { "lt;","amp;","gt;","apos;","quot;" };
  	static int anCodeLen[] = { 3,4,3,5,5 };
  	static char* szSymbol = "<&>\'\"";
  	std::string strResult;
  	strResult.reserve( nRight - nLeft + 1 );
  	const char* pSource = m_strDoc.c_str();
  	int nChar = nLeft;
  	char cSource = pSource[nChar];
  	while ( nChar <= nRight )
  	{
  		if ( cSource == '&' )
  		{
  			// If no match is found it means XML doc is invalid
  			// no devastating harm done, ampersand code will just be left in result
  			for ( int nMatch = 0; nMatch < 5; ++nMatch )
  			{
  				if ( nChar <= nRight - anCodeLen[nMatch]
  					&& strncmp(szaCode[nMatch],&pSource[nChar+1],anCodeLen[nMatch]) == 0 )
  				{
  					cSource = szSymbol[nMatch];
  					nChar += anCodeLen[nMatch];
  					break;
  				}
  			}
  		}
  		strResult += cSource;
  		nChar++;
  		cSource = pSource[nChar];
  	}
  	return strResult;
  }
  
  void CMarkupSTL::x_DocChange( int nLeft, int nReplace, const std::string& strInsert )
  {
  	// Insert strInsert int m_strDoc at nLeft replacing nReplace chars
  	//
  	m_strDoc.replace( nLeft, nReplace, strInsert);
  }
  
  void CMarkupSTL::x_Adjust( int iPos, int nShift, bool bAfterPos )
  {
  	// Loop through affected elements and adjust indexes
  	// Algorithm:
  	// 1. update children unless bAfterPos
  	//    (if no children or bAfterPos is true, end tag of iPos not affected)
  	// 2. update next siblings and their children
  	// 3. go up until there is a next sibling of a parent and update end tags
  	// 4. step 2
  	int iPosTop = m_aPos[iPos].iElemParent;
  	bool bPosFirst = bAfterPos; // mark as first to skip its children
  	while ( iPos )
  	{
  		// Were we at containing parent of affected position?
  		bool bPosTop = false;
  		if ( iPos == iPosTop )
  		{
  			// Move iPosTop up one towards root
  			iPosTop = m_aPos[iPos].iElemParent;
  			bPosTop = true;
  		}
  
  		// Traverse to the next update position
  		if ( ! bPosTop && ! bPosFirst && m_aPos[iPos].iElemChild )
  		{
  			// Depth first
  			iPos = m_aPos[iPos].iElemChild;
  		}
  		else if ( m_aPos[iPos].iElemNext )
  		{
  			iPos = m_aPos[iPos].iElemNext;
  		}
  		else
  		{
  			// Look for next sibling of a parent of iPos
  			// When going back up, parents have already been done except iPosTop
  			while ( (iPos=m_aPos[iPos].iElemParent) != 0 && iPos != iPosTop )
  				if ( m_aPos[iPos].iElemNext )
  				{
  					iPos = m_aPos[iPos].iElemNext;
  					break;
  				}
  		}
  		bPosFirst = false;
  
  		// Shift indexes at iPos
  		if ( iPos != iPosTop )
  			m_aPos[iPos].AdjustStart( nShift );
  		m_aPos[iPos].AdjustEnd( nShift );
  	}
  }
  
  void CMarkupSTL::x_LocateNew( int iPosParent, int& iPosRel, int& nOffset, int nLength, int nFlags )
  {
  	// Determine where to insert new element or node
  	//
  	bool bInsert = (nFlags&1)?true:false;
  	bool bHonorWhitespace = (nFlags&2)?true:false;
  
  	int nStartL;
  	if ( nLength )
  	{
  		// Located at a non-element node
  		if ( bInsert )
  			nStartL = nOffset;
  		else
  			nStartL = nOffset + nLength;
  	}
  	else if ( iPosRel )
  	{
  		// Located at an element
  		if ( bInsert ) // precede iPosRel
  			nStartL = m_aPos[iPosRel].nStartL;
  		else // follow iPosRel
  			nStartL = m_aPos[iPosRel].nEndR + 1;
  	}
  	else if ( m_aPos[iPosParent].IsEmptyElement() )
  	{
  		// Parent has no separate end tag, so split empty element
  		nStartL = m_aPos[iPosParent].nStartR;
  	}
  	else
  	{
  		if ( bInsert ) // after start tag
  			nStartL = m_aPos[iPosParent].nStartR + 1;
  		else // before end tag
  			nStartL = m_aPos[iPosParent].nEndL;
  	}
  
  	// Go up to start of next node, unless its splitting an empty element
  	if ( ! bHonorWhitespace && ! m_aPos[iPosParent].IsEmptyElement() )
  	{
  		TokenPos token( m_strDoc.c_str() );
  		token.nNext = nStartL;
  		if ( ! x_FindToken(token) || m_strDoc[token.nL] == '<' )
  			nStartL = token.nL;
  	}
  
  	// Determine iPosBefore
  	int iPosBefore = 0;
  	if ( iPosRel )
  	{
  		if ( bInsert )
  		{
  			// Is iPosRel past first sibling?
  			int iPosPrev = m_aPos[iPosParent].iElemChild;
  			if ( iPosPrev != iPosRel )
  			{
  				// Find previous sibling of iPosRel
  				while ( m_aPos[iPosPrev].iElemNext != iPosRel )
  					iPosPrev = m_aPos[iPosPrev].iElemNext;
  				iPosBefore = iPosPrev;
  			}
  		}
  		else
  		{
  			iPosBefore = iPosRel;
  		}
  	}
  	else if ( m_aPos[iPosParent].iElemChild )
  	{
  		if ( ! bInsert )
  		{
  			// Find last element under iPosParent
  			int iPosLast = m_aPos[iPosParent].iElemChild;
  			int iPosNext = iPosLast;
  			while ( iPosNext )
  			{
  				iPosLast = iPosNext;
  				iPosNext = m_aPos[iPosNext].iElemNext;
  			}
  			iPosBefore = iPosLast;
  		}
  	}
  
  	nOffset = nStartL;
  	iPosRel = iPosBefore;
  }
  
  bool CMarkupSTL::x_AddElem( const char* szName, const char* szValue, bool bInsert, bool bAddChild )
  {
  	if ( bAddChild )
  	{
  		// Adding a child element under main position
  		if ( ! m_iPos )
  			return false;
  	}
  	else if ( m_iPosParent == 0 )
  	{
  		// Adding root element
  		if ( IsWellFormed() )
  			return false;
  
  		// Locate after any version and DTD
  		m_aPos[0].nEndL = m_strDoc.size();
  	}
  
  	// Locate where to add element relative to current node
  	int iPosParent, iPosBefore, nOffset = 0, nLength = 0;
  	if ( bAddChild )
  	{
  		iPosParent = m_iPos;
  		iPosBefore = m_iPosChild;
  	}
  	else
  	{
  		iPosParent = m_iPosParent;
  		iPosBefore = m_iPos;
  	}
  	int nFlags = bInsert?1:0;
  	x_LocateNew( iPosParent, iPosBefore, nOffset, nLength, nFlags );
  	bool bEmptyParent = m_aPos[iPosParent].IsEmptyElement();
  	if ( bEmptyParent )
  		nOffset += 2; // include CRLF
  
  	// Create element and modify positions of affected elements
  	// If no szValue is specified, an empty element is created
  	// i.e. either <NAME>value</NAME> or <NAME/>
  	//
  	int iPos = x_GetFreePos();
  	m_aPos[iPos].nStartL = nOffset;
  
  	// Set links
  	m_aPos[iPos].iElemParent = iPosParent;
  	m_aPos[iPos].iElemChild = 0;
  	m_aPos[iPos].iElemNext = 0;
  	if ( iPosBefore )
  	{
  		// Link in after iPosBefore
  		m_aPos[iPos].iElemNext = m_aPos[iPosBefore].iElemNext;
  		m_aPos[iPosBefore].iElemNext = iPos;
  	}
  	else
  	{
  		// First child
  		m_aPos[iPos].iElemNext = m_aPos[iPosParent].iElemChild;
  		m_aPos[iPosParent].iElemChild = iPos;
  	}
  
  	// Create string for insert
  	std::string strInsert;
  	int nLenName = strlen(szName);
  	int nLenValue = szValue? strlen(szValue) : 0;
  	if ( ! nLenValue )
  	{
  		// <NAME/> empty element
  		strInsert = "<";
  		strInsert += szName;
  		strInsert += "/>\r\n";
  		m_aPos[iPos].nStartR = m_aPos[iPos].nStartL + nLenName + 2;
  		m_aPos[iPos].nEndL = m_aPos[iPos].nStartR - 1;
  		m_aPos[iPos].nEndR = m_aPos[iPos].nEndL + 1;
  	}
  	else
  	{
  		// <NAME>value</NAME>
  		std::string strValue = x_TextToDoc( szValue );
  		nLenValue = strValue.size();
  		strInsert = "<";
  		strInsert += szName;
  		strInsert += ">";
  		strInsert += strValue;
  		strInsert += "</";
  		strInsert += szName;
  		strInsert += ">\r\n";
  		m_aPos[iPos].nStartR = m_aPos[iPos].nStartL + nLenName + 1;
  		m_aPos[iPos].nEndL = m_aPos[iPos].nStartR + nLenValue + 1;
  		m_aPos[iPos].nEndR = m_aPos[iPos].nEndL + nLenName + 2;
  	}
  
  	// Insert
  	int nReplace = 0, nLeft = m_aPos[iPos].nStartL;
  	if ( bEmptyParent )
  	{
  		std::string strParentTagName = x_GetTagName(iPosParent);
  		std::string strFormat;
  		strFormat = ">\r\n";
  		strFormat += strInsert;
  		strFormat += "</";
  		strFormat += strParentTagName;
  		strInsert = strFormat;
  		nLeft -= 3;
  		nReplace = 1;
  		// x_Adjust is going to update all affected indexes by one amount
  		// This will satisfy all except the empty parent
  		// Here we pre-adjust for the empty parent
  		// The empty tag slash is removed
  		m_aPos[iPosParent].nStartR -= 1;
  		// For the newly created end tag, see the following example:
  		// <A/> (len 4) becomes <A><B/></A> (len 11)
  		// In x_Adjust everything will be adjusted 11 - 4 = 7
  		// But the nEndL of element A should only be adjusted 5
  		m_aPos[iPosParent].nEndL -= (strParentTagName.size() + 1);
  	}
  	x_DocChange( nLeft, nReplace, strInsert );
  	x_Adjust( iPos, strInsert.size() - nReplace );
  
  	if ( bAddChild )
  		x_SetPos( m_iPosParent, iPosParent, iPos );
  	else
  		x_SetPos( iPosParent, iPos, 0 );
  	return true;
  }
  
  bool CMarkupSTL::x_AddSubDoc( const char* szSubDoc, bool bInsert, bool bAddChild )
  {
  	// Add subdocument, parse, and modify positions of affected elements
  	//
  	int nOffset = 0, iPosParent, iPosBefore;
  	if ( bAddChild )
  	{
  		// Add a subdocument under main position, after current child position
  		if ( ! m_iPos )
  			return false;
  		iPosParent = m_iPos;
  		iPosBefore = m_iPosChild;
  	}
  	else
  	{
  		iPosParent = m_iPosParent;
  		iPosBefore = m_iPos;
  	}
  	int nFlags = bInsert?1:0;
  	x_LocateNew( iPosParent, iPosBefore, nOffset, 0, nFlags );
  	bool bEmptyParent = m_aPos[iPosParent].IsEmptyElement();
  	if ( bEmptyParent )
  		nOffset += 2; // include CRLF
  
  	// if iPosBefore is NULL, insert as first element under parent
  	int nParentEndLBeforeAdd = m_aPos[iPosParent].nEndL;
  	int iPosFreeBeforeAdd = m_iPosFree;
  
  	// Skip version tag or DTD at start of subdocument
  	TokenPos token( szSubDoc );
  	int nNodeType = x_ParseNode( token );
  	while ( nNodeType && nNodeType != MNT_ELEMENT )
  	{
  		token.szDoc = &szSubDoc[token.nNext];
  		token.nNext = 0;
  		nNodeType = x_ParseNode( token );
  	}
  	std::string strInsert = token.szDoc;
  
  	// Insert subdocument
  	m_aPos[iPosParent].nEndL = nOffset;
  	int nReplace = 0, nLeft = nOffset;
  	std::string strParentTagName;
  	if ( bEmptyParent )
  	{
  		strParentTagName = x_GetTagName(iPosParent);
  		std::string strFormat;
  		strFormat = ">\r\n";
  		strFormat += strInsert;
  		strFormat += "</";
  		strFormat += strParentTagName;
  		strInsert = strFormat;
  		m_aPos[iPosParent].nEndL = m_aPos[iPosParent].nStartR + 2;
  		nLeft = m_aPos[iPosParent].nStartR - 1;
  		nReplace = 1;
  	}
  	x_DocChange( nLeft, nReplace, strInsert );
  
  	// Parse subdocument
  	int iPos = x_ParseElem(iPosParent);
  	m_aPos[iPosParent].nEndL = nParentEndLBeforeAdd;
  	if ( iPos <= 0 )
  	{
  		// Abort because not well-formed
  		std::string strRevert = bEmptyParent?"/":"";
  		x_DocChange( nLeft, strInsert.size(), strRevert );
  		m_iPosFree = iPosFreeBeforeAdd;
  		return false;
  	}
  	else
  	{
  		// Link in parent and siblings
  		m_aPos[iPos].iElemParent = iPosParent;
  		if ( iPosBefore )
  		{
  			m_aPos[iPos].iElemNext = m_aPos[iPosBefore].iElemNext;
  			m_aPos[iPosBefore].iElemNext = iPos;
  		}
  		else
  		{
  			m_aPos[iPos].iElemNext = m_aPos[iPosParent].iElemChild;
  			m_aPos[iPosParent].iElemChild = iPos;
  		}
  
  		// Make empty parent pre-adjustment
  		if ( bEmptyParent )
  		{
  			m_aPos[iPosParent].nStartR -= 1;
  			m_aPos[iPosParent].nEndL -= (strParentTagName.size() + 1);
  		}
  
  		// Adjust, but don't adjust children of iPos (bAfterPos=true)
  		x_Adjust( iPos, strInsert.size() - nReplace, true );
  	}
  
  	// Set position to top element of subdocument
  	if ( bAddChild )
  		x_SetPos( m_iPosParent, iPosParent, iPos );
  	else // Main
  		x_SetPos( m_iPosParent, iPos, 0 );
  	return true;
  }
  
  int CMarkupSTL::x_RemoveElem( int iPos )
  {
  	// Remove element and all contained elements
  	// Return new position
  	//
  	int iPosParent = m_aPos[iPos].iElemParent;
  
  	// Find previous sibling and bypass removed element
  	// This leaves orphan positions in m_aPos array
  	int iPosLook = m_aPos[iPosParent].iElemChild;
  	int iPosPrev = 0;
  	while ( iPosLook != iPos )
  	{
  		iPosPrev = iPosLook;
  		iPosLook = m_aPos[iPosLook].iElemNext;
  	}
  	if ( iPosPrev )
  		m_aPos[iPosPrev].iElemNext = m_aPos[iPos].iElemNext;
  	else
  		m_aPos[iPosParent].iElemChild = m_aPos[iPos].iElemNext;
  
  	// Remove from document
  	// Links have been changed to go around removed element
  	// But element position and links are still valid
  	int nAfterEnd = m_aPos[iPos].nEndR + 1;
  	TokenPos token( m_strDoc.c_str() );
  	token.nNext = nAfterEnd;
  	if ( ! x_FindToken(token) || token.szDoc[token.nL] == '<' )
  		nAfterEnd = token.nL;
  	int nLen = nAfterEnd - m_aPos[iPos].nStartL;
  	x_DocChange( m_aPos[iPos].nStartL, nLen, std::string() );
  	x_Adjust( iPos, - nLen, true );
  	return iPosPrev;
  }
  
  
  }				//StdUtils
  