1 /*
2 ------------------------------------------------------------------------------
3 BOUND.C
4 By Bob Jenkins, in association with his Masters Thesis
5 Routines dealing with boundary manipulations of weaves
6 Public Domain
7 ------------------------------------------------------------------------------
8 */
9 #include <stdlib.h>
10 #include <gc.h>
11
12 #include "standard.h"
13 #include "order.h"
14 #include "control.h"
15 #include "bound.h"
16
17 /*
18 ------------------------------------------------------------------------------
19 B_MANIP computes values of the global boundary variables.
20 A step is either adding a crossing, adding a crossing and removing a pair of
21 boundary crossings, or just removing a pair of boundary crossings.
22 ------------------------------------------------------------------------------
23 */
24 word list[BIGWEAVE]; /* description of first new weave */
25 word list2[BIGWEAVE]; /* description of second, if needed */
26 word old_going_in[BIGWEAVE];/* Was *i* an input? *old_going_in[i]*. */
27 word going_in[BIGWEAVE]; /* Will *i* be an input? *going_in[i]*. */
28 word map[BIGWEAVE]; /* i of old weave becomes map[i] of new weave */
29 word first; /* first boundary crossing to remove */
30 word second; /* second boundary crossing to remove */
31 word right; /* Is the crossing being added be righthanded? */
32 word oldcross; /* number of boundary crossings in the old weave */
33 word newcross; /* number of boundary crossings in each new weave */
34 word oldin; /* number of inputs to the old weave */
35 word newin; /* number of inputs to the new weave */
36
b_manip(weave * oldweaves)37 void b_manip(weave *oldweaves)
38 {
39 word i, j, k;
40 ub4 boundary[2];
41
42 oldcross = plan.oldn; /* number of original boundary crossings */
43 oldin = oldcross/2; /* number of original inputs */
44 newcross = plan.newn; /* number of boundary crossings in resulting weaves */
45 newin = newcross/2; /* " inputs " */
46
47 /*--------------------------------------------------- Compute old_going_in */
48 for (i = 0; !oldweaves[i].tag.len; i++) ; /* find a defined weave */
49 boundary[0] = oldweaves[i].boundary[0];
50 boundary[1] = oldweaves[i].boundary[1];
51 for (i = 0; i < oldcross; i++)
52 old_going_in[i] = 1; /* pretend all crossings are inputs */
53 for (i = 0; i < oldin; i++)
54 {
55 k = (i < 6) ? 0 : 1;
56 if (old_going_in[(boundary[k] & 0x1f)] == 0) {
57 printf("cannot have both ends of a string be an output\n");
58 }
59 old_going_in[(boundary[k] & 0x1f)] = 0; /* unmark the outputs */
60 boundary[k] >>= 5;
61 }
62 right = plan.right;
63 if (plan.which != -1)
64 {
65 for (i = 0; i < oldcross; ++i)
66 {
67 if (old_going_in[i] != plan.going_in[i]) {
68 printf("going_in is messed up\n");
69 break;
70 }
71 }
72 }
73
74 /*--------------------------- Set first and second, if they need to be set */
75 first = plan.r0[0];
76 second = plan.r1[0];
77 if (plan.reductions && plan.which != -1) /* crossing added, pair removed */
78 {
79 if (first > plan.which+1) --first;
80 if (second > plan.which+1) --second;
81 if (first > plan.which) --first;
82 if (second > plan.which) --second;
83 }
84 else ; /* crossing added, no pair removed */
85
86 /*---------------------------------------------------------------- Set map */
87 if (plan.reductions == 0)
88 {
89 for (i = 0, j = 0; i < oldcross+2; ++i)
90 if ((i != plan.which) && (i != plan.which+2)) map[j++] = i;
91 }
92 else if (plan.which == (-1))
93 {
94 for (i = 0, j = 0; j < oldcross; ++j)
95 if ((j != plan.r0[0]) && (j != plan.r1[0])) map[j] = i++;
96 }
97 else if (plan.r0[0] > plan.r1[0])
98 {
99 for (i = 0; i < oldcross; i++) map[i] = i;
100 map[first] = (second);
101 map[second] = (first);
102 }
103 else if (plan.which == 0)
104 {
105 for (i = 0; i < oldcross; i++) map[i] = i+1;
106 map[0] = 0;
107 map[oldcross-1] = 1;
108 }
109 else
110 {
111 for (i = 0; i < oldcross; i++) map[i] = i-1;
112 map[0] = oldcross-2;
113 map[oldcross-1] = oldcross-1;
114 }
115
116 /*----------------------------------------------------------- Set going_in */
117 if (plan.which != (-1))
118 {
119 for (i = 0; i < oldcross; i++)
120 {
121 going_in[map[i]] = old_going_in[i];
122 }
123 }
124 else
125 {
126 for (i = 0; i < oldcross; i++)
127 {
128 if ((i != first) && (i != second))
129 {
130 going_in[map[i]] = old_going_in[i];
131 }
132 }
133 }
134
135 if (plan.reductions == 0)
136 {
137 going_in[plan.which] = plan.prev;
138 going_in[plan.which+2] = !plan.prev;
139 }
140 }
141
142
143
144
145 /*
146 ------------------------------------------------------------------------------
147 B_NO_PAIRS adds a single crossing to a single weave.
148 Either the crossing is correct, in which case *one* will be set, or it is
149 wrong. In this case no more than two weaves are needed, so *two* will be set.
150 ------------------------------------------------------------------------------
151 */
b_no_pairs(word * list,word * list2,word * one,word * two)152 void b_no_pairs(word *list, /* list of original inputs/outputs, modified by this routine */
153 word *list2, /* inputs/outputs of the second new weave */
154 word *one, /* will one new weave suffice? */
155 word *two) /* will two new weaves suffice? */
156 {
157 word i,
158 a,
159 b,
160 c;
161
162
163 /*-------------------------------------------------- Make the new boundary */
164 for (i = oldcross; --i >= 0;) list[map[i]] = map[list[i]];
165 a = plan.which+1;
166 list[a-1] = a+1;
167 list[a+1] = a-1;
168
169 /*------------------------- Decide if the crossing needs to be operated on */
170 c = a-1;
171 b_right(list, going_in, c, a, i);
172 *one = (i == right);
173 *two = !*one;
174 if (*two)
175 {
176 for (i = newcross; --i >= 0;) list2[i] = list[i];
177 b = (plan.prev == going_in[a]) ? a-1 : a+1;
178 c = (plan.prev == going_in[a]) ? a+1 : a-1;
179 list2[list2[a]] = b;
180 list2[b] = list2[a];
181 list2[a] = c;
182 list2[c] = a;
183 }
184 }
185
186
187
188 /*
189 ------------------------------------------------------------------------------
190 B_ONE_PAIR handles adding one crossing and removing one pair of boundary
191 crossings. This may require replacing the original weave with one, two, or
192 more new weaves. If more than two are needed, do not set *one* or *two*.
193 ------------------------------------------------------------------------------
194 */
b_one_pair(list,list2,one,two)195 void b_one_pair(list, list2, one, two)
196 word *list; /* list of original inputs/outputs, modified by this routine */
197 word *list2; /* inputs/outputs of the second new weave */
198 word *one; /* will one new weave suffice? */
199 word *two; /* will two new weaves suffice? */
200 {
201 word a;
202 word i;
203 word crossed;
204 word shouldBeRight;
205 word temp[BIGWEAVE];
206
207 /*---------------------------------- Check for a couple easy to spot cases */
208 a = plan.which;
209 if ((plan.r0[0] == a+1) || (plan.r1[0] == a+1))
210 { /* A Type I Reidemeister move */
211 *one = 1;
212 return;
213 }
214
215 /*---------------- Handle the cases where the reduction is the 0..n-1 jump */
216 if (plan.r0[0] < plan.r1[0])
217 {
218 if (old_going_in[0] && old_going_in[oldcross-1]) return;
219 crossed = b_cross(first, second, list[first], list[second]);
220 b_right(list, old_going_in, first, second, shouldBeRight);
221 /* werecrossed */
222 if (list[first] == second)
223 {
224 /* A Type I Reidemeister move */
225 for (i = oldcross; --i >= 0; ) temp[map[i]] = list[i];
226 for (i = oldcross; --i >= 0; ) list[i] = map[temp[i]];
227 *one = 1;
228 return;
229 }
230
231 if (old_going_in[first] != old_going_in[second])
232 {
233 /* this may be complicated */
234 return;
235 }
236
237 for (i = oldcross; --i >= 0; ) temp[map[i]] = list[i];
238 for (i = oldcross; --i >= 0; ) list[i] = map[temp[i]];
239 if (!old_going_in[first] && !old_going_in[second] &&
240 (crossed ^ shouldBeRight ^ right))
241 {
242 *two = 1;
243 for (i = 0; i < newcross; i++) list2[i] = list[i];
244 if (plan.which == 0) b_switch(list2, 1, 0, i);
245 else b_switch(list2, newcross-1, newcross-2, i);
246 }
247 else *one = 1;
248 return;
249 }
250
251 /*-------- Handle the cases where the numbers on the boundary are adjacent */
252 if (list[first] == second) /* A Type I Reidemeister move */
253 {
254 *one = 1;
255 return;
256 }
257 crossed = b_cross(first, second, list[first], list[second]);/* werecrossed */
258 b_right(list, old_going_in, first, second, a); /* old crossing righthanded */
259 b_switch(list, first, second, i); /* switch the boundary crossings */
260 b_right(list, going_in, first, second, i); /* new should be righthanded */
261 *one = (((crossed) && (a != right)) || ((!crossed) && (i == right)));
262 if (*two = !*one)
263 {
264 if (old_going_in[first] != old_going_in[second])
265 {
266 *two = 0;
267 b_switch(list, first, second, i);
268 }
269 else
270 {
271 for (i = newcross; --i >= 0; ) list2[i] = list[i];
272 b_switch(list2, first, second, i);
273 }
274 }
275 }
276
277