1/* FILE:		sub_base.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
29SubGraph::SubGraph (SubGraph *baseG)
30{
31    int count= strlen(baseG->title);
32    title= new char [count+1];
33    strcpy (title, baseG->title);
34    ruleId= baseG->ruleId;
35    arc= new NUANArc * [BLKSIZE];
36    popOp= 0;
37    numVertex= baseG->numVertex;
38    lastScope= SCOPE_ROOT;
39    startId= baseG->startId;
40    lastId= baseG->lastId;
41    endId= baseG->endId;
42    forwardList= 0;
43    backwardList= 0;
44    sortNum= 0;
45    numArc= 0;
46    CopyFastArcs (baseG, 0, baseG->numArc, 0, -1, -1, -1, -1);
47    UpdateVertexCount (0);
48
49    return;
50}
51
52int SubGraph::NewVertexId ()
53{
54    return (numVertex++);
55}
56
57void SubGraph::AllocateSpaceForArc ()
58{
59    if (numArc == 0) {
60        arc= new NUANArc * [BLKSIZE];
61    }
62    if (numArc%BLKSIZE == 0) {
63        NUANArc **new_arc= new NUANArc * [numArc+BLKSIZE];
64        for (int ii= 0; ii < numArc; ii++)
65            new_arc[ii]= arc[ii];
66        delete [] arc;
67        arc= new_arc;
68    }
69}
70
71NUANArc *SubGraph::CreateArc (int iLabel, int oLabel, int from, int to)
72{
73    assert (!(iLabel == NONE_LABEL && from == to));
74    AllocateSpaceForArc ();
75    NUANArc *arc_one= new NUANArc (iLabel, oLabel, from, to);
76    arc[numArc]= arc_one;
77    numArc++;
78    return arc_one;
79}
80
81NUANArc *SubGraph::InheritArc (NUANArc *arcBase, int id)
82{
83    AllocateSpaceForArc ();
84    NUANArc *arc_one= new NUANArc (arcBase);
85    arc_one->AssignFromId (id);
86    arc[numArc]= arc_one;
87    numArc++;
88    return arc_one;
89}
90
91NUANArc *SubGraph::InheritReverseArc (NUANArc *arcBase, int id)
92{
93    AllocateSpaceForArc ();
94    NUANArc *arc_one= new NUANArc (arcBase);
95    arc_one->AssignToId (id);
96    arc[numArc]= arc_one;
97    numArc++;
98    return arc_one;
99}
100
101NUANArc *SubGraph::InheritReverseArcWithTag (NUANArc *arcBase, int id, int tagId)
102{
103    AllocateSpaceForArc ();
104    NUANArc *arc_one= new NUANArc (arcBase);
105    arc_one->AssignToId (id);
106    arc_one->AssignOutput (tagId);
107    arc[numArc]= arc_one;
108    numArc++;
109    return arc_one;
110}
111
112NUANArc *SubGraph::CreateCopyWithOutput (NUANArc *arcBase, int id)
113{
114    AllocateSpaceForArc ();
115    NUANArc *arc_one= new NUANArc (arcBase);
116    arc_one->AssignOutput (id);
117    arc[numArc]= arc_one;
118    numArc++;
119    return arc_one;
120}
121
122void SubGraph::CopyFastArcs (SubGraph *subG, int startLoc, int endLoc, int offset, int headId, int newHeadId, int tailId, int newTailId)
123{
124    NUANArc *arc_one;
125
126    for (int ii= startLoc; ii < endLoc; ii++) {
127        if (numArc%BLKSIZE == 0) {
128            NUANArc **new_arc= new NUANArc * [numArc+BLKSIZE];
129            for (int ii= 0; ii < numArc; ii++)
130                new_arc[ii]= arc[ii];
131            delete [] arc;
132            arc= new_arc;
133        }
134        arc_one= new NUANArc (subG->arc[ii], offset, headId, newHeadId, tailId, newTailId);
135        arc[numArc]= arc_one;
136        numArc++;
137    }
138    return;
139}
140
141void SubGraph::Print ()
142{
143    int loc;
144
145    printf ("Graph %s (%d %d)\n", title, startId, lastId);
146    for (int ii= 0; ii < numArc; ii++) {
147        loc= forwardList[ii];
148        // loc= ii;
149        arc[loc]->Print();
150    }
151    return;
152}
153
154void SubGraph::PrintText ()
155{
156    int loc;
157
158    printf ("Graph %s (%d %d)\n", title, startId, lastId);
159    for (int ii= 0; ii < numArc; ii++) {
160        loc= forwardList[ii];
161        // loc= ii;
162        arc[loc]->PrintText();
163    }
164    return;
165}
166
167void SubGraph::ReverseDepthOnTerminal (int *depthMap)
168{
169    for (int ii= 0; ii < numArc; ii++)
170        if (arc[ii]->GetInput() == TERMINAL_LABEL)
171            ReverseDepthData (arc[ii]->GetFromId(), depthMap, 1);
172        return;
173}
174
175void SubGraph::ReverseDepthData (int startId, int *depthMap, int depth)
176{
177    int rix, nextId, nextInp;
178
179    if (depthMap[startId] > depth)
180        depthMap[startId]= depth;
181    else
182        return;
183    rix= FindToIndex (startId);
184    if (rix < 0)
185        return;
186    while (rix < numArc && arc[backwardList[rix]]->GetToId() == startId) {
187        nextId= arc[backwardList[rix]]->GetFromId();
188        nextInp= arc[backwardList[rix]]->GetInput();
189        if (nextId >= 0 && nextInp != DISCARD_LABEL)
190            ReverseDepthData (nextId, depthMap, depth+1);
191        rix++;
192    }
193    return;
194}
195
196void SubGraph::ForwardDepthData (int startId, int *depthMap, int depth)
197{
198    int rix, nextId, nextInp;
199
200    if (depthMap[startId] > depth)
201        depthMap[startId]= depth;
202    else
203        return;
204    rix= FindFromIndex (startId);
205    if (rix < 0)
206        return;
207    while (rix < numArc && arc[forwardList[rix]]->GetFromId() == startId) {
208        nextId= arc[forwardList[rix]]->GetToId();
209        nextInp= arc[forwardList[rix]]->GetInput();
210        if (nextId >= 0 && nextInp != DISCARD_LABEL)
211            ForwardDepthData (nextId, depthMap, depth+1);
212        rix++;
213    }
214    return;
215}
216
217void SubGraph::RemoveUnvisitedArcs (int initialId, int finalId)
218{
219    int ii;
220    int *forwardDepth= new int [numVertex];
221    int *reverseDepth= new int [numVertex];
222
223    for (ii= 0; ii < numVertex; ii++)
224        forwardDepth[ii]= reverseDepth[ii]= MAXNUM;     //  TODO: review
225    SortLanguage();
226    SortLanguageReverse();
227
228    ForwardDepthData (initialId, forwardDepth, 1);
229    if (finalId >= 0)
230        ReverseDepthData (finalId, reverseDepth, 1);
231    ReverseDepthOnTerminal (reverseDepth);
232
233    for (ii= 0; ii < numVertex; ii++) {
234        if (forwardDepth[ii] == MAXNUM)
235            forwardDepth[ii]= -1;
236        if (reverseDepth[ii] == MAXNUM)
237            reverseDepth[ii]= -1;
238    }
239    RemoveMarkedNodes (forwardDepth, reverseDepth);
240    delete [] forwardDepth;
241    delete [] reverseDepth;
242    return;
243}
244
245void SubGraph::RemoveMarkedNodes (int *forwardDepth, int *reverseDepth)
246{
247    int ii, currId, incId, outId;
248
249    currId= 0;
250    for (ii= 0; ii < numArc; ii++) {
251        incId= arc[ii]->GetFromId();
252        outId= arc[ii]->GetToId();
253        assert (outId == DISCARD_LABEL || outId == TERMINAL_LABEL || outId >= 0);
254        if (incId != DISCARD_LABEL && outId != DISCARD_LABEL
255            && arc[ii]->GetInput() != DISCARD_LABEL
256            && forwardDepth[incId] > 0
257            && (outId == TERMINAL_LABEL || reverseDepth[outId] > 0)) {
258            arc[currId]= arc[ii];
259            currId++;
260        }
261        else
262            delete arc[ii];
263    }
264    for (ii= currId; ii < numArc; ii++)
265	arc[ii]= 0;
266    numArc= currId;
267    return;
268}
269
270void SubGraph::RemoveDiscardedArcs ()
271{
272    int ii, currId, outId, inpId;
273
274    currId= 0;
275    for (ii= 0; ii < numArc; ii++) {
276        outId= arc[ii]->GetToId();
277        inpId= arc[ii]->GetInput();
278        if (outId != DISCARD_LABEL && inpId != DISCARD_LABEL) {
279            arc[currId]= arc[ii];
280            currId++;
281        }
282        else
283            delete arc[ii];
284    }
285    for (ii= currId; ii < numArc; ii++)
286	arc[ii]= 0;
287    numArc= currId;
288    return;
289}
290
291void SubGraph::MapGraphVertices (int *equivMap)
292{
293    int ii, fromId, toId;
294
295    for (ii= 0; ii < numArc; ii++) {
296        fromId= arc[ii]->GetFromId();
297        if (fromId >= 0)
298            if (equivMap[fromId] != fromId)
299                arc[ii]->AssignInput (DISCARD_LABEL);
300        toId= arc[ii]->GetToId();
301        if (toId >= 0)
302            if (equivMap[toId] != toId)
303                arc[ii]->AssignToId (equivMap[toId]);
304    }
305    return;
306}
307
308void SubGraph::DebugPrintDirective (char *dirrData)
309{
310    for (int ii= 0; ii < (popOp/7); ii++)
311        printf ("  ");
312    printf ("%s\n", dirrData);
313    return;
314}
315
316void SubGraph::DebugPrintLabel (int labId)
317{
318    for (int ii= 0; ii <= (popOp/7); ii++)
319        printf ("  ");
320    printf ("%d\n", labId);
321    return;
322}
323
324void SubGraph::ClearLabelledConnections (int labItem)
325{
326    for (int ii= 0; ii < numArc; ii++) {
327        if (arc[ii]->GetInput() == labItem)
328            arc[ii]->AssignToId (DISCARD_LABEL);
329    }
330    return;
331}
332
333void SubGraph::ClearRuleIds ()
334{
335    for (int ii= 0; ii < numArc; ii++) {
336        if (arc[ii]->GetInput() < 0 && arc[ii]->GetInput() > NONE_LABEL)
337            arc[ii]->AssignToId (DISCARD_LABEL);
338    }
339    return;
340}
341
342void SubGraph::ClearOutputs ()
343{
344    for (int ii= 0; ii < numArc; ii++)
345        arc[ii]->AssignOutput (NONE_LABEL);
346    return;
347}
348