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
SubGraph(SubGraph * baseG)29 SubGraph::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
NewVertexId()52 int SubGraph::NewVertexId ()
53 {
54 return (numVertex++);
55 }
56
AllocateSpaceForArc()57 void 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
CreateArc(int iLabel,int oLabel,int from,int to)71 NUANArc *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
InheritArc(NUANArc * arcBase,int id)81 NUANArc *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
InheritReverseArc(NUANArc * arcBase,int id)91 NUANArc *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
InheritReverseArcWithTag(NUANArc * arcBase,int id,int tagId)101 NUANArc *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
CreateCopyWithOutput(NUANArc * arcBase,int id)112 NUANArc *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
CopyFastArcs(SubGraph * subG,int startLoc,int endLoc,int offset,int headId,int newHeadId,int tailId,int newTailId)122 void 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
Print()141 void 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
PrintText()154 void 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
ReverseDepthOnTerminal(int * depthMap)167 void 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
ReverseDepthData(int startId,int * depthMap,int depth)175 void 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
ForwardDepthData(int startId,int * depthMap,int depth)196 void 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
RemoveUnvisitedArcs(int initialId,int finalId)217 void 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
RemoveMarkedNodes(int * forwardDepth,int * reverseDepth)245 void 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
RemoveDiscardedArcs()270 void 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
MapGraphVertices(int * equivMap)291 void 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
DebugPrintDirective(char * dirrData)308 void 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
DebugPrintLabel(int labId)316 void 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
ClearLabelledConnections(int labItem)324 void 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
ClearRuleIds()333 void 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
ClearOutputs()342 void SubGraph::ClearOutputs ()
343 {
344 for (int ii= 0; ii < numArc; ii++)
345 arc[ii]->AssignOutput (NONE_LABEL);
346 return;
347 }
348