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    }
373    return;
374}
375
376void 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
421void 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
449void 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
466void 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