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
SortLanguage()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
SortLanguageAtIndices(int begIx,int endIx)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
SortLanguageAtSortIndices(int begIx,int endIx)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
FindFromIndex(int element)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
SortLanguageReverse()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
FindToIndex(int element)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
UpdateSortForLanguage()334 void SubGraph::UpdateSortForLanguage ()
335 {
336 SortLanguageAtIndices (sortNum, numArc);
337 }
338
CheckSort()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
CheckSortReverse()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
ClearDuplicateArcs()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
RenumberNodes()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
RemoveDuplicatesAtNode(int rixBegin,int rixEnd)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
SortLanguageForMin()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
SortLanguageAtIndicesForMin(int begIx,int endIx)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