tools/grxmlcompile/sub_base.cpp - platform/external/srec - Git at Google

 /* FILE:		sub_base.cpp
  *  DATE MODIFIED:	31-Aug-07
  *  DESCRIPTION:	Part of the  SREC graph compiler project source files.
  *
  *  Copyright 2007, 2008 Nuance Communciations, Inc.                               *
  *                                                                           *
  *  Licensed under the Apache License, Version 2.0 (the 'License');          *
  *  you may not use this file except in compliance with the License.         *
  *                                                                           *
  *  You may obtain a copy of the License at                                  *
  *      http://www.apache.org/licenses/LICENSE-2.0                           *
  *                                                                           *
  *  Unless required by applicable law or agreed to in writing, software      *
  *  distributed under the License is distributed on an 'AS IS' BASIS,        *
  *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. *
  *  See the License for the specific language governing permissions and      *
  *  limitations under the License.                                           *
  *                                                                           *
  *---------------------------------------------------------------------------*/

 #include <iostream>
 #include <string>
 #include <assert.h>
 #include <cstdio>

 #include "sub_grph.h"


 SubGraph::SubGraph (SubGraph *baseG)
 {
     int count= strlen(baseG->title);
     title= new char [count+1];
     strcpy (title, baseG->title);
     ruleId= baseG->ruleId;
     arc= new NUANArc * [BLKSIZE];
     popOp= 0;
     numVertex= baseG->numVertex;
     lastScope= SCOPE_ROOT;
     startId= baseG->startId;
     lastId= baseG->lastId;
     endId= baseG->endId;
     forwardList= 0;
     backwardList= 0;
     sortNum= 0;
     numArc= 0;
     CopyFastArcs (baseG, 0, baseG->numArc, 0, -1, -1, -1, -1);
     UpdateVertexCount (0);

     return;
 }

 int SubGraph::NewVertexId ()
 {
     return (numVertex++);
 }

 void SubGraph::AllocateSpaceForArc ()
 {
     if (numArc == 0) {
         arc= new NUANArc * [BLKSIZE];
     }
     if (numArc%BLKSIZE == 0) {
         NUANArc **new_arc= new NUANArc * [numArc+BLKSIZE];
         for (int ii= 0; ii < numArc; ii++)
             new_arc[ii]= arc[ii];
         delete [] arc;
         arc= new_arc;
     }
 }

 NUANArc *SubGraph::CreateArc (int iLabel, int oLabel, int from, int to)
 {
     assert (!(iLabel == NONE_LABEL && from == to));
     AllocateSpaceForArc ();
     NUANArc *arc_one= new NUANArc (iLabel, oLabel, from, to);
     arc[numArc]= arc_one;
     numArc++;
     return arc_one;
 }

 NUANArc *SubGraph::InheritArc (NUANArc *arcBase, int id)
 {
     AllocateSpaceForArc ();
     NUANArc *arc_one= new NUANArc (arcBase);
     arc_one->AssignFromId (id);
     arc[numArc]= arc_one;
     numArc++;
     return arc_one;
 }

 NUANArc *SubGraph::InheritReverseArc (NUANArc *arcBase, int id)
 {
     AllocateSpaceForArc ();
     NUANArc *arc_one= new NUANArc (arcBase);
     arc_one->AssignToId (id);
     arc[numArc]= arc_one;
     numArc++;
     return arc_one;
 }

 NUANArc *SubGraph::InheritReverseArcWithTag (NUANArc *arcBase, int id, int tagId)
 {
     AllocateSpaceForArc ();
     NUANArc *arc_one= new NUANArc (arcBase);
     arc_one->AssignToId (id);
     arc_one->AssignOutput (tagId);
     arc[numArc]= arc_one;
     numArc++;
     return arc_one;
 }

 NUANArc *SubGraph::CreateCopyWithOutput (NUANArc *arcBase, int id)
 {
     AllocateSpaceForArc ();
     NUANArc *arc_one= new NUANArc (arcBase);
     arc_one->AssignOutput (id);
     arc[numArc]= arc_one;
     numArc++;
     return arc_one;
 }

 void SubGraph::CopyFastArcs (SubGraph *subG, int startLoc, int endLoc, int offset, int headId, int newHeadId, int tailId, int newTailId)
 {
     NUANArc *arc_one;

     for (int ii= startLoc; ii < endLoc; ii++) {
         if (numArc%BLKSIZE == 0) {
             NUANArc **new_arc= new NUANArc * [numArc+BLKSIZE];
             for (int ii= 0; ii < numArc; ii++)
                 new_arc[ii]= arc[ii];
             delete [] arc;
             arc= new_arc;
         }
         arc_one= new NUANArc (subG->arc[ii], offset, headId, newHeadId, tailId, newTailId);
         arc[numArc]= arc_one;
         numArc++;
     }
     return;
 }

 void SubGraph::Print ()
 {
     int loc;

     printf ("Graph %s (%d %d)\n", title, startId, lastId);
     for (int ii= 0; ii < numArc; ii++) {
         loc= forwardList[ii];
         // loc= ii;
         arc[loc]->Print();
     }
     return;
 }

 void SubGraph::PrintText ()
 {
     int loc;

     printf ("Graph %s (%d %d)\n", title, startId, lastId);
     for (int ii= 0; ii < numArc; ii++) {
         loc= forwardList[ii];
         // loc= ii;
         arc[loc]->PrintText();
     }
     return;
 }

 void SubGraph::ReverseDepthOnTerminal (int *depthMap)
 {
     for (int ii= 0; ii < numArc; ii++)
         if (arc[ii]->GetInput() == TERMINAL_LABEL)
             ReverseDepthData (arc[ii]->GetFromId(), depthMap, 1);
         return;
 }

 void SubGraph::ReverseDepthData (int startId, int *depthMap, int depth)
 {
     int rix, nextId, nextInp;

     if (depthMap[startId] > depth)
         depthMap[startId]= depth;
     else
         return;
     rix= FindToIndex (startId);
     if (rix < 0)
         return;
     while (rix < numArc && arc[backwardList[rix]]->GetToId() == startId) {
         nextId= arc[backwardList[rix]]->GetFromId();
         nextInp= arc[backwardList[rix]]->GetInput();
         if (nextId >= 0 && nextInp != DISCARD_LABEL)
             ReverseDepthData (nextId, depthMap, depth+1);
         rix++;
     }
     return;
 }

 void SubGraph::ForwardDepthData (int startId, int *depthMap, int depth)
 {
     int rix, nextId, nextInp;

     if (depthMap[startId] > depth)
         depthMap[startId]= depth;
     else
         return;
     rix= FindFromIndex (startId);
     if (rix < 0)
         return;
     while (rix < numArc && arc[forwardList[rix]]->GetFromId() == startId) {
         nextId= arc[forwardList[rix]]->GetToId();
         nextInp= arc[forwardList[rix]]->GetInput();
         if (nextId >= 0 && nextInp != DISCARD_LABEL)
             ForwardDepthData (nextId, depthMap, depth+1);
         rix++;
     }
     return;
 }

 void SubGraph::RemoveUnvisitedArcs (int initialId, int finalId)
 {
     int ii;
     int *forwardDepth= new int [numVertex];
     int *reverseDepth= new int [numVertex];

     for (ii= 0; ii < numVertex; ii++)
         forwardDepth[ii]= reverseDepth[ii]= MAXNUM;     //  TODO: review
     SortLanguage();
     SortLanguageReverse();

     ForwardDepthData (initialId, forwardDepth, 1);
     if (finalId >= 0)
         ReverseDepthData (finalId, reverseDepth, 1);
     ReverseDepthOnTerminal (reverseDepth);

     for (ii= 0; ii < numVertex; ii++) {
         if (forwardDepth[ii] == MAXNUM)
             forwardDepth[ii]= -1;
         if (reverseDepth[ii] == MAXNUM)
             reverseDepth[ii]= -1;
     }
     RemoveMarkedNodes (forwardDepth, reverseDepth);
     delete [] forwardDepth;
     delete [] reverseDepth;
     return;
 }

 void SubGraph::RemoveMarkedNodes (int *forwardDepth, int *reverseDepth)
 {
     int ii, currId, incId, outId;

     currId= 0;
     for (ii= 0; ii < numArc; ii++) {
         incId= arc[ii]->GetFromId();
         outId= arc[ii]->GetToId();
         assert (outId == DISCARD_LABEL || outId == TERMINAL_LABEL || outId >= 0);
         if (incId != DISCARD_LABEL && outId != DISCARD_LABEL
             && arc[ii]->GetInput() != DISCARD_LABEL
             && forwardDepth[incId] > 0
             && (outId == TERMINAL_LABEL || reverseDepth[outId] > 0)) {
             arc[currId]= arc[ii];
             currId++;
         }
         else
             delete arc[ii];
     }
     for (ii= currId; ii < numArc; ii++)
 	arc[ii]= 0;
     numArc= currId;
     return;
 }

 void SubGraph::RemoveDiscardedArcs ()
 {
     int ii, currId, outId, inpId;

     currId= 0;
     for (ii= 0; ii < numArc; ii++) {
         outId= arc[ii]->GetToId();
         inpId= arc[ii]->GetInput();
         if (outId != DISCARD_LABEL && inpId != DISCARD_LABEL) {
             arc[currId]= arc[ii];
             currId++;
         }
         else
             delete arc[ii];
     }
     for (ii= currId; ii < numArc; ii++)
 	arc[ii]= 0;
     numArc= currId;
     return;
 }

 void SubGraph::MapGraphVertices (int *equivMap)
 {
     int ii, fromId, toId;

     for (ii= 0; ii < numArc; ii++) {
         fromId= arc[ii]->GetFromId();
         if (fromId >= 0)
             if (equivMap[fromId] != fromId)
                 arc[ii]->AssignInput (DISCARD_LABEL);
         toId= arc[ii]->GetToId();
         if (toId >= 0)
             if (equivMap[toId] != toId)
                 arc[ii]->AssignToId (equivMap[toId]);
     }
     return;
 }

 void SubGraph::DebugPrintDirective (char *dirrData)
 {
     for (int ii= 0; ii < (popOp/7); ii++)
         printf ("  ");
     printf ("%s\n", dirrData);
     return;
 }

 void SubGraph::DebugPrintLabel (int labId)
 {
     for (int ii= 0; ii <= (popOp/7); ii++)
         printf ("  ");
     printf ("%d\n", labId);
     return;
 }

 void SubGraph::ClearLabelledConnections (int labItem)
 {
     for (int ii= 0; ii < numArc; ii++) {
         if (arc[ii]->GetInput() == labItem)
             arc[ii]->AssignToId (DISCARD_LABEL);
     }
     return;
 }

 void SubGraph::ClearRuleIds ()
 {
     for (int ii= 0; ii < numArc; ii++) {
         if (arc[ii]->GetInput() < 0 && arc[ii]->GetInput() > NONE_LABEL)
             arc[ii]->AssignToId (DISCARD_LABEL);
     }
     return;
 }

 void SubGraph::ClearOutputs ()
 {
     for (int ii= 0; ii < numArc; ii++)
         arc[ii]->AssignOutput (NONE_LABEL);
     return;
 }
	/* FILE: sub_base.cpp
	* DATE MODIFIED: 31-Aug-07
	* DESCRIPTION: Part of the SREC graph compiler project source files.
	*
	* Copyright 2007, 2008 Nuance Communciations, Inc. *
	* *
	* Licensed under the Apache License, Version 2.0 (the 'License'); *
	* you may not use this file except in compliance with the License. *
	* *
	* You may obtain a copy of the License at *
	* http://www.apache.org/licenses/LICENSE-2.0 *
	* *
	* Unless required by applicable law or agreed to in writing, software *
	* distributed under the License is distributed on an 'AS IS' BASIS, *
	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. *
	* See the License for the specific language governing permissions and *
	* limitations under the License. *
	* *
	---------------------------------------------------------------------------/

	#include <iostream>
	#include <string>
	#include <assert.h>
	#include <cstdio>

	#include "sub_grph.h"


	SubGraph::SubGraph (SubGraph *baseG)
	{
	int count= strlen(baseG->title);
	title= new char [count+1];
	strcpy (title, baseG->title);
	ruleId= baseG->ruleId;
	arc= new NUANArc * [BLKSIZE];
	popOp= 0;
	numVertex= baseG->numVertex;
	lastScope= SCOPE_ROOT;
	startId= baseG->startId;
	lastId= baseG->lastId;
	endId= baseG->endId;
	forwardList= 0;
	backwardList= 0;
	sortNum= 0;
	numArc= 0;
	CopyFastArcs (baseG, 0, baseG->numArc, 0, -1, -1, -1, -1);
	UpdateVertexCount (0);

	return;
	}

	int SubGraph::NewVertexId ()
	{
	return (numVertex++);
	}

	void SubGraph::AllocateSpaceForArc ()
	{
	if (numArc == 0) {
	arc= new NUANArc * [BLKSIZE];
	}
	if (numArc%BLKSIZE == 0) {
	NUANArc *new_arc= new NUANArc [numArc+BLKSIZE];
	for (int ii= 0; ii < numArc; ii++)
	new_arc[ii]= arc[ii];
	delete [] arc;
	arc= new_arc;
	}
	}

	NUANArc *SubGraph::CreateArc (int iLabel, int oLabel, int from, int to)
	{
	assert (!(iLabel == NONE_LABEL && from == to));
	AllocateSpaceForArc ();
	NUANArc *arc_one= new NUANArc (iLabel, oLabel, from, to);
	arc[numArc]= arc_one;
	numArc++;
	return arc_one;
	}

	NUANArc SubGraph::InheritArc (NUANArc arcBase, int id)
	{
	AllocateSpaceForArc ();
	NUANArc *arc_one= new NUANArc (arcBase);
	arc_one->AssignFromId (id);
	arc[numArc]= arc_one;
	numArc++;
	return arc_one;
	}

	NUANArc SubGraph::InheritReverseArc (NUANArc arcBase, int id)
	{
	AllocateSpaceForArc ();
	NUANArc *arc_one= new NUANArc (arcBase);
	arc_one->AssignToId (id);
	arc[numArc]= arc_one;
	numArc++;
	return arc_one;
	}

	NUANArc SubGraph::InheritReverseArcWithTag (NUANArc arcBase, int id, int tagId)
	{
	AllocateSpaceForArc ();
	NUANArc *arc_one= new NUANArc (arcBase);
	arc_one->AssignToId (id);
	arc_one->AssignOutput (tagId);
	arc[numArc]= arc_one;
	numArc++;
	return arc_one;
	}

	NUANArc SubGraph::CreateCopyWithOutput (NUANArc arcBase, int id)
	{
	AllocateSpaceForArc ();
	NUANArc *arc_one= new NUANArc (arcBase);
	arc_one->AssignOutput (id);
	arc[numArc]= arc_one;
	numArc++;
	return arc_one;
	}

	void SubGraph::CopyFastArcs (SubGraph *subG, int startLoc, int endLoc, int offset, int headId, int newHeadId, int tailId, int newTailId)
	{
	NUANArc *arc_one;

	for (int ii= startLoc; ii < endLoc; ii++) {
	if (numArc%BLKSIZE == 0) {
	NUANArc *new_arc= new NUANArc [numArc+BLKSIZE];
	for (int ii= 0; ii < numArc; ii++)
	new_arc[ii]= arc[ii];
	delete [] arc;
	arc= new_arc;
	}
	arc_one= new NUANArc (subG->arc[ii], offset, headId, newHeadId, tailId, newTailId);
	arc[numArc]= arc_one;
	numArc++;
	}
	return;
	}

	void SubGraph::Print ()
	{
	int loc;

	printf ("Graph %s (%d %d)\n", title, startId, lastId);
	for (int ii= 0; ii < numArc; ii++) {
	loc= forwardList[ii];
	// loc= ii;
	arc[loc]->Print();
	}
	return;
	}

	void SubGraph::PrintText ()
	{
	int loc;

	printf ("Graph %s (%d %d)\n", title, startId, lastId);
	for (int ii= 0; ii < numArc; ii++) {
	loc= forwardList[ii];
	// loc= ii;
	arc[loc]->PrintText();
	}
	return;
	}

	void SubGraph::ReverseDepthOnTerminal (int *depthMap)
	{
	for (int ii= 0; ii < numArc; ii++)
	if (arc[ii]->GetInput() == TERMINAL_LABEL)
	ReverseDepthData (arc[ii]->GetFromId(), depthMap, 1);
	return;
	}

	void SubGraph::ReverseDepthData (int startId, int *depthMap, int depth)
	{
	int rix, nextId, nextInp;

	if (depthMap[startId] > depth)
	depthMap[startId]= depth;
	else
	return;
	rix= FindToIndex (startId);
	if (rix < 0)
	return;
	while (rix < numArc && arc[backwardList[rix]]->GetToId() == startId) {
	nextId= arc[backwardList[rix]]->GetFromId();
	nextInp= arc[backwardList[rix]]->GetInput();
	if (nextId >= 0 && nextInp != DISCARD_LABEL)
	ReverseDepthData (nextId, depthMap, depth+1);
	rix++;
	}
	return;
	}

	void SubGraph::ForwardDepthData (int startId, int *depthMap, int depth)
	{
	int rix, nextId, nextInp;

	if (depthMap[startId] > depth)
	depthMap[startId]= depth;
	else
	return;
	rix= FindFromIndex (startId);
	if (rix < 0)
	return;
	while (rix < numArc && arc[forwardList[rix]]->GetFromId() == startId) {
	nextId= arc[forwardList[rix]]->GetToId();
	nextInp= arc[forwardList[rix]]->GetInput();
	if (nextId >= 0 && nextInp != DISCARD_LABEL)
	ForwardDepthData (nextId, depthMap, depth+1);
	rix++;
	}
	return;
	}

	void SubGraph::RemoveUnvisitedArcs (int initialId, int finalId)
	{
	int ii;
	int *forwardDepth= new int [numVertex];
	int *reverseDepth= new int [numVertex];

	for (ii= 0; ii < numVertex; ii++)
	forwardDepth[ii]= reverseDepth[ii]= MAXNUM; // TODO: review
	SortLanguage();
	SortLanguageReverse();

	ForwardDepthData (initialId, forwardDepth, 1);
	if (finalId >= 0)
	ReverseDepthData (finalId, reverseDepth, 1);
	ReverseDepthOnTerminal (reverseDepth);

	for (ii= 0; ii < numVertex; ii++) {
	if (forwardDepth[ii] == MAXNUM)
	forwardDepth[ii]= -1;
	if (reverseDepth[ii] == MAXNUM)
	reverseDepth[ii]= -1;
	}
	RemoveMarkedNodes (forwardDepth, reverseDepth);
	delete [] forwardDepth;
	delete [] reverseDepth;
	return;
	}

	void SubGraph::RemoveMarkedNodes (int forwardDepth, int reverseDepth)
	{
	int ii, currId, incId, outId;

	currId= 0;
	for (ii= 0; ii < numArc; ii++) {
	incId= arc[ii]->GetFromId();
	outId= arc[ii]->GetToId();
	assert (outId == DISCARD_LABEL \|\| outId == TERMINAL_LABEL \|\| outId >= 0);
	if (incId != DISCARD_LABEL && outId != DISCARD_LABEL
	&& arc[ii]->GetInput() != DISCARD_LABEL
	&& forwardDepth[incId] > 0
	&& (outId == TERMINAL_LABEL \|\| reverseDepth[outId] > 0)) {
	arc[currId]= arc[ii];
	currId++;
	}
	else
	delete arc[ii];
	}
	for (ii= currId; ii < numArc; ii++)
	arc[ii]= 0;
	numArc= currId;
	return;
	}

	void SubGraph::RemoveDiscardedArcs ()
	{
	int ii, currId, outId, inpId;

	currId= 0;
	for (ii= 0; ii < numArc; ii++) {
	outId= arc[ii]->GetToId();
	inpId= arc[ii]->GetInput();
	if (outId != DISCARD_LABEL && inpId != DISCARD_LABEL) {
	arc[currId]= arc[ii];
	currId++;
	}
	else
	delete arc[ii];
	}
	for (ii= currId; ii < numArc; ii++)
	arc[ii]= 0;
	numArc= currId;
	return;
	}

	void SubGraph::MapGraphVertices (int *equivMap)
	{
	int ii, fromId, toId;

	for (ii= 0; ii < numArc; ii++) {
	fromId= arc[ii]->GetFromId();
	if (fromId >= 0)
	if (equivMap[fromId] != fromId)
	arc[ii]->AssignInput (DISCARD_LABEL);
	toId= arc[ii]->GetToId();
	if (toId >= 0)
	if (equivMap[toId] != toId)
	arc[ii]->AssignToId (equivMap[toId]);
	}
	return;
	}

	void SubGraph::DebugPrintDirective (char *dirrData)
	{
	for (int ii= 0; ii < (popOp/7); ii++)
	printf (" ");
	printf ("%s\n", dirrData);
	return;
	}

	void SubGraph::DebugPrintLabel (int labId)
	{
	for (int ii= 0; ii <= (popOp/7); ii++)
	printf (" ");
	printf ("%d\n", labId);
	return;
	}

	void SubGraph::ClearLabelledConnections (int labItem)
	{
	for (int ii= 0; ii < numArc; ii++) {
	if (arc[ii]->GetInput() == labItem)
	arc[ii]->AssignToId (DISCARD_LABEL);
	}
	return;
	}

	void SubGraph::ClearRuleIds ()
	{
	for (int ii= 0; ii < numArc; ii++) {
	if (arc[ii]->GetInput() < 0 && arc[ii]->GetInput() > NONE_LABEL)
	arc[ii]->AssignToId (DISCARD_LABEL);
	}
	return;
	}

	void SubGraph::ClearOutputs ()
	{
	for (int ii= 0; ii < numArc; ii++)
	arc[ii]->AssignOutput (NONE_LABEL);
	return;
	}