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
34void 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
51void 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
131void 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
204int 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
229void 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
309int 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
334void SubGraph::UpdateSortForLanguage ()
335{
336    SortLanguageAtIndices (sortNum, numArc);
337}
338
339bool 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
348bool 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
359void 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
375void 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
420void 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
448void 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
465void 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