1 /* diffreduce.c 1/11/95
2 * 6/8/98 large-scale re-organisation to elimiante externals.
3 * 9/1/98 type of generator changed from char to `gen'
4 * Copied from old automata package and edited.
5 * This file contains the procedure for reducing a word using a
6 * word-difference machine *wd_fsa (defined externally).
7 */
8 #include "defs.h"
9 #include "fsa.h"
10 #include "rws.h"
11 #include "externals.h"
12
13 #define MAXV 65536 /* The maximum number of vertices allowed. */
14
15 /* functions defined in this file */
16
17 /* w is the word to be reduced using the word-difference machine *wd_fsa.
18 * It is assumed that wd_fsa->table->table_data_dptr is set up.
19 * This function allocates its own space.
20 * NOTE: No checks on the validity of the word are carried out.
21 */
diff_reduce(gen * w,reduction_struct * rs_wd)22 int diff_reduce(gen *w, reduction_struct *rs_wd)
23 {
24 int ndiff, ngens, identity, padsymbol, wordlen, ***difftab, gct, *gpref,
25 level, gen1, gen2, diff, diffct = 0, newdiff, olen, nlen, i, j;
26 boolean deqi, donesub, *cf;
27 fsa *wd_fsa = rs_wd->wd_fsa;
28 int maxv = MAXV;
29 struct vertexd {
30 gen genno;
31 int diffno;
32 int sublen;
33 struct vertexd *backptr;
34 } * gptr, *ngptr, *substruc;
35
36 /* vertexd is the structure used to store a vertex in the graph of strings
37 for possible substitution. The components are as follows.
38 backptr - points back to another vertexd, or to zero.
39 genno - the number of the generator at the end of the string.
40 diffno - the word difference number of the string defined by following
41 backptr back to zero (using genno), relative to the corresponding
42 part of the word being reduced.
43 sublen - plus or minus the length of this string. sublen is positive if and
44 only if the string lexicographically precedes the
45 corresponding part of the word being reduced.
46 sublen is put in to save time.
47 Another essential component of a vertexd is its level (i.e. the length of
48 the string got by chasing back to the beginning of the word)
49 but we always calculate this, using
50 the integers defined by gpref. (See below))
51 */
52
53 if (wd_fsa->alphabet->type != PRODUCT || wd_fsa->alphabet->arity != 2) {
54 fprintf(
55 stderr,
56 "Error: diff_reduce must be called with a word-difference machine.\n");
57 return -1;
58 }
59 ndiff = wd_fsa->states->size;
60 ngens = wd_fsa->alphabet->base->size;
61 identity = wd_fsa->initial[1];
62 padsymbol = ngens + 1;
63 wordlen = genstrlen(w);
64 if (wordlen <= 0)
65 return 0;
66 difftab = wd_fsa->table->table_data_dptr;
67 w = w - 1; /* since code below assumes word is from w[1] .. w[wordlen]. */
68
69 tmalloc(cf, boolean, ndiff + 1);
70 /* cf is used as a characteristic function, when constructing a subset of the
71 set D of word differences.
72 */
73
74 tmalloc(gpref, int, wordlen + 1);
75 gct = -1;
76 gpref[0] = -1;
77 /* gpref[n]+1 is the number of vertices that have been defined after reading
78 the first n elements of the word. These vertices are
79 gptr[0],...,gptr[gpref[n]]. We start by allocating space for maxv vertices.
80 */
81
82 tmalloc(gptr, struct vertexd, maxv);
83
84 /* Now we start reading the word. */
85 level = 0;
86 while (++level <= wordlen) {
87 for (i = 1; i <= ndiff; i++)
88 cf[i] = FALSE;
89 /* Read the element of the word at position level. */
90 gen1 = w[level];
91
92 /* The next loop is over the identity and the subset of D defined at the
93 previous level, level-1.
94 */
95 diff = identity;
96 while (1) {
97 deqi = diff == identity;
98 /* First look for a possible substitution of a shorter string */
99 newdiff = dense_dtarget(difftab, gen1, padsymbol, diff);
100 if (newdiff == identity) {
101 /* Make substitution and reduce length of word by 1. */
102 i = level - 1;
103 if (!deqi) {
104 substruc = gptr + diffct;
105 do {
106 w[i] = substruc->genno;
107 substruc = substruc->backptr;
108 i--;
109 } while (substruc);
110 }
111 for (j = level; j < wordlen; j++)
112 w[j] = w[j + 1];
113 w[wordlen] = 0;
114 wordlen--;
115
116 /* Whenever we make a substitution, we have to go back one level more
117 than expected, because of our policy of looking ahead for
118 substitutions that reduce the length by 2.
119 */
120 level = i > 0 ? i - 1 : i;
121 gct = gpref[level];
122 break;
123 }
124 else if (newdiff && level < wordlen) {
125 j = dense_dtarget(difftab, w[level + 1], padsymbol, newdiff);
126 if (j == identity)
127 /* Make substitution and reduce length of word by 2. */
128 {
129 i = level - 1;
130 if (!deqi) {
131 substruc = gptr + diffct;
132 do {
133 w[i] = substruc->genno;
134 substruc = substruc->backptr;
135 i--;
136 } while (substruc);
137 }
138 for (j = level; j < wordlen - 1; j++)
139 w[j] = w[j + 2];
140 w[wordlen - 1] = 0;
141 wordlen -= 2;
142 level = i > 0 ? i - 1 : i;
143 gct = gpref[level];
144 break;
145 }
146 }
147
148 donesub = FALSE;
149 /* Now we loop over the generator that is a candidate for substitution
150 at this point.
151 */
152 for (gen2 = 1; gen2 <= ngens; gen2++) {
153 newdiff = dense_dtarget(difftab, gen1, gen2, diff);
154 if (newdiff) {
155 if (newdiff == identity) {
156 if (deqi) {
157 if (gen2 < gen1) {
158 w[level] = gen2;
159 level = level > 1 ? level - 2 : level - 1;
160 gct = gpref[level];
161 donesub = TRUE;
162 break;
163 }
164 }
165 else if (gptr[diffct].sublen > 0) {
166 /* Make a substitution (by a string of equal length). */
167 w[level] = gen2;
168 i = level - 1;
169 substruc = gptr + diffct;
170 do {
171 w[i] = substruc->genno;
172 substruc = substruc->backptr;
173 i--;
174 } while (substruc);
175 level = i > 0 ? i - 1 : i;
176 gct = gpref[level];
177 donesub = TRUE;
178 break;
179 }
180 }
181 else {
182 if (cf[newdiff])
183 /* We have this word difference stored already, but we will check
184 to see if the current string precedes the existing one.
185 */
186 for (i = gpref[level - 1] + 1;; i++) {
187 substruc = gptr + i;
188 if (substruc->diffno == newdiff) {
189 olen = substruc->sublen;
190 nlen = deqi ? (gen2 < gen1 ? 1 : -1)
191 : (j = (gptr[diffct].sublen)) > 0 ? j + 1 : j - 1;
192 if (nlen > olen) {
193 /* The new string is better than the existing one */
194 substruc->genno = gen2;
195 substruc->sublen = nlen;
196 substruc->backptr = deqi ? 0 : gptr + diffct;
197 }
198 break;
199 }
200 }
201 else
202 /* This is a new word difference at this level, so we define a new
203 vertexd in graph.
204 */
205 {
206 gct++;
207 if (gct >= maxv) {
208 /* We need more space for vertices. Allocate twice the preceding
209 space and copy existing data.
210 */
211 tmalloc(ngptr, struct vertexd, 2 * maxv);
212 if (kbm_print_level >= 3)
213 printf(" #Allocating more space in diff_reduce.\n");
214 for (i = 0; i < maxv; i++) {
215 ngptr[i].genno = gptr[i].genno;
216 ngptr[i].diffno = gptr[i].diffno;
217 ngptr[i].sublen = gptr[i].sublen;
218 substruc = gptr[i].backptr;
219 if (substruc == 0)
220 ngptr[i].backptr = 0;
221 else
222 for (j = i - 1;; j--)
223 if (substruc == gptr + j) {
224 ngptr[i].backptr = ngptr + j;
225 break;
226 }
227 }
228 tfree(gptr);
229 gptr = ngptr;
230 maxv *= 2;
231 }
232 /* Define the new vertexd. */
233 substruc = gptr + gct;
234 nlen = deqi ? (gen2 < gen1 ? 1 : -1)
235 : (j = (gptr[diffct].sublen)) > 0 ? j + 1 : j - 1;
236 substruc->genno = gen2;
237 substruc->diffno = newdiff;
238 substruc->sublen = nlen;
239 substruc->backptr = deqi ? 0 : gptr + diffct;
240 cf[newdiff] = TRUE;
241 }
242 }
243 }
244 } /*End of loop over gen2 */
245
246 if (donesub)
247 break;
248
249 /* Go on to next word difference from previous level. */
250 if (diff == identity) {
251 if (level == 1)
252 break;
253 diffct = gpref[level - 2] + 1;
254 }
255 else
256 diffct++;
257 if (diffct > gpref[level - 1])
258 break;
259 diff = gptr[diffct].diffno;
260 } /* end of loop over word differences at previous level */
261
262 gpref[level] = gct;
263 }
264
265 tfree(gptr);
266 tfree(cf);
267 tfree(gpref);
268 return 0;
269 }
270