1 /* FILE: sub_supp.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 #define ARC_COMPARE(x,y) (arc[x]->Compare(arc[y])) 30 #define ARC_COMPARE_REV(x,y) (arc[x]->CompareReverse(arc[y])) 31 #define ARC_COMPARE_MIN(x,y) (arc[x]->CompareForMin(arc[y])) 32 33 34 void SubGraph::SortLanguage () 35 { 36 int *sortList; 37 38 if (numArc <= 1) { 39 sortList= new int [numArc+2]; 40 sortList[0]= 0; 41 if (forwardList) 42 delete [] forwardList; 43 forwardList= sortList; 44 sortNum= numArc; 45 return; 46 } 47 SortLanguageAtIndices (-1, -1); 48 return; 49 } 50 51 void SubGraph::SortLanguageAtIndices (int begIx, int endIx) 52 { 53 int ii, jj, hired, retd; 54 int holdArc, *sortList; 55 56 if (begIx < 0) 57 begIx= 0; 58 if (endIx < 0) 59 endIx= numArc; 60 61 if (endIx <= begIx) 62 return; 63 64 sortList= new int [numArc+2]; 65 for (ii= 0; ii < sortNum && ii < numArc; ii++) 66 sortList[ii]= forwardList[ii]; 67 for (ii= begIx; ii < endIx; ii++) 68 sortList[ii]= ii; 69 sortList--; 70 71 /* Hiring 72 */ 73 hired= (numArc >> 1)+1; 74 while (hired-- > 1) { 75 holdArc= sortList[hired]; 76 ii= hired; 77 jj= hired << 1; 78 while (jj <= numArc) { 79 if (jj < numArc && ARC_COMPARE (sortList[jj], sortList[jj+1]) <= 0 ) 80 jj++; 81 if (ARC_COMPARE (holdArc, sortList[jj]) < 0) { 82 sortList[ii]= sortList[jj]; 83 ii= jj; 84 jj <<= 1; 85 } 86 else 87 break; 88 } 89 sortList[ii]= holdArc; 90 } 91 92 /* Retiring 93 */ 94 retd= numArc; 95 while (retd > 0) { 96 holdArc= sortList[retd]; 97 sortList[retd]= sortList[1]; 98 if (--retd == 1) { 99 sortList[1]= holdArc; 100 break; 101 } 102 ii= 1; 103 jj= 2; 104 while (jj <= retd) { 105 if (jj < retd && ARC_COMPARE (sortList[jj], sortList[jj+1]) <= 0) 106 jj++; 107 if (ARC_COMPARE (holdArc, sortList[jj]) < 0) { 108 sortList[ii]= sortList[jj]; 109 ii= jj; 110 jj <<= 1; 111 } 112 else 113 break; 114 } 115 sortList[ii]= holdArc; 116 } 117 sortList++; 118 119 if (forwardList) 120 delete [] forwardList; 121 forwardList= sortList; 122 sortNum= numArc; 123 124 /* Now carry out some checks 125 */ 126 assert(CheckSort()); 127 128 return; 129 } 130 131 void SubGraph::SortLanguageAtSortIndices (int begIx, int endIx) 132 { 133 int ii, jj, hired, retd; 134 int holdArc, *sortList; 135 136 if (begIx < 0) 137 begIx= 0; 138 if (endIx < 0) 139 endIx= numArc; 140 141 if (endIx <= begIx) 142 return; 143 144 sortList= forwardList; 145 sortList--; 146 147 /* Hiring 148 */ 149 hired= (numArc >> 1)+1; 150 while (hired-- > 1) { 151 holdArc= sortList[hired]; 152 ii= hired; 153 jj= hired << 1; 154 while (jj <= numArc) { 155 if (jj < numArc && ARC_COMPARE (sortList[jj], sortList[jj+1]) <= 0 ) 156 jj++; 157 if (ARC_COMPARE (holdArc, sortList[jj]) < 0) { 158 sortList[ii]= sortList[jj]; 159 ii= jj; 160 jj <<= 1; 161 } 162 else 163 break; 164 } 165 sortList[ii]= holdArc; 166 } 167 168 /* Retiring 169 */ 170 retd= numArc; 171 while (retd > 0) { 172 holdArc= sortList[retd]; 173 sortList[retd]= sortList[1]; 174 if (--retd == 1) { 175 sortList[1]= holdArc; 176 break; 177 } 178 ii= 1; 179 jj= 2; 180 while (jj <= retd) { 181 if (jj < retd && ARC_COMPARE (sortList[jj], sortList[jj+1]) <= 0) 182 jj++; 183 if (ARC_COMPARE (holdArc, sortList[jj]) < 0) { 184 sortList[ii]= sortList[jj]; 185 ii= jj; 186 jj <<= 1; 187 } 188 else 189 break; 190 } 191 sortList[ii]= holdArc; 192 } 193 sortList++; 194 195 forwardList= sortList; 196 197 /* Now carry out some checks 198 */ 199 assert(CheckSort()); 200 201 return; 202 } 203 204 int SubGraph::FindFromIndex (int element) 205 { 206 int rix, rix_low, rix_high, direction; 207 208 rix_low= -1; 209 rix_high= sortNum; 210 while ((rix_high - rix_low) > 1) { 211 rix= (rix_high + rix_low) >> 1; 212 direction= element - arc[forwardList[rix]]->GetFromId(); 213 if (direction < 0) 214 rix_high= rix; 215 else if (direction > 0) 216 rix_low= rix; 217 else { 218 assert (arc[forwardList[rix]]->GetFromId() == element); 219 while (rix > 0 && arc[forwardList[rix-1]]->GetFromId() == element) 220 rix--; 221 assert (arc[forwardList[rix]]->GetFromId() == element); 222 assert (rix < sortNum); 223 return (rix); 224 } 225 } 226 return (-1); 227 } 228 229 void SubGraph::SortLanguageReverse () 230 { 231 int ii, jj, hired, retd; 232 int holdArc, *sortList; 233 234 if (numArc <= 1) { 235 sortList= new int [numArc+2]; 236 sortList[0]= 0; 237 if (backwardList) 238 delete [] backwardList; 239 backwardList= sortList; 240 sortRevNum= numArc; 241 return; 242 } 243 244 sortList= new int [numArc+2]; 245 for (ii= 0; ii < numArc; ii++) 246 sortList[ii]= ii; 247 sortList--; 248 249 /* Hiring 250 */ 251 hired= (numArc >> 1)+1; 252 while (hired-- > 1) { 253 holdArc= sortList[hired]; 254 ii= hired; 255 jj= hired << 1; 256 while (jj <= numArc) { 257 if (jj < numArc && ARC_COMPARE_REV (sortList[jj], sortList[jj+1]) <= 0 ) 258 jj++; 259 if (ARC_COMPARE_REV (holdArc, sortList[jj]) < 0) { 260 sortList[ii]= sortList[jj]; 261 ii= jj; 262 jj <<= 1; 263 } 264 else 265 break; 266 } 267 sortList[ii]= holdArc; 268 } 269 270 /* Retiring 271 */ 272 retd= numArc; 273 while (retd > 0) { 274 holdArc= sortList[retd]; 275 sortList[retd]= sortList[1]; 276 if (--retd == 1) { 277 sortList[1]= holdArc; 278 break; 279 } 280 ii= 1; 281 jj= 2; 282 while (jj <= retd) { 283 if (jj < retd && ARC_COMPARE_REV (sortList[jj], sortList[jj+1]) <= 0) 284 jj++; 285 if (ARC_COMPARE_REV (holdArc, sortList[jj]) < 0) { 286 sortList[ii]= sortList[jj]; 287 ii= jj; 288 jj <<= 1; 289 } 290 else 291 break; 292 } 293 sortList[ii]= holdArc; 294 } 295 sortList++; 296 297 if (backwardList) 298 delete [] backwardList; 299 backwardList= sortList; 300 sortRevNum= numArc; 301 302 /* Now carry out some checks 303 */ 304 assert(CheckSortReverse()); 305 306 return; 307 } 308 309 int SubGraph::FindToIndex (int element) 310 { 311 int rix, rix_low, rix_high, direction; 312 313 rix_low= -1; 314 rix_high= sortRevNum; 315 while ((rix_high - rix_low) > 1) { 316 rix= (rix_high + rix_low) >> 1; 317 direction= element - arc[backwardList[rix]]->GetToId(); 318 if (direction < 0) 319 rix_high= rix; 320 else if (direction > 0) 321 rix_low= rix; 322 else { 323 assert (arc[backwardList[rix]]->GetToId() == element); 324 while (rix > 0 && arc[backwardList[rix-1]]->GetToId() == element) 325 rix--; 326 assert (arc[backwardList[rix]]->GetToId() == element); 327 assert (rix < sortRevNum); 328 return (rix); 329 } 330 } 331 return (-1); 332 } 333 334 void SubGraph::UpdateSortForLanguage () 335 { 336 SortLanguageAtIndices (sortNum, numArc); 337 } 338 339 bool SubGraph::CheckSort () 340 { 341 for (int ii= 1; ii < numArc; ii++) { 342 if (ARC_COMPARE (forwardList[ii-1], forwardList[ii]) > 0) 343 return false; 344 } 345 return true; 346 } 347 348 bool SubGraph::CheckSortReverse () 349 { 350 for (int ii= 1; ii < numArc; ii++) { 351 if (ARC_COMPARE_REV (backwardList[ii-1], backwardList[ii]) > 0) { 352 printf ("Failed at %d\n", ii); 353 return false; 354 } 355 } 356 return true; 357 } 358 359 void SubGraph::ClearDuplicateArcs () 360 { 361 int currId; 362 363 SortLanguage(); 364 currId= 0; 365 for (int ii= 1; ii < numArc; ii++) { 366 if (arc[forwardList[ii]]->GetInput() != DISCARD_LABEL) 367 if (ARC_COMPARE (forwardList[currId], forwardList[ii]) == 0) 368 arc[forwardList[ii]]->AssignInput (DISCARD_LABEL); 369 else 370 currId= ii; 371 } 372 return; 373 } 374 375 void SubGraph::RenumberNodes () 376 { 377 int ii, id, count; 378 379 UpdateVertexCount (0); 380 if (numVertex > 0) { 381 int *mapList= new int [numVertex]; 382 for (ii= 0; ii < numVertex; ii++) 383 mapList[ii]= -1; 384 385 for (ii= 0; ii < numArc; ii++) { 386 id= arc[ii]->GetFromId(); 387 mapList[id]= 1; 388 id= arc[ii]->GetToId(); 389 if (id >= 0) 390 mapList[id]= 1; 391 } 392 393 count= 0; 394 for (ii= 0; ii < numVertex; ii++) 395 if (mapList[ii] > 0) { 396 mapList[ii]= count; 397 count++; 398 } 399 400 for (ii= 0; ii < numArc; ii++) { 401 id= arc[ii]->GetFromId(); 402 arc[ii]->AssignFromId(mapList[id]); 403 id= arc[ii]->GetToId(); 404 if (id >= 0) 405 arc[ii]->AssignToId(mapList[id]); 406 } 407 startId= mapList[startId]; 408 if (lastId >= 0) 409 lastId= mapList[lastId]; 410 delete [] mapList; 411 } 412 else { 413 startId= 0; 414 lastId= -1; 415 endId= -1; 416 } 417 return; 418 } 419 420 void SubGraph::RemoveDuplicatesAtNode (int rixBegin, int rixEnd) 421 // Works only within one node/vertex 422 { 423 int rix, lastRix; 424 bool needSort; 425 426 SortLanguageAtSortIndices (rixBegin, rixEnd); 427 428 // Check for duplicate transitions 429 needSort= false; 430 lastRix= rixBegin; 431 for (rix= rixBegin+1; rix < rixEnd; rix++) { 432 assert (arc[forwardList[lastRix]]->GetFromId() == arc[forwardList[rix]]->GetFromId()); 433 if (ARC_COMPARE (forwardList[lastRix], forwardList[rix]) == 0) { 434 arc[forwardList[rix]]->AssignInput (DISCARD_LABEL); 435 needSort= true; 436 } 437 else 438 lastRix= rix; 439 } 440 441 // Resort 442 if (needSort) 443 SortLanguageAtSortIndices (rixBegin, rixEnd); 444 445 return; 446 } 447 448 void SubGraph::SortLanguageForMin () 449 { 450 int *sortList; 451 452 if (numArc <= 1) { 453 sortList= new int [numArc+2]; 454 sortList[0]= 0; 455 if (forwardList) 456 delete [] forwardList; 457 forwardList= sortList; 458 sortNum= numArc; 459 return; 460 } 461 SortLanguageAtIndicesForMin (-1, -1); 462 return; 463 } 464 465 void SubGraph::SortLanguageAtIndicesForMin (int begIx, int endIx) 466 { 467 int ii, jj, hired, retd; 468 int holdArc, *sortList; 469 470 if (begIx < 0) 471 begIx= 0; 472 if (endIx < 0) 473 endIx= numArc; 474 475 if (endIx <= begIx) 476 return; 477 478 sortList= new int [numArc+2]; 479 for (ii= 0; ii < sortNum && ii < numArc; ii++) 480 sortList[ii]= forwardList[ii]; 481 for (ii= begIx; ii < endIx; ii++) 482 sortList[ii]= ii; 483 sortList--; 484 485 /* Hiring 486 */ 487 hired= (numArc >> 1)+1; 488 while (hired-- > 1) { 489 holdArc= sortList[hired]; 490 ii= hired; 491 jj= hired << 1; 492 while (jj <= numArc) { 493 if (jj < numArc && ARC_COMPARE_MIN (sortList[jj], sortList[jj+1]) <= 0 ) 494 jj++; 495 if (ARC_COMPARE_MIN (holdArc, sortList[jj]) < 0) { 496 sortList[ii]= sortList[jj]; 497 ii= jj; 498 jj <<= 1; 499 } 500 else 501 break; 502 } 503 sortList[ii]= holdArc; 504 } 505 506 /* Retiring 507 */ 508 retd= numArc; 509 while (retd > 0) { 510 holdArc= sortList[retd]; 511 sortList[retd]= sortList[1]; 512 if (--retd == 1) { 513 sortList[1]= holdArc; 514 break; 515 } 516 ii= 1; 517 jj= 2; 518 while (jj <= retd) { 519 if (jj < retd && ARC_COMPARE_MIN (sortList[jj], sortList[jj+1]) <= 0) 520 jj++; 521 if (ARC_COMPARE_MIN (holdArc, sortList[jj]) < 0) { 522 sortList[ii]= sortList[jj]; 523 ii= jj; 524 jj <<= 1; 525 } 526 else 527 break; 528 } 529 sortList[ii]= holdArc; 530 } 531 sortList++; 532 533 if (forwardList) 534 delete [] forwardList; 535 forwardList= sortList; 536 sortNum= numArc; 537 538 /* Now carry out some checks 539 */ 540 int checkSort = CheckSort(); 541 if(checkSort == 0) { 542 // printf("assert(0) in SubGraph::CheckSort %d\n", checkSort); 543 // hmm .. this seems harmless but ...! 544 // assert(checkSort); 545 } 546 547 return; 548 } 549 550
