aboutsummaryrefslogtreecommitdiff
path: root/src/alg.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/alg.c')
-rw-r--r--src/alg.c459
1 files changed, 0 insertions, 459 deletions
diff --git a/src/alg.c b/src/alg.c
deleted file mode 100644
index d806178..0000000
--- a/src/alg.c
+++ /dev/null
@@ -1,459 +0,0 @@
1#define ALG_C
2
3#include "alg.h"
4
5static int axis(Move m);
6static void free_alglistnode(AlgListNode *aln);
7static void realloc_alg(Alg *alg, int n);
8
9void
10append_alg(AlgList *l, Alg *alg)
11{
12 AlgListNode *node = malloc(sizeof(AlgListNode));
13 int i;
14
15 node->alg = new_alg("");
16 for (i = 0; i < alg->len; i++)
17 append_move(node->alg, alg->move[i], alg->inv[i]);
18 node->next = NULL;
19
20 if (++l->len == 1)
21 l->first = node;
22 else
23 l->last->next = node;
24 l->last = node;
25}
26
27void
28append_move(Alg *alg, Move m, bool inverse)
29{
30 if (alg->len == alg->allocated)
31 realloc_alg(alg, 2*alg->len);
32
33 alg->move[alg->len] = m;
34 alg->inv [alg->len] = inverse;
35 alg->len++;
36
37 if (inverse)
38 alg->move_inverse[alg->len_inverse++] = m;
39 else
40 alg->move_normal[alg->len_normal++] = m;
41}
42
43static int
44axis(Move m)
45{
46 static int aux[] = {
47 [NULLMOVE] = 0,
48
49 [U] = 1, [U2] = 1, [U3] = 1,
50 [D] = 1, [D2] = 1, [D3] = 1,
51 [Uw] = 1, [Uw2] = 1, [Uw3] = 1,
52 [Dw] = 1, [Dw2] = 1, [Dw3] = 1,
53 [E] = 1, [E2] = 1, [E3] = 1,
54 [y] = 1, [y2] = 1, [y3] = 1,
55
56 [R] = 2, [R2] = 2, [R3] = 2,
57 [L] = 2, [L2] = 2, [L3] = 2,
58 [Rw] = 2, [Rw2] = 2, [Rw3] = 2,
59 [Lw] = 2, [Lw2] = 2, [Lw3] = 2,
60 [M] = 2, [M2] = 2, [M3] = 2,
61 [x] = 2, [x2] = 2, [x3] = 2,
62
63 [F] = 3, [F2] = 3, [F3] = 3,
64 [B] = 3, [B2] = 3, [B3] = 3,
65 [Fw] = 3, [Fw2] = 3, [Fw3] = 3,
66 [Bw] = 3, [Bw2] = 3, [Bw3] = 3,
67 [S] = 3, [S2] = 3, [S3] = 3,
68 [z] = 3, [z2] = 3, [z3] = 3,
69 };
70
71 return aux[m];
72}
73
74Move
75base_move(Move m)
76{
77 if (m == NULLMOVE)
78 return NULLMOVE;
79 else
80 return m - (m-1)%3;
81}
82
83bool
84commute(Move m1, Move m2)
85{
86 return axis(m1) == axis(m2);
87}
88
89int
90compare(Move m1, Move m2)
91{
92 if (!commute(m1, m2))
93 return 0;
94
95 return m1 < m2 ? 1 : -1;
96}
97
98int
99compare_last(Alg *alg, Move m, bool inverse)
100{
101 Move last;
102 int n;
103
104 if (inverse) {
105 n = alg->len_inverse;
106 last = n > 0 ? alg->move_inverse[n-1] : NULLMOVE;
107 } else {
108 n = alg->len_normal;
109 last = n > 0 ? alg->move_normal[n-1] : NULLMOVE;
110 }
111
112 return compare(last, m);
113}
114
115void
116compose_alg(Alg *alg1, Alg *alg2)
117{
118 int i;
119
120 for (i = 0; i < alg2->len; i++)
121 append_move(alg1, alg2->move[i], alg2->inv[i]);
122}
123
124void
125copy_alg(Alg *src, Alg *dst)
126{
127 dst->len = dst->len_normal = dst->len_inverse = 0;
128 compose_alg(dst, src);
129}
130
131void
132free_alg(Alg *alg)
133{
134 free(alg->move);
135 free(alg->inv);
136 free(alg);
137}
138
139void
140free_alglist(AlgList *l)
141{
142 AlgListNode *aux, *i = l->first;
143
144 while (i != NULL) {
145 aux = i->next;
146 free_alglistnode(i);
147 i = aux;
148 }
149 free(l);
150}
151
152static void
153free_alglistnode(AlgListNode *aln)
154{
155 free_alg(aln->alg);
156 free(aln);
157}
158
159Alg *
160inverse_alg(Alg *alg)
161{
162 Alg *ret = new_alg("");
163 int i;
164
165 for (i = alg->len-1; i >= 0; i--)
166 append_move(ret, inverse_move(alg->move[i]), alg->inv[i]);
167
168 return ret;
169}
170
171Move
172inverse_move(Move m)
173{
174 return m == NULLMOVE ? NULLMOVE : m + 2 - 2*((m-1) % 3);
175}
176
177char *
178move_string(Move m)
179{
180 static char move_string_aux[NMOVES][7] = {
181 [NULLMOVE] = "-",
182 [U] = "U", [U2] = "U2", [U3] = "U\'",
183 [D] = "D", [D2] = "D2", [D3] = "D\'",
184 [R] = "R", [R2] = "R2", [R3] = "R\'",
185 [L] = "L", [L2] = "L2", [L3] = "L\'",
186 [F] = "F", [F2] = "F2", [F3] = "F\'",
187 [B] = "B", [B2] = "B2", [B3] = "B\'",
188 [Uw] = "Uw", [Uw2] = "Uw2", [Uw3] = "Uw\'",
189 [Dw] = "Dw", [Dw2] = "Dw2", [Dw3] = "Dw\'",
190 [Rw] = "Rw", [Rw2] = "Rw2", [Rw3] = "Rw\'",
191 [Lw] = "Lw", [Lw2] = "Lw2", [Lw3] = "Lw\'",
192 [Fw] = "Fw", [Fw2] = "Fw2", [Fw3] = "Fw\'",
193 [Bw] = "Bw", [Bw2] = "Bw2", [Bw3] = "Bw\'",
194 [M] = "M", [M2] = "M2", [M3] = "M\'",
195 [E] = "E", [E2] = "E2", [E3] = "E\'",
196 [S] = "S", [S2] = "S2", [S3] = "S\'",
197 [x] = "x", [x2] = "x2", [x3] = "x\'",
198 [y] = "y", [y2] = "y2", [y3] = "y\'",
199 [z] = "z", [z2] = "z2", [z3] = "z\'",
200 };
201
202 return move_string_aux[m];
203}
204
205Alg *
206new_alg(char *str)
207{
208 Alg *alg;
209 int i;
210 bool niss, move_read;
211 Move j, m;
212
213 alg = malloc(sizeof(Alg));
214 alg->allocated = 30;
215 alg->move = malloc(alg->allocated * sizeof(Move));
216 alg->inv = malloc(alg->allocated * sizeof(bool));
217 alg->move_normal = malloc(alg->allocated * sizeof(Move));
218 alg->move_inverse = malloc(alg->allocated * sizeof(Move));
219 alg->len = 0;
220 alg->len_normal = 0;
221 alg->len_inverse = 0;
222
223 niss = false;
224 for (i = 0; str[i]; i++) {
225 if (str[i] == ' ' || str[i] == '\t' || str[i] == '\n')
226 continue;
227
228 if (str[i] == '(' && niss) {
229 fprintf(stderr, "Error reading moves: nested ( )\n");
230 alg->len = alg->len_normal = alg->len_inverse = 0;
231 return alg;
232 }
233
234 if (str[i] == ')' && !niss) {
235 fprintf(stderr, "Error reading moves: unmatched )\n");
236 alg->len = alg->len_normal = alg->len_inverse = 0;
237 return alg;
238 }
239
240 if (str[i] == '(' || str[i] == ')') {
241 niss = !niss;
242 continue;
243 }
244
245 /* Single slash for comments */
246 if (str[i] == '/') {
247 while (str[i] && str[i] != '\n')
248 i++;
249
250 if (!str[i])
251 i--;
252
253 continue;
254 }
255
256 move_read = false;
257 for (j = U; j < NMOVES; j++) {
258 if (str[i] == move_string(j)[0] ||
259 (str[i] >= 'a' && str[i] <= 'z' &&
260 str[i] == move_string(j)[0]-('A'-'a') && j<=B)) {
261 m = j;
262 if (str[i] >= 'a' && str[i] <= 'z' && j<=B) {
263 m += Uw - U;
264 }
265 if (m <= B && str[i+1]=='w') {
266 m += Uw - U;
267 i++;
268 }
269 if (str[i+1]=='2') {
270 m += 1;
271 i++;
272 } else if (str[i+1] == '\'' ||
273 str[i+1] == '3' ||
274 str[i+1] == '`' ) {
275 m += 2;
276 i++;
277 } else if ((int)str[i+1] == -62 &&
278 (int)str[i+2] == -76) {
279 /* Weird apostrophe */
280 m += 2;
281 i += 2;
282 } else if ((int)str[i+1] == -30 &&
283 (int)str[i+2] == -128 &&
284 (int)str[i+3] == -103) {
285 /* MacOS apostrophe */
286 m += 2;
287 i += 3;
288 }
289 append_move(alg, m, niss);
290 move_read = true;
291 break;
292 }
293 }
294
295 if (!move_read) {
296 free(alg);
297 return new_alg("");
298 }
299 }
300
301 if (niss) {
302 fprintf(stderr, "Error reading moves: unmatched (\n");
303 alg->len = alg->len_normal = alg->len_inverse = 0;
304 }
305
306 return alg;
307}
308
309AlgList *
310new_alglist()
311{
312 AlgList *ret = malloc(sizeof(AlgList));
313
314 ret->len = 0;
315 ret->first = NULL;
316 ret->last = NULL;
317
318 return ret;
319}
320
321Alg *
322on_inverse(Alg *alg)
323{
324 Alg *ret = new_alg("");
325 int i;
326
327 for (i = 0; i < alg->len; i++)
328 append_move(ret, alg->move[i], !alg->inv[i]);
329
330 return ret;
331}
332
333void
334print_alg(Alg *alg, bool l)
335{
336 char fill[4];
337 int i;
338 bool niss = false;
339
340 for (i = 0; i < alg->len; i++) {
341 if (!niss && alg->inv[i])
342 strcpy(fill, i == 0 ? "(" : " (");
343 if (niss && !alg->inv[i])
344 strcpy(fill, ") ");
345 if (niss == alg->inv[i])
346 strcpy(fill, i == 0 ? "" : " ");
347
348 printf("%s%s", fill, move_string(alg->move[i]));
349 niss = alg->inv[i];
350 }
351
352 if (niss)
353 printf(")");
354 if (l)
355 printf(" (%d)", alg->len);
356
357 printf("\n");
358}
359
360void
361print_alglist(AlgList *al, bool l)
362{
363 AlgListNode *i;
364
365 for (i = al->first; i != NULL; i = i->next)
366 print_alg(i->alg, l);
367}
368
369static void
370realloc_alg(Alg *alg, int n)
371{
372 if (alg == NULL) {
373 fprintf(stderr, "Error: trying to reallocate NULL alg.\n");
374 return;
375 }
376
377 if (n < alg->len) {
378 fprintf(stderr, "Error: alg too long for reallocation ");
379 fprintf(stderr, "(%d vs %d)\n", alg->len, n);
380 return;
381 }
382
383 if (n > 1000000) {
384 fprintf(stderr, "Warning: very long alg,");
385 fprintf(stderr, "something might go wrong.\n");
386 }
387
388 alg->move = realloc(alg->move, n * sizeof(int));
389 alg->inv = realloc(alg->inv, n * sizeof(int));
390 alg->move_normal = realloc(alg->move_normal, n * sizeof(int));
391 alg->move_inverse = realloc(alg->move_inverse, n * sizeof(int));
392 alg->allocated = n;
393}
394
395void
396remove_last_move(Alg *a)
397{
398 a->len--;
399
400 if (a->inv[a->len])
401 a->len_inverse--;
402 else
403 a->len_normal--;
404}
405
406void
407swapmove(Move *m1, Move *m2)
408{
409 Move aux;
410
411 aux = *m1;
412 *m1 = *m2;
413 *m2 = aux;
414}
415
416char *
417trans_string(Trans t)
418{
419 static char trans_string_aux[NTRANS][20] = {
420 [uf] = "uf", [ur] = "ur", [ub] = "ub", [ul] = "ul",
421 [df] = "df", [dr] = "dr", [db] = "db", [dl] = "dl",
422 [rf] = "rf", [rd] = "rd", [rb] = "rb", [ru] = "ru",
423 [lf] = "lf", [ld] = "ld", [lb] = "lb", [lu] = "lu",
424 [fu] = "fu", [fr] = "fr", [fd] = "fd", [fl] = "fl",
425 [bu] = "bu", [br] = "br", [bd] = "bd", [bl] = "bl",
426
427 [uf_mirror] = "uf*", [ur_mirror] = "ur*",
428 [ub_mirror] = "ub*", [ul_mirror] = "ul*",
429 [df_mirror] = "df*", [dr_mirror] = "dr*",
430 [db_mirror] = "db*", [dl_mirror] = "dl*",
431 [rf_mirror] = "rf*", [rd_mirror] = "rd*",
432 [rb_mirror] = "rb*", [ru_mirror] = "ru*",
433 [lf_mirror] = "lf*", [ld_mirror] = "ld*",
434 [lb_mirror] = "lb*", [lu_mirror] = "lu*",
435 [fu_mirror] = "fu*", [fr_mirror] = "fr*",
436 [fd_mirror] = "fd*", [fl_mirror] = "fl*",
437 [bu_mirror] = "bu*", [br_mirror] = "br*",
438 [bd_mirror] = "bd*", [bl_mirror] = "bl*",
439 };
440
441 return trans_string_aux[t];
442}
443
444Alg *
445unniss(Alg *alg)
446{
447 int i;
448 Alg *ret;
449
450 ret = new_alg("");
451
452 for (i = 0; i < alg->len_normal; i++)
453 append_move(ret, alg->move_normal[i], false);
454
455 for (i = 0; i < alg->len_inverse; i++)
456 append_move(ret, inverse_move(alg->move_inverse[i]), false);
457
458 return ret;
459}

Generated with cgit - Back to sebastiano.tronto.net