1
2 /**************************************************************************
3
4 enum.c
5 Colin Ramsay (cram@itee.uq.edu.au)
6 20 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 This is the main enumeration stuff for the core coset enumerator.
18
19 Note: many of the functions `borrow' the scanning code (R-style or C-style)
20 & the deduction processing code from one another. We do this for speed
21 (wrapping things up in a function can carry a significant penalty, and
22 generality `costs') or because the code in not _exactly_ the same (be
23 warned!). I sometimes don't bother commenting such copies as fully as I
24 might; check all copies for the full details. (This is a form of
25 distributed documentation!)
26
27 **************************************************************************/
28
29 #include "al0.h"
30
31 /******************************************************************
32 This macro readies a new coset for use, and gathers some
33 statistics.
34 ******************************************************************/
35
36 #define NEXTC(kk) \
37 kk = nextdf; \
38 for (col = 1; col <= ncol; col++) \
39 { CT(kk, col) = 0; } \
40 nextdf++; \
41 totcos++; \
42 if (++nalive > maxcos) \
43 { maxcos = nalive; } \
44
45 /******************************************************************
46 This is all the stuff declared in al0.h
47 ******************************************************************/
48
49 FILE *fop, *fip;
50 double begintime, endtime, deltatime, totaltime;
51 Logic msgctrl, msghol;
52 int msgincr, msgnext;
53 Logic mendel, rfill, pcomp;
54 int maxrow, rfactor, cfactor, comppc, nrinsgp, lahead;
55 int tlimit, hlimit, llimit, lcount;
56 int nalive, maxcos, totcos;
57 int chead, ctail;
58 int pdefn;
59 float ffactor;
60 int pdsiz, *pdqcol, *pdqrow, toppd, botpd;
61 int dedsiz, *dedrow, *dedcol, topded, dedmode;
62 Logic disded;
63 int *edp, *edpbeg, *edpend;
64 int ncol, **colptr, *col1ptr, *col2ptr, *invcol;
65 int ndrel, *relind, *relexp, *rellen, *relators;
66 int nsgpg, *subggen, *subgindex, *subglength;
67 Logic sgdone;
68 int knr, knh, nextdf;
69
70 #ifdef AL0_STAT
71 int cdcoinc; /* primary D-coincidences in _cdefn()/_rpefn() */
72 int rdcoinc; /* primary R-coincidences in _rdefn()/_rpefn() */
73 int apcoinc; /* primary coincidences in _apply() */
74 int rlcoinc; /* primary coincidences in _rl() */
75 int clcoinc; /* primary coincidences in _cl() */
76 int xcoinc; /* calls to _coinc() */
77 int xcols12; /* calls to _cols12() */
78 int qcoinc; /* number of actual coincs queued */
79
80 int xsave12; /* calls to SAVE12() */
81 int s12dup; /* number of duplicates */
82 int s12new; /* number of new ones */
83
84 /* The number of column 1 table accesses for CREP is xcrep+crepred+crepwrk.
85 For COMPRESS, the number is xcomp+2*compwrk. */
86
87 int xcrep; /* calls to CREP() */
88 int crepred; /* number involving redundant cosets */
89 int crepwrk; /* number of `links' followed */
90 int xcomp; /* calls to COMPRESS() */
91 int compwrk; /* number of `links' altered */
92
93 int xsaved; /* calls to SAVED() */
94 int sdmax; /* max (used) size of dedn stack */
95 int sdoflow; /* number of dedn stack overflows */
96
97 int xapply; /* calls to _apply() */
98 int apdedn; /* number of dedn in _apply() */
99 int apdefn; /* number of defn in _apply() */
100
101 int rldedn; /* number of dedn in _rl() */
102 int cldedn; /* number of dedn in _cl() */
103
104 int xrdefn; /* calls to _rdefn()/_rpefn() */
105 int rddedn; /* number of R-dedn in _rdefn()/_rpefn() */
106 int rddefn; /* number of defn in _rdefn()/_rpefn() */
107 int rdfill; /* number of fill in _rdefn()/_rpefn() */
108
109 int xcdefn; /* calls to _cdefn() */
110 int cddproc; /* number of dedn processed (ie, unstacked) */
111 int cdddedn; /* number of coinc dedn (ie, dead) */
112 int cddedn; /* number of dedn (in dedn processing) */
113 int cdgap; /* number of gap of len 1 */
114 int cdidefn; /* number of immediate defn */
115 int cdidedn; /* number of immediate dedn */
116 int cdpdl; /* number of pd listed */
117 int cdpof; /* number of pdl overflows */
118 int cdpdead; /* number of dead pd */
119 int cdpdefn; /* number of pref defn */
120 int cddefn; /* number of defn */
121 #endif
122
123 /******************************************************************
124 int al0_apply(int cos, int *beg, int *end, Logic defn, Logic save)
125
126 Apply coset cos to the word stored in beg...end. If defn is true
127 then definitions are made to complete the trace, and if save is
128 true any definitions are saved on the deduction stack. This
129 routine is intended for `general' use during R-style scans, so it
130 does _not_ worry about fill-factors or short gaps, nor is there any
131 limit on the number of definitions made. It's main use is in the
132 subgroup generator & relators as generators phases (when defn
133 will be true, and save may be true or false).
134
135 If a finite `index' is obtained, this is the return value. If an
136 overflow occurs, 0 is returned. Otherwise -1 is returned.
137
138 Warning: cos _must_ be a valid (1...nextdf-1) & non-coincident
139 coset. This routine must _never_ be called if the coincidence
140 queue is non-empty (i.e., all coincidences must have been fully
141 processed).
142 ******************************************************************/
143
al0_apply(int cos,int * beg,int * end,Logic defn,Logic save)144 int al0_apply(int cos, int *beg, int *end, Logic defn, Logic save)
145 {
146 int i,j,k;
147 int *fwd, *bwd;
148 int col, ifront, iback, ji;
149
150 INCR(xapply);
151 ifront = iback = cos;
152
153 /* Forward scan, leaving ifront set to coset at left of leftmost hole in
154 relator or to the last coset in the relator if no hole. */
155
156 for (fwd = beg; fwd <= end; fwd++)
157 {
158 if ((i = CT(ifront, *fwd)) > 0)
159 { ifront = i; }
160 else
161 { break; }
162 }
163
164 /* If the scan completed, then i = ifront & iback = cos, and we'll fall
165 right through and check for a coincidence (i.e., has ifront cycled back
166 to cos or not?). Else, there's a hole & a backward scan is required. */
167
168 if (i == 0)
169 {
170 for (bwd = end; bwd >= fwd; bwd--)
171 {
172 j = *bwd;
173 ji = invcol[j];
174
175 if ((i = CT(iback, ji)) > 0)
176 { iback = i; }
177 else /* Scan stalled */
178 {
179 if (bwd == fwd)
180 {
181 /* The backward scan has only one gap, so note the deduction to
182 complete the cycle. */
183
184 CT(iback, ji) = ifront;
185 if (save)
186 { SAVED(iback, ji); }
187
188 /* Since bwd == fwd and there was a hole, then either
189 CT(ifront,j) is still 0, or it has been set by a `backward'
190 definition (particularly if j's an involution). If it has been
191 set (on-the-fly, so to speak), we need to setup correctly for a
192 possible coincidence. */
193
194 if (CT(ifront,j) > 0)
195 { ifront = CT(ifront,j); } /* May be a coincidence here */
196 else
197 {
198 CT(ifront,j) = iback;
199 ifront = iback; /* Prevent false coincidence */
200 }
201
202 INCR(apdedn);
203 }
204 else if (defn) /* Define a new coset */
205 {
206 /* Note that, if j is an involution, and occurs next to itself,
207 then after the first defn, the remainder of the string of j's
208 will close. Note that if j^2 = 1 & j is _not_ being treated as
209 an involution, then `removing' it is a Tietze transformation, not
210 a free reduction! */
211
212 if (nextdf > maxrow) /* Overflow */
213 { return(0); }
214 NEXTC(k);
215 CT(iback,ji) = k;
216 CT(k,j) = iback;
217 if (save)
218 { SAVED(iback,ji); }
219
220 iback = k;
221 INCR(apdefn);
222
223 if (msgctrl && --msgnext == 0)
224 {
225 msgnext = msgincr;
226 ETINT;
227 fprintf(fop, "AD: a=%d r=%d h=%d n=%d;",
228 nalive, knr, knh, nextdf);
229 MSGMID;
230 fprintf(fop, " m=%d t=%d\n", maxcos, totcos);
231 BTINT;
232 }
233 }
234 else
235 { return(-1); } /* New coset definition disabled */
236 }
237 }
238 }
239
240 /* If we get here, the scan has been completed. Check to see if we've
241 found a pair of coincident cosets. */
242
243 if (ifront != iback)
244 {
245 INCR(apcoinc);
246 if ((i = al0_coinc(ifront,iback,save)) > 0)
247 { return(i); }
248 }
249
250 return(-1);
251 }
252
253 /******************************************************************
254 static int al0_rl(int first, int last, Logic saved)
255
256 Do an R-style lookahead from coset #first up to #last. We return
257 -1 if nothing exciting happens and >=1 if we get a finite `index'
258 (ie, collapse to 1). `Approx.' complexity is rl or rl^2. Note
259 that this (incl. its call to _coinc) does _not_ alter knr/knh,
260 although in may `invalidate' them. Lookahead _never_ makes _new_
261 definitions (so, it never overflows), but it may stack deductions,
262 if requested.
263 ******************************************************************/
264
al0_rl(int first,int last,Logic saved)265 static int al0_rl(int first, int last, Logic saved)
266 {
267 int row,rel,i,ii,j,k,l;
268 int *pj, *pk, *fwd, *bwd;
269 int ifront, iback;
270
271 for (row = first; row <= last; row++)
272 {
273 if (COL1(row) >= 0)
274 {
275 for (rel = 1; rel <= ndrel; rel++)
276 {
277 j = (mendel ? rellen[rel]/relexp[rel] : 1);
278 for (k = 0; k < j; k++)
279 {
280 pj = &(relators[relind[rel]+k]);
281 pk = pj + rellen[rel]-1;
282
283 /* <-- cancel indent; the code here is essentially al0_apply(). */
284
285 ifront = iback = row;
286
287 for (fwd = pj; fwd <= pk; fwd++)
288 {
289 if ((l = CT(ifront, *fwd)) > 0)
290 { ifront = l; }
291 else
292 { break; }
293 }
294
295 if (l == 0)
296 {
297 for (bwd = pk; bwd >= fwd; bwd--)
298 {
299 i = *bwd;
300 ii = invcol[i];
301
302 if ((l = CT(iback, ii)) > 0)
303 { iback = l; }
304 else if (bwd == fwd)
305 {
306 CT(iback, ii) = ifront;
307 if (saved)
308 { SAVED(iback, ii); }
309
310 /* Since we're _not_ making definitions, there is no need to check
311 if CT(ifront,i) is still undefined. The _only_ case where it's
312 not is if ifront=iback & i=ii; ie, i's an involution & we've just
313 deduced that ifront.i=ifront. So, we may set CT(ifront,i) twice,
314 but that's rare & does no damage, and is cheaper than checking. */
315
316 CT(ifront, i) = iback;
317
318 INCR(rldedn);
319 goto next_k;
320 }
321 else
322 { goto next_k; }
323 }
324 }
325
326 if (ifront != iback)
327 {
328 INCR(rlcoinc);
329 if ((l = al0_coinc(ifront,iback,saved)) > 0)
330 { return(l); }
331 }
332
333 /* --> restore indent */
334
335 if (COL1(row) < 0) /* We've become redundant */
336 { goto next_row; }
337
338 next_k:
339 ;
340 }
341 }
342 }
343 next_row:
344 ; /* Prevent non-ANSI warning */
345 }
346
347 return(-1);
348 }
349
350 /******************************************************************
351 static int al0_cl(int first, int last, Logic saved)
352
353 Do a C-style `lookahead' over all the entries in the table from
354 row #first to row #last inclusive; ie, treat it as a deduction
355 stack. We may, or may not, save deductions, depending as we're in
356 R-style or C-style. Returned value & comments as for al0_rl().
357 `Approx.' complexity is rcl.
358 ******************************************************************/
359
al0_cl(int first,int last,Logic saved)360 static int al0_cl(int first, int last, Logic saved)
361 {
362 int row,col,beg,end,i,j,ji,k;
363 int *pj, *pk, *fwd, *bwd;
364 int ifront, iback;
365
366 for (row = first; row <= last; row++)
367 {
368 if (COL1(row) >= 0)
369 {
370 for (col = 1; col <= ncol; col++)
371 {
372 if (CT(row,col) > 0)
373 {
374 if ((beg = edpbeg[col]) >= 0)
375 {
376 end = edpend[col];
377 for (i = beg; i <= end; i += 2)
378 {
379 pj = &(relators[edp[i]]);
380 pk = pj + edp[i+1]-1;
381
382 /* <-- cancel indent; the code here is essentially al0_apply(). */
383
384 ifront = iback = row;
385
386 for (fwd = pj; fwd <= pk; fwd++)
387 {
388 if ((k = CT(ifront, *fwd)) > 0)
389 { ifront = k; }
390 else
391 { break; }
392 }
393
394 if (k == 0)
395 {
396 for (bwd = pk; bwd >= fwd; bwd--)
397 {
398 j = *bwd;
399 ji = invcol[j];
400
401 if ((k = CT(iback, ji)) > 0)
402 { iback = k; }
403 else if (bwd == fwd)
404 {
405 CT(iback, ji) = ifront;
406 if (saved)
407 { SAVED(iback, ji); }
408
409 CT(ifront, j) = iback;
410
411 INCR(cldedn);
412 goto next_i;
413 }
414 else
415 { goto next_i; }
416 }
417 }
418
419 if (ifront != iback)
420 {
421 INCR(clcoinc);
422 if ((k = al0_coinc(ifront,iback,saved)) > 0)
423 { return(k); }
424 }
425
426 /* --> restore indent */
427
428 if (COL1(row) < 0) /* We've become redundant */
429 { goto next_row; }
430
431 next_i:
432 ;
433 }
434 }
435 }
436 }
437 }
438 next_row:
439 ; /* Prevent non-ANSI warning */
440 }
441
442 return(-1);
443 }
444
445 /******************************************************************
446 static int al0_rdefn(int cnt, Logic fillr, Logic saved)
447
448 Start scanning through the relators at coset knr, making
449 definitions as necessary to close the scans. If coset knr closes
450 against all relators, we fill any empty slots in its row (if fillr
451 is set), bump knr up, and loop round to process the next row. On
452 overflow we return 0 (leaving knr unchanged & the row only
453 partially scanned) and on a finite index we return nalive. Up to
454 cnt rows will be scanned (either completely or partially). If
455 nothing `exciting' happens, we return -1. Deductions are stacked
456 if saved is true. If cnt <0 then an infinite number of rows will
457 be scanned (so we'll get an index or overflow). We try as far as
458 possible to exit with complete rows scanned, so we do not continue
459 scanning after we've processed cnt rows (although the next active
460 row could close without any definitions required, or, in fact, we
461 could have finished without knowing it).
462
463 Note that a finite index is only correct if the table has no holes.
464 If we get knr = nextdf & there are holes, then one option open to
465 the control logic is to set knr to 1, and then rerun _rdefn() with
466 fillr set to fill the holes. (Of course, this _isn't_ what we
467 actually do in this situation, since a holy-table is precisely
468 what we'd expect if some of the generators don't appear in any of
469 the relators!)
470 ******************************************************************/
471
al0_rdefn(int cnt,Logic fillr,Logic saved)472 static int al0_rdefn(int cnt, Logic fillr, Logic saved)
473 {
474 int i, j, k, l, m, mi, n;
475 int *beg, *end, *fwd, *bwd;
476 int col, ifront, iback;
477
478 INCR(xrdefn);
479
480 /* Count current knr up if it's redundant and/or get an index. Note, we
481 check nextdf _first_ so that COL1(knr) (ie, CT(knr,1)) is defined. */
482
483 while (knr < nextdf && COL1(knr) < 0)
484 { knr++; }
485 if (knr == nextdf)
486 { return(nalive); }
487
488 while (cnt != 0)
489 {
490 /* Scan through all relators for this coset. The code here is
491 essentially the same as that in al0_apply. We inline for speed (and
492 flexibility; the code's not _exactly_ the same). */
493
494 for (i = 1; i <= ndrel; i++)
495 {
496 j = (mendel ? rellen[i]/relexp[i] : 1);
497 for (k = 0; k < j; k++)
498 {
499
500 /* <-- cancel indent */
501
502 /* Setup start & stop positions for scan, and the coset at the current
503 scan positions. */
504
505 beg = &(relators[relind[i]+k]);
506 end = beg-1 + rellen[i];
507 ifront = iback = knr;
508
509 /* Forward scan, leaving ifront set to coset at left of leftmost hole in
510 relator or to the last coset in the relator if no hole. */
511 l = 0;
512 for (fwd = beg; fwd <= end; fwd++)
513 {
514 if ((l = CT(ifront, *fwd)) > 0)
515 { ifront = l; }
516 else
517 { break; }
518 }
519
520 /* If the scan completed, then l = ifront & iback = cos, and we'll fall
521 right through and check for a coincidence (i.e., has ifront cycled back
522 to cos or not?). Else, there's a hole & a backward scan is required. */
523
524 if (l == 0)
525 {
526 for (bwd = end; bwd >= fwd; bwd--)
527 {
528 m = *bwd;
529 mi = invcol[m];
530
531 if ((l = CT(iback, mi)) > 0)
532 { iback = l; }
533 else /* Scan stalled */
534 {
535 if (bwd == fwd)
536 {
537 /* The backward scan has only one gap, so note the deduction to
538 complete the cycle & prime for coincidence check. */
539
540 CT(iback, mi) = ifront;
541 if (saved)
542 { SAVED(iback, mi); }
543
544 if (CT(ifront, m) > 0)
545 { ifront = CT(ifront, m); }
546 else
547 {
548 CT(ifront, m) = iback;
549 ifront = iback;
550 }
551
552 INCR(rddedn);
553 }
554 else /* Need to define a new coset */
555 {
556 /* Note that, if m is an involution, and occurs next to itself,
557 then after the first defn, the remainder of the string of m's
558 will close. Note that if m^2 = 1 & m is _not_ being treated as
559 an involution, then `removing' it is a Tietze transformation, not
560 a free reduction! */
561
562 if (nextdf > maxrow) /* Overflow */
563 { return(0); }
564
565 NEXTC(n); /* Making a definition ... */
566
567 CT(iback,mi) = n;
568 CT(n,m) = iback;
569 if (saved)
570 { SAVED(iback,mi); }
571
572 iback = n; /* Advance to next spot */
573
574 INCR(rddefn);
575
576 if (msgctrl && --msgnext == 0)
577 {
578 msgnext = msgincr;
579 ETINT;
580 fprintf(fop, "RD: a=%d r=%d h=%d n=%d;",
581 nalive, knr, knh, nextdf);
582 MSGMID;
583 fprintf(fop, " m=%d t=%d\n", maxcos, totcos);
584 BTINT;
585 }
586 }
587 }
588 }
589 }
590
591 /* If we get here, the scan has been completed. Check to see if we've
592 found a pair of coincident cosets. Recall that _coinc (if it does not
593 return >0) is guaranteed _not_ to change knc/knh, although it may render
594 them redundant. */
595
596 if (ifront != iback)
597 {
598 INCR(rdcoinc);
599 if ((l = al0_coinc(ifront,iback,saved)) > 0)
600 { return(l); }
601 if (COL1(knr) < 0)
602 { goto do_next; } /* knr now redundant */
603 }
604
605 /* --> restore indent */
606
607 }
608 }
609
610 /* All relators close at this coset, any row-filling to do? Only
611 (formally) necessary if some g/G does _not_ appear in any relator,
612 but it's usually a good thing to do. */
613
614 if (fillr)
615 {
616 for (i = 1; i <= ncol; i++)
617 {
618 if (CT(knr,i) == 0)
619 {
620 if (nextdf > maxrow) /* Overflow */
621 { return(0); }
622
623 NEXTC(k); /* Make definition */
624 CT(knr,i) = k;
625 CT(k,invcol[i]) = knr;
626 if (saved)
627 { SAVED(knr,i); }
628
629 INCR(rdfill);
630
631 if (msgctrl && --msgnext == 0)
632 {
633 msgnext = msgincr;
634 ETINT;
635 fprintf(fop, "RF: a=%d r=%d h=%d n=%d;",
636 nalive, knr, knh, nextdf);
637 MSGMID;
638 fprintf(fop, " m=%d t=%d\n", maxcos, totcos);
639 BTINT;
640 }
641 }
642 }
643 }
644
645 /* Row knr is fully scanned (or redundant), so we adjust knr up,
646 jumping over any redundancies & checking to see if we've finished. We
647 have also used up one of our allowed rows, if there's a limit. */
648
649 do_next: /* from al0_coinc(): knr redundant */
650
651 do
652 { knr++; }
653 while (knr < nextdf && COL1(knr) < 0);
654
655 if (knr == nextdf)
656 { return(nalive); }
657
658 if (cnt > 0)
659 { cnt--; }
660 }
661
662 return(-1); /* `normal' termination */
663 }
664
665 /******************************************************************
666 static int al0_cdefn(int cnt)
667
668 Repeatedly process any outstanding deductions and make definitions
669 until: we get a finite result (return > 0), we get an overflow
670 (return 0), or we've defined cnt new cosets (return -1). If cnt
671 is zero then we make no definitions, simply clearing the deduction
672 stack. If cnt < 0 there's no limit on the number of definitions.
673 ******************************************************************/
674
al0_cdefn(int cnt)675 static int al0_cdefn(int cnt)
676 {
677 int icol, rcol, irow, ires, k, col, pdqr, pdqc;
678 int first, last, i, ifront, iback, l, m, mi;
679 int *beg, *end, *fwd, *bwd;
680 Logic fi;
681
682 INCR(xcdefn);
683
684 while(TRUE)
685 {
686 /* Process all outstanding deductions on the stack */
687
688 while (topded >= 0)
689 {
690 INCR(cddproc);
691
692 irow = dedrow[topded];
693 icol = dedcol[topded--];
694 if (COL1(irow) < 0)
695 {
696 INCR(cdddedn);
697 continue; /* coset has become redundant */
698 }
699 else
700 {
701 ires = CT(irow,icol);
702 rcol = invcol[icol];
703 }
704
705 fi = TRUE; /* first pass through */
706
707 proc_ded: /* entry point for second pass through */
708
709 if ((first = edpbeg[icol]) >= 0)
710 {
711 last = edpend[icol];
712 for (i = first; i <= last; i += 2)
713 {
714 beg = &(relators[edp[i]]);
715 end = beg + edp[i+1]-1;
716
717 /* <-- cancel indent */
718
719 /* We scan this e.d.p. against irow. We don't need to scan the first
720 position, since we _know_ it must be ok. We have to set l, in case the
721 relator has length precisely one! */
722
723 ifront = l = ires;
724 iback = irow;
725
726 /* Forward scan, leaving ifront set to coset at left of leftmost hole in
727 relator or to the last coset in the relator if no hole. */
728
729 for (fwd = beg+1; fwd <= end; fwd++)
730 {
731 if ((l = CT(ifront, *fwd)) > 0)
732 { ifront = l; }
733 else
734 { break; }
735 }
736
737 /* If the scan completed, ifront = l > 0 & iback = irow, and we'll fall
738 right through and check for a coincidence (i.e., has ifront cycled back
739 to irow or not?). Else, there's a hole & a backward scan is required. */
740
741 if (l == 0)
742 {
743 for (bwd = end; bwd >= fwd; bwd--)
744 {
745 m = *bwd;
746 mi = invcol[m];
747
748 if ((l = CT(iback, mi)) > 0)
749 { iback = l; }
750 else /* Scan stalled */
751 {
752 if (bwd == fwd)
753 {
754 /* The backward scan has only one gap, so note the deduction to
755 complete the cycle. */
756
757 CT(iback, mi) = ifront;
758 CT(ifront, m) = iback;
759 SAVED(iback, mi);
760
761 INCR(cddedn);
762 }
763 else if (bwd == fwd + 1) /* gap of length = 1 */
764 {
765 INCR(cdgap);
766
767 /* In pdefn = 1 or 2 mode make definition immediately, if fill-
768 factor permits, there's space & it's allowed. If not, do
769 nothing. Note that we can handle the deduction from this
770 definition at this stage, or not (it'll come out in a later pass
771 through the loop), depending as pdefn = 1 or 2. In general,
772 these strategies blow out the count of total cosets, although
773 making definitions immediately is quicker than storing them on
774 the pdq & making them later, so pdefn=1/2 has a higher
775 `throughput'; whether this compensates for the larger totcos
776 figure is moot! */
777
778 switch(pdefn)
779 {
780 case 1:
781 if (cnt != 0 && nextdf <= maxrow &&
782 (float)(knh-1)*ffactor >= (float)(nextdf-1) )
783 {
784 NEXTC(k);
785 CT(iback, mi) = k;
786 CT(k, m) = iback;
787 SAVED(iback, mi);
788
789 if (cnt > 0)
790 { cnt--; } /* used an `allowed' definition */
791 INCR(cdidefn);
792
793 if (msgctrl && --msgnext == 0)
794 {
795 msgnext = msgincr;
796 ETINT;
797 fprintf(fop, "CG: a=%d r=%d h=%d n=%d;",
798 nalive, knr, knh, nextdf);
799 MSGMID;
800 fprintf(fop, " m=%d t=%d\n", maxcos, totcos);
801 BTINT;
802 }
803 }
804 break;
805
806 case 2:
807 if (cnt != 0 && nextdf <= maxrow &&
808 (float)(knh-1)*ffactor >= (float)(nextdf-1) )
809 {
810 NEXTC(k);
811 CT(iback, mi) = k;
812 CT(k, m) = iback;
813 SAVED(iback, mi);
814
815 if (cnt > 0)
816 { cnt--; } /* used an `allowed' definition */
817 INCR(cdidefn);
818
819 CT(ifront,*fwd) = k;
820 CT(k,invcol[*fwd]) = ifront;
821 SAVED(ifront,*fwd);
822
823 INCR(cdidedn);
824
825 if (msgctrl && --msgnext == 0)
826 {
827 msgnext = msgincr;
828 ETINT;
829 fprintf(fop, "CG: a=%d r=%d h=%d n=%d;",
830 nalive, knr, knh, nextdf);
831 MSGMID;
832 fprintf(fop, " m=%d t=%d\n", maxcos, totcos);
833 BTINT;
834 }
835 }
836 break;
837
838 case 3: /* store definition on pdq */
839 pdqrow[botpd] = iback;
840 pdqcol[botpd] = mi;
841 INCR(cdpdl);
842 if ((botpd = NEXTPD(botpd)) == toppd)
843 {
844 toppd = NEXTPD(toppd);
845 INCR(cdpof);
846 }
847 break;
848 }
849 }
850
851 iback = ifront; /* prevents a false coincidence */
852 break;
853 }
854 }
855 }
856
857 /* At this stage, if ifront != iback, then either the initial forward
858 scan did not cycle back to irow, or a backward scan produced a mismatch;
859 in either case, we have found a coincidence. In all other cases ifront =
860 iback has been enforced, to prevent problems. */
861
862 if (iback != ifront)
863 {
864 /* We do _not_ return an index at this stage if _coinc() returns a +ve
865 value, since there may still be deductions to process (which might
866 _decrease_ nalive). We do, however, detect if the current rows have
867 become redundant. Currently, the only finite value returned by
868 _coinc() is 1, on a total collapse. This clears the dedn stack, so
869 we'll drop out of the while(topded>=1) loop immediately & then drop
870 out of this function with an index of 1. */
871
872 INCR(cdcoinc);
873 al0_coinc(ifront,iback,TRUE);
874 if (COL1(irow) < 0 || COL1(ires) < 0)
875 { goto next_ded; }
876 }
877
878 /* --> restore indent */
879
880 }
881 }
882
883 /* Do we have to do a second pass? */
884
885 if (fi && (irow != ires || icol != rcol))
886 {
887 SWAP(irow,ires);
888 SWAP(icol,rcol);
889 fi = FALSE;
890 goto proc_ded;
891 }
892
893 /* End of processing this deduction, loop back to next deduction. We
894 also jump here if current deduction becomes redundant. */
895
896 next_ded:
897 ;
898
899 #ifdef AL0_DD
900 if (msgctrl && --msgnext == 0)
901 {
902 msgnext = msgincr;
903 ETINT;
904 fprintf(fop, "DD: a=%d r=%d h=%d n=%d;", nalive, knr, knh, nextdf);
905 MSGMID;
906 fprintf(fop, " d=%d\n", topded+1);
907 BTINT;
908 }
909 #endif
910 }
911
912 /* Find next empty position (& maybe finish). */
913
914 for ( ; knh < nextdf; knh++)
915 {
916 if (COL1(knh) >= 0)
917 {
918 for (icol = 1; icol <= ncol; icol++)
919 {
920 if (CT(knh, icol) == 0)
921 { goto hfill; }
922 }
923 }
924 }
925 return(nalive); /* coset table is complete */
926
927 /* Try to fill the next hole in the table */
928
929 hfill:
930
931 if (cnt == 0) /* `normal' termination, since */
932 { return(-1); } /* done all requested definitions */
933 else
934 {
935 /* Do we have space to make a definition? If not, return overflow.
936 If yes, prime the next sequential position & get its row number. */
937
938 if (nextdf > maxrow)
939 { return(0); } /* unable to make definition */
940 NEXTC(k); /* ready for definition ... */
941
942 /* We try to make a preferred definition, if possible. If we do,
943 fi is set TRUE. */
944
945 fi = FALSE;
946 if ( pdefn == 3 && toppd != botpd
947 && (float)(knh-1)*ffactor >= (float)(nextdf-1) )
948 {
949 pdqr = pdqrow[toppd];
950 pdqc = pdqcol[toppd];
951 while (COL1(pdqr) < 0 || CT(pdqr,pdqc) != 0)
952 {
953 INCR(cdpdead);
954 if ((toppd = NEXTPD(toppd)) == botpd)
955 { break; }
956 pdqr = pdqrow[toppd];
957 pdqc = pdqcol[toppd];
958 }
959
960 if (toppd != botpd)
961 {
962 toppd = NEXTPD(toppd);
963 CT(pdqr,pdqc) = k;
964 CT(k,invcol[pdqc]) = pdqr;
965 SAVED(pdqr,pdqc);
966
967 fi = TRUE;
968 INCR(cdpdefn);
969
970 if (msgctrl && --msgnext == 0)
971 {
972 msgnext = msgincr;
973 ETINT;
974 fprintf(fop, "CP: a=%d r=%d h=%d n=%d;",
975 nalive, knr, knh, nextdf);
976 MSGMID;
977 fprintf(fop, " m=%d t=%d\n", maxcos, totcos);
978 BTINT;
979 }
980 }
981 }
982
983 /* If no preferred definition made, fill next hole. */
984
985 if (!fi)
986 {
987 CT(knh,icol) = k;
988 CT(k,invcol[icol]) = knh;
989 SAVED(knh,icol);
990
991 INCR(cddefn);
992
993 if (msgctrl && --msgnext == 0)
994 {
995 msgnext = msgincr;
996 ETINT;
997 fprintf(fop, "CD: a=%d r=%d h=%d n=%d;",
998 nalive, knr, knh, nextdf);
999 MSGMID;
1000 fprintf(fop, " m=%d t=%d\n", maxcos, totcos);
1001 BTINT;
1002 }
1003 }
1004
1005 if (cnt > 0) /* keep track, if there's a limit */
1006 { cnt--; }
1007 }
1008 }
1009 }
1010
1011 /******************************************************************
1012 static int al0_rpefn(int cnt, Logic fill)
1013 ******************************************************************/
1014
1015 #include "enum01.c"
1016
1017 /******************************************************************
1018 Pull in the state machine.
1019 ******************************************************************/
1020
1021 #include "enum00.c"
1022
1023 /******************************************************************
1024 int al0_enum(int mode, int style)
1025
1026 mode 0 : start enumeration (from row 1 of zeroed table)
1027 1 : continue enumeration (from current row of current table)
1028 2 : redo enumeration (from row 1 of current table)
1029
1030 style 0 : R/C HLT until overflow, then CR-style
1031 1 : R* R-style + dedn stacking/processing
1032 2 : Cr 1 pass Felsch, 1 pass HLT, then C-style
1033 3 : reserved Level 1: C* (?!)
1034 4 : reserved Level 1: defaulted R/C
1035 5 : C Felsch strategy
1036 6 : Rc 1 pass HLT, 1 pass Felsch, then R-style
1037 7 : R HLT strategy
1038 8 : CR alternate Felsch & HLT passes
1039
1040 We can `start' at any time. We can `redo' at any time provided
1041 that any changes to the presentation are confined to _adding_
1042 group relators or subgroup generators. We can `continue' only if
1043 we have made _no_ changes to the presentation (& even if we already
1044 have a finite index). The rfactor/cfactor parameters must be set
1045 correctly (ie, >0) for the `style' of this call; they can be 0 (or
1046 even <0), but this may cause weirdness (although some intriguing
1047 things become possible).
1048
1049 return >1 : non-trivial finite index
1050 1 : index of 1 (? collapse in coincidence processing)
1051 0 : overflow
1052 -256 : incomplete table (ie, unfilled positions)
1053 -257 : hole limit exceeded
1054 -258 : time limit exceeded
1055 -259 : iteration (loops) limit exceeded
1056 -260 : overflow during SG phase
1057 -512 : disallowed mode
1058 -513 : disallowed style
1059 -514 : disallowed mode/style combination (not used yet))
1060 -4096 : invalid machine state (aka reality failure)
1061 -4097 : invalid finite result (aka reality failure)
1062 ******************************************************************/
1063
al0_enum(int mode,int style)1064 int al0_enum(int mode, int style)
1065 {
1066 int state, action, result; /* The current state, action & result. */
1067 Logic isave; /* Save definitions/deductions on stack? */
1068 static Logic rhfree; /* Table guaranteed hole-free (R-style)? */
1069 static Logic cdapp; /* All definitions applied (C-style)? */
1070 int i,j,k; /* temp ints / indices */
1071 int *pj, *pk; /* temp pointers */
1072 Logic li; /* temp booleans */
1073
1074 /* Start up the timing for this call. Prime the message counter (if
1075 required), initialise the stats package (if macro is defined), and zero
1076 the loop count. */
1077
1078 totaltime = 0.0;
1079 begintime = al0_clock();
1080 if (msgctrl)
1081 { msgnext = msgincr; }
1082 STATINIT;
1083 lcount = 0;
1084
1085 /* Check mode, style, and their combination. */
1086
1087 if (mode < 0 || mode > 2)
1088 {
1089 result = -512;
1090 goto tail_tail;
1091 }
1092 if (style < 0 || style > 8 || style == 3 || style == 4)
1093 {
1094 result = -513;
1095 goto tail_tail;
1096 }
1097
1098 /* Do the appropriate setup for the requested mode. Note that we _never_
1099 preserve pd's between calls, and there are _never_ outstanding coincs
1100 at a call's exit (so we don't actually need to zero chead/ctail, but we
1101 do anyway!). We may, or may not, preserve deduction stack, entries in
1102 the table and the various `progress' counters. */
1103
1104 toppd = botpd = 0;
1105 chead = ctail = 0;
1106
1107 switch(mode)
1108 {
1109 case 0: /* start; ie, a new run */
1110
1111 topded = -1;
1112 disded = FALSE;
1113
1114 for (i = 1; i <= ncol; i++)
1115 { CT(1, i) = 0; }
1116
1117 nalive = maxcos = totcos = 1;
1118 knr = knh = 1;
1119 nextdf = 2;
1120
1121 sgdone = FALSE; /* SG not (successfully) run yet */
1122 rhfree = cdapp = TRUE; /* prime for this new run */
1123
1124 break;
1125
1126 case 1: /* continue */
1127
1128 ;
1129
1130 break;
1131
1132 case 2: /* redo */
1133
1134 topded = -1;
1135 disded = FALSE;
1136
1137 knr = knh = 1;
1138
1139 sgdone = FALSE;
1140
1141 break;
1142 }
1143
1144 /* The static variable rhfree is primed to true at the start of every run
1145 (ie, start mode), and retains its value across a sequence of continue &
1146 redo commands until the next start. Any time we could _potentially_ do
1147 any R-style applying without filling rows, we toggle it to false. This
1148 indicates that the table _may_ contain holes, and that the al0_upknh()
1149 routine may need to be called before a finite index (due to knr = nextdf)
1150 is returned. Any code anywhere which could cause empty table slots
1151 should take care to ensure that rhfree is false. Since rhfree is only
1152 invoked when checking a finite result due to knr = nextdf, its value if
1153 we get a result due to knh=nextdf is of no concern (here, the table is
1154 hole-free, since that's what knh means!).
1155
1156 Instead of trying to be clever, and keeping a close watch on what the
1157 value of this should be at each point, we simply reset it at the start of
1158 any call(s) where the rfill control parameter is false. The cost of
1159 running _upknh() is no more than that of row-filling (although it's
1160 concentrated in one `lump'), since all table positions are checked in
1161 both cases. In fact, it will usually be less, since we can start the
1162 check at knh, we need not check rows that have become redundant, and we
1163 make no definitions. Note that, even if row-filling is not needed (to
1164 obtain a finite index), it may still be beneficial to turn it on, since
1165 it may alter the definition sequence. */
1166
1167 if (!rfill)
1168 { rhfree = FALSE; }
1169
1170 /* Do the appropriate setup for the requested style. Our main concern
1171 is whether or not to stack defns/dedns (isave flag) so that these can be
1172 tested against all edp, for C-style enumerations. We also have to track
1173 whether or not we have done this over the course of an entire run; we use
1174 the cdapp flag for this. This flag is similar in concept to the rhfree
1175 one, but is more difficult to manage, since it is `more expensive' to get
1176 it `wrong'. Furthermore, saving & applying dedns is a 3-stage process,
1177 and cdapp only tracks the first step.
1178
1179 cdapp is static, and is primed to true. Any time we _may_ make any table
1180 entries _without_ stacking them, we toggle it to false. Whether or not
1181 the stacking (call to SAVED()) was successful is monitored by the global
1182 disded flag. Whether or not all the stacked dedns have been processed is
1183 determined by the stack size (the global topded). If knh=nextdf and all
1184 three stages were successful (ie, cdapp=TRUE & disded=FALSE & topded==-1)
1185 then the result is valid. If not, then the actual index may be smaller
1186 than the `current' one (ie, nalive). Since our table is guaranteed hole-
1187 free at this stage, the quickest check is to run an R-style scan (with
1188 definitions & deduction stacking both off!) to move knr up to nextdf,
1189 perhaps finding some coincs along the way; this RA phase is the default
1190 action.
1191
1192 The settings below prime isave & cdapp for the styles. However, finer
1193 control is needed since, for example, a (successful) CL phase forces
1194 cdapp back to true (provided further dedns _will_ be stacked (ie, isave
1195 is true)). We use the switch at the end of the state machine's main
1196 loop to do this. Note that we must be careful, since we can exit at any
1197 time and we must ensure that the status is valid for any continues or
1198 redos. We err on the side of caution, so the RA phase may be done when
1199 it is not (formally) required.
1200
1201 Note that in some styles we don't save deductions initially, since we do
1202 a C-style table lookahead at the point where we switch from R-style to
1203 C-style (which effectively forces cdapp to true). (We could also insist
1204 that _all_ dedns _are_ applied, and do a C-style lookahead at any point
1205 where we detect `missed' dedns.) Of course, if the dedn stack is large
1206 enough, then we'll never lose dedn's; but we could end up having to
1207 process _very_ large dedn stacks, which can be expensive. */
1208
1209 isave = FALSE;
1210 switch(style)
1211 {
1212 case 0:
1213 isave = FALSE;
1214 cdapp = FALSE;
1215 break;
1216
1217 case 1:
1218 isave = TRUE;
1219 break;
1220
1221 case 2:
1222 isave = TRUE;
1223 break;
1224
1225 case 5:
1226 isave = TRUE;
1227 break;
1228
1229 case 6:
1230 isave = FALSE;
1231 cdapp = FALSE;
1232 break;
1233
1234 case 7:
1235 isave = FALSE;
1236 cdapp = FALSE;
1237 break;
1238
1239 case 8:
1240 isave = TRUE;
1241 break;
1242 }
1243
1244 /* Combine the style with the mode into the machine's starting state.
1245 Prime machine with `dummy'/`null' action & `success' result. */
1246
1247 state = 1 + 9*mode + style;
1248
1249 action = 0;
1250 result = -1;
1251
1252 /* THE MACHINE ... */
1253
1254 while (TRUE)
1255 {
1256 /* lcount tracks which pass through the machine's loop this is. Then
1257 use result of last action to get next state & action. */
1258
1259 lcount++;
1260
1261 /* DEBUG/TEST/TRACE (DTT) code. Monitors the state machine. */
1262 /*
1263 fprintf(fop, "DTT: lcount=%d; state=%d action=%d result=%d",
1264 lcount, state, action, result);
1265 */
1266
1267 action = al0_act[state][-result];
1268 state = al0_st[state][-result];
1269
1270 /* Warning: DTT code (see above) */
1271 /*
1272 fprintf(fop, " --> state=%d action=%d\n", state, action);
1273 */
1274
1275 switch(action)
1276 {
1277
1278 /* <-- cancel indent */
1279
1280 /* The null action; allows timing tests, progress messages, etc. */
1281
1282 case 0:
1283 result = -1;
1284 break;
1285
1286 /* Make some R-style definitions. al0_rdefn() can return -1 (`nothing'
1287 happened), 0 (unable to make definition), or >0 (finite result). Note
1288 that _all_ finite `index' return values are `filtered' through the check
1289 phase (action #6), to prevent `problems'. */
1290
1291 case 1:
1292
1293 if ((result = al0_rdefn(rfactor, rfill, isave)) > 0)
1294 { result = -2; }
1295
1296 break;
1297
1298 /* Perform lookahead, in R-style _only_, if enabled. This lookahead is
1299 used when we run out of table space, and it could allow us to continue
1300 _without_ running a compaction. However, we elect not to detect this
1301 state of affairs in the current version. Instead, we'll _always_ try to
1302 compact, and we'll check after doing that whether or not there's any
1303 space available in the table (however it was obtained!). Note that
1304 lookahead (& any coincidence processing) does _not_ alter nextdf or knr/
1305 knh (except in the collapse to 1 case, of course), although it may render
1306 them redundant. Since this is a _lookahead_ only, there is never any
1307 need to stack deductions. We don't try to trap an invalid lahead value.
1308 If we don't recognise it, we just quietly do nothing.
1309
1310 Note that we can be as `sloppy' as we wish, in the sense that all we
1311 require is one or more coincs to free up some table space. The current
1312 options all look only for immediate consequences of the current table,
1313 and don't worry about consequent consequences. There are a great variety
1314 of other ways to do lookahead. For example: we could repeatedly run
1315 _rl() until there's no further improvement; or we could bail out early,
1316 after a burst of `significant' progress or if we're achieving
1317 `nothing'. */
1318
1319 case 2:
1320
1321 switch(lahead)
1322 {
1323 case 1:
1324 result = al0_rl(knr, nextdf-1, FALSE);
1325 if (msgctrl)
1326 {
1327 msgnext = msgincr; /* start new count */
1328 ETINT;
1329 fprintf(fop, "L1: a=%d r=%d h=%d n=%d;", nalive, knr, knh, nextdf);
1330 MSGMID;
1331 fprintf(fop, " m=%d t=%d\n", maxcos, totcos);
1332 BTINT;
1333 }
1334 break;
1335 case 2:
1336 result = al0_cl(1, nextdf-1, FALSE);
1337 if (msgctrl)
1338 {
1339 msgnext = msgincr;
1340 ETINT;
1341 fprintf(fop, "L2: a=%d r=%d h=%d n=%d;", nalive, knr, knh, nextdf);
1342 MSGMID;
1343 fprintf(fop, " m=%d t=%d\n", maxcos, totcos);
1344 BTINT;
1345 }
1346 break;
1347 case 3:
1348 result = al0_rl(1, nextdf-1, FALSE);
1349 if (msgctrl)
1350 {
1351 msgnext = msgincr;
1352 ETINT;
1353 fprintf(fop, "L3: a=%d r=%d h=%d n=%d;", nalive, knr, knh, nextdf);
1354 MSGMID;
1355 fprintf(fop, " m=%d t=%d\n", maxcos, totcos);
1356 BTINT;
1357 }
1358 break;
1359 case 4:
1360 result = al0_cl(knr, nextdf-1, FALSE);
1361 if (msgctrl)
1362 {
1363 msgnext = msgincr;
1364 ETINT;
1365 fprintf(fop, "L4: a=%d r=%d h=%d n=%d;", nalive, knr, knh, nextdf);
1366 MSGMID;
1367 fprintf(fop, " m=%d t=%d\n", maxcos, totcos);
1368 BTINT;
1369 }
1370 break;
1371 default:
1372 result = -1;
1373 break;
1374 }
1375
1376 if (result > 0)
1377 { result = -2; }
1378
1379 break;
1380
1381 /* Perform compaction (any style) if it's allowed & then check whether
1382 the table has any space left. If so, then continue, else return
1383 overflow. Note that compaction does _not_ alter nalive, but may change
1384 (reduce) knr/knh/nextdf. It makes `free' space _available_, but it does
1385 not _create_ it; coincidences (normal, or in lookahead) do that. */
1386
1387 case 3:
1388
1389 if (nalive >= maxrow)
1390 {
1391 result = 0;
1392 goto tail_tail;
1393 }
1394 else if ( (double)(nextdf-1 - nalive)/(double)(nextdf-1)
1395 >= (double)comppc/100.0 )
1396 {
1397 /* DTT: how expensive is compaction? */
1398 /*
1399 if (msgctrl)
1400 {
1401 msgnext = msgincr;
1402 ETINT;
1403 fprintf(fop, "co: a=%d r=%d h=%d n=%d;", nalive, knr, knh, nextdf);
1404 MSGMID;
1405 fprintf(fop, " m=%d t=%d\n", maxcos, totcos);
1406 BTINT;
1407 }
1408 */
1409 al0_compact();
1410 if (msgctrl)
1411 {
1412 msgnext = msgincr;
1413 ETINT;
1414 fprintf(fop, "CO: a=%d r=%d h=%d n=%d;", nalive, knr, knh, nextdf);
1415 MSGMID;
1416 fprintf(fop, " m=%d t=%d\n", maxcos, totcos);
1417 BTINT;
1418 }
1419 }
1420
1421 if (nextdf <= maxrow)
1422 { result = -1; }
1423 else
1424 {
1425 result = 0;
1426 goto tail_tail;
1427 }
1428
1429 break;
1430
1431 /* Do some C-style definitions / deduction processing. al0_cdefn() can
1432 return -1 (`nothing' happened), 0 (unable to make definition), or >0
1433 (finite result - potential index, needs checking). */
1434
1435 case 4:
1436
1437 if ((result = al0_cdefn(cfactor)) > 0)
1438 { result = -2; }
1439
1440 break;
1441
1442 /* Do a C-style complete table lookahead. This is run when we're
1443 switching styles from R- to C-style, or when we're `starting' C-style
1444 with an already existing table. Since we maybe haven't being processing
1445 definitions, we need to run through the entire table. We treat each
1446 table entry as a deduction and stack any new deductions. A subsequent
1447 C-style defn/dedn pass will clear the stack, as usual; we can now enter
1448 C-style, and be confident of any C-style result.
1449
1450 Actually, calling this lookahead is a misnomer. It more correctly might
1451 be thought of as either a `check' (when we have a finite result but
1452 cannot guarantee that all definitions have been processed, or when we
1453 call the enumerator in the redo mode) or a `prime' (when we're switching
1454 to C-style) phase. */
1455
1456 case 5:
1457
1458 if ((result = al0_cl(1, nextdf-1, TRUE)) > 0)
1459 { result = -2; }
1460 if (msgctrl)
1461 {
1462 msgnext = msgincr;
1463 ETINT;
1464 fprintf(fop, "CL: a=%d r=%d h=%d n=%d;", nalive, knr, knh, nextdf);
1465 MSGMID;
1466 fprintf(fop, " m=%d t=%d\n", maxcos, totcos);
1467 BTINT;
1468 }
1469
1470 break;
1471
1472 /* We have a finite result; triggered by knr=nextdf, knh=nextdf, or a
1473 collapse to 1 in coinc processing. Check that it's a valid index; it may
1474 be a multiple, or the table may have holes. If knr=nextdf, then all
1475 relators close against all cosets, so we need only check whether or not
1476 the table has any holes. If knh=nextdf, then the table is hole-free, so
1477 we need to check that all table entries have been scanned in all edp.
1478 Note that we have to check for a `clean' C-style termination _before_ we
1479 may bump knh; this is an artifact of the overloading of knh's meaning. */
1480
1481 case 6:
1482
1483 if (knr == nextdf && rhfree)
1484 { ; } /* ok, fall through */
1485 else if (knh == nextdf && cdapp && !disded && topded < 0)
1486 { ; } /* ok, fall through */
1487 else if (knr == nextdf)
1488 {
1489 al0_upknh(); /* check for holes ... */
1490 if (msgctrl)
1491 {
1492 msgnext = msgincr;
1493 ETINT;
1494 fprintf(fop, "UH: a=%d r=%d h=%d n=%d;", nalive, knr, knh, nextdf);
1495 MSGMID;
1496 fprintf(fop, " m=%d t=%d\n", maxcos, totcos);
1497 BTINT;
1498 }
1499 if (knh < nextdf) /* ... table is incomplete */
1500 {
1501 result = -256;
1502 goto tail_tail;
1503 }
1504 }
1505 else if (knh == nextdf)
1506 {
1507 /* Apply all remaining cosets. Note that knh=nextdf, so there are no
1508 holes & no defns will (can!) be made. Since we are only interested in
1509 moving knr up to nextdf (perhaps finding coincs), we turn mendel off;
1510 if it's on (& left on), it can cause a dramatic slow-down. */
1511
1512 li = mendel;
1513 mendel = FALSE;
1514 al0_rdefn(-1,FALSE,FALSE);
1515 mendel = li;
1516
1517 if (msgctrl)
1518 {
1519 msgnext = msgincr;
1520 ETINT;
1521 fprintf(fop, "RA: a=%d r=%d h=%d n=%d;", nalive, knr, knh, nextdf);
1522 MSGMID;
1523 fprintf(fop, " m=%d t=%d\n", maxcos, totcos);
1524 BTINT;
1525 }
1526 }
1527 else
1528 { /* fatal error (ie, can't happen!) */
1529 result = -4097;
1530 goto tail_tail;
1531 }
1532
1533 result = nalive;
1534 goto tail_tail;
1535
1536 break; /* not really needed! */
1537
1538 /* If start or redo, scan & close the subgroup generators on coset #1.
1539 Note that we can get coincidences, or collapses, or overflows here. We
1540 treat an overflow as fatal, and return a special value (-260) to alert
1541 the caller to the fact that the subgroup generators have not been fully
1542 processed (so we _must_ (re)start, we can't continue). Note that knr =
1543 knh = 1 here, and they are _not_ changed (we do no scanning against the
1544 relators, so they can't go up, and coset 1 is never redundant). Thus the
1545 only finite index we can get is a collapse to 1, and this is a valid
1546 result.
1547
1548 Note that closing subgroup generators against coset 1 is done R-style, in
1549 that we (maybe) stack up definitions/deductions for later action, and
1550 make as many definitions as required to (immediately) fill any empty
1551 relator table positions. If the enumeration is a (pure) C-style one, we
1552 should process each definition (ie, stacked deduction) _immediately_,
1553 since we should only make definitions if there's nothing else we can do.
1554 For the moment, we don't worry about his `complication'.
1555
1556 As this phase _must_ be successfully completed before a continue is
1557 allowed, and it need not be the 1st phase (it can be the 2nd in redo), a
1558 time/hole/loop limit could cause an early return. So we make sure the
1559 sgdone flag is correctly (re)set at all times. */
1560
1561 case 7:
1562
1563 if (nsgpg > 0)
1564 {
1565 for (i = 1; i <= nsgpg; i++)
1566 {
1567 pj = &(subggen[subgindex[i]]);
1568 pk = pj-1 + subglength[i];
1569
1570 if ((result = al0_apply(1,pj,pk,TRUE,isave)) >= 0)
1571 { break; }
1572 }
1573
1574 if (msgctrl)
1575 {
1576 msgnext = msgincr;
1577 ETINT;
1578 fprintf(fop, "SG: a=%d r=%d h=%d n=%d;", nalive, knr, knh, nextdf);
1579 MSGMID;
1580 fprintf(fop, " m=%d t=%d\n", maxcos, totcos);
1581 BTINT;
1582 }
1583
1584 sgdone = TRUE;
1585 if (result == 0)
1586 {
1587 result = -260;
1588 sgdone = FALSE;
1589 goto tail_tail;
1590 }
1591 else if (result > 0)
1592 { result = -2; }
1593 }
1594 else
1595 {
1596 result = -1; /* `default' result */
1597 sgdone = TRUE; /* ok, since nothing to do! */
1598 }
1599
1600 break;
1601
1602 /* If start or redo (modes 0/2) and in an appropriate style (ie, 1st step
1603 will be a C-style scan), and requested (nrinsgp > 0), then scan & close
1604 the first nrinsgp group relators against coset 1. Similar comments to
1605 those for the subgroup generators apply here, although an overflow does
1606 _not_ force a restart here. */
1607
1608 case 8:
1609
1610 if (nrinsgp > 0)
1611 {
1612 for (i = 1; i <= nrinsgp; i++)
1613 {
1614 j = (mendel ? rellen[i]/relexp[i] : 1);
1615 for (k = 0; k < j; k++)
1616 {
1617 pj = &(relators[relind[i]+k]);
1618 pk = pj-1 + rellen[i];
1619
1620 if ((result = al0_apply(1,pj,pk,TRUE,isave)) >= 0)
1621 { break; }
1622 }
1623
1624 if (result >= 0)
1625 { break; }
1626 }
1627
1628 if (msgctrl)
1629 {
1630 msgnext = msgincr;
1631 ETINT;
1632 fprintf(fop, "RS: a=%d r=%d h=%d n=%d;", nalive, knr, knh, nextdf);
1633 MSGMID;
1634 fprintf(fop, " m=%d t=%d\n", maxcos, totcos);
1635 BTINT;
1636 }
1637
1638 if (result > 0)
1639 { result = -2; }
1640 }
1641 else
1642 { result = -1; } /* `default' result */
1643
1644 break;
1645
1646 /* Do some R*-style definitions / deduction processing. al0_rpefn() can
1647 return -1 (`nothing' happened), 0 (unable to make definition), or >0
1648 (finite result - potential index, needs checking). Note the row-filling
1649 argument and the fact that we don't use (need?) isave, since dedn
1650 stacking is mandatory here. */
1651
1652 case 9:
1653
1654 if ((result = al0_rpefn(rfactor, rfill)) > 0)
1655 { result = -2; }
1656
1657 break;
1658
1659 /* If we get here, something's a touch awry. */
1660
1661 default:
1662 result = -4096;
1663 goto tail_tail;
1664
1665 /* --> restore indent */
1666
1667 } /* end of "switch(action)" */
1668
1669 /* At this point, we have just completed action in state, and are about
1670 to `leave' state via one of its exit paths (selected by the (state,
1671 result) pair). Now is the time to perform any action specific to this
1672 point. Note that the checks for the various limits (times, holes, ...)
1673 are done _after_ this, so we're guaranteed that the (updated) status
1674 will be correct on any `early' exit. */
1675
1676 switch(state)
1677 {
1678 case 32:
1679 if (result == -1)
1680 { cdapp = TRUE; }
1681 break;
1682 case 38:
1683 if (result == -1)
1684 { cdapp = TRUE; }
1685 break;
1686 case 45:
1687 if (result == 0)
1688 { isave = TRUE; }
1689 break;
1690 case 46:
1691 if (result == -1)
1692 { cdapp = TRUE; }
1693 break;
1694 case 47:
1695 if (result == -1)
1696 { cdapp = TRUE; }
1697 break;
1698 case 55:
1699 if (result == -1)
1700 { cdapp = TRUE; }
1701 break;
1702 case 56:
1703 if (result == -1)
1704 { cdapp = TRUE; }
1705 break;
1706 case 58:
1707 if (result == -1 || result == 0)
1708 { cdapp = FALSE; }
1709 break;
1710 case 59:
1711 if (result == -1)
1712 { cdapp = TRUE; }
1713 break;
1714 }
1715
1716 /* Only calculate % holes if requested, since it's expensive! We only
1717 treat the value as significant if we've actually defined some cosets
1718 other than #1! We ignore the case where nalive=1 and not all #1's row
1719 entries are 0 (ie, some, but not necessarily all, are 1 instead). */
1720
1721 if (hlimit >= 0 && nalive > 1)
1722 {
1723 if (al0_nholes() >= (double)hlimit)
1724 {
1725 result = -257;
1726 break;
1727 }
1728 }
1729
1730 /* We have to correctly find the total accumulated time, without
1731 disturbing any messaging (which must always print the elapsed time
1732 since the last message). So we _can't_ use the ETINT/BTINT macros. */
1733
1734 if (tlimit >= 0)
1735 {
1736 if ((totaltime + al0_diff(begintime,al0_clock())) >= (double)tlimit)
1737 {
1738 result = -258;
1739 break;
1740 }
1741 }
1742
1743 /* Any loop limit in force? */
1744
1745 if (llimit > 0 && lcount >= llimit)
1746 {
1747 result = -259;
1748 break;
1749 }
1750
1751 } /* end of "while(TRUE)" */
1752
1753 /* We've either jumped here (finite result, overflow, error), or we've
1754 broken out the main loop (time / holes / iterations limit). We simply
1755 update the total time for this call & return the `status'. */
1756
1757 tail_tail:
1758
1759 endtime = al0_clock();
1760 totaltime += al0_diff(begintime,endtime);
1761
1762 return(result);
1763 }
1764
1765