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 } 373 return; 374 } 375 376 void SubGraph::RenumberNodes () 377 { 378 int ii, id, count; 379 380 UpdateVertexCount (0); 381 if (numVertex > 0) { 382 int *mapList= new int [numVertex]; 383 for (ii= 0; ii < numVertex; ii++) 384 mapList[ii]= -1; 385 386 for (ii= 0; ii < numArc; ii++) { 387 id= arc[ii]->GetFromId(); 388 mapList[id]= 1; 389 id= arc[ii]->GetToId(); 390 if (id >= 0) 391 mapList[id]= 1; 392 } 393 394 count= 0; 395 for (ii= 0; ii < numVertex; ii++) 396 if (mapList[ii] > 0) { 397 mapList[ii]= count; 398 count++; 399 } 400 401 for (ii= 0; ii < numArc; ii++) { 402 id= arc[ii]->GetFromId(); 403 arc[ii]->AssignFromId(mapList[id]); 404 id= arc[ii]->GetToId(); 405 if (id >= 0) 406 arc[ii]->AssignToId(mapList[id]); 407 } 408 startId= mapList[startId]; 409 if (lastId >= 0) 410 lastId= mapList[lastId]; 411 delete [] mapList; 412 } 413 else { 414 startId= 0; 415 lastId= -1; 416 endId= -1; 417 } 418 return; 419 } 420 421 void SubGraph::RemoveDuplicatesAtNode (int rixBegin, int rixEnd) 422 // Works only within one node/vertex 423 { 424 int rix, lastRix; 425 bool needSort; 426 427 SortLanguageAtSortIndices (rixBegin, rixEnd); 428 429 // Check for duplicate transitions 430 needSort= false; 431 lastRix= rixBegin; 432 for (rix= rixBegin+1; rix < rixEnd; rix++) { 433 assert (arc[forwardList[lastRix]]->GetFromId() == arc[forwardList[rix]]->GetFromId()); 434 if (ARC_COMPARE (forwardList[lastRix], forwardList[rix]) == 0) { 435 arc[forwardList[rix]]->AssignInput (DISCARD_LABEL); 436 needSort= true; 437 } 438 else 439 lastRix= rix; 440 } 441 442 // Resort 443 if (needSort) 444 SortLanguageAtSortIndices (rixBegin, rixEnd); 445 446 return; 447 } 448 449 void SubGraph::SortLanguageForMin () 450 { 451 int *sortList; 452 453 if (numArc <= 1) { 454 sortList= new int [numArc+2]; 455 sortList[0]= 0; 456 if (forwardList) 457 delete [] forwardList; 458 forwardList= sortList; 459 sortNum= numArc; 460 return; 461 } 462 SortLanguageAtIndicesForMin (-1, -1); 463 return; 464 } 465 466 void SubGraph::SortLanguageAtIndicesForMin (int begIx, int endIx) 467 { 468 int ii, jj, hired, retd; 469 int holdArc, *sortList; 470 471 if (begIx < 0) 472 begIx= 0; 473 if (endIx < 0) 474 endIx= numArc; 475 476 if (endIx <= begIx) 477 return; 478 479 sortList= new int [numArc+2]; 480 for (ii= 0; ii < sortNum && ii < numArc; ii++) 481 sortList[ii]= forwardList[ii]; 482 for (ii= begIx; ii < endIx; ii++) 483 sortList[ii]= ii; 484 sortList--; 485 486 /* Hiring 487 */ 488 hired= (numArc >> 1)+1; 489 while (hired-- > 1) { 490 holdArc= sortList[hired]; 491 ii= hired; 492 jj= hired << 1; 493 while (jj <= numArc) { 494 if (jj < numArc && ARC_COMPARE_MIN (sortList[jj], sortList[jj+1]) <= 0 ) 495 jj++; 496 if (ARC_COMPARE_MIN (holdArc, sortList[jj]) < 0) { 497 sortList[ii]= sortList[jj]; 498 ii= jj; 499 jj <<= 1; 500 } 501 else 502 break; 503 } 504 sortList[ii]= holdArc; 505 } 506 507 /* Retiring 508 */ 509 retd= numArc; 510 while (retd > 0) { 511 holdArc= sortList[retd]; 512 sortList[retd]= sortList[1]; 513 if (--retd == 1) { 514 sortList[1]= holdArc; 515 break; 516 } 517 ii= 1; 518 jj= 2; 519 while (jj <= retd) { 520 if (jj < retd && ARC_COMPARE_MIN (sortList[jj], sortList[jj+1]) <= 0) 521 jj++; 522 if (ARC_COMPARE_MIN (holdArc, sortList[jj]) < 0) { 523 sortList[ii]= sortList[jj]; 524 ii= jj; 525 jj <<= 1; 526 } 527 else 528 break; 529 } 530 sortList[ii]= holdArc; 531 } 532 sortList++; 533 534 if (forwardList) 535 delete [] forwardList; 536 forwardList= sortList; 537 sortNum= numArc; 538 539 /* Now carry out some checks 540 */ 541 int checkSort = CheckSort(); 542 if(checkSort == 0) { 543 // printf("assert(0) in SubGraph::CheckSort %d\n", checkSort); 544 // hmm .. this seems harmless but ...! 545 // assert(checkSort); 546 } 547 548 return; 549 } 550 551
