/*********************************************************************
Copyright (C) 2001 by
Alexander Berthold, alexander-berthold@web.de.
Hoegestr. 54
79108 Freiburg i. Breisgau
Germany
-- This file is part of cxAnalyzer --
"cxAnalyzer" is free software; you can redistribute it and/or
modify it under the terms of the GNU Lesser General Public
License as published by the Free Software Foundation; either
version 2 of the License, or any later version.
"cxAnalyzer" is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU Lesser General Public License for more details.
You should have received a copy of the GNU Lesser General Public
License along with "cxAnalyzer"; if not, write to the Free
Software Foundation, Inc., 59 Temple Place, Suite 330,
Boston, MA 02111-1307 USA
---------------------------------------------------------------
If you find any bugs or if you make other corrections/
enhancements, i'd appreciate if you'd let me know about
that. My email is
alexander-berthold@web.de
If you share this code, do not remove this text.
---------------------------------------------------------------
*********************************************************************/
// cxaParseTree.cpp: implementation of the cxaParseTree class.
//
//////////////////////////////////////////////////////////////////////
#include "stdafx.h"
#include "cxAnalyzerTypeMap.h"
#include "cxaToken.h"
#include "cxAnalyzerExpression.h"
#include "cxAnalyzerTree.h"
#include "cxaRuleCacheElement.h"
#include "cxaRuleCache.h"
#include "cxAnalyzerMain.h"
#include "cxAnalyzerException.h"
#include "cxaParseTree.h"
#ifndef _DEBUG
#undef TRACE
#define TRACE printf
#endif
#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
cxaParseTree::cxaParseTree()
{
m_papbRoot =new cxaParseBranch(ATM_ID_INVALID,TOKEN_ID_INVALID,32767,false,false);
m_papbCurBranch =m_papbRoot;
}
cxaParseTree::~cxaParseTree()
{
if(m_papbRoot)
delete m_papbRoot;
}
void cxaParseTree::vBeginRule(int nAtmType, int nIDValue, int nPrecPrio, bool fLeftBound, bool fRightBound)
{
cxaParseBranch *papbNew = new cxaParseBranch(
nAtmType,
nIDValue,
nPrecPrio,
fLeftBound,
fRightBound);
m_papbCurBranch->push_back(papbNew);
m_papbCurBranch =papbNew;
}
void cxaParseTree::vEndRule()
{
m_papbCurBranch =m_papbCurBranch->papbGetParent();
ASSERT(m_papbCurBranch!=NULL);
}
void cxaParseTree::vToken(const cxaToken* patToken)
{
cxaParseNode *papnNew = new cxaParseNode(
patToken);
m_papbCurBranch->push_back(papnNew);
}
void cxaParseTree::vDump(int nSpaces, const cxaParseBranch *papbBranch)
{
if(papbBranch==NULL)
papbBranch=m_papbRoot;
cxaParseBranch::const_iterator it;
for(it=papbBranch->begin();it!=papbBranch->end();it++)
{
const cxaParseElement *pape = (*it);
if(pape->fIsBranch())
{
cxaParseBranch *papb = ((cxaParseBranch*)pape);
char c1,c2;
if(papb->fIsLeftBound()) c1='('; else c1='[';
if(papb->fIsRightBound()) c2=')'; else c2=']';
// spaces(nSpaces);
TRACE(_T("<< BEGIN %c%d%c {id=%d,atm=%d}\n"), c1, ((cxaParseBranch*)pape)->nGetPrecPrio() , c2,
papb->nGetIDValue(),papb->nGetAtmType());
vDump(nSpaces+1, (cxaParseBranch*)pape);
// spaces(nSpaces);
TRACE(_T("END >>\n"));
}
else
{
// spaces(nSpaces);
const cxaToken* pat=((cxaParseNode*)pape)->patGetToken();
if(pat)
TRACE(_T("* %s,%d,%d\n"), pat->lpszTokenText, pat->nAtmType, pat->nIDValue);
else
TRACE(_T("* NULL\n"));
}
}
}
void cxaParseTree::vRebalance(cxaParseBranch *papbBranch, int nAtmType)
{
papbBranch->vDump();
vRebalanceInner(papbBranch, nAtmType);
papbBranch->vDump();
vCleanupTree(papbBranch);
}
void cxaParseTree::vCleanupTree(cxaParseBranch *papbBranch)
{
// Use depth-first algorithm
cxaParseBranch::iterator it;
for(it=papbBranch->begin();it!=papbBranch->end();it++)
{
cxaParseElement *pape = (*it);
if(pape->fIsBranch())
vCleanupTree( (cxaParseBranch*)pape );
}
if( papbBranch->papeGetFrontElement()==papbBranch->papeGetBackElement() &&
papbBranch->papbGetParent()!=NULL)
papbBranch->vRemoveOnlyChildBranch();
}
void cxaParseTree::vRebalanceInner(cxaParseBranch *papbBranch, int nAtmType)
{
// Use depth-first algorithm
cxaParseBranch::iterator it;
for(it=papbBranch->begin();it!=papbBranch->end();it++)
{
cxaParseElement *pape = (*it);
if(pape->fIsBranch())
vRebalanceInner( (cxaParseBranch*)pape , nAtmType);
}
cxaParseBranch::iterator istart = papbBranch->begin();
bool fRepeat = true;
while(fRepeat)
{
fRepeat = false;
cxaParseBranch::iterator _start = papbBranch->end();
cxaParseBranch::iterator _end = papbBranch->end();
for(it=istart;it!=papbBranch->end();it++)
{
cxaParseElement *pape = (*it);
cxaParseBranch *papbCur = NULL;
if(pape->fIsBranch())
papbCur =(cxaParseBranch*)pape;
if(papbCur)
{
if(papbCur->nGetAtmType()==nAtmType)
{
if(_start==papbBranch->end())
_start=it;
}
else
{
if(_start!=papbBranch->end())
_end=it;
}
}
else
{
if(_start!=papbBranch->end())
_end=it;
}
if(_end!=papbBranch->end())
{
fRepeat = true;
break;
}
}
if(fRepeat==false && _start!=papbBranch->end() && _end==papbBranch->end())
{
fRepeat = true;
_end = papbBranch->end();
}
if(fRepeat)
{
fRebalancePart(papbBranch,nAtmType,_start,_end);
istart=_end;
}
}
}
void cxaParseTree::vSwapElements(cxaParseElement *papeOne,
cxaParseElement *papeTwo)
{
ASSERT(papeOne!=NULL);
ASSERT(papeTwo!=NULL);
cxaParseBranch *papbPOne, *papbPTwo;
cxaParseElement *papeOneBefore, *papeTwoBefore;
papbPOne =(cxaParseBranch*)papeOne->tGetParent();
papbPTwo =(cxaParseBranch*)papeTwo->tGetParent();
ASSERT(papbPOne!=NULL);
ASSERT(papbPTwo!=NULL);
papbPOne->vUnlink(papeOne,papeOne,&papeOneBefore,NULL,true);
papbPTwo->vUnlink(papeTwo,papeTwo,&papeTwoBefore,NULL,true);
if(papeOneBefore==NULL)
papbPOne->vPushFront(papeTwo);
else
papbPOne->vInsertAfter(papeOneBefore,papeTwo);
if(papeTwoBefore==NULL)
papbPTwo->vPushFront(papeOne);
else
papbPTwo->vInsertAfter(papeTwoBefore,papeOne);
}
void cxaParseTree::vSiblingAppendAfterAndUnlink(
cxaParseBranch* papbWhere,
cxaParseBranch* papbWhat)
{
ASSERT(papbWhere!=NULL);
ASSERT(papbWhat!=NULL);
cxaParseBranch *papbPWhere = papbWhere->papbGetParent();
cxaParseBranch *papbPWhat = papbWhat->papbGetParent();
ASSERT(papbPWhere!=NULL);
if(papbPWhat==NULL)
{
// The most likely cause for this to happen is calling
// vCleanupTree before calling vRebalance, because vCleanupTree
// also removes the first nest level (which always contains
// only one child).
// This is correct behavior, but the algorithm here relies
// on the 'non-cleaned' original state. One could fix this
// by creating an branch with TOKEN_ID_REORDER/rebalance Atm
// containing the branch to be rebalanced.
ASSERT(FALSE);
return;
}
papbPWhat->vUnlink(papbWhat,papbWhat,NULL,NULL,true);
papbPWhere->vInsertAfter(papbWhere,papbWhat);
}
void cxaParseTree::vChildAppendAfterAndUnlink(
cxaParseBranch* papbWhere,
cxaParseBranch* papbWhat)
{
ASSERT(papbWhere!=NULL);
ASSERT(papbWhat!=NULL);
cxaParseBranch *papbPWhat = papbWhat->papbGetParent();
ASSERT(papbPWhat!=NULL);
papbPWhat->vUnlink(papbWhat,papbWhat,NULL,NULL,true);
papbWhere->vPushBack(papbWhat);
}
void cxaParseTree::vChildPrependBefore(
cxaParseBranch* papbWhere,
cxaParseBranch* papbWhat)
{
ASSERT(papbWhere!=NULL);
ASSERT(papbWhat!=NULL);
cxaParseBranch *papbPWhat = papbWhat->papbGetParent();
ASSERT(papbPWhat!=NULL);
papbPWhat->vUnlink(papbWhat,papbWhat,NULL,NULL,true);
papbWhere->vPushFront(papbWhat);
}
cxaParseBranch *cxaParseTree::papbGetParentWithPrio(
cxaParseBranch *papbStart,
int nPrecPrio,
cxaParseBranch *papbLimit)
{
ASSERT(papbStart!=NULL);
cxaParseBranch *papbParent, *papbTemp;
papbParent =papbStart;
for(;;)
{
papbTemp =papbParent->papbGetParent();
if(papbTemp==papbLimit)
break;
if(papbTemp->nGetPrecPrio()>nPrecPrio)
break;
papbParent =papbTemp;
if(papbParent->nGetPrecPrio()==nPrecPrio)
return papbParent;
}
cxaParseBranch *papbNew;
cxaParseElement *papeBefore;
papbNew =new cxaParseBranch(
papbStart->nGetAtmType(),
TOKEN_ID_REORDER,nPrecPrio,
false,false);
papbTemp =papbParent->papbGetParent();
papbTemp->vUnlink(papbParent,papbParent,&papeBefore,NULL,true);
papbNew->vPushBack(papbParent);
if(papeBefore)
papbTemp->vInsertAfter(papeBefore,papbNew);
else
papbTemp->vPushFront(papbNew);
papbTemp->vDump();
return papbNew;
/* papbParent =NULL;
papbTemp =papbStart->papbGetParent();
while(papbTemp!=NULL)
{
if(papbTemp->nGetAtmType()!=papbStart->nGetAtmType())
break;
if(papbTemp->nGetPrecPrio()<=nPrecPrio)
papbParent =papbTemp;
if(papbTemp->nGetPrecPrio()>=nPrecPrio)
break;
papbTemp =papbTemp->papbGetParent();
}
ASSERT(papbParent!=NULL);
// Test if we have found a parent with _equal_ priority to
// 'nPrecPrio'
if(papbParent->nGetPrecPrio()==nPrecPrio)
{
// Yes, everything is done
return papbParent;
}
// No parent with equal priority -> create one
ASSERT(papbParent->nGetPrecPrio()>nPrecPrio);
cxaParseBranch *papbNew;
papbNew =new cxaParseBranch(
papbStart->nGetAtmType(),
IDVALUE_REORDER,nPrecPrio,
false,false);
papbTemp =papbParent->papbGetParent();
papbTemp->vUnlink(papbParent,papbParent,NULL,NULL,true);
papbNew->vPushBack(papbParent);
return papbNew;*/
}
cxaParseBranch *cxaParseTree::papbReverseSearchWithEqualPrio(
cxaParseBranch *papbElem)
{
ASSERT(papbElem!=NULL);
cxaParseElement *papeTemp;
cxaParseBranch *papbTemp;
int nPrecPrio = papbElem->nGetPrecPrio();
int nAtmType = papbElem->nGetAtmType();
while(papbElem!=NULL)
{
papeTemp =papbElem->tGetPrev();
if(papeTemp==NULL)
break;
if(!papeTemp->fIsBranch())
break;
papbTemp =(cxaParseBranch*)papeTemp;
if(papbTemp->nGetAtmType()!=nAtmType)
break;
if(papbTemp->nGetPrecPrio()!=nPrecPrio)
break;
papbElem =papbTemp;
}
return papbElem;
}
cxaParseBranch *cxaParseTree::papbMoveToSubbranch(
cxaParseBranch *papbFirst,
cxaParseBranch *papbLast)
{
ASSERT(papbFirst!=NULL);
ASSERT(papbLast!=NULL);
ASSERT(papbFirst->papbGetParent()==papbLast->papbGetParent());
ASSERT(papbFirst->papbGetParent()!=NULL);
cxaParseBranch *papbParent = papbFirst->papbGetParent();
cxaParseElement *papeBefore = NULL;
papbParent->vUnlink(papbFirst,papbLast,&papeBefore,NULL,true);
cxaParseBranch *papbNew = new cxaParseBranch(
papbFirst->nGetAtmType(),
TOKEN_ID_REORDER,papbFirst->nGetPrecPrio(),
false,false);
cxaParseElement *papeCur = papbFirst;
while(true)
{
papbNew->vPushBack(papeCur);
if(papeCur==papbLast)
break;
papeCur =papeCur->tGetNext();
ASSERT(papeCur!=NULL);
}
if(papeBefore==NULL)
papbParent->vPushFront(papbNew);
else
papbParent->vInsertAfter(papeBefore,papbNew);
return papbNew;
}
bool cxaParseTree::fRebalancePart(cxaParseBranch * /*papbParent*/,
int nAtmType,
cxaParseBranch::iterator _start,
cxaParseBranch::iterator _end)
{
cxaParseBranch::iterator it;
cxaParseBranch *papbNest = NULL; // the 'real' predecessor of 'papbCur',
// child of 'papbPrev'
bool fDone = false;
for(it=_start;it!=_end;)
{
cxaParseBranch *papbCur = (cxaParseBranch*)(*it);
it++;
if(papbNest == NULL)
{
papbNest =papbCur;
continue;
}
// 1. If the adjacent elements 'papbNest' and 'papbCur' are right/left
// bound and one of both has a 'hole' (i.e. a NULL token) to the
// respective sides the one with the higher priority receives
// the non-NULL element.
if( papbNest->fIsRightBound() &&
(papbNest->nGetPrecPrio()<papbCur->nGetPrecPrio()) &&
(papbNest->fIsBackNULLToken()) )
{
vSwapElements( papbNest->papeGetBackElement(),
papbCur->papeGetFrontElement() );
if( papbCur->papeGetFrontElement()==papbCur->papeGetBackElement() &&
papbCur->papeGetFrontElement()->fIsNode() &&
papbCur->papeGetFrontElement()->papnElem()->patGetToken()==NULL)
{
papbCur->papbGetParent()->vUnlink(papbCur,papbCur,NULL,NULL,true),
delete papbCur;
continue;
}
}
if( papbCur->fIsLeftBound() &&
(papbNest->nGetPrecPrio()>papbCur->nGetPrecPrio()) &&
(papbCur->fIsFrontNULLToken()) )
{
vSwapElements( papbNest->papeGetBackElement(),
papbCur->papeGetFrontElement() );
if( papbNest->papeGetFrontElement()==papbNest->papeGetBackElement() &&
papbNest->papeGetFrontElement()->fIsNode() &&
papbNest->papeGetFrontElement()->papnElem()->patGetToken()==NULL)
{
papbNest->papbGetParent()->vUnlink(papbNest,papbNest,NULL,NULL,true),
delete papbNest;
continue;
}
}
// 2. Examine the priority of the two adjacent elements 'papbNest' and
// 'papbCur'. If it is equal, 'papbCur' must be inserted right after
// 'papbNest'. If 'papbNest's priority is higher (numerically lower)
// all precessors of 'papbNest' having the same priority are inserted
// to the front of the child elements of 'papbCur'.
// If 'papbCur's priority is higher, 'papbCur' is inserted as child
// element of 'papbNest' at the back of its child elements.
bool fSkip = false;
if(papbNest->nGetPrecPrio()==papbCur->nGetPrecPrio())
{
vSiblingAppendAfterAndUnlink(papbNest,papbCur);
// papbCur->papbGetParent()->nIDValue = TOKEN_ID_REORDER;
papbNest =papbCur;
fSkip =true;
}
if(!fSkip && papbNest->nGetPrecPrio()>papbCur->nGetPrecPrio())
{
vChildAppendAfterAndUnlink(papbNest,papbCur);
papbNest =papbCur;
fDone =true;
fSkip =true;
}
if(!fSkip && papbNest->nGetPrecPrio()<papbCur->nGetPrecPrio())
{
cxaParseBranch *papbParent;
papbParent =papbGetParentWithPrio( papbNest,
papbCur->nGetPrecPrio(),
papbCur->papbGetParent());
vSiblingAppendAfterAndUnlink(papbParent,papbCur);
papbNest =papbCur;
fDone =true;
}
// To avoid doing multiple levels of nested branches
if( papbCur->papbGetParent()!=NULL &&
papbCur->papbGetParent()->nGetIDValue()!=TOKEN_ID_REORDER)
{
cxaParseBranch *papbCurParent = papbCur->papbGetParent();
cxaParseBranch *papbFirst = papbReverseSearchWithEqualPrio(papbCur);
ASSERT(papbFirst!=NULL);
ASSERT(papbFirst->papbGetParent() == papbCurParent);
if(papbFirst != papbCur)
{
cxaParseBranch *papbNew;
cxaParseElement *papbBefore = NULL;
papbCurParent->vUnlink(papbFirst,papbCur,&papbBefore,NULL,true);
papbNew =new cxaParseBranch(nAtmType,TOKEN_ID_REORDER,
papbCur->nGetPrecPrio(),
false,false);
cxaParseElement *papeCur = papbFirst, *papeNext;
while(true)
{
papeNext =papeCur->tGetNext();
papbNew->vPushBack(papeCur);
if(papeCur==papbCur)
break;
papeCur =papeNext;
ASSERT(papeCur!=NULL);
}
if(papbBefore!=NULL)
papbCurParent->vInsertAfter(papbBefore,papbNew);
else
papbCurParent->vPushFront(papbNew);
}
}
}
return fDone;
}
Submit an article or tip