1
2 /**************************************************************************
3
4 util1.c
5 Colin Ramsay (cram@itee.uq.edu.au)
6 22 Dec 00
7
8 ADVANCED COSET ENUMERATOR, Version 3.001
9
10 Copyright 2000
11 Centre for Discrete Mathematics and Computing,
12 Department of Mathematics and
13 Department of Computer Science & Electrical Engineering,
14 The University of Queensland, QLD 4072.
15 (http://staff.itee.uq.edu.au/havas)
16
17 These are the utilities for Level 1 of ACE.
18
19 **************************************************************************/
20
21 #include "al1.h"
22
23 #include <ctype.h>
24
25 /******************************************************************
26 void al1_init(void)
27
28 One-off initialisation of the Level 1 stuff, and all lower levels.
29 Note that there is no need to initialise, for example, genal[].
30 ******************************************************************/
31
al1_init(void)32 void al1_init(void)
33 {
34 al0_init();
35
36 workspace = DEFWORK;
37 workmult = 1;
38 costable = NULL;
39 tabsiz = 0;
40
41 currrep = NULL;
42 repsiz = repsp = 0;
43
44 asis = FALSE;
45
46 grpname = NULL;
47 rellst = NULL;
48 trellen = 0;
49
50 ndgen = 0;
51 geninv = NULL;
52 gencol = colgen = NULL;
53 galpha = FALSE;
54 algen[0] = algen[1] = '\0'; /* &algen[1] is printable string */
55
56 subgrpname = NULL;
57 genlst = NULL;
58 tgenlen = 0;
59
60 rfactor1 = cfactor1 = 0;
61 pdsiz1 = dedsiz1 = 0;
62 maxrow1 = ffactor1 = 0;
63 nrinsgp1 = -1;
64 }
65
66 /******************************************************************
67 void al1_dump(Logic allofit)
68
69 Dump out the internals of Level 1 of ACE, working through al1.h
70 more or less in order.
71 ******************************************************************/
72
al1_dump(Logic allofit)73 void al1_dump(Logic allofit)
74 {
75 int i;
76 Wlelt *p;
77
78 fprintf(fop, " #---- %s: Level 1 Dump ----\n", ACE_VER);
79
80 /* workspace, workmult, costable, tabsiz; */
81 fprintf(fop, "workspace=%d workmult=%d", workspace, workmult);
82 if (costable == NULL)
83 { fprintf(fop, " costable=NULL"); }
84 else
85 { fprintf(fop, " costable=non-NULL"); }
86 fprintf(fop, " tabsiz=%d\n", tabsiz);
87
88 /* currrep, repsiz, repsp; */
89 if (currrep == NULL)
90 { fprintf(fop, "currrep=NULL"); }
91 else
92 { fprintf(fop, "currrep=non-NULL"); }
93 fprintf(fop, " repsiz=%d repsp=%d\n", repsiz, repsp);
94
95 /* LLL, asis */
96 fprintf(fop, "LLL=%d, asis=%d\n", LLL, asis);
97
98 /* group: name, generators, geninv */
99 if (grpname == NULL)
100 { fprintf(fop, "grpname=NULL\n"); }
101 else
102 { fprintf(fop, "grpname=%s\n", grpname); }
103
104 if (ndgen == 0)
105 { fprintf(fop, "ndgen=%d\n", ndgen); }
106 else if (galpha)
107 {
108 fprintf(fop, "ndgen=%d galpha=%d algen[]=", ndgen, galpha);
109 for (i = 1; i <= ndgen; i++)
110 { fprintf(fop, "%c", algen[i]); }
111 fprintf(fop, "\n");
112
113 if (allofit)
114 {
115 fprintf(fop, " genal[]=");
116 for (i = 1; i <= 26; i++)
117 { fprintf(fop, "%d ", genal[i]); }
118 fprintf(fop, "\n");
119 }
120 }
121 else
122 { fprintf(fop, "ndgen=%d galpha=%d\n", ndgen, galpha); }
123
124 if (geninv == NULL)
125 { fprintf(fop, "geninv=NULL\n"); }
126 else
127 {
128 fprintf(fop, "geninv[]=");
129 for (i = 1; i <= ndgen; i++)
130 { fprintf(fop, "%d ", geninv[i]); }
131 fprintf(fop, "\n");
132 }
133
134 /* gencol, colgen */
135 if (gencol == NULL)
136 { fprintf(fop, "gencol=NULL\n"); }
137 else
138 {
139 fprintf(fop, "gencol[]=");
140 for (i = -ndgen; i <= -1; i++)
141 { fprintf(fop, "%d ", gencol[ndgen+i]); }
142 fprintf(fop, "x ");
143 for (i = 1; i <= ndgen; i++)
144 { fprintf(fop, "%d ", gencol[ndgen+i]); }
145 fprintf(fop, "\n");
146 }
147 if (colgen == NULL)
148 { fprintf(fop, "colgen=NULL\n"); }
149 else
150 {
151 fprintf(fop, "colgen[]=");
152 for (i = 1; i <= ncol; i++)
153 { fprintf(fop, "%d ", colgen[i]); }
154 fprintf(fop, "\n");
155 }
156
157 /* group relators + trellen */
158 if (rellst == NULL)
159 { fprintf(fop, "rellst=NULL trellen=%d\n", trellen); }
160 else if (rellst->len == 0)
161 { fprintf(fop, "rellst->len=0 trellen=%d\n", trellen); }
162 else
163 {
164 fprintf(fop, "rellst->len=%d trellen=%d\n", rellst->len, trellen);
165 if (allofit)
166 {
167 fprintf(fop, " len exp inv word\n");
168 for (p = rellst->first; ; p = p->next)
169 {
170 fprintf(fop, " %3d %3d %3d ", p->len, p->exp, p->invol);
171 for (i = 1; i <= p->len; i++)
172 { fprintf(fop, "%d ", p->word[i]); }
173 fprintf(fop, "\n");
174
175 if (p == rellst->last)
176 { break; }
177 }
178 }
179 }
180
181 /* subgroup: name */
182 if (subgrpname == NULL)
183 { fprintf(fop, "subgrpname=NULL\n"); }
184 else
185 { fprintf(fop, "subgrpname=%s\n", subgrpname); }
186
187 /* subgroup generators + tgenlen */
188 if (genlst == NULL)
189 { fprintf(fop, "genlst=NULL tgenlen=%d\n", tgenlen); }
190 else if (genlst->len == 0)
191 { fprintf(fop, "genlst->len=0 tgenlen=%d\n", tgenlen); }
192 else
193 {
194 fprintf(fop, "genlst->len=%d tgenlen=%d\n", genlst->len, tgenlen);
195 if (allofit)
196 {
197 fprintf(fop, " len exp inv word\n");
198 for (p = genlst->first; ; p = p->next)
199 {
200 fprintf(fop, " %3d %3d %3d ", p->len, p->exp, p->invol);
201 for (i = 1; i <= p->len; i++)
202 { fprintf(fop, "%d ", p->word[i]); }
203 fprintf(fop, "\n");
204
205 if (p == genlst->last)
206 { break; }
207 }
208 }
209 }
210
211 /* rfactor1, cfactor1 */
212 fprintf(fop, "rfactor1=%d cfactor1=%d\n", rfactor1, cfactor1);
213
214 /* pdsiz1, dedsiz1 */
215 fprintf(fop, "pdsiz1=%d dedsiz1=%d\n", pdsiz1, dedsiz1);
216
217 /* maxrow1, ffactor1, nrinsgp1 */
218 fprintf(fop, "maxrow1=%d ffactor1=%d nrinsgp1=%d\n",
219 maxrow1, ffactor1, nrinsgp1);
220
221 fprintf(fop, " #---------------------------------\n");
222 }
223
224 /******************************************************************
225 void al1_prtdetails(int bits)
226
227 This prints out details of the Level 0 & 1 settings, in a form
228 suitable for reading in by applications using the core enumerator
229 plus its wrapper (eg, ACE Level 2). If bits is 0, then enum, rel,
230 subg & gen are printed. If 1 then *all* of the presentation and
231 the enumerator control settings (this allows the run to be
232 duplicated at a later date). If bits is 2-5, then only enum, rel,
233 subg & gen, respectively, are printed. This routine is really
234 intended for the ACE Level 2 interface, where some items cannot be
235 examined by invoking them with an empty argument. However it is
236 put here (at Level 1), since it is a useful utility for any
237 application.
238
239 If messaging in on, this routine (with bits 1) is called by
240 al1_start() after all the setup & just before the call to
241 al0_enum(). So it shows what the parameters actually were. They
242 may not match what you thought they were, since the Level 1 wrapper
243 (which interfaces between applications (ie, ACE's Level 2
244 interactive interface) and the Level 0 enumerator) trys to prevent
245 errors, and may occasionally ignore or change something. If you
246 call this after changing parameters, but before calling _start(),
247 the values do *not* reflect the new values. If you want to see
248 what the Level 2 parameters are (as opposed to the current Level 0
249 parameters), use the `empty argument' form of the commands, or the
250 "sr;" Level 2 command (which invokes this function with bits
251 false.
252
253 To *exactly* duplicate a run, you may need to duplicate the entire
254 sequence of commands since ACE was started, the execution
255 environment, and use the same executable; but that's a project for
256 some rainy Sunday afternoon sometime in the future. However do
257 note that the allocation of generators to columns may have upset
258 your intended handling of involutions and/or the ordering of the
259 generators; do a (full) Level 0/1 dump to check this, if you care!
260 In particular, the value of asis is the *current* value, which may
261 not match that when the call to _start() which allocated columns &
262 determined which generators will be involutions was made.
263 ******************************************************************/
264
al1_prtdetails(int bits)265 void al1_prtdetails(int bits)
266 {
267 if (bits < 2)
268 { fprintf(fop, " #--- %s: Run Parameters ---\n", ACE_VER); }
269
270 if (bits == 0 || bits == 1 || bits == 2)
271 {
272 if (grpname != NULL)
273 { fprintf(fop, "Group Name: %s;\n", grpname); }
274 else
275 { fprintf(fop, "Group Name: ;\n"); }
276 }
277
278 if (bits == 1)
279 {
280 if (ndgen > 0)
281 {
282 fprintf(fop, "Group Generators: ");
283 if (!galpha)
284 { fprintf(fop, "%d", ndgen); }
285 else
286 { fprintf(fop, "%s", &algen[1]); }
287 fprintf(fop, ";\n");
288 }
289 }
290
291 if (bits == 0 || bits == 1 || bits == 3)
292 {
293 if (rellst != NULL)
294 {
295 fprintf(fop, "Group Relators: ");
296 al1_prtwl(rellst, 16);
297 fprintf(fop, ";\n");
298 }
299 else
300 { fprintf(fop, "Group Relators: ;\n"); }
301 }
302
303 if (bits == 0 || bits == 1 || bits == 4)
304 {
305 if (subgrpname != NULL)
306 { fprintf(fop, "Subgroup Name: %s;\n", subgrpname); }
307 else
308 { fprintf(fop, "Subgroup Name: ;\n"); }
309 }
310
311 if (bits == 0 || bits == 1 || bits == 5)
312 {
313 if (genlst != NULL)
314 {
315 fprintf(fop, "Subgroup Generators: ");
316 al1_prtwl(genlst, 21);
317 fprintf(fop, ";\n");
318 }
319 else
320 { fprintf(fop, "Subgroup Generators: ;\n"); }
321 }
322
323 if (bits == 1)
324 {
325 switch (workmult)
326 {
327 case 1:
328 fprintf(fop, "Wo:%d;", workspace);
329 break;
330 case KILO:
331 fprintf(fop, "Wo:%dK;", workspace);
332 break;
333 case MEGA:
334 fprintf(fop, "Wo:%dM;", workspace);
335 break;
336 case GIGA:
337 fprintf(fop, "Wo:%dG;", workspace);
338 break;
339 }
340 fprintf(fop, " Max:%d;", maxrow);
341 if (msgctrl)
342 {
343 if (msghol)
344 { fprintf(fop, " Mess:-%d;", msgincr); }
345 else
346 { fprintf(fop, " Mess:%d;", msgincr); }
347 }
348 else
349 { fprintf(fop, " Mess:0;"); }
350 fprintf(fop, " Ti:%d; Ho:%d; Loop:%d;\n", tlimit, hlimit, llimit);
351
352 if (asis)
353 { fprintf(fop, "As:1;"); }
354 else
355 { fprintf(fop, "As:0;"); }
356 if (pcomp)
357 { fprintf(fop, " Path:1;"); }
358 else
359 { fprintf(fop, " Path:0;"); }
360 if (rfill)
361 { fprintf(fop, " Row:1;"); }
362 else
363 { fprintf(fop, " Row:0;"); }
364 if (mendel)
365 { fprintf(fop, " Mend:1;"); }
366 else
367 { fprintf(fop, " Mend:0;"); }
368 fprintf(fop, " No:%d; Look:%d; Com:%d;\n", nrinsgp, lahead, comppc);
369
370 /* Note that we printout using the aliases, since we want to know (or,
371 at least, be able to deduce) what style was used. Note that, although
372 ffactor is a float, the Level 1 (& Level 2) interfaces use ffactor1,
373 which is an int. So we need to convert for printout, to maintain the
374 ability to read the output back in. */
375
376 fprintf(fop, "C:%d; R:%d; Fi:%d;", cfactor1, rfactor1, (int)ffactor);
377 fprintf(fop, " PMod:%d; PSiz:%d; DMod:%d;", pdefn, pdsiz, dedmode);
378 fprintf(fop, " DSiz:%d;\n", dedsiz);
379 }
380
381 if (bits < 2)
382 { fprintf(fop, " #---------------------------------\n"); }
383 }
384
385 /******************************************************************
386 void al1_rslt(int rslt)
387
388 Pretty-print the result of a run of al1_start(). If there were no
389 problems at Level 1, this will just be the result of the call to
390 al0_enum(), printed via al0_rslt().
391 ******************************************************************/
392
al1_rslt(int rslt)393 void al1_rslt(int rslt)
394 {
395 if (rslt > -8192)
396 { al0_rslt(rslt); }
397 else
398 {
399 switch(rslt)
400 {
401 case -8194: fprintf(fop, "TABLE TOO SMALL\n"); break;
402 case -8193: fprintf(fop, "MEMORY PROBLEM\n"); break;
403 case -8192: fprintf(fop, "INVALID MODE\n"); break;
404 default: fprintf(fop, "UNKNOWN ERROR (%d)\n", rslt); break;
405 }
406 }
407 }
408
409 /**************************************************************************
410 These are the utilities for the simple list manipulation package used to
411 handle the group's relators & the subgroup's generators. Note that it is
412 up to the caller to catch any errors (flagged by the return values).
413 **************************************************************************/
414
415 /******************************************************************
416 Wlist *al1_newwl(void)
417
418 Creates a new (empty) word list. Returns NULL on failure.
419 ******************************************************************/
420
al1_newwl(void)421 Wlist *al1_newwl(void)
422 {
423 Wlist *p = (Wlist *)malloc(sizeof(Wlist));
424
425 if (p != NULL)
426 {
427 p->len = 0;
428 p->first = p->last = NULL;
429 }
430
431 return(p);
432 }
433
434 /******************************************************************
435 Wlelt *al1_newelt(void)
436
437 Creates a new (empty) word-list element. Returns NULL on failure.
438 ******************************************************************/
439
al1_newelt(void)440 Wlelt *al1_newelt(void)
441 {
442 Wlelt *p = (Wlelt *)malloc(sizeof(Wlelt));
443
444 if (p != NULL)
445 {
446 p->word = NULL;
447 p->len = p->exp = 0;
448 p->invol = FALSE;
449 p->next = NULL;
450 }
451
452 return(p);
453 }
454
455 /******************************************************************
456 void al1_addwl(Wlist *l, Wlelt *w)
457
458 Adds a word (if it's non-null & non-empty) to a word list. l must
459 be non-null, but may be empty.
460 ******************************************************************/
461
al1_addwl(Wlist * l,Wlelt * w)462 void al1_addwl(Wlist *l, Wlelt *w)
463 {
464 if (w == NULL || w->len == 0) /* ignore null/empty words */
465 { return; }
466
467 if (l->len == 0)
468 { l->first = w; } /* add word to start of list */
469 else
470 { l->last->next = w; } /* add word to end of list */
471
472 l->last = w;
473 l->len++;
474 }
475
476 /******************************************************************
477 void al1_concatwl(Wlist *l, Wlist *m);
478
479 Concatenate m's list to l's, and delete m's header node. Note that
480 l is guaranteed non-null, but may be empty. m may be null, empty,
481 or contain data.
482 ******************************************************************/
483
al1_concatwl(Wlist * l,Wlist * m)484 void al1_concatwl(Wlist *l, Wlist *m)
485 {
486 if (m == NULL)
487 { return; }
488 else if (m->len == 0)
489 {
490 free(m);
491 return;
492 }
493
494 /* If we get here, m contains data */
495
496 if (l->len == 0) /* l is empty */
497 {
498 l->len = m->len;
499 l->first = m->first;
500 l->last = m->last;
501 }
502 else /* l is non-empty */
503 {
504 l->len += m->len;
505 l->last->next = m->first;
506 l->last = m->last;
507 }
508
509 free(m);
510 }
511
512 /******************************************************************
513 void al1_emptywl(Wlist *l)
514
515 Delete the list of words in l, leaving l as an empty list. Does
516 *not* delete the storage for l.
517 ******************************************************************/
518
al1_emptywl(Wlist * l)519 void al1_emptywl(Wlist *l)
520 {
521 Wlelt *p, *q;
522
523 if (l == NULL || l->len == 0)
524 { return; }
525
526 for (p = l->first; p != NULL; )
527 {
528 q = p->next;
529
530 if (p->word != NULL)
531 { free(p->word); }
532 free(p);
533
534 p = q;
535 }
536
537 l->len = 0;
538 l->first = l->last = NULL;
539 }
540
541 /******************************************************************
542 void al1_prtwl(Wlist *l, int n)
543
544 Attempt to pretty-print a list of group relators or subgroup
545 generators within the allowed (i.e., LLL) number of columns. n is
546 the current output column. (Not quite sure how this would cope
547 with a really nasty presentation!) Note that this prints out words
548 in exp form. If no enumeration has yet been run, exp is at its
549 default of 1, so a printout will not be `exponentiated'. Note that
550 relators of the form xx are *always* printed out in the form (x)^2
551 *if* they were entered thus; in all other cases they are printed as
552 xx. This is to preserve the ability to specify whether or not a
553 generator should be treated as an involution when asis is true.
554
555 Warning: if the list contains any empty words superfluous commas
556 may be introduced, rendering the list `invalid' to the Level 2
557 input parser! If _start() has been called in start/redo mode, then
558 the relator & generator lists are guaranteed to be free of empty
559 word (although they may contain duplicates).
560 ******************************************************************/
561
al1_prtwl(Wlist * l,int n)562 void al1_prtwl(Wlist *l, int n)
563 {
564 Wlelt *e;
565 int elen, eexp;
566 int i, len;
567 char c;
568
569 if (l == NULL || l->len == 0)
570 { return; }
571
572 for (e = l->first; e != NULL; e = e->next)
573 {
574 elen = e->len; /* Alias e->len & e->exp ... */
575 eexp = e->exp;
576
577 if (elen == 2 && e->word[1] == e->word[2])
578 { /* ... adjust them if involn */
579 if (e->invol)
580 { eexp = 2; }
581 else
582 { eexp = 1; }
583 }
584
585 len = elen/eexp;
586
587 if (!galpha)
588 { /* numeric generators */
589 if (eexp == 1)
590 {
591 n += 2 + len*2; /* +2 for \ , *2 for \ n */
592 if (n > LLL)
593 {
594 fprintf(fop, "\n ");
595 n = 2+2 + len*2;
596 }
597 }
598 else
599 {
600 n += 2+4 + len*2; /* 4 for ()^e */
601 if (n > LLL)
602 {
603 fprintf(fop, "\n ");
604 n = 4+4 + len*2;
605 }
606 fprintf(fop, "(");
607 }
608
609 for (i = 1; i <= len; i++)
610 { fprintf(fop, "%d ", e->word[i]); }
611
612 if (eexp != 1)
613 { fprintf(fop, ")^%d", eexp); }
614 if (e->next != NULL && len != 0) /* len = 0 not poss? */
615 { fprintf(fop, ", "); }
616 }
617 else
618 { /* alphabetic generators */
619 if (eexp == 1)
620 {
621 n += 2 + len;
622 if (n > LLL)
623 {
624 fprintf(fop, "\n ");
625 n = 2+1 + len;
626 }
627 }
628 else
629 {
630 n += 2+4 + len; /* 4 for ()^x */
631 if (n > LLL)
632 {
633 fprintf(fop, "\n ");
634 n = 3+4 + len;
635 }
636 fprintf(fop, "(");
637 }
638
639 for (i = 1; i <= len; i++)
640 {
641 c = (e->word[i] > 0) ? algen[e->word[i]]
642 : toupper(algen[-e->word[i]]);
643 fprintf(fop, "%c", c);
644 }
645
646 if (eexp != 1)
647 { fprintf(fop, ")^%d", eexp); }
648 if (e->next != NULL && len !=0)
649 { fprintf(fop, ", "); }
650 }
651 }
652 }
653
654 /**************************************************************************
655 These are the utilities for handling coset representatives.
656 **************************************************************************/
657
658 /******************************************************************
659 Logic al1_addrep(int col)
660
661 Add #col to the current rep've, possibly extending its storage.
662 Fails if we can't allocate memory.
663 ******************************************************************/
664
al1_addrep(int col)665 Logic al1_addrep(int col)
666 {
667 if (currrep == NULL)
668 {
669 repsp = 8;
670 if ((currrep = (int*)malloc(repsp*sizeof(int))) == NULL)
671 {
672 repsiz = repsp = 0;
673 return(FALSE);
674 }
675 }
676 else if (repsiz == repsp) /* current entries are 0..repsiz-1 */
677 {
678 repsp *= 2;
679 if ((currrep = (int*)realloc(currrep, repsp*sizeof(int))) == NULL)
680 {
681 repsiz = repsp = 0;
682 return(FALSE);
683 }
684 }
685
686 currrep[repsiz++] = col;
687 return(TRUE);
688 }
689
690 /******************************************************************
691 Logic al1_bldrep(int cos)
692
693 Traces back through the table, building up a rep've of #cos in
694 currrep. The rep've is in terms of column numbers, and is
695 guaranteed to be the `canonic' rep've (ie, first in `length + col
696 order' order) in terms of the *current* table. The table may or
697 may not be compact/standard. If the table is compact & standard,
698 then the rep've is guaranteed to be `really' canonic, independant
699 of the details of the enumeration. Fails if _addrep() fails.
700
701 The order of the columns is *not* constrained in any way (apart
702 from the col 1/2 stuff), so we have to be careful to pick up the
703 1st col (ie, scol) in order (*after* they have been inverted) if
704 more than one entry in a row is minimal.
705
706 Note that our ability to backtrace is predicated on the fact that
707 the first definition of a coset is always in terms of a lower-
708 numbered coset, and during coinc processing we keep the lower-
709 numbered coset & move data from the higher to the lower. So each
710 coset's row, apart from #1, *must* contain a lower-numbered entry.
711 In this routine we *assume* that this property of the table has not
712 been compromised in any way; if it has, then the behaviour is
713 undefined.
714 ******************************************************************/
715
al1_bldrep(int cos)716 Logic al1_bldrep(int cos)
717 {
718 int low, slow, col, scol, i;
719
720 repsiz = 0;
721 if (cos <= 1 || cos >= nextdf || COL1(cos) < 0)
722 { return(TRUE); }
723
724 low = slow = cos;
725 while (low > 1)
726 {
727 scol = 0;
728 for (col = 1; col <= ncol; col++)
729 {
730 if ((i = CT(low,col)) > 0)
731 {
732 if (i < slow) /* Lower row number found */
733 {
734 slow = i;
735 scol = col;
736 }
737 else if (i == slow && scol != 0) /* Same row & slow < low */
738 { /* ... earlier column? */
739 if (invcol[col] < invcol[scol])
740 { scol = col; }
741 }
742 }
743 }
744
745 /* Add it (increases repsiz); note the column inversion! Failure sets
746 repsiz to 0 */
747
748 if (!al1_addrep(invcol[scol]))
749 { return(FALSE); }
750
751 low = slow;
752 }
753
754 /* Reverse representative (note: inversion already done) */
755
756 for (i = 1; i <= repsiz/2; i++)
757 {
758 col = currrep[i-1];
759 scol = currrep[repsiz-i];
760
761 currrep[i-1] = scol;
762 currrep[repsiz-i] = col;
763 }
764
765 return(TRUE);
766 }
767
768 /******************************************************************
769 int al1_trrep(int cos)
770
771 Traces currrep, starting at #cos. Returns 0 on redundant cosets,
772 on empty slot, or if there's no rep've.
773 ******************************************************************/
774
al1_trrep(int cos)775 int al1_trrep(int cos)
776 {
777 int i;
778
779 if (repsiz == 0)
780 { return(0); }
781
782 for (i = 0; i < repsiz; i++)
783 {
784 if ((COL1(cos) < 0) || ((cos = CT(cos,currrep[i])) == 0))
785 { return(0); }
786 }
787
788 return(cos);
789 }
790
791 /******************************************************************
792 int al1_ordrep(void)
793
794 Traces currrep repeatedly until we arrive back at #1, or an empty
795 slot. The number of times round the loop is the order; return 0 if
796 the tracing doesn't complete or the rep is empty. Note that
797 termination is guaranteed, since the table is finite!
798 ******************************************************************/
799
al1_ordrep(void)800 int al1_ordrep(void)
801 {
802 int i,j;
803
804 if (repsiz == 0)
805 { return(0); }
806
807 for (i = j = 1; ; j++)
808 {
809 if ((i = al1_trrep(i)) == 1)
810 { return(j); }
811 else if (i == 0)
812 { return(0); }
813 }
814
815 return(0); /* Can't get here; prevent compiler whinging */
816 }
817
818 /******************************************************************
819 void al1_prtct(int f, int l, int s, Logic c, Logic or)
820
821 This is a general-purpose coset table printer. It prints rows from
822 f[irst] to l[ast] inclusive, in steps of s. On a bad value, we try
823 to do the `right' thing. If c[oinc] is true then the print-out
824 includes coincident rows, else not; we skip the appropriate number
825 of rows whatever the c flag is. If or is true then the order and
826 a representative are printed. The rep've is found via a backtrace
827 of the table; if the table is in standard form, this rep will be
828 minimal & the `first' in `order' (length + *column* order). Note
829 that the table may or may not have been compacted and/or
830 standardised.
831
832 Warnings/Notes:
833 i) If you print entries >999999, then the neatly aligned columns
834 will be lost, although the entries *will* be spaced.
835 ii) _bldrep() can fail. Most probably due to a lack of memory, but
836 also if the table is `corrupt' or it is called `inappropriately'.
837 In this situation we should perhaps alert the user, but we choose
838 simply to print `?'s instead!
839 ******************************************************************/
840
al1_prtct(int f,int l,int s,Logic c,Logic or)841 void al1_prtct(int f, int l, int s, Logic c, Logic or)
842 {
843 int i, j, row;
844
845 if (f < 1)
846 { f = 1; }
847 if (l > nextdf-1)
848 { l = nextdf-1; }
849 if (s < 1)
850 { s = 1; }
851
852 fprintf(fop, " coset |"); /* above coset number */
853 if (!galpha)
854 {
855 for (i = 1; i <= ncol; i++)
856 { fprintf(fop, " %6d", colgen[i]); }
857 }
858 else
859 {
860 for (i = 1; i <= ncol; i++)
861 { fprintf(fop, " %c", (colgen[i] > 0)
862 ? algen[colgen[i]] : toupper(algen[-colgen[i]])); }
863 }
864 if (or)
865 { fprintf(fop," order rep've"); }
866 fprintf(fop, "\n");
867
868 fprintf(fop, "-------+");
869 for (i = 1; i <= ncol; i++)
870 { fprintf(fop, "-------"); }
871 if (or)
872 { fprintf(fop,"-----------------"); }
873 fprintf(fop, "\n");
874
875 row = f;
876 if (!c)
877 {
878 while (row < nextdf && COL1(row) < 0)
879 { row++; }
880 }
881 while (row <= l)
882 {
883 fprintf(fop, "%6d |", row);
884 for (i = 1; i <= ncol; i++)
885 { fprintf(fop, " %6d", CT(row,i)); }
886 if (or && row != 1)
887 {
888 if (COL1(row) < 0)
889 { fprintf(fop, " - -"); }
890 else
891 {
892 if (al1_bldrep(row))
893 {
894 fprintf(fop, " %7d ", al1_ordrep());
895 for (i = 0; i < repsiz; i++)
896 {
897 j = colgen[currrep[i]]; /* generator number */
898 if (!galpha)
899 { fprintf(fop, "%d ", j); }
900 else
901 { fprintf(fop, "%c",
902 (j > 0) ? algen[j] : toupper(algen[-j])); }
903 }
904 }
905 else
906 { fprintf(fop, " ? ?"); }
907 }
908 }
909 fprintf(fop, "\n");
910
911 /* If we're printing *all* rows, we can just incr row by s. If not, we
912 have to jump over non-redundant rows. */
913
914 if (c)
915 { row += s; }
916 else
917 {
918 for (i = 1; i <= s; i++)
919 {
920 row++;
921 while (row < nextdf && COL1(row) < 0)
922 { row++; }
923 if (row == nextdf)
924 { break; }
925 }
926 }
927 }
928 }
929
930