1/* FILE: sub_base.cpp 2 * DATE MODIFIED: 31-Aug-07 3 * DESCRIPTION: Part of the SREC graph compiler project source files. 4 * 5 * Copyright 2007, 2008 Nuance Communciations, Inc. * 6 * * 7 * Licensed under the Apache License, Version 2.0 (the 'License'); * 8 * you may not use this file except in compliance with the License. * 9 * * 10 * You may obtain a copy of the License at * 11 * http://www.apache.org/licenses/LICENSE-2.0 * 12 * * 13 * Unless required by applicable law or agreed to in writing, software * 14 * distributed under the License is distributed on an 'AS IS' BASIS, * 15 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * 16 * See the License for the specific language governing permissions and * 17 * limitations under the License. * 18 * * 19 *---------------------------------------------------------------------------*/ 20 21#include <iostream> 22#include <string> 23#include <assert.h> 24#include <cstdio> 25 26#include "sub_grph.h" 27 28 29SubGraph::SubGraph (SubGraph *baseG) 30{ 31 int count= strlen(baseG->title); 32 title= new char [count+1]; 33 strcpy (title, baseG->title); 34 ruleId= baseG->ruleId; 35 arc= new NUANArc * [BLKSIZE]; 36 popOp= 0; 37 numVertex= baseG->numVertex; 38 lastScope= SCOPE_ROOT; 39 startId= baseG->startId; 40 lastId= baseG->lastId; 41 endId= baseG->endId; 42 forwardList= 0; 43 backwardList= 0; 44 sortNum= 0; 45 numArc= 0; 46 CopyFastArcs (baseG, 0, baseG->numArc, 0, -1, -1, -1, -1); 47 UpdateVertexCount (0); 48 49 return; 50} 51 52int SubGraph::NewVertexId () 53{ 54 return (numVertex++); 55} 56 57void SubGraph::AllocateSpaceForArc () 58{ 59 if (numArc == 0) { 60 arc= new NUANArc * [BLKSIZE]; 61 } 62 if (numArc%BLKSIZE == 0) { 63 NUANArc **new_arc= new NUANArc * [numArc+BLKSIZE]; 64 for (int ii= 0; ii < numArc; ii++) 65 new_arc[ii]= arc[ii]; 66 delete [] arc; 67 arc= new_arc; 68 } 69} 70 71NUANArc *SubGraph::CreateArc (int iLabel, int oLabel, int from, int to) 72{ 73 assert (!(iLabel == NONE_LABEL && from == to)); 74 AllocateSpaceForArc (); 75 NUANArc *arc_one= new NUANArc (iLabel, oLabel, from, to); 76 arc[numArc]= arc_one; 77 numArc++; 78 return arc_one; 79} 80 81NUANArc *SubGraph::InheritArc (NUANArc *arcBase, int id) 82{ 83 AllocateSpaceForArc (); 84 NUANArc *arc_one= new NUANArc (arcBase); 85 arc_one->AssignFromId (id); 86 arc[numArc]= arc_one; 87 numArc++; 88 return arc_one; 89} 90 91NUANArc *SubGraph::InheritReverseArc (NUANArc *arcBase, int id) 92{ 93 AllocateSpaceForArc (); 94 NUANArc *arc_one= new NUANArc (arcBase); 95 arc_one->AssignToId (id); 96 arc[numArc]= arc_one; 97 numArc++; 98 return arc_one; 99} 100 101NUANArc *SubGraph::InheritReverseArcWithTag (NUANArc *arcBase, int id, int tagId) 102{ 103 AllocateSpaceForArc (); 104 NUANArc *arc_one= new NUANArc (arcBase); 105 arc_one->AssignToId (id); 106 arc_one->AssignOutput (tagId); 107 arc[numArc]= arc_one; 108 numArc++; 109 return arc_one; 110} 111 112NUANArc *SubGraph::CreateCopyWithOutput (NUANArc *arcBase, int id) 113{ 114 AllocateSpaceForArc (); 115 NUANArc *arc_one= new NUANArc (arcBase); 116 arc_one->AssignOutput (id); 117 arc[numArc]= arc_one; 118 numArc++; 119 return arc_one; 120} 121 122void SubGraph::CopyFastArcs (SubGraph *subG, int startLoc, int endLoc, int offset, int headId, int newHeadId, int tailId, int newTailId) 123{ 124 NUANArc *arc_one; 125 126 for (int ii= startLoc; ii < endLoc; ii++) { 127 if (numArc%BLKSIZE == 0) { 128 NUANArc **new_arc= new NUANArc * [numArc+BLKSIZE]; 129 for (int ii= 0; ii < numArc; ii++) 130 new_arc[ii]= arc[ii]; 131 delete [] arc; 132 arc= new_arc; 133 } 134 arc_one= new NUANArc (subG->arc[ii], offset, headId, newHeadId, tailId, newTailId); 135 arc[numArc]= arc_one; 136 numArc++; 137 } 138 return; 139} 140 141void SubGraph::Print () 142{ 143 int loc; 144 145 printf ("Graph %s (%d %d)\n", title, startId, lastId); 146 for (int ii= 0; ii < numArc; ii++) { 147 loc= forwardList[ii]; 148 // loc= ii; 149 arc[loc]->Print(); 150 } 151 return; 152} 153 154void SubGraph::PrintText () 155{ 156 int loc; 157 158 printf ("Graph %s (%d %d)\n", title, startId, lastId); 159 for (int ii= 0; ii < numArc; ii++) { 160 loc= forwardList[ii]; 161 // loc= ii; 162 arc[loc]->PrintText(); 163 } 164 return; 165} 166 167void SubGraph::ReverseDepthOnTerminal (int *depthMap) 168{ 169 for (int ii= 0; ii < numArc; ii++) 170 if (arc[ii]->GetInput() == TERMINAL_LABEL) 171 ReverseDepthData (arc[ii]->GetFromId(), depthMap, 1); 172 return; 173} 174 175void SubGraph::ReverseDepthData (int startId, int *depthMap, int depth) 176{ 177 int rix, nextId, nextInp; 178 179 if (depthMap[startId] > depth) 180 depthMap[startId]= depth; 181 else 182 return; 183 rix= FindToIndex (startId); 184 if (rix < 0) 185 return; 186 while (rix < numArc && arc[backwardList[rix]]->GetToId() == startId) { 187 nextId= arc[backwardList[rix]]->GetFromId(); 188 nextInp= arc[backwardList[rix]]->GetInput(); 189 if (nextId >= 0 && nextInp != DISCARD_LABEL) 190 ReverseDepthData (nextId, depthMap, depth+1); 191 rix++; 192 } 193 return; 194} 195 196void SubGraph::ForwardDepthData (int startId, int *depthMap, int depth) 197{ 198 int rix, nextId, nextInp; 199 200 if (depthMap[startId] > depth) 201 depthMap[startId]= depth; 202 else 203 return; 204 rix= FindFromIndex (startId); 205 if (rix < 0) 206 return; 207 while (rix < numArc && arc[forwardList[rix]]->GetFromId() == startId) { 208 nextId= arc[forwardList[rix]]->GetToId(); 209 nextInp= arc[forwardList[rix]]->GetInput(); 210 if (nextId >= 0 && nextInp != DISCARD_LABEL) 211 ForwardDepthData (nextId, depthMap, depth+1); 212 rix++; 213 } 214 return; 215} 216 217void SubGraph::RemoveUnvisitedArcs (int initialId, int finalId) 218{ 219 int ii; 220 int *forwardDepth= new int [numVertex]; 221 int *reverseDepth= new int [numVertex]; 222 223 for (ii= 0; ii < numVertex; ii++) 224 forwardDepth[ii]= reverseDepth[ii]= MAXNUM; // TODO: review 225 SortLanguage(); 226 SortLanguageReverse(); 227 228 ForwardDepthData (initialId, forwardDepth, 1); 229 if (finalId >= 0) 230 ReverseDepthData (finalId, reverseDepth, 1); 231 ReverseDepthOnTerminal (reverseDepth); 232 233 for (ii= 0; ii < numVertex; ii++) { 234 if (forwardDepth[ii] == MAXNUM) 235 forwardDepth[ii]= -1; 236 if (reverseDepth[ii] == MAXNUM) 237 reverseDepth[ii]= -1; 238 } 239 RemoveMarkedNodes (forwardDepth, reverseDepth); 240 delete [] forwardDepth; 241 delete [] reverseDepth; 242 return; 243} 244 245void SubGraph::RemoveMarkedNodes (int *forwardDepth, int *reverseDepth) 246{ 247 int ii, currId, incId, outId; 248 249 currId= 0; 250 for (ii= 0; ii < numArc; ii++) { 251 incId= arc[ii]->GetFromId(); 252 outId= arc[ii]->GetToId(); 253 assert (outId == DISCARD_LABEL || outId == TERMINAL_LABEL || outId >= 0); 254 if (incId != DISCARD_LABEL && outId != DISCARD_LABEL 255 && arc[ii]->GetInput() != DISCARD_LABEL 256 && forwardDepth[incId] > 0 257 && (outId == TERMINAL_LABEL || reverseDepth[outId] > 0)) { 258 arc[currId]= arc[ii]; 259 currId++; 260 } 261 else 262 delete arc[ii]; 263 } 264 for (ii= currId; ii < numArc; ii++) 265 arc[ii]= 0; 266 numArc= currId; 267 return; 268} 269 270void SubGraph::RemoveDiscardedArcs () 271{ 272 int ii, currId, outId, inpId; 273 274 currId= 0; 275 for (ii= 0; ii < numArc; ii++) { 276 outId= arc[ii]->GetToId(); 277 inpId= arc[ii]->GetInput(); 278 if (outId != DISCARD_LABEL && inpId != DISCARD_LABEL) { 279 arc[currId]= arc[ii]; 280 currId++; 281 } 282 else 283 delete arc[ii]; 284 } 285 for (ii= currId; ii < numArc; ii++) 286 arc[ii]= 0; 287 numArc= currId; 288 return; 289} 290 291void SubGraph::MapGraphVertices (int *equivMap) 292{ 293 int ii, fromId, toId; 294 295 for (ii= 0; ii < numArc; ii++) { 296 fromId= arc[ii]->GetFromId(); 297 if (fromId >= 0) 298 if (equivMap[fromId] != fromId) 299 arc[ii]->AssignInput (DISCARD_LABEL); 300 toId= arc[ii]->GetToId(); 301 if (toId >= 0) 302 if (equivMap[toId] != toId) 303 arc[ii]->AssignToId (equivMap[toId]); 304 } 305 return; 306} 307 308void SubGraph::DebugPrintDirective (char *dirrData) 309{ 310 for (int ii= 0; ii < (popOp/7); ii++) 311 printf (" "); 312 printf ("%s\n", dirrData); 313 return; 314} 315 316void SubGraph::DebugPrintLabel (int labId) 317{ 318 for (int ii= 0; ii <= (popOp/7); ii++) 319 printf (" "); 320 printf ("%d\n", labId); 321 return; 322} 323 324void SubGraph::ClearLabelledConnections (int labItem) 325{ 326 for (int ii= 0; ii < numArc; ii++) { 327 if (arc[ii]->GetInput() == labItem) 328 arc[ii]->AssignToId (DISCARD_LABEL); 329 } 330 return; 331} 332 333void SubGraph::ClearRuleIds () 334{ 335 for (int ii= 0; ii < numArc; ii++) { 336 if (arc[ii]->GetInput() < 0 && arc[ii]->GetInput() > NONE_LABEL) 337 arc[ii]->AssignToId (DISCARD_LABEL); 338 } 339 return; 340} 341 342void SubGraph::ClearOutputs () 343{ 344 for (int ii= 0; ii < numArc; ii++) 345 arc[ii]->AssignOutput (NONE_LABEL); 346 return; 347} 348