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 return;
373 }
374
RenumberNodes()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
RemoveDuplicatesAtNode(int rixBegin,int rixEnd)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
SortLanguageForMin()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
SortLanguageAtIndicesForMin(int begIx,int endIx)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