/* FILE: sub_grph.h
* 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. *
* *
*---------------------------------------------------------------------------*/
#ifndef __sub_grph_h__
#define __sub_grph_h__
#include "netw_arc.h"
#include "vocab.h"
// TODO:
// Guards various stages 1. Compiling 2. Processing
#define SCOPE_ROOT 0
#define SCOPE_ITEM -1
#define SCOPE_RULE -2
#define SCOPE_ONEOF -3
#define SCOPE_COUNT -4
#define SCOPE_OPT -5
#define SCOPE_REPEAT -6
#define NONE_LABEL -100000 // Null transition
#define TAG_LABEL -100001 // Tag transition
#define WB_LABEL -100002 // Word boundary transition
#define TERMINAL_LABEL -100003 // Terminal transition
#define BEGINSCOPE_LABEL -100004 // Start of scope
#define ENDSCOPE_LABEL -100005 // End of scope
#define BEGINRULE_LABEL -100006 // Start of rule
#define ENDRULE_LABEL -100007 // End of rule
#define DISCARD_LABEL -100010 // Discard (internal)
#define INITIAL_LABEL -100011 // Initial silence
#define FINAL_LABEL -100012 // Final silence
#define MAXNUM 100000 // A large number
#define BLKSIZE 10000 // Buffer size
#define MAXITS 5 // Maximum equivalence reduction iterations
// #define MAX(X,Y) ((X) > (Y) ? (X) : (Y))
// #define MIN(X,Y) ((X) > (Y) ? (X) : (Y))
// General functions
bool IsSlot (std::string label);
class DetCache {
public:
DetCache () { num= 0; dataPack= 0; };
void AddEntry (int comb, int first, int second) {
if (num == 0)
dataPack= new int [3*BLKSIZE];
else if ((num%BLKSIZE) == 0) {
int *newPack = new int [num+3*BLKSIZE];
for (int ii= 0; ii < (3*num); ii++)
newPack[ii]= dataPack[ii];
delete [] dataPack;
dataPack= newPack;
}
dataPack[3*num]= first;
dataPack[3*num+1]= second;
dataPack[3*num+2]= comb;
num++;
return;
};
int QueryEntry (int first, int second) {
if (!dataPack)
return -1;
for (int ii= 0; ii < num; ii++)
if (dataPack[3*ii] == first && dataPack[3*ii+1] == second)
return (dataPack[3*ii+2]);
return -1;
}
~DetCache () { if (dataPack) delete [] dataPack; };
private:
int num;
int *dataPack;
};
class SubGraph
{
public:
SubGraph (char *name, int ruleNo)
{
int count= strlen(name);
title= new char [count+1];
strcpy (title, name);
// printf ("New Rule %s\n", title);
ruleId= ruleNo;
popOp= 0;
numArc= 0;
numVertex= 0;
lastScope= SCOPE_ROOT;
startId= NewVertexId();
lastId= startId;
endId= lastId;
forwardList= 0;
backwardList= 0;
sortNum= 0;
vertexProp= 0;
sizeProp= 0;
return;
};
SubGraph (SubGraph *baseG);
~SubGraph ()
{
delete [] title;
for (int ii= 0; ii < numArc; ii++)
delete arc[ii];
if (numArc >0)
delete [] arc;
if (forwardList)
delete [] forwardList;
if (backwardList)
delete [] backwardList;
return;
}
void getName (char *name, int maxlen)
{
strncpy (name, title, maxlen);
}
int getRuleId () {
return ruleId;
}
/** Creates a copy of the graph */
void CopyFastArcs (SubGraph *subG, int startLoc, int endLoc, int offset, int headId, int newHeadId, int tailId, int newTailId);
/** Graph construction routines */
void BeginScope (int scopeType, int arg1, int arg2);
void EndScope ();
int AddItem (int inputLabel, int tagLabel);
int AddTag (int tagLabel);
void ExpandRules (SubGraph **subList, int *lookupList, int numSubs);
/** Reverse subgraph */
void ReverseGraphForOutput ();
void SortLanguage ();
void SortLanguageForMin ();
void SortLanguageReverse ();
void UpdateSortForLanguage ();
void RemoveRuleConnections ();
void RemoveInternalConnections ();
void RemoveUnreachedConnections (int startPoint, int endPoint);
void RemoveUnreachedConnectionsDebug (int startPoint, int endPoint);
void RemoveTagConnections (int startPoint, int endPoint);
void AddTerminalConnections ();
void Print ();
void PrintText ();
void PrintWithLabels( GRXMLDoc &p_Doc );
void RemapForSortedOutput ( GRXMLDoc & doc );
void WriteForwardGraphWithSemantic ( std::string & fileName, GRXMLDoc &p_Doc );
void WriteForwardGraphFile ( std::string & fileName, GRXMLDoc &p_Doc );
void WriteFile ( std::string & fileName, GRXMLDoc &p_Doc );
void WritePhonemeGraphFile( std::string & fileName, GRXMLDoc &p_Doc );
void WriteHMMGraphFile( std::string & fileName, GRXMLDoc &p_Doc );
void DeterminizeArcs ();
int IsDeterminized (int currId);
void ReduceArcsByEquivalence ();
void ExpandPhonemes ( GRXMLDoc & doc );
void AddLeftContexts ();
void AddRightContexts ();
void ExpandToHMMs ( GRXMLDoc & doc );
void ExpandIntraWordSilence ( GRXMLDoc & doc );
void ClearOutputs ();
void ShiftOutputsToLeft ();
void FinalProcessing ( GRXMLDoc & doc );
void DebugPrintDirective (char *dirrData);
void DebugPrintLabel (int labId);
private:
int NewVertexId ();
int numVertex;
void AllocateSpaceForArc ();
NUANArc *CreateArc (int iLabel, int oLabel, int from, int to);
NUANArc *InheritArc (NUANArc *arcBase, int id);
NUANArc *InheritReverseArc (NUANArc *arcBase, int id);
NUANArc *CreateCopyWithOutput (NUANArc *arcBase, int id);
NUANArc *InheritReverseArcWithTag (NUANArc *arcBase, int id, int tagId);
int numArc;
NUANArc **arc;
int sortNum;
int sortRevNum;
int *forwardList;
int *backwardList;
int ConnectLastScope (int beginScopeId, int endScopeId);
int CloseScope ();
void UpdateVertexCount (int startLoc);
int FindFromIndex (int element);
int FindToIndex (int element);
void PullUpBegins (int currId, int baseId, int endId, int procLabel, int *nodeList, int currNum, int maxNum);
void ProcessBegins (int currId, int endId, int procLabel, int *nodeList, int currNum, int *visitMark, int maxNum);
void PullUpEnds (int currId, int baseId, int initialId, int procLabel, int *nodeList, int currNum, int maxNum);
void ProcessEnds (int currId, int initialId, int procLabel, int *nodeList, int currNum, int *visitMark, int maxNum);
bool PullUpTags (int currId, int baseId, int initialId, int outTag, int *nodeList, int currNum, int maxNum);
void ProcessTags (int currId, int initialId, int *nodeList, int currNum, int *visitMark, int maxNum);
void ClearDuplicateArcs ();
void RemoveRuleStarts (int startId, int endId);
void RemoveRuleEnds (int startId, int endId);
void RemoveNulls (int startPoint, int endPoint);
void RemoveForwardConnections (int startId, int endId);
void RemoveBackwardConnections (int startId, int endId);
void ClearLabelledConnections (int labItem);
void RemoveUnvisitedArcs (int initialId, int finalId);
void RemoveMarkedNodes (int *forwardDepth, int *reverseDepth);
void RemoveDiscardedArcs ();
void RenumberNodes ();
bool EquivalenceTestForward (int firstId, int secondId, int *equivMap);
void ForwardDepthData (int startId, int *depthMap, int depth);
void ReverseDepthData (int startId, int *depthMap, int depth);
void ReverseDepthOnTerminal (int *depthMap);
void MapGraphVertices (int *equivMap);
void IdentifyEquivalence (int *depthMap, int *equivMap);
void CheckForChangeAndResort (int currId, int *mapList);
void SortLanguageAtIndices (int begIx, int endIx);
void SortLanguageAtIndicesForMin (int begIx, int endIx);
void SortLanguageAtSortIndices (int begIx, int endIx);
bool CheckSort ();
bool CheckSortReverse ();
void RemoveDuplicatesAtNode (int rixBegin, int rixEnd);
void MergeVertices (int newId, int firstId, int secondId);
void DeterminizeAtVertex (int baseId, DetCache *cache);
int PairwiseDeterminize (int baseId, int firstId, int fixStart, int secondId, int sixStart, DetCache *cache);
void ClearRuleIds ();
void ViewNode (int currId);
void ReverseMarkArcs ();
void ReverseMarkOutput (int currId, int initialId, int outId);
void MarkNodesByOutputAndClearArcs ();
void ExpandWordBoundaries ( GRXMLDoc & doc );
void AddInitialFinalSilences ( GRXMLDoc & doc );
void UpdateVisitationCache (int startNo);
void ClearVisitationCache ();
void SetupVisitationCache ();
void DecVisitationCache (int currId);
void IncVisitationCache (int currId);
int VisitationConsistencyCheck ();
void CreateNodeProperty () {
vertexProp= new int [BLKSIZE];
vertexMinned= new bool [BLKSIZE];
sizeProp= BLKSIZE;
for (int ii= 0; ii < sizeProp; ii++) {
vertexProp[ii]= 0;
vertexMinned[ii]= false;
}
return;
}
void IncNodeProperty (int vertNo) {
if (vertNo >= sizeProp) {
int newSize= (vertNo/BLKSIZE + 1)*BLKSIZE;
int *newPack = new int [newSize];
bool *newMinned = new bool [newSize];
int ii;
for (ii= 0; ii < sizeProp; ii++) {
newPack[ii]= vertexProp[ii];
newMinned[ii]= vertexMinned[ii];
}
for (ii= sizeProp; ii < newSize; ii++) {
newPack[ii]= 0;
newMinned[ii]= false;
}
delete [] vertexProp;
delete [] vertexMinned;
vertexProp= newPack;
vertexMinned= newMinned;
sizeProp= newSize;
}
vertexProp[vertNo]++;
return;
}
void DecNodeProperty (int vertNo) {
if (vertNo < sizeProp)
vertexProp[vertNo]--;
return;
}
void SetNodeProperty (int vertNo, int value) {
if (vertNo < sizeProp)
vertexProp[vertNo]= value;
return;
}
void SetMinProperty (int vertNo) {
if (vertNo < sizeProp)
vertexMinned[vertNo]= true;
return;
}
int QueryNodeProperty (int vertNo) {
if (vertNo < sizeProp)
return (vertexProp[vertNo]);
return -1;
}
int QueryMinProperty (int vertNo) {
if (vertNo < sizeProp)
return (vertexMinned[vertNo]);
return false;
}
void DeleteNodeProperty () {
delete [] vertexProp;
delete [] vertexMinned;
vertexProp= 0;
vertexMinned= 0;
}
/* Stacking of operations and related data
*/
char *title;
int ruleId;
int lastScope;
int startId;
int endId;
int prevStartId;
int prevEndId;
int lastId;
int arg1;
int arg2;
int arcLoc;
int opStack[100000]; // TODO: remove hard coded number
int popOp;
void pushScope ();
void popScope ();
int silenceId;
int intraId;
int *vertexProp; // Vertex properties
bool *vertexMinned; // Vertex properties
int sizeProp;
};
#endif // __sub_grph_h__