1
2 /**************************************************************************
3
4 control.c
5 Colin Ramsay (cram@itee.uq.edu.au)
6 2 Mar 01
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 This is Level 1 of ACE; i.e., an `easy to use' wrapper round the core
18 enumerator. Note that we choose to always free & then reallocate space for
19 the data structures. This is simple, but may be inefficient on a long
20 series of runs. It would be more efficient to keep track of how much
21 memory is currently allocated (for each structure), and only free/malloc
22 if the new structure is *bigger*!
23
24 **************************************************************************/
25
26 #include "al1.h"
27
28 /******************************************************************
29 This is all the stuff declared in al1.h
30 ******************************************************************/
31
32 int workspace, workmult, *costable, tabsiz;
33 int *currrep, repsiz, repsp;
34 Logic asis;
35 char *grpname;
36 Wlist *rellst;
37 int trellen, ndgen, *gencol, *colgen;
38 Logic *geninv, galpha;
39 char algen[28];
40 int genal[27];
41 char *subgrpname;
42 Wlist *genlst;
43 int tgenlen;
44
45 /******************************************************************
46 These are the Level 0 parameters `aliased' in Level 1.
47 ******************************************************************/
48
49 int rfactor1, cfactor1;
50 int pdsiz1, dedsiz1;
51 int maxrow1, ffactor1, nrinsgp1;
52
53 /******************************************************************
54 void al1_freered(Wlist *w)
55
56 Freely reduce all the words in a word list. Can reduce words to
57 zero length; we leave these in, since they'll be removed (&
58 deallocated) by _remempt() later. We keep it simple, and make
59 multiple passes through the word until there are no changes.
60 ******************************************************************/
61
al1_freered(Wlist * w)62 void al1_freered(Wlist *w)
63 {
64 Wlelt *p;
65 Logic done;
66 int i,j;
67
68 if (w == NULL || w->len == 0)
69 { return; }
70
71 for (p = w->first; p != NULL; p = p->next)
72 {
73 do
74 {
75 done = TRUE;
76
77 for (i = 1; i <= p->len-1; i++)
78 {
79 if (p->word[i] == -p->word[i+1])
80 {
81 for (j = i; j <= p->len-2; j++)
82 { p->word[j] = p->word[j+2]; }
83 p->len -= 2;
84
85 done = FALSE;
86 break;
87 }
88 }
89 }
90 while (!done);
91 }
92 }
93
94 /******************************************************************
95 void al1_cycred(Wlist *w)
96
97 Cyclically reduce all the words in a word list. Since this is run
98 *after* _freered(), it can't introduce any 0-length words (think
99 about it!).
100 ******************************************************************/
101
al1_cycred(Wlist * w)102 void al1_cycred(Wlist *w)
103 {
104 Wlelt *p;
105 Logic done;
106 int j;
107
108 if (w == NULL || w->len == 0)
109 { return; }
110
111 for (p = w->first; p != NULL; p = p->next)
112 {
113 do
114 {
115 done = TRUE;
116
117 if ((p->len >= 2) && (p->word[1] == -p->word[p->len]))
118 {
119 for (j = 1; j <= p->len-2; j++)
120 { p->word[j] = p->word[j+1]; }
121 p->len -= 2;
122
123 done = FALSE;
124 }
125 }
126 while (!done);
127 }
128 }
129
130 /******************************************************************
131 void al1_remempt(Wlist *w)
132
133 Removes & deallocates zero-length or null words from the list. We
134 KISS, and do a `copy', dropping any empty words.
135
136 Note: we make no attempt to remove duplicate words!
137 ******************************************************************/
138
al1_remempt(Wlist * w)139 void al1_remempt(Wlist *w)
140 {
141 Wlelt *newf, *newl, *old, *tmp;
142 int length;
143
144 if (w == NULL || w->len == 0)
145 { return; }
146
147 newf = newl = NULL;
148 length = 0;
149
150 for (old = w->first; old != NULL; )
151 {
152 tmp = old;
153 old = old->next;
154
155 if (tmp->word == NULL || tmp->len == 0) /* blow away */
156 {
157 if (tmp->word != NULL)
158 { free(tmp->word); }
159 free(tmp);
160 }
161 else /* move to `new' list */
162 {
163 if (newf == NULL)
164 {
165 newf = newl = tmp;
166 tmp->next = NULL;
167 }
168 else
169 {
170 newl->next = tmp;
171 newl = tmp;
172 tmp->next = NULL;
173 }
174
175 length++;
176 }
177 }
178
179 w->first = newf;
180 w->last = newl;
181 w->len = length;
182 }
183
184 /******************************************************************
185 void al1_sort(Wlist *w)
186
187 Sort word list into nondecreasing length order, using a stable (as
188 regards words of the same length) insertion sort. Note that the
189 list may contain duplicates, but is guaranteed *not* to contain any
190 empty words. We trace through the original list, stripping
191 elements off the front & inserting them in the new list in their
192 correct place. Note the speculative check to see if we can tag the
193 next element on at the end of the new list, instead of having to
194 traverse the list looking for its proper place; this means that
195 already sorted (or partially sorted) lists process fast.
196 ******************************************************************/
197
al1_sort(Wlist * w)198 void al1_sort(Wlist *w)
199 {
200 Wlelt *newf, *newl;
201 Wlelt *old, *tmp;
202 Wlelt *curr, *currp;
203
204 if (w == NULL || w->len < 2)
205 { return; }
206
207 /* The list contains >1 word! We move the first word to the new list,
208 remove it from the old list & make the new list `correct'. */
209
210 newf = newl = w->first;
211 old = w->first->next;
212 newl->next = NULL;
213
214 while (old != NULL)
215 {
216 tmp = old;
217 old = old->next;
218
219 if (tmp->len >= newl->len) /* tag onto the end */
220 {
221 newl->next = tmp;
222 tmp->next = NULL;
223 newl = tmp;
224 }
225 else if (tmp->len < newf->len) /* tag onto the front */
226 {
227 tmp->next = newf;
228 newf = tmp;
229 }
230 else
231 {
232 /* At this point we have to scan the new list looking for tmp's
233 position; this *cannot* be the first or last, because of the
234 preceding checks. Further the new list must have at least two
235 elements in it by now (think about it!). */
236
237 currp = newf;
238 curr = newf->next;
239
240 while (tmp->len >= curr->len)
241 {
242 currp = curr;
243 curr = curr->next;
244 }
245
246 tmp->next = curr;
247 currp->next = tmp;
248 }
249 }
250
251 w->first = newf;
252 w->last = newl;
253 }
254
255 /******************************************************************
256 Logic al1_chkinvol(void)
257
258 First stage of involution checking / column allocation. Builds up
259 the initial version of the geninv[] array, based on the relator
260 list and the asis flag. If asis is false, any xx/x^2 (or whatever)
261 sets x to an involution. If asis is true, only a relator flagged
262 as an invol does the trick.
263 ******************************************************************/
264
al1_chkinvol(void)265 Logic al1_chkinvol(void)
266 {
267 int i;
268 Wlelt *p;
269
270 if (geninv != NULL)
271 { free(geninv); }
272 if ((geninv = (int *)malloc((ndgen+1)*sizeof(Logic))) == NULL)
273 { return(FALSE); }
274
275 geninv[0] = FALSE; /* P.P.P. */
276 for (i = 1; i <= ndgen; i++)
277 { geninv[i] = FALSE; }
278
279 if (rellst != NULL && rellst->len > 0)
280 {
281 for (p = rellst->first; p != NULL; p = p->next)
282 {
283 if (p->len == 2 && p->word[1] == p->word[2])
284 {
285 if (asis)
286 {
287 if (p->invol)
288 { geninv[abs(p->word[1])] = TRUE; }
289 }
290 else
291 { geninv[abs(p->word[1])] = TRUE; }
292 }
293 }
294 }
295
296 return(TRUE);
297 }
298
299 /******************************************************************
300 Logic al1_cols(void)
301
302 At this stage, geninv contains a list of the generators we would
303 *like* to treat as involutions, based on the presentation & the
304 asis flag. We now allocate the generators to columns, honouring
305 geninv & the order of entry, as far as we can. We *must* ensure
306 that the first two columns are either a generator & its inverse,
307 or two involutions. Once all this has been done, geninv & the
308 columns are *fixed* for the entire run. The invcol & gencol/colgen
309 arrays are created here; note the offsetting of the data in gencol,
310 to cope with -ve generator nos (inverses)!
311 ******************************************************************/
312
al1_cols(void)313 Logic al1_cols(void)
314 {
315 int i,j;
316
317 /* First, we dispose of the anomalous case of one generator */
318
319 if (ndgen == 1)
320 {
321 geninv[1] = FALSE;
322 ncol = 2;
323
324 if (invcol != NULL)
325 { free(invcol); }
326 if (gencol != NULL)
327 { free(gencol); }
328 if (colgen != NULL)
329 { free(colgen); }
330 if ( (invcol = (int *)malloc(3*sizeof(int))) == NULL ||
331 (gencol = (int *)malloc(3*sizeof(int))) == NULL ||
332 (colgen = (int *)malloc(3*sizeof(int))) == NULL )
333 { return(FALSE); }
334
335 invcol[0] = 0; /* P.P.P. */
336 invcol[1] = 2; /* col 2 is inv of col 1 */
337 invcol[2] = 1; /* col 1 is inv of col 2 */
338
339 gencol[0] = 2; /* -gen #1 is col #2 */
340 gencol[1] = 0; /* P.P.P. */
341 gencol[2] = 1; /* +gen #1 is col #1 */
342
343 colgen[0] = 0; /* P.P.P. */
344 colgen[1] = +1; /* col 1 is + gen 1 */
345 colgen[2] = -1; /* col 2 is - gen 1 */
346
347 return(TRUE);
348 }
349
350 /* As ndgen > 1, we can honour geninv. Allocate the required space,
351 since we now know that ncol will be 2*ndgen - #involns. */
352
353 ncol = 2*ndgen;
354 for (i = 1; i <= ndgen; i++)
355 {
356 if (geninv[i])
357 { ncol--; }
358 }
359
360 if (invcol != NULL)
361 { free(invcol); }
362 if (gencol != NULL)
363 { free(gencol); }
364 if (colgen != NULL)
365 { free(colgen); }
366 if ( (invcol = (int *)malloc((ncol+1)*sizeof(int))) == NULL ||
367 (gencol = (int *)malloc((2*ndgen+1)*sizeof(int))) == NULL ||
368 (colgen = (int *)malloc((ncol+1)*sizeof(int))) == NULL )
369 { return(FALSE); }
370
371 invcol[0] = 0; /* P.P.P. ... */
372 gencol[ndgen] = 0;
373 colgen[0] = 0;
374
375 /* We can honour the generator ordering if the first generator is not an
376 involution, or if both the first two are. */
377
378 if (!geninv[1] || (geninv[1] && geninv[2]))
379 {
380 j = 0;
381 for (i = 1; i <= ndgen; i++)
382 {
383 if (geninv[i]) /* involution, 1 col */
384 {
385 j++;
386 invcol[j] = j;
387 gencol[ndgen+i] = j;
388 gencol[ndgen-i] = j;
389 colgen[j] = +i;
390 }
391 else /* noninvolution, 2 cols */
392 {
393 j++;
394 invcol[j] = j+1;
395 gencol[ndgen+i] = j;
396 colgen[j] = +i;
397 j++;
398 invcol[j] = j-1;
399 gencol[ndgen-i] = j;
400 colgen[j] = -i;
401 }
402 }
403
404 return(TRUE);
405 }
406
407 /* We have to shuffle the columns. At this point, generator #1 is an
408 involution & #2 is not (think about it); we'll swap gen'rs 1 & 2, and
409 then honour the order. */
410
411 invcol[1] = 2;
412 invcol[2] = 1;
413 invcol[3] = 3;
414
415 gencol[ndgen+1] = 3;
416 gencol[ndgen-1] = 3;
417 gencol[ndgen+2] = 1;
418 gencol[ndgen-2] = 2;
419
420 colgen[1] = +2;
421 colgen[2] = -2;
422 colgen[3] = +1;
423
424 j = 3;
425 for (i = 3; i <= ndgen; i++) /* any more gen'rs? */
426 {
427 if (geninv[i]) /* involution, 1 col */
428 {
429 j++;
430 invcol[j] = j;
431 gencol[ndgen+i] = j;
432 gencol[ndgen-i] = j;
433 colgen[j] = +i;
434 }
435 else /* noninvolution, 2 cols */
436 {
437 j++;
438 invcol[j] = j+1;
439 gencol[ndgen+i] = j;
440 colgen[j] = +i;
441 j++;
442 invcol[j] = j-1;
443 gencol[ndgen-i] = j;
444 colgen[j] = -i;
445 }
446 }
447
448 return(TRUE);
449 }
450
451 /******************************************************************
452 void al1_getlen(void)
453
454 Compute the total length of the relators and the generators.
455 ******************************************************************/
456
al1_getlen(void)457 void al1_getlen(void)
458 {
459 Wlelt *p;
460
461 trellen = 0;
462 if (rellst != NULL && rellst->len > 0)
463 {
464 for (p = rellst->first; p != NULL; p = p->next)
465 { trellen += p->len; }
466 }
467
468 tgenlen = 0;
469 if (genlst != NULL && genlst->len > 0)
470 {
471 for (p = genlst->first; p != NULL; p = p->next)
472 { tgenlen += p->len; }
473 }
474 }
475
476 /******************************************************************
477 void al1_baseexp(Wlelt *e)
478
479 Compute exponent of word *e. btry is current attempt at base
480 length. This counts up, so get exp correct (i.e., as large as
481 possible). Originally used internally to save storage space (but
482 not time); now used for edps & print-out. Note that geninv is now
483 frozen & any involutary X's changed to x's, so we do not need to
484 worry about these when trying to find the max possible exponent.
485 ******************************************************************/
486
al1_baseexp(Wlelt * e)487 void al1_baseexp(Wlelt *e)
488 {
489 int i, j, btry;
490
491 for (btry = 1; btry <= e->len/2; btry++)
492 {
493 if (e->len % btry == 0)
494 { /* possible base length */
495 e->exp = e->len / btry;
496
497 for (i = 1; i <= btry; i++)
498 { /* for each gen in possible base */
499 for (j = i + btry; j <= e->len; j += btry)
500 { /* for each poss copy */
501 if (e->word[i] != e->word[j])
502 { goto eLoop; } /* mismatch, this e->exp failed */
503 }
504 }
505
506 return; /* this e->exp is the exponent */
507 }
508
509 eLoop:
510 ; /* try next potential exponent */
511 }
512
513 e->exp = 1; /* nontrivial exponent not found */
514 }
515
516 /******************************************************************
517 void al1_getexp(void)
518
519 Compute exponents of all words in both lists.
520 ******************************************************************/
521
al1_getexp(void)522 void al1_getexp(void)
523 {
524 Wlelt *p;
525
526 if (rellst != NULL && rellst->len > 0)
527 {
528 for (p = rellst->first; p != NULL; p = p->next)
529 { al1_baseexp(p); }
530 }
531
532 if (genlst != NULL && genlst->len > 0)
533 {
534 for (p = genlst->first; p != NULL; p = p->next)
535 { al1_baseexp(p); }
536 }
537 }
538
539 /******************************************************************
540 void al1_xtox(void)
541
542 Change any involutary X to x.
543 ******************************************************************/
544
al1_xtox(void)545 void al1_xtox(void)
546 {
547 Wlelt *p;
548 int i;
549
550 if (rellst != NULL && rellst->len > 0)
551 {
552 for (p = rellst->first; p != NULL; p = p->next)
553 {
554 if (p->word != NULL && p->len > 0)
555 {
556 for (i = 1; i <= p->len; i++)
557 {
558 if (p->word[i] < 0 && geninv[-p->word[i]])
559 { p->word[i] = -p->word[i]; }
560 }
561 }
562 }
563 }
564
565 if (genlst != NULL && genlst->len > 0)
566 {
567 for (p = genlst->first; p != NULL; p = p->next)
568 {
569 if (p->word != NULL && p->len > 0)
570 {
571 for (i = 1; i <= p->len; i++)
572 {
573 if (p->word[i] < 0 && geninv[-p->word[i]])
574 { p->word[i] = -p->word[i]; }
575 }
576 }
577 }
578 }
579 }
580
581 /******************************************************************
582 Logic al1_setrel(void)
583
584 Setup the relators for the enumerator. Note how we double up the
585 relators, so we can do `cyclic' scans efficiently. If ndrel=0, we
586 could skip this & leave the last setup present, but we choose to
587 tidy up.
588 ******************************************************************/
589
al1_setrel(void)590 Logic al1_setrel(void)
591 {
592 Wlelt *p;
593 int i, j, first, second;
594
595 if (relind != NULL)
596 { free(relind); }
597 if ((relind = (int *)malloc((ndrel+1)*sizeof(int))) == NULL)
598 { return(FALSE); }
599 relind[0] = -1; /* P.P.P. */
600
601 if (relexp != NULL)
602 { free(relexp); }
603 if ((relexp = (int *)malloc((ndrel+1)*sizeof(int))) == NULL)
604 { return(FALSE); }
605 relexp[0] = 0; /* P.P.P. */
606
607 if (rellen != NULL)
608 { free(rellen); }
609 if ((rellen = (int *)malloc((ndrel+1)*sizeof(int))) == NULL)
610 { return(FALSE); }
611 rellen[0] = 0; /* P.P.P. */
612
613 if (relators != NULL)
614 { free(relators); }
615 if ((relators = (int *)malloc(2*trellen*sizeof(int))) == NULL)
616 { return(FALSE); }
617
618 if (rellst != NULL && rellst->len > 0)
619 {
620 second = 0;
621 i = 1;
622
623 for (p = rellst->first; p != NULL; p = p->next)
624 {
625 rellen[i] = p->len;
626 relexp[i] = p->exp;
627 first = second;
628 second = first + p->len;
629 relind[i] = first;
630 for (j = 1; j <= p->len; j++)
631 { relators[first++] = relators[second++] = p->word[j]; }
632 i++;
633 }
634 }
635
636 return(TRUE);
637 }
638
639 /******************************************************************
640 Logic al1_setgen(void)
641
642 Build the generator array. Again, if nsgpg=0 we could skip this.
643 ******************************************************************/
644
al1_setgen(void)645 Logic al1_setgen(void)
646 {
647 Wlelt *p;
648 int i, j, first;
649
650 if (subgindex != NULL)
651 { free(subgindex); }
652 if ((subgindex = (int *)malloc((nsgpg+1)*sizeof(int))) == NULL)
653 { return(FALSE); }
654 subgindex[0] = -1; /* P.P.P. */
655
656 if (subglength != NULL)
657 { free(subglength); }
658 if ((subglength = (int *)malloc((nsgpg+1)*sizeof(int))) == NULL)
659 { return(FALSE); }
660 subglength[0] = 0; /* P.P.P. */
661
662 if (subggen != NULL)
663 { free(subggen); }
664 if ((subggen = (int *)malloc(tgenlen*sizeof(int))) == NULL)
665 { return(FALSE); }
666
667 if (genlst != NULL && genlst->len > 0)
668 {
669 first = 0;
670 i = 1;
671
672 for (p = genlst->first; p != NULL; p = p->next)
673 {
674 subglength[i] = p->len;
675 subgindex[i] = first;
676 for (j = 1; j <= p->len; j++)
677 { subggen[first++] = p->word[j]; }
678 i++;
679 }
680 }
681
682 return(TRUE);
683 }
684
685 /******************************************************************
686 Logic al1_bldedp(void)
687
688 Build the edp data structure by scanning through the appropriate
689 portion of relators[] array for each relator. Note that *if* x is
690 to be treated as an involution, then relators of the form xx are
691 *not* included, since they yield nothing. However, relators of the
692 form xx *must* be included if x/X has more than 1 column allocated
693 in the table (ie, it is *not* treated as an involution). At this
694 stage, relators[] is still in the form of +/- gen'r nos. Note that
695 generators with single cols are being treated as involutions, and
696 any X's have been changed to x's, so we do not need to worry about
697 picking up inverses of 1-column generators.
698
699 Remark: if defn:1 is active there are no involns, so *all* the
700 relators will be included.
701 ******************************************************************/
702
al1_bldedp(void)703 Logic al1_bldedp(void)
704 {
705 int start, col, gen, rel;
706 int b,e,i;
707
708 if (edpbeg != NULL)
709 { free(edpbeg); }
710 if (edpend != NULL)
711 { free(edpend); }
712 if (edp != NULL)
713 { free(edp); }
714
715 if ( (edpbeg = (int *)malloc((ncol + 1)*sizeof(int))) == NULL ||
716 (edpend = (int *)malloc((ncol + 1)*sizeof(int))) == NULL ||
717 (edp = (int *)malloc(2*trellen*sizeof(int))) == NULL )
718 { return(FALSE); }
719 edpbeg[0] = edpend[0] = -1; /* P.P.P. */
720
721 start = 0;
722 for (col = 1; col <= ncol; col++)
723 {
724 edpbeg[col] = start; /* index of first edp, this col */
725 gen = colgen[col];
726
727 for (rel = 1; rel <= ndrel; rel++)
728 {
729 /* b points to the beginning & e to the end of the base of (the first
730 copy of) relator rel. */
731
732 b = relind[rel];
733 e = b-1 + rellen[rel]/relexp[rel];
734
735 for (i = b; i <= e; i++)
736 {
737 if (relators[i] == gen)
738 {
739 if (!(b == e && relexp[rel] == 2 && invcol[col] == col))
740 {
741 edp[start++] = i;
742 edp[start++] = rellen[rel];
743 }
744 }
745 }
746 }
747
748 if (start == edpbeg[col]) /* none found! */
749 { edpbeg[col] = edpend[col] = -1; }
750 else
751 { edpend[col] = start - 2; } /* index of last edp, this col */
752 }
753
754 return(TRUE);
755 }
756
757 /******************************************************************
758 void al1_transl(void)
759
760 Translate the relators & generators from arrays in terms of
761 generators & inverses to arrays in terms of their associated column
762 numbers in the coset table.
763 ******************************************************************/
764
al1_transl(void)765 void al1_transl(void)
766 {
767 int i;
768
769 for (i = 0; i < 2*trellen; i++)
770 { relators[i] = gencol[ndgen+relators[i]]; }
771
772 for (i = 0; i < tgenlen; i++)
773 { subggen[i] = gencol[ndgen+subggen[i]]; }
774 }
775
776 /******************************************************************
777 int al1_start(int mode)
778
779 This is a wrapper for the enumerator (ie, al0_enum()). The mode
780 parameter indicates what we want to do; for the moment it is the
781 same as al0_enum()'s mode parameter, and is used to determine how
782 much `set-up' we have to do. (The order in which this setting-up
783 is done is *important*, since there are dependencies between the
784 various components.) The style parameter for the call will be
785 built from the values of rfactor1/cfactor1. Several other of the
786 Level 0 parameters are `aliased', to enable us to set them
787 `conveniently'. The return value is either a Level 1 error (ie, <=
788 -8192), or is that returned by _enum() (ie, > -8192).
789
790 -8192 disallowed mode
791 -8193 memory problem
792 -8194 table too small
793
794 Note: this routine (& all of Level 1) is written to be as general-
795 purpose as possible. In particular, it is *not* assumed that it
796 will be driven by the Level 2 interactive interface. So some of
797 the code may seem unnecessary, or needlessly complicated.
798
799 Warning: this wrapper routine prevents some of the more obvious
800 `errors' that may occur when continuing/redoing enumerations.
801 However, it cannot pick up all such errors; either be very careful,
802 or use the Level 2 interactive interface. It is the caller's
803 responsibility to ensure that call sequences are valid!
804
805 Warning: this routine may invalidate the current table, without
806 explicitly noting this fact. You *must* check the return value,
807 and only `believe' the table if this is >= -259 (ie, if the
808 enumerator is called and if it does something ok)!
809 ******************************************************************/
810
al1_start(int mode)811 int al1_start(int mode)
812 {
813 int i, style;
814
815 if (mode < 0 || mode > 2)
816 { return(-8192); }
817
818 /* If the mode is start or redo, then we have a (possibly) new or
819 (possibly) expanded (ie, *additional* relators/generators) presentation;
820 we have to do all the setup associated with the relator and generator
821 lists. If the mode is continue, we simply fall through. */
822
823 if (mode == 0 || mode == 2)
824 {
825 /* If asis if false, then we freely/cyclically reduce the relators and
826 freely reduce the generators. (This may introduce (additional) empty
827 and/or duplicate words.) We then remove any empty words, irrespective
828 of the value of asis; duplicates are not (currently) removed. If asis
829 is false, we sort both lists. We *always* (re)set ndrel & nsgpg, since
830 it is not incumbent on a caller of _start() to set (& reset) these
831 correctly, and the length of the lists may have changed anyway!
832
833 Note: we do *not* do any Tietze transformations, thus we are not free
834 to do, for example, xx --> 1 if x is an involution. */
835
836 if (!asis)
837 {
838 al1_freered(rellst);
839 al1_freered(genlst);
840 al1_cycred(rellst);
841 }
842
843 al1_remempt(rellst);
844 al1_remempt(genlst);
845
846 if (!asis)
847 {
848 al1_sort(rellst);
849 al1_sort(genlst);
850 }
851
852 if (rellst == NULL)
853 { ndrel = 0; }
854 else
855 { ndrel = rellst->len; }
856 if (genlst == NULL)
857 { nsgpg = 0; }
858 else
859 { nsgpg = genlst->len; }
860 }
861
862 /* If we're in start mode, we need to build a list of which generators
863 are to be *treated* as involutions & do a column allocation (possibly
864 changing this list). These are *fixed* over a run (incl any redos), even
865 if later relators / values of asis would have changed it! */
866
867 if (mode == 0)
868 {
869 if (!al1_chkinvol())
870 { return(-8193); }
871 if (!al1_cols())
872 { return(-8193); }
873 }
874
875 /* If we're in start mode, then we have to build the empty table.
876 Although coset numbers are limited to 2G, the workspace can exceed the
877 32-bit limit; hence the messing around with floating-point to find the
878 max number of cosets given the number of columns. Note the extra
879 rounding down by 1 (for safety), and that coset #0 dne. Note the error
880 if there's not enough memory for at least 2 rows. */
881
882 if (mode == 0)
883 {
884 tabsiz =
885 (int)(((double)workspace*(double)workmult)/(double)ncol) -1 -1;
886 if (tabsiz < 2)
887 { return(-8194); }
888
889 if (colptr != NULL)
890 { free(colptr); }
891 if ((colptr = (int **)malloc((ncol + 1)*sizeof(int *))) == NULL)
892 {
893 tabsiz = 0;
894 maxrow = 1;
895 return(-8193);
896 }
897
898 /* We now chop up our block of memory into (tabsiz+1)-sized chunks, one
899 for each column of the table. Whether or not this is the best way to
900 do things in moot (cf, caching). Recall that coset #0 is unused, and
901 note the (IP27/R10000) 64-bit addressing kludge! */
902
903 colptr[0] = NULL;
904 for (i = 1; i <= ncol; i++)
905 { colptr[i] = costable + (long)(i-1)*(long)(tabsiz+1); }
906 col1ptr = colptr[1];
907 col2ptr = colptr[2];
908 }
909
910 /* In start/redo mode, we now have to (re)build the data structures
911 associated with the relators & generators. */
912
913 if (mode == 0 || mode == 2)
914 {
915 /* The values in geninv have now been decided, and will be frozen for
916 this run. We now go through the relators/generators and change X to x
917 if x is to be *treated* as an involution. */
918
919 al1_xtox();
920
921 /* Calculate the total length of the relators & generators, and their
922 correct exponents. */
923
924 al1_getlen();
925 al1_getexp();
926
927 /* Build the doubled-up list of relators. */
928
929 if (!al1_setrel())
930 { return(-8193); }
931
932 /* Build the list of generators. */
933
934 if (!al1_setgen())
935 { return(-8193); }
936
937 /* Build the edp's. */
938
939 if (!al1_bldedp())
940 { return(-8193); }
941
942 /* Change relator/generator lists to column-based form. */
943
944 al1_transl();
945 }
946
947 /* Having now done all the mode-specific setup, we embark on setting-up
948 those Level 0 parameters which are aliased at Level 1 (ie, those which
949 are not set *directly* by the user). We *assume* that the caller hasn't
950 done anything stupid, and try to honour the parameters requested. This
951 may be automatic, involve changing the enumerator's state on the fly,
952 cause an error return, or be silently ignored ... */
953
954 /* Pd's are not preserved between calls, but we may need to honour a new
955 value of pdsiz. Values <=0 translate to the default of 256 and >0 is
956 honoured. It is up to the caller to ensure that pdsiz1 is a power of 2 &
957 is >=2. We don't bother malloc'ing if we already have enough memory.
958 Note that pdsiz is initialised to 0, so we are guaranteed to allocate
959 list space the first time through. */
960
961 toppd = botpd = 0;
962
963 if (pdsiz1 <= 0)
964 { pdsiz1 = 256; }
965
966 if (pdsiz1 < pdsiz)
967 { pdsiz = pdsiz1; }
968 else if (pdsiz1 == pdsiz)
969 { ; }
970 else
971 {
972 if (pdqrow != NULL)
973 { free(pdqrow); }
974 if (pdqcol != NULL)
975 { free(pdqcol); }
976 if ( (pdqcol = (int *)malloc(pdsiz1*sizeof(int))) == NULL ||
977 (pdqrow = (int *)malloc(pdsiz1*sizeof(int))) == NULL )
978 {
979 pdsiz = 0;
980 return(-8193);
981 }
982
983 pdsiz = pdsiz1;
984 }
985
986 /* A fill factor request of <= 0 picks up the default, anything else
987 is honoured. Levels 1/2 use ffactor1, which is always integral, so we
988 need to convert to float; in general, we can convert (int)<->(float)
989 without any problems, since ffactor1 is a `small' integer. */
990
991 if (ffactor1 <= 0)
992 {
993 ffactor1 = 0;
994 ffactor = (float)((int)((5*(ncol + 2))/4));
995 }
996 else
997 { ffactor = (float)ffactor1; }
998
999 /* Deductions *may* be preserved betweens calls; we need to be careful to
1000 preserve them if we're in continue mode, but we are free to empty the
1001 stack in start/redo mode (if we choose). We honour size increases using
1002 realloc (which acts like malloc if the existing pointer is null); this
1003 preserves the stack, in the absence of allocation errors. We honour size
1004 reductions simply by changing dedsiz, but we take care to note if we have
1005 to discard any deductions. dedsiz <=0 means the `smallish' default of
1006 1000, and >0 is honoured. Comments similar to those for pdsiz1 apply. */
1007
1008 if (dedsiz1 <= 0)
1009 { dedsiz1 = 1000; }
1010
1011 if (dedsiz1 < dedsiz)
1012 {
1013 if (topded >= dedsiz1) /* We've lost some deductions */
1014 {
1015 topded = dedsiz1-1;
1016 disded = TRUE;
1017 }
1018 dedsiz = dedsiz1;
1019 }
1020 else if (dedsiz1 == dedsiz)
1021 { ; }
1022 else
1023 {
1024 if ( (dedrow = (int *)realloc(dedrow, dedsiz1*sizeof(int))) == NULL ||
1025 (dedcol = (int *)realloc(dedcol, dedsiz1*sizeof(int))) == NULL )
1026 {
1027 if (topded >= 0)
1028 { disded = TRUE; }
1029 topded = -1;
1030 dedsiz = 0;
1031 return(-8193);
1032 }
1033
1034 dedsiz = dedsiz1;
1035 }
1036
1037 /* If nrinsgp1 <0 or nrinsgp >ndrel, then the default is to use all the
1038 relators. Otherwise the request is honoured. */
1039
1040 if (nrinsgp1 < 0 || nrinsgp1 > ndrel)
1041 {
1042 nrinsgp1 = -1;
1043 nrinsgp = ndrel;
1044 }
1045 else
1046 { nrinsgp = nrinsgp1; }
1047
1048 /* If maxrow1 <= 1, or >= the number of rows allowed by the allocated
1049 memory, then maxrow defaults to the allocated memory size; else if it's
1050 >= the current value of maxrow, then the request is honoured. Otherwise,
1051 the request is honoured in start mode, and is honoured in redo &
1052 continue modes *provided* that it is at least as large as nextdf; it not,
1053 it's (re)set to nextdf-1 (here, maxrow >= 2, so we're OK as regards
1054 always allowing at least 2 rows in the table). Note that maxrow1 is
1055 initialised to 0 & nextdf to 2, so we're ok the first time through. */
1056
1057 if (maxrow1 <= 1 || maxrow1 >= tabsiz)
1058 {
1059 maxrow1 = 0;
1060 maxrow = tabsiz;
1061 }
1062 else if (maxrow1 >= maxrow)
1063 { maxrow = maxrow1; }
1064 else
1065 {
1066 /* Note: 1 < maxrow1 < tabsiz and maxrow1 < maxrow */
1067 if (mode == 0) /* start mode */
1068 { maxrow = maxrow1; }
1069 else /* redo/continue modes */
1070 {
1071 if (maxrow1 >= nextdf)
1072 { maxrow = maxrow1; }
1073 else
1074 /* Note: 2 <= maxrow1 < nextdf <= maxrow+1 <= tabsiz+1 */
1075 { maxrow = nextdf-1; } /* (re)set to CT size */
1076 }
1077 }
1078
1079 /* Pick up the required style & set the blocking factors. */
1080
1081 if (rfactor1 < 0)
1082 {
1083 if (cfactor1 < 0) /* R/C-style */
1084 {
1085 rfactor = -rfactor1;
1086 cfactor = -cfactor1;
1087 style = 0;
1088 }
1089 else if (cfactor1 == 0) /* R*-style */
1090 {
1091 rfactor = -rfactor1;
1092 cfactor = 0;
1093 style = 1;
1094 }
1095 else /* Cr-style */
1096 {
1097 rfactor = -rfactor1;
1098 cfactor = cfactor1;
1099 style = 2;
1100 }
1101 }
1102 else if (rfactor1 == 0)
1103 {
1104 if (cfactor1 < 0) /* C*-style */
1105 {
1106 /* C* is not yet implemented. For the moment, just use C-style. */
1107
1108 rfactor = 0;
1109 cfactor = -cfactor1;
1110 style = 5; /* ! */
1111 }
1112 else if (cfactor1 == 0) /* R/C-style (defaulted) */
1113 {
1114 /* R/C-style with defaulted parameters, which try to `balance' the
1115 R- & C-style activity. We set C-style to 1000 definitions, and
1116 assume that 1 in 2 of the positions in a relator yield a definition,
1117 hence the 2000 (ie, 2x1000). Note the care to prevent rfactor=0, as
1118 we're doing integer divisions. If there are no relators, we'll
1119 simply fill the columns of each row, hence the 1000/ncol. */
1120
1121 if (ndrel == 0)
1122 { rfactor = 1 + 1000/ncol; }
1123 else
1124 { rfactor = 1 + 2000/(1 + trellen); }
1125 cfactor = 1000;
1126 style = 0; /* Nota bene! */
1127 }
1128 else /* C-style */
1129 {
1130 rfactor = 0;
1131 cfactor = cfactor1;
1132 style = 5;
1133 }
1134 }
1135 else
1136 {
1137 if (cfactor1 < 0) /* Rc-style */
1138 {
1139 rfactor = rfactor1;
1140 cfactor = -cfactor1;
1141 style = 6;
1142 }
1143 else if (cfactor1 == 0) /* R-style */
1144 {
1145 rfactor = rfactor1;
1146 cfactor = 0;
1147 style = 7;
1148 }
1149 else /* CR-style */
1150 {
1151 rfactor = rfactor1;
1152 cfactor = cfactor1;
1153 style = 8;
1154 }
1155 }
1156
1157 /* And away we go ... */
1158
1159 if (msgctrl) /* normal message control */
1160 { al1_prtdetails(1); }
1161
1162 /* Warning: DTT code */
1163 /*
1164 fprintf(fop, "DTT: mode = %d & style = %d\n", mode, style);
1165 */
1166
1167 i = al0_enum(mode,style);
1168
1169 return i;
1170 }
1171
1172