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 29 SubGraph::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 52 int SubGraph::NewVertexId () 53 { 54 return (numVertex++); 55 } 56 57 void 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 71 NUANArc *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 81 NUANArc *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 91 NUANArc *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 101 NUANArc *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 112 NUANArc *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 122 void 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 141 void 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 154 void 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 167 void 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 175 void 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 196 void 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 217 void 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 245 void 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 270 void 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 291 void 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 308 void 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 316 void 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 324 void 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 333 void 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 342 void SubGraph::ClearOutputs () 343 { 344 for (int ii= 0; ii < numArc; ii++) 345 arc[ii]->AssignOutput (NONE_LABEL); 346 return; 347 } 348
