Logo Search packages:      
Sourcecode: magnus version File versions  Download package

enum.c

/**************************************************************************

      enum.c
      Colin Ramsay (cram@csee.uq.edu.au)
        13 Feb 99

      ADAPTIVE COSET ENUMERATOR, Version 3.000

      Copyright 1999
      Centre for Discrete Mathematics and Computing,
      Department of Mathematics and 
      Department of Computer Science & Electrical Engineering,
      The University of Queensland, QLD 4072.
      (http://www.csee.uq.edu.au/~havas/cdmc.html)

This is the main enumeration stuff for the core coset enumerator.

Note: many of the functions `borrow' the scanning code (R-style or C-style)
& the deduction processing code from one another.  We do this for speed
(wrapping things up in a function can carry a significant penalty, and
generality `costs') or because the code in not _exactly_ the same (be
warned!).  I sometimes don't bother commenting such copies as fully as I 
might; check all copies for the full details.  (This is a form of
distributed documentation!)

**************************************************************************/

#include "al0.h"

      /******************************************************************
      This macro readies a new coset for use, and gathers some 
      statistics.
      ******************************************************************/

#define NEXTC(kk)                   \
  kk = nextdf;                      \
  for (col = 1; col <= ncol; col++) \
    { CT(kk, col) = 0; }            \
  nextdf++;                         \
  totcos++;                         \
  if (++nalive > maxcos)            \
    { maxcos = nalive; }            \

      /******************************************************************
      This is all the stuff declared in al0.h
      ******************************************************************/

FILE  *fop, *fip;
double begintime, endtime, deltatime, totaltime;
Logic  msgctrl, msghol;
int    msgincr, msgnext;
Logic  mendel, rfill, pcomp;
int    maxrow, rfactor, cfactor, comppc, nrinsgp, lahead;
int    tlimit, hlimit, llimit, lcount;
int    nalive, maxcos, totcos;
int    chead, ctail;
int    pdefn;
float  ffactor; 
int    pdsiz, *pdqcol, *pdqrow, toppd, botpd;
int    dedsiz, *dedrow, *dedcol, topded, dedmode;
Logic  disded;
int   *edp, *edpbeg, *edpend;
int    ncol, **colptr, *col1ptr, *col2ptr, *invcol;
int    ndrel, *relind, *relexp, *rellen, *relators;
int    nsgpg, *subggen, *subgindex, *subglength;
Logic  sgdone;
int    knr, knh, nextdf;

#ifdef AL0_STAT
int cdcoinc;            /* primary D-coincidences in _cdefn()/_rpefn() */
int rdcoinc;            /* primary R-coincidences in _rdefn()/_rpefn() */
int apcoinc;            /* primary coincidences in _apply() */
int rlcoinc;            /* primary coincidences in _rl() */
int clcoinc;            /* primary coincidences in _cl() */
int xcoinc;       /* calls to _coinc() */
int xcols12;            /* calls to _cols12() */
int qcoinc;       /* number of actual coincs queued */

int xsave12;            /* calls to SAVE12() */
int s12dup;       /* number of duplicates */
int s12new;       /* number of new ones */

/* The number of column 1 table accesses for CREP is xcrep+crepred+crepwrk.
For COMPRESS, the number is xcomp+2*compwrk. */

int xcrep;        /* calls to CREP() */
int crepred;            /* number involving redundant cosets */
int crepwrk;            /* number of `links' followed */
int xcomp;        /* calls to COMPRESS() */
int compwrk;            /* number of `links' altered */

int xsaved;       /* calls to SAVED() */
int sdmax;        /* max (used) size of dedn stack */
int sdoflow;            /* number of dedn stack overflows */

int xapply;       /* calls to _apply() */
int apdedn;       /* number of dedn in _apply() */
int apdefn;       /* number of defn in _apply() */

int rldedn;       /* number of dedn in _rl() */
int cldedn;       /* number of dedn in _cl() */

int xrdefn;       /* calls to _rdefn()/_rpefn() */
int rddedn;       /* number of R-dedn in _rdefn()/_rpefn() */
int rddefn;       /* number of defn in _rdefn()/_rpefn() */
int rdfill;       /* number of fill in _rdefn()/_rpefn() */

int xcdefn;       /* calls to _cdefn() */
int cddproc;            /* number of dedn processed (ie, unstacked) */
int cdddedn;            /* number of coinc dedn (ie, dead) */
int cddedn;       /* number of dedn (in dedn processing) */
int cdgap;        /* number of gap of len 1 */
int cdidefn;            /* number of immediate defn */
int cdidedn;            /* number of immediate dedn */
int cdpdl;        /* number of pd listed */
int cdpof;        /* number of pdl overflows */
int cdpdead;            /* number of dead pd */
int cdpdefn;            /* number of pref defn */
int cddefn;       /* number of defn */
#endif

      /******************************************************************
      int al0_apply(int cos, int *beg, int *end, Logic defn, Logic save)

      Apply coset cos to the word stored in beg...end.  If defn is true
      then definitions are made to complete the trace, and if save is
      true any definitions are saved on the deduction stack.  This
      routine is intended for `general' use during R-style scans, so it 
      does _not_ worry about fill-factors or short gaps, nor is there any
      limit on the number of definitions made.  It's main use is in the 
      subgroup generator & relators as generators phases (when defn 
      will be true, and save may be true or false). 

      If a finite `index' is obtained, this is the return value.  If an
      overflow occurs, 0 is returned.  Otherwise -1 is returned.

      Warning: cos _must_ be a valid (1...nextdf-1) & non-coincident 
      coset.  This routine must _never_ be called if the coincidence 
      queue is non-empty (i.e., all coincidences must have been fully
      processed).
      ******************************************************************/

int al0_apply(int cos, int *beg, int *end, Logic defn, Logic save)
  {
  int i,j,k;
  int *fwd, *bwd;
  int col, ifront, iback, ji;

  INCR(xapply);
  ifront = iback = cos;

  /* Forward scan, leaving ifront set to coset at left of leftmost hole in
  relator or to the last coset in the relator if no hole. */

  for (fwd = beg; fwd <= end; fwd++) 
    { 
    if ((i = CT(ifront, *fwd)) > 0) 
      { ifront = i; }
    else 
      { break; }
    }

  /* If the scan completed, then i = ifront & iback = cos, and we'll fall
  right through and check for a coincidence (i.e., has ifront cycled back
  to cos or not?).  Else, there's a hole & a backward scan is required. */

  if (i == 0)
    {
    for (bwd = end; bwd >= fwd; bwd--) 
      {
      j  = *bwd; 
      ji =  invcol[j]; 

      if ((i = CT(iback, ji)) > 0) 
        { iback = i; }
      else                    /* Scan stalled */
        {
        if (bwd == fwd)
          {
          /* The backward scan has only one gap, so note the deduction to
          complete the cycle. */

          CT(iback, ji) = ifront; 
          if (save) 
            { SAVED(iback, ji); }

          /* Since bwd == fwd and there was a hole, then either 
          CT(ifront,j) is still 0, or it has been set by a `backward'
          definition (particularly if j's an involution).  If it has been
          set (on-the-fly, so to speak), we need to setup correctly for a 
          possible coincidence. */
 
          if (CT(ifront,j) > 0)
            { ifront = CT(ifront,j); }    /* May be a coincidence here */
          else
            {
            CT(ifront,j) = iback;
            ifront = iback;         /* Prevent false coincidence */
            }

          INCR(apdedn);
          }
        else if (defn)              /* Define a new coset */
          {
          /* Note that, if j is an involution, and occurs next to itself,
          then after the first defn, the remainder of the string of j's
          will close.  Note that if j^2 = 1 & j is _not_ being treated as
          an involution, then `removing' it is a Tietze transformation, not
          a free reduction! */

          if (nextdf > maxrow)            /* Overflow */
            { return(0); }
          NEXTC(k); 
          CT(iback,ji) = k;  
          CT(k,j) = iback; 
          if (save) 
            { SAVED(iback,ji); }
          iback = k;
          INCR(apdefn);

          if (msgctrl && --msgnext == 0)
            {
            msgnext = msgincr;
            ETINT;
            fprintf(fop, "AD: a=%d r=%d h=%d n=%d;", 
                         nalive, knr, knh, nextdf);
            MSGMID;
            fprintf(fop, " m=%d t=%d\n", maxcos, totcos);
            BTINT;
            }
          } 
        else 
          { return(-1); }           /* New coset definition disabled */
        }
      }
    }

  /* If we get here, the scan has been completed.  Check to see if we've
  found a pair of coincident cosets. */
 
  if (ifront != iback)
    {
    INCR(apcoinc);
    if ((i = al0_coinc(ifront,iback,save)) > 0)
      { return(i); } 
    }

  return(-1);
  }

      /******************************************************************
      static int al0_rl(int first, int last, Logic saved)

      Do an R-style lookahead from coset #first up to #last.  We return 
      -1 if nothing exciting happens and >=1 if we get a finite `index' 
      (ie, collapse to 1).  `Approx.' complexity is rl or rl^2.  Note 
      that this (incl. its call to _coinc) does _not_ alter knr/knh, 
      although in may `invalidate' them.   Lookahead _never_ makes _new_ 
      definitions (so, it never overflows), but it may stack deductions,
      if requested.
      ******************************************************************/

static int al0_rl(int first, int last, Logic saved)
  {
  int row,rel,i,ii,j,k,l;
  int *pj, *pk, *fwd, *bwd;
  int ifront, iback;

  for (row = first; row <= last; row++)
    {
    if (COL1(row) >= 0)
      {
      for (rel = 1; rel <= ndrel; rel++)
        {
        j = (mendel ? rellen[rel]/relexp[rel] : 1);
        for (k = 0; k < j; k++)
          {
          pj = &(relators[relind[rel]+k]);
          pk = pj + rellen[rel]-1;

  /* <-- cancel indent; the code here is essentially al0_apply(). */

  ifront = iback = row;

  for (fwd = pj; fwd <= pk; fwd++) 
    { 
    if ((l = CT(ifront, *fwd)) > 0) 
      { ifront = l; }
    else 
      { break; }
    }

  if (l == 0)
    {
    for (bwd = pk; bwd >= fwd; bwd--) 
      {
      i  = *bwd; 
      ii =  invcol[i]; 

      if ((l = CT(iback, ii)) > 0) 
        { iback = l; }
      else if (bwd == fwd)
        {
        CT(iback, ii) = ifront; 
        if (saved) 
          { SAVED(iback, ii); }

        /* Since we're _not_ making definitions, there is no need to check
        if CT(ifront,i) is still undefined.  The _only_ case where it's
        not is if ifront=iback & i=ii; ie, i's an involution & we've just 
        deduced that ifront.i=ifront.  So, we may set CT(ifront,i) twice,
        but that's rare & does no damage, and is cheaper than checking. */

        CT(ifront, i) = iback;

        INCR(rldedn);
        goto next_k;
        }
      else 
        { goto next_k; }
      }
    }

  if (ifront != iback)
    {
    INCR(rlcoinc);
    if ((l = al0_coinc(ifront,iback,saved)) > 0)
      { return(l); } 
    }

  /* --> restore indent */

          if (COL1(row) < 0)        /* We've become redundant */
            { goto next_row; }

          next_k:
            ;
          }
        }
      }
    next_row:
      ;                             /* Prevent non-ANSII warning */
    }

  return(-1);
  }

        /******************************************************************
        static int al0_cl(int first, int last, Logic saved)

        Do a C-style `lookahead' over all the entries in the table from
      row #first to row #last inclusive; ie, treat it as a deduction 
      stack.  We may, or may not, save deductions, depending as we're in 
      R-style or C-style.  Returned value & comments as for al0_rl().  
      `Approx.' complexity is rcl.
        ******************************************************************/

static int al0_cl(int first, int last, Logic saved)
  {
  int row,col,beg,end,i,j,ji,k;
  int *pj, *pk, *fwd, *bwd;
  int ifront, iback;

  for (row = first; row <= last; row++)
    {
    if (COL1(row) >= 0)
      {
      for (col = 1; col <= ncol; col++)
        {
        if (CT(row,col) > 0)
          {
          if ((beg = edpbeg[col]) >= 0)
            {
            end = edpend[col];
            for (i = beg; i <= end; i += 2)
              {
              pj = &(relators[edp[i]]);
              pk = pj + edp[i+1]-1;

  /* <-- cancel indent; the code here is essentially al0_apply(). */

  ifront = iback = row;

  for (fwd = pj; fwd <= pk; fwd++) 
    { 
    if ((k = CT(ifront, *fwd)) > 0) 
      { ifront = k; }
    else 
      { break; }
    }

  if (k == 0)
    {
    for (bwd = pk; bwd >= fwd; bwd--) 
      {
      j  = *bwd; 
      ji =  invcol[j]; 

      if ((k = CT(iback, ji)) > 0) 
        { iback = k; }
      else if (bwd == fwd)
        {
        CT(iback, ji) = ifront; 
        if (saved) 
          { SAVED(iback, ji); }
        CT(ifront, j) = iback;

        INCR(cldedn);
        goto next_i;
        }
      else 
        { goto next_i; }
      }
    }

  if (ifront != iback)
    {
    INCR(clcoinc);
    if ((k = al0_coinc(ifront,iback,saved)) > 0)
      { return(k); } 
    }

  /* --> restore indent */

              if (COL1(row) < 0)        /* We've become redundant */
                { goto next_row; }

              next_i:
                ;
              }
            }
          }
        }
      }
    next_row:
      ;                                 /* Prevent non-ANSII warning */
    }

  return(-1);
  }

      /******************************************************************
      static int al0_rdefn(int cnt, Logic fillr, Logic saved)

      Start scanning through the relators at coset knr, making 
      definitions as necessary to close the scans.  If coset knr closes 
      against all relators, we fill any empty slots in its row (if fillr 
      is set), bump knr up, and loop round to process the next row.  On 
      overflow we return 0 (leaving knr unchanged & the row only 
      partially scanned) and on a finite index we return nalive.  Up to
      cnt rows will be scanned (either completely or partially).  If 
      nothing `exciting' happens, we return -1.  Deductions are stacked 
      if saved is true.  If cnt <0 then an infinite number of rows will 
      be scanned (so we'll get an index or overflow).  We try as far as 
      possible to exit with complete rows scanned, so we do not continue 
      scanning after we've processed cnt rows (although the next active 
      row could close without any definitions required, or, in fact, we 
      could have finished without knowing it).

      Note that a finite index is only correct if the table has no holes.
      If we get knr = nextdf & there are holes, then one option open to
      the control logic is to set knr to 1, and then rerun _rdefn() with 
      fillr set to fill the holes.  (Of course, this _isn't_ what we
      actually do in this situation, since a holy-table is precisely
      what we'd expect if some of the generators don't appear in any of 
      the relators!)
      ******************************************************************/

static int al0_rdefn(int cnt, Logic fillr, Logic saved)
  {
  int i, j, k, l, m, mi, n;
  int *beg, *end, *fwd, *bwd;
  int col, ifront, iback;

  INCR(xrdefn);

  /* Count current knr up if it's redundant and/or get an index.  Note, we
  check nextdf _first_ so that COL1(knr) (ie, CT(knr,1)) is defined. */

  while (knr < nextdf && COL1(knr) < 0)
    { knr++; } 
  if (knr == nextdf)
    { return(nalive); }

  while (cnt != 0)
    {
    /* Scan through all relators for this coset.  The code here is 
    essentially the same as that in al0_apply.  We inline for speed (and 
    flexibility; the code's not _exactly_ the same). */

    for (i = 1; i <= ndrel; i++)
      {
      j = (mendel ? rellen[i]/relexp[i] : 1);
      for (k = 0; k < j; k++)
        {

  /* <-- cancel indent */

  /* Setup start & stop positions for scan, and the coset at the current
  scan positions. */

  beg = &(relators[relind[i]+k]);
  end = beg-1 + rellen[i];
  ifront = iback = knr;

  /* Forward scan, leaving ifront set to coset at left of leftmost hole in
  relator or to the last coset in the relator if no hole. */

  for (fwd = beg; fwd <= end; fwd++) 
    { 
    if ((l = CT(ifront, *fwd)) > 0) 
      { ifront = l; }
    else 
      { break; }
    }

  /* If the scan completed, then l = ifront & iback = cos, and we'll fall
  right through and check for a coincidence (i.e., has ifront cycled back
  to cos or not?).  Else, there's a hole & a backward scan is required. */

  if (l == 0)
    {
    for (bwd = end; bwd >= fwd; bwd--) 
      {
      m  = *bwd; 
      mi =  invcol[m]; 

      if ((l = CT(iback, mi)) > 0) 
        { iback = l; }
      else                              /* Scan stalled */
        {
        if (bwd == fwd)
          {
          /* The backward scan has only one gap, so note the deduction to
          complete the cycle & prime for coincidence check. */

          CT(iback, mi) = ifront; 
          if (saved) 
            { SAVED(iback, mi); }

          if (CT(ifront, m) > 0)
            { ifront = CT(ifront, m); }
          else
            {
            CT(ifront, m) = iback;
            ifront = iback;
            }

          INCR(rddedn);
          }
        else                              /* Need to define a new coset  */
          {
          /* Note that, if m is an involution, and occurs next to itself,
          then after the first defn, the remainder of the string of m's
          will close.  Note that if m^2 = 1 & m is _not_ being treated as
          an involution, then `removing' it is a Tietze transformation, not
          a free reduction! */

          if (nextdf > maxrow)            /* Overflow */
            { return(0); }

          NEXTC(n);                 /* Making a definition ... */

          CT(iback,mi) = n;
          CT(n,m) = iback;
          if (saved)
            { SAVED(iback,mi); }
          iback = n;                /* Advance to next spot */

          INCR(rddefn);

          if (msgctrl && --msgnext == 0)
            {
            msgnext = msgincr;
            ETINT;
            fprintf(fop, "RD: a=%d r=%d h=%d n=%d;",
                         nalive, knr, knh, nextdf);
            MSGMID;
            fprintf(fop, " m=%d t=%d\n", maxcos, totcos);
            BTINT;
            }
          }
        }
      }
    }

  /* If we get here, the scan has been completed.  Check to see if we've
  found a pair of coincident cosets.  Recall that _coinc (if it does not
  return >0) is guaranteed _not_ to change knc/knh, although it may render
  them redundant. */
 
  if (ifront != iback)
    {
    INCR(rdcoinc);
    if ((l = al0_coinc(ifront,iback,saved)) > 0)
      { return(l); } 
    if (COL1(knr) < 0)
      { goto do_next; }             /* knr now redundant */
    }

  /* --> restore indent */

        }
      }

    /* All relators close at this coset, any row-filling to do?  Only 
    (formally) necessary if some g/G does _not_ appear in any relator,
    but it's usually a good thing to do. */

    if (fillr)
      {
      for (i = 1; i <= ncol; i++)
        {
        if (CT(knr,i) == 0)
          {
          if (nextdf > maxrow)          /* Overflow */
            { return(0); }

          NEXTC(k);                 /* Make definition */
          CT(knr,i) = k;
          CT(k,invcol[i]) = knr;
          if (saved)
            { SAVED(knr,i); }

          INCR(rdfill);

          if (msgctrl && --msgnext == 0)
            {
            msgnext = msgincr;
            ETINT;
            fprintf(fop, "RF: a=%d r=%d h=%d n=%d;",
                         nalive, knr, knh, nextdf);
            MSGMID;
            fprintf(fop, " m=%d t=%d\n", maxcos, totcos);
            BTINT;
            }
          }
        }
      }

    /* Row knr is fully scanned (or redundant), so we adjust knr up, 
    jumping over any redundancies & checking to see if we've finished.  We
    have also used up one of our allowed rows, if there's a limit. */

    do_next:                  /* from al0_coinc(): knr redundant */

    do
      { knr++; }
    while (knr < nextdf && COL1(knr) < 0);

    if (knr == nextdf)
      { return(nalive); }

    if (cnt > 0)
      { cnt--; }
    }

  return(-1);                 /* `normal' termination */
  }

      /******************************************************************
      static int al0_cdefn(int cnt)

      Repeatedly process any outstanding deductions and make definitions
      until: we get a finite result (return > 0), we get an overflow
      (return 0), or we've defined cnt new cosets (return -1).  If cnt
      is zero then we make no definitions, simply clearing the deduction 
      stack.  If cnt < 0 there's no limit on the number of definitions.
      ******************************************************************/

static int al0_cdefn(int cnt)
  {
  int icol, rcol, irow, ires, k, col, pdqr, pdqc;
  int first, last, i, ifront, iback, l, m, mi;
  int *beg, *end, *fwd, *bwd;
  Logic fi;

  INCR(xcdefn);

  while(TRUE)
    {
    /* Process all outstanding deductions on the stack */

    while (topded >= 0)
      {
      INCR(cddproc);

      irow = dedrow[topded];
      icol = dedcol[topded--];
      if (COL1(irow) < 0)
        { 
        INCR(cdddedn);
        continue;       /* coset has become redundant */
        }
      else
        {
        ires = CT(irow,icol);
        rcol = invcol[icol];
        }
      
      fi = TRUE;        /* first pass through */

      proc_ded:               /* entry point for second pass through */

      if ((first = edpbeg[icol]) >= 0)
        {
        last = edpend[icol];
        for (i = first; i <= last; i += 2)
          {
          beg = &(relators[edp[i]]);
          end = beg + edp[i+1]-1;

  /* <-- cancel indent */

  /* We scan this e.d.p. against irow.  We don't need to scan the first
  position, since we _know_ it must be ok.  We have to set l, in case the
  relator has length precisely one! */

  ifront = l = ires;
  iback  = irow;

  /* Forward scan, leaving ifront set to coset at left of leftmost hole in
  relator or to the last coset in the relator if no hole. */

  for (fwd = beg+1; fwd <= end; fwd++) 
    { 
    if ((l = CT(ifront, *fwd)) > 0) 
      { ifront = l; }
    else 
      { break; }
    }

  /* If the scan completed, ifront = l > 0 & iback = irow, and we'll fall
  right through and check for a coincidence (i.e., has ifront cycled back
  to irow or not?).  Else, there's a hole & a backward scan is required. */

  if (l == 0)
    {
    for (bwd = end; bwd >= fwd; bwd--)
      {
      m  = *bwd; 
      mi =  invcol[m];

      if ((l = CT(iback, mi)) > 0) 
        { iback = l; }
      else                              /* Scan stalled */
        {
        if (bwd == fwd)
          {
          /* The backward scan has only one gap, so note the deduction to
          complete the cycle. */

          CT(iback, mi) = ifront; 
          CT(ifront, m) = iback;
          SAVED(iback, mi);
          INCR(cddedn); 
          }
        else if (bwd == fwd + 1)    /* gap of length = 1 */
          {
          INCR(cdgap);

          /* In pdefn = 1 or 2 mode make definition immediately, if fill-
          factor permits, there's space & it's allowed.  If not, do 
          nothing.  Note that we can handle the deduction from this 
          definition at this stage, or not (it'll come out in a later pass
          through the loop), depending as pdefn = 1 or 2.  In general,
          these strategies blow out the count of total cosets, although 
          making definitions immediately is quicker than storing them on 
          the pdq & making them later, so pdefn=1/2 has a higher 
          `throughput'; whether this compensates for the larger totcos
          figure is moot! */

          switch(pdefn)
            {
            case 1:
            if (cnt != 0 && nextdf <= maxrow && 
                 (float)(knh-1)*ffactor >= (float)(nextdf-1) )
              {
              NEXTC(k);
              CT(iback, mi) = k;
              CT(k, m) = iback;
              SAVED(iback, mi);
              if (cnt > 0)
                { cnt--; }          /* used an `allowed' definition */
              INCR(cdidefn);

              if (msgctrl && --msgnext == 0)
                {
                msgnext = msgincr;
                ETINT;
                fprintf(fop, "CG: a=%d r=%d h=%d n=%d;",
                             nalive, knr, knh, nextdf);
                MSGMID;
                fprintf(fop, " m=%d t=%d\n", maxcos, totcos);
                BTINT;
                }
              }
            break;

            case 2:
            if (cnt != 0 && nextdf <= maxrow && 
                 (float)(knh-1)*ffactor >= (float)(nextdf-1) )
              {
              NEXTC(k);
              CT(iback, mi) = k;
              CT(k, m) = iback;
              SAVED(iback, mi);
              if (cnt > 0)
                { cnt--; }          /* used an `allowed' definition */
              INCR(cdidefn);
            
              CT(ifront,*fwd) = k;
              CT(k,invcol[*fwd]) = ifront;
              SAVED(ifront,*fwd);
              INCR(cdidedn);

              if (msgctrl && --msgnext == 0)
                {
                msgnext = msgincr;
                ETINT;
                fprintf(fop, "CG: a=%d r=%d h=%d n=%d;",
                             nalive, knr, knh, nextdf);
                MSGMID;
                fprintf(fop, " m=%d t=%d\n", maxcos, totcos);
                BTINT;
                }
              }
            break;

            case 3:                 /* store definition on pdq */
            pdqrow[botpd] = iback;
            pdqcol[botpd] = mi;
            INCR(cdpdl);
            if ((botpd = NEXTPD(botpd)) == toppd)
              {
              toppd = NEXTPD(toppd);
              INCR(cdpof);
              }
            break;
            }
          }

        iback = ifront;             /* prevents a false coincidence */
        break;
        }
      }
    }

  /* At this stage, if ifront != iback, then either the initial forward
  scan did not cycle back to irow, or a backward scan produced a mismatch;
  in either case, we have found a coincidence. In all other cases ifront =
  iback has been enforced, to prevent problems. */

  if (iback != ifront)
    {
    /* We do _not_ return an index at this stage if _coinc() returns a +ve
    value, since there may still be deductions to process (which might
    _decrease_ nalive).  We do, however, detect if the current rows have
    become redundant.  Currently, the only finite value returned by
    _coinc() is 1, on a total collapse.  This clears the dedn stack, so
    we'll drop out of the while(topded>=1) loop immediately & then drop
    out of this function with an index of 1.  */

    INCR(cdcoinc);
    al0_coinc(ifront,iback,TRUE);
    if (COL1(irow) < 0 || COL1(ires) < 0)
      { goto next_ded; }
    }

  /* --> restore indent */

          }
        }

      /* Do we have to do a second pass? */

      if (fi && (irow != ires || icol != rcol))
        {
        SWAP(irow,ires);
        SWAP(icol,rcol);
        fi = FALSE;
        goto proc_ded;
        }

      /* End of processing this deduction, loop back to next deduction.  We
      also jump here if current deduction becomes redundant. */

      next_ded:
        ;

#ifdef AL0_DD
      if (msgctrl && --msgnext == 0)
        {
        msgnext = msgincr;
        ETINT;
        fprintf(fop, "DD: a=%d r=%d h=%d n=%d;", nalive, knr, knh, nextdf);
        MSGMID;
        fprintf(fop, " d=%d\n", topded+1);
        BTINT;
        }
#endif
      }

    /* Find next empty position (& maybe finish). */

    for ( ; knh < nextdf; knh++) 
      {
      if (COL1(knh) >= 0) 
        {
        for (icol = 1; icol <= ncol; icol++)
          {
          if (CT(knh, icol) == 0) 
            { goto hfill; }
          }
        }
      }
    return(nalive);           /* coset table is complete */

    /* Try to fill the next hole in the table */

    hfill:

    if (cnt == 0)       /* `normal' termination, since */
      { return(-1); }         /*   done all requested definitions */
    else
      {                       
      /* Do we have space to make a definition?  If not, return overflow.
      If yes, prime the next sequential position & get its row number. */

      if (nextdf > maxrow)
        { return(0); }        /* unable to make definition */
      NEXTC(k);               /* ready for definition ... */

      /* We try to make a preferred definition, if possible.  If we do,
      fi is set TRUE. */

      fi = FALSE;       
      if ( pdefn == 3 && toppd != botpd
             && (float)(knh-1)*ffactor >= (float)(nextdf-1) )
        {
        pdqr = pdqrow[toppd];
        pdqc = pdqcol[toppd];
        while (COL1(pdqr) < 0 || CT(pdqr,pdqc) != 0)
          {
          INCR(cdpdead);
          if ((toppd = NEXTPD(toppd)) == botpd)
            { break; }
          pdqr = pdqrow[toppd];
          pdqc = pdqcol[toppd];
          }

        if (toppd != botpd)
          {
          toppd = NEXTPD(toppd);
          CT(pdqr,pdqc) = k;
          CT(k,invcol[pdqc]) = pdqr;
          SAVED(pdqr,pdqc);
          fi = TRUE;
          INCR(cdpdefn);

          if (msgctrl && --msgnext == 0)
            {
            msgnext = msgincr;
            ETINT;
            fprintf(fop, "CP: a=%d r=%d h=%d n=%d;",
                         nalive, knr, knh, nextdf);
            MSGMID;
            fprintf(fop, " m=%d t=%d\n", maxcos, totcos);
            BTINT;
            }
          }
        }

      /* If no preferred definition made, fill next hole. */

      if (!fi)
        {
        CT(knh,icol) = k;
        CT(k,invcol[icol]) = knh;
        SAVED(knh,icol);
        INCR(cddefn);

        if (msgctrl && --msgnext == 0)
          {
          msgnext = msgincr;
          ETINT;
          fprintf(fop, "CD: a=%d r=%d h=%d n=%d;",
                       nalive, knr, knh, nextdf);
          MSGMID;
          fprintf(fop, " m=%d t=%d\n", maxcos, totcos);
          BTINT;
          }
        }

      if (cnt > 0)            /* keep track, if there's a limit */
        { cnt--; }
      }
    }
  }

      /******************************************************************
      static int al0_rpefn(int cnt, Logic fill)
      ******************************************************************/

#include "enum01.c"

      /******************************************************************
      Pull in the state machine.
      ******************************************************************/

#include "enum00.c"

      /******************************************************************
      int al0_enum(int mode, int style)

      mode 0 : start enumeration (from row 1 of zeroed table)
           1 : continue enumeration (from current row of current table)
           2 : redo enumeration (from row 1 of current table)

      style 0 : R/C           HLT until overflow, then CR-style
            1 : R*            R-style + dedn stacking/processing
            2 : Cr            1 pass Felsch, 1 pass HLT, then C-style
            3 : reserved      Level 1: C* (?!)
            4 : reserved      Level 1: defaulted R/C
            5 : C       Felsch strategy
            6 : Rc            1 pass HLT, 1 pass Felsch, then R-style
            7 : R       HLT strategy
            8 : CR            alternate Felsch & HLT passes

      We can `start' at any time.  We can `redo' at any time provided 
      that any changes to the presentation are confined to _adding_ 
      group relators or subgroup generators.  We can `continue' only if 
      we have made _no_ changes to the presentation (& even if we already
      have a finite index).  The rfactor/cfactor parameters must be set 
      correctly (ie, >0) for the `style' of this call; they can be 0 (or 
      even <0), but this may cause weirdness (although some intriguing 
      things become possible). 

      return >1 : non-trivial finite index
              1 : index of 1 (? collapse in coincidence processing)
              0 : overflow
           -256 : incomplete table (ie, unfilled positions)
           -257 : hole limit exceeded
           -258 : time limit exceeded
           -259 : iteration (loops) limit exceeded
           -260 : overflow during SG phase
           -512 : disallowed mode
           -513 : disallowed style
           -514 : disallowed mode/style combination (not used yet))
          -4096 : invalid machine state (aka reality failure)
          -4097 : invalid finite result (aka reality failure)
      ******************************************************************/

int al0_enum(int mode, int style)
  {
  int state, action, result;  /* The current state, action & result. */
  Logic isave;                /* Save definitions/deductions on stack? */
  static Logic rhfree;        /* Table guaranteed hole-free (R-style)? */
  static Logic cdapp;         /* All definitions applied (C-style)? */
  int i,j,k;                  /* temp ints / indices */
  int *pj, *pk;               /* temp pointers */
  Logic li;             /* temp booleans */

  /* Start up the timing for this call.  Prime the message counter (if
  required), initialise the stats package (if macro is defined), and zero
  the loop count. */

  totaltime = 0.0;
  begintime = al0_clock();
  if (msgctrl)
    { msgnext = msgincr; }
  STATINIT;
  lcount = 0;

  /* Check mode, style, and their combination. */

  if (mode < 0 || mode > 2)
    {
    result = -512;
    goto tail_tail;
    }
  if (style < 0 || style > 8 || style == 3 || style == 4)
    {
    result = -513;
    goto tail_tail;
    }

  /* Do the appropriate setup for the requested mode.  Note that we _never_
  preserve pd's between calls, and there are _never_ outstanding coincs
  at a call's exit (so we don't actually need to zero chead/ctail, but we
  do anyway!).  We may, or may not, preserve deduction stack, entries in
  the table and the various `progress' counters. */

  toppd = botpd = 0;
  chead = ctail = 0;

  switch(mode)
    {
    case 0:                   /* start; ie, a new run */

      topded = -1;
      disded = FALSE;

      for (i = 1; i <= ncol; i++) 
        { CT(1, i) = 0; }

      nalive = maxcos = totcos = 1;
      knr    = knh    = 1;
      nextdf = 2;

      sgdone = FALSE;               /* SG not (successfully) run yet */
      rhfree = cdapp = TRUE;        /* prime for this new run */
    
    break;

    case 1:                   /* continue */

      ;

    break;
    
    case 2:                   /* redo */

      topded = -1;
      disded = FALSE;

      knr = knh = 1;

      sgdone = FALSE;

    break;
    }

  /* The static variable rhfree is primed to true at the start of every run
  (ie, start mode), and retains its value across a sequence of continue &
  redo commands until the next start.  Any time we could _potentially_ do 
  any R-style applying without filling rows, we toggle it to false.  This 
  indicates that the table _may_ contain holes, and that the al0_upknh() 
  routine may need to be called before a finite index (due to knr = nextdf)
  is returned.  Any code anywhere which could cause empty table slots 
  should take care to ensure that rhfree is false (eg, adaptive mode code).
  Since rhfree is only invoked when checking a finite result due to knr = 
  nextdf, its value if we get a result due to knh=nextdf is of no concern
  (here, the table is hole-free, since that's what knh means!).

  Instead of trying to be clever, and keeping a close watch on what the
  value of this should be at each point, we simply reset it at the start of
  any call(s) where the rfill control parameter is false.  The cost of 
  running _upknh() is no more than that of row-filling (although it's
  concentrated in one `lump'), since all table positions are checked in 
  both cases.  In fact, it will usually be less, since we can start the
  check at knh, we need not check rows that have become redundant, and we
  make no definitions.  Note that, even if row-filling is not needed (to
  obtain a finite index), it may still be beneficial to turn it on, since
  it may alter the definition sequence. */

  if (!rfill)
    { rhfree = FALSE; }

  /* Do the appropriate setup for the requested style.  Our main concern
  is whether or not to stack defns/dedns (isave flag) so that these can be
  tested against all edp, for C-style enumerations.  We also have to track
  whether or not we have done this over the course of an entire run; we use
  the cdapp flag for this.  This flag is similar in concept to the rhfree
  one, but is more difficult to manage, since it is `more expensive' to get
  it `wrong'.  Furthermore, saving & applying dedns is a 3-stage process, 
  and cdapp only tracks the first step.

  cdapp is static, and is primed to true.  Any time we _may_ make any table
  entries _without_ stacking them, we toggle it to false.  Whether or not
  the stacking (call to SAVED()) was successful is monitored by the global
  disded flag.  Whether or not all the stacked dedns have been processed is
  determined by the stack size (the global topded).  If knh=nextdf and all
  three stages were successful (ie, cdapp=TRUE & disded=FALSE & topded==-1)
  then the result is valid.  If not, then the actual index may be smaller
  than the `current' one (ie, nalive).  Since our table is guaranteed hole-
  free at this stage, the quickest check is to run an R-style scan (with 
  definitions & deduction stacking both off!) to move knr up to nextdf,
  perhaps finding some coincs along the way; this RA phase is the default
  action.

  The settings below prime isave & cdapp for the styles.  However, finer 
  control is needed since, for example, a (successful) CL phase forces
  cdapp back to true (provided further dedns _will_ be stacked (ie, isave
  is true)).  We use the switch at the end of the state machine's main
  loop to do this.  Note that we must be careful, since we can exit at any
  time and we must ensure that the status is valid for any continues or
  redos.  We err on the side of caution, so the RA phase may be done when
  it is not (formally) required.

  Note that in some styles we don't save deductions initially, since we do
  a C-style table lookahead at the point where we switch from R-style to 
  C-style (which effectively forces cdapp to true).  (We could also insist
  that _all_ dedns _are_ applied, and do a C-style lookahead at any point
  where we detect `missed' dedns.)  Of course, if the dedn stack is large
  enough, then we'll never lose dedn's; but we could end up having to
  process _very_ large dedn stacks, which can be expensive. */

  switch(style)
    {
    case 0:
      isave = FALSE;
      cdapp = FALSE;
    break;

    case 1:
      isave = TRUE;
    break;

    case 2:
      isave = TRUE;
    break;

    case 5:
      isave = TRUE;
    break;

    case 6:
      isave = FALSE;
      cdapp = FALSE;
    break;

    case 7:
      isave = FALSE;
      cdapp = FALSE;
    break;

    case 8:
      isave = TRUE;
    break;
    }

  /* Combine the style with the mode into the machine's starting state.  
  Prime machine with `dummy'/`null' action & `success' result. */

  state = 1 + 9*mode + style;

  action = 0;
  result = -1;

  /* THE MACHINE ... */

  while (TRUE)
    {
    lcount++;

    /* Advance to the next state and perform the requested action. */

    /* DEBUG/TEST/TRACE */ /*
    fprintf(fop, "DTT: lcount=%d; state=%d action=%d result=%d", 
                       lcount,    state,   action,   result);
    */

    action = al0_act[state][-result];
    state  =  al0_st[state][-result];

    /* DEBUG/TEST/TRACE */ /*
    fprintf(fop, " --> state=%d action=%d\n", state, action);
    */

    switch(action)
      {

  /* <-- cancel indent */

  /* The null action; allows timing tests, progress messages, etc. */

  case 0:
  result = -1;
  break;

  /* Make some R-style definitions.  al0_rdefn() can return -1 (`nothing'
  happened), 0 (unable to make definition), or >0 (finite result).  Note 
  that _all_ finite `index' return values are `filtered' through the check
  phase (action #6), to prevent `problems'. */

  case 1:

  if ((result = al0_rdefn(rfactor, rfill, isave)) > 0)
    { result = -2; }

  break;

  /* Perform lookahead, in R-style _only_, if enabled.  This lookahead is 
  used when we run out of table space, and it could allow us to continue
  _without_ running a compaction.  However, we elect not to detect this
  state of affairs in the current version.  Instead, we'll _always_ try to
  compact, and we'll check after doing that whether or not there's any 
  space available in the table (however it was obtained!).  Note that 
  lookahead (& any coincidence processing) does _not_ alter nextdf or knr/
  knh (except in the collapse to 1 case, of course), although it may render
  them redundant.  Since this is a _lookahead_ only, there is never any 
  need to stack deductions.  We don't try to trap an invalid lahead value.
  If we don't recognise it, we just quietly do nothing.

  Note that we can be as `sloppy' as we wish, in the sense that all we
  require is one or more coincs to free up some table space.  The current
  options all look only for immediate consequences of the current table,
  and don't worry about consequent consequences.  There are a great variety
  of other ways to do lookahead.  For example: we could repeatedly run 
  _rl() until there's no further improvement; or we could bail out early,
  after a burst of `significant' progress or if we're achieving 
  `nothing'. */

  case 2:

  switch(lahead)
    {
    case 1:
      result = al0_rl(knr, nextdf-1, FALSE);
      if (msgctrl)
        {
        msgnext = msgincr;          /* start new count */
        ETINT;
        fprintf(fop, "L1: a=%d r=%d h=%d n=%d;", nalive, knr, knh, nextdf);
        MSGMID;
        fprintf(fop, " m=%d t=%d\n", maxcos, totcos);
        BTINT;
        }
      break;
    case 2:
      result = al0_cl(1, nextdf-1, FALSE);
      if (msgctrl)
        {
        msgnext = msgincr;
        ETINT;
        fprintf(fop, "L2: a=%d r=%d h=%d n=%d;", nalive, knr, knh, nextdf);
        MSGMID;
        fprintf(fop, " m=%d t=%d\n", maxcos, totcos);
        BTINT;
        }
      break;
    case 3:
      result = al0_rl(1, nextdf-1, FALSE);
      if (msgctrl)
        {
        msgnext = msgincr;
        ETINT;
        fprintf(fop, "L3: a=%d r=%d h=%d n=%d;", nalive, knr, knh, nextdf);
        MSGMID;
        fprintf(fop, " m=%d t=%d\n", maxcos, totcos);
        BTINT;
        }
      break;
    case 4:
      result = al0_cl(knr, nextdf-1, FALSE);
      if (msgctrl)
        {
        msgnext = msgincr;
        ETINT;
        fprintf(fop, "L4: a=%d r=%d h=%d n=%d;", nalive, knr, knh, nextdf);
        MSGMID;
        fprintf(fop, " m=%d t=%d\n", maxcos, totcos);
        BTINT;
        }
      break;
    default:
      result = -1;
      break;
    }

  if (result > 0)
    { result = -2; }

  break;

  /* Perform compaction (any style) if it's allowed & then check whether 
  the table has any space left.  If so, then continue, else return 
  overflow.  Note that compaction does _not_ alter nalive, but may change
  (reduce) knr/knh/nextdf.  It makes `free' space _available_, but it does
  not _create_ it; coincidences (normal, or in lookahead) do that. */

  case 3:

  if (nalive >= maxrow)
    {
    result = 0;
    goto tail_tail;
    }
  else if ( (double)(nextdf-1 - nalive)/(double)(nextdf-1) 
              >= (double)comppc/100.0 )
    {
    al0_compact();
    if (msgctrl)
      {
      msgnext = msgincr;
      ETINT;
      fprintf(fop, "CO: a=%d r=%d h=%d n=%d;", nalive, knr, knh, nextdf);
      MSGMID;
      fprintf(fop, " m=%d t=%d\n", maxcos, totcos);
      BTINT;
      }
    }

  if (nextdf <= maxrow)
    { result = -1; }
  else 
    {
    result = 0;
    goto tail_tail;
    }

  break;

  /* Do some C-style definitions / deduction processing.  al0_cdefn() can 
  return -1 (`nothing' happened), 0 (unable to make definition), or >0 
  (finite result - potential index, needs checking).  */

  case 4:

  if ((result = al0_cdefn(cfactor)) > 0)
    { result = -2; }

  break;

  /* Do a C-style complete table lookahead.  This is run when we're
  switching styles from R- to C-style, or when we're `starting' C-style
  with an already existing table.  Since we maybe haven't being processing 
  definitions, we need to run through the entire table.  We treat each
  table entry as a deduction and stack any new deductions.  A subsequent
  C-style defn/dedn pass will clear the stack, as usual; we can now enter
  C-style, and be confident of any C-style result.

  Actually, calling this lookahead is a misnomer.  It more correctly might
  be thought of as either a `check' (when we have a finite result but 
  cannot guarantee that all definitions have been processed, or when we
  call the enumerator in the redo mode) or a `prime' (when we're switching
  to C-style) phase. */

  case 5:

  if ((result = al0_cl(1, nextdf-1, TRUE)) > 0)
    { result = -2; }
  if (msgctrl)
    {
    msgnext = msgctrl;
    ETINT;
    fprintf(fop, "CL: a=%d r=%d h=%d n=%d;", nalive, knr, knh, nextdf);
    MSGMID;
    fprintf(fop, " m=%d t=%d\n", maxcos, totcos);
    BTINT;
    }

  break;

  /* We have a finite result; triggered by knr=nextdf, knh=nextdf, or a
  collapse to 1 in coinc processing.  Check that it's a valid index; it may
  be a multiple, or the table may have holes.  If knr=nextdf, then all
  relators close against all cosets, so we need only check whether or not
  the table has any holes.  If knh=nextdf, then the table is hole-free, so
  we need to check that all table entries have been scanned in all edp.
  Note that we have to check for a `clean' C-style termination _before_ we
  may bump knh; this is an artifact of the overloading of knh's meaning. */

  case 6:

  if (knr == nextdf && rhfree)
    { ; }                     /* ok, fall through */
  else if (knh == nextdf && cdapp && !disded && topded < 0)
    { ; }                     /* ok, fall through */
  else if (knr == nextdf)
    {
    al0_upknh();              /* check for holes ... */
    if (msgctrl)
      {
      msgnext = msgctrl;
      ETINT;
      fprintf(fop, "UH: a=%d r=%d h=%d n=%d;", nalive, knr, knh, nextdf);
      MSGMID;
      fprintf(fop, " m=%d t=%d\n", maxcos, totcos);
      BTINT;
      }
    if (knh < nextdf)               /* ... table is incomplete */
      { 
      result = -256;
      goto tail_tail;
      }
    }
  else if (knh == nextdf)
    {
    /* Apply all remaining cosets.  Note that knh=nextdf, so there are no
    holes & no defns will (can!) be made.  Since we are only interested in
    moving knr up to nextdf (perhaps finding coincs), we turn mendel off; 
    if it's on (& left on), it can cause a dramatic slow-down. */

    li = mendel;
    mendel = FALSE;
    al0_rdefn(-1,FALSE,FALSE);
    mendel = li;

    if (msgctrl)
      {
      msgnext = msgctrl;
      ETINT;
      fprintf(fop, "RA: a=%d r=%d h=%d n=%d;", nalive, knr, knh, nextdf);
      MSGMID;
      fprintf(fop, " m=%d t=%d\n", maxcos, totcos);
      BTINT;
      }
    }
  else
    {                   /* fatal error (ie, can't happen!) */
    result = -4097;
    goto tail_tail;
    }

  result = nalive;
  goto tail_tail;

  break;                      /* not really needed! */

  /* If start or redo, scan & close the subgroup generators on coset #1.  
  Note that we can get coincidences, or collapses, or overflows here.  We 
  treat an overflow as fatal, and return a special value (-260) to alert 
  the caller to the fact that the subgroup generators have not been fully 
  processed (so we _must_ (re)start, we can't continue).  Note that knr =
  knh = 1 here, and they are _not_ changed (we do no scanning against the 
  relators, so they can't go up, and coset 1 is never redundant).  Thus the
  only finite index we can get is a collapse to 1, and this is a valid 
  result.

  Note that closing subgroup generators against coset 1 is done R-style, in
  that we (maybe) stack up definitions/deductions for later action, and
  make as many definitions as required to (immediately) fill any empty
  relator table positions.  If the enumeration is a (pure) C-style one, we
  should process each definition (ie, stacked deduction) _immediately_, 
  since we should only make definitions if there's nothing else we can do.
  For the moment, we don't worry about his `complication'.

  As this phase _must_ be successfully completed before a continue is
  allowed, and it need not be the 1st phase (it can be the 2nd in redo), a
  time/hole/loop limit could cause an early return.  So we make sure the
  sgdone flag is correctly (re)set at all times. */

  case 7:

  if (nsgpg > 0)
    {
    for (i = 1; i <= nsgpg; i++)
      {
      pj = &(subggen[subgindex[i]]);
      pk = pj-1 + subglength[i];

      if ((result = al0_apply(1,pj,pk,TRUE,isave)) >= 0)
        { break; }
      }

    if (msgctrl)
      {
      msgnext = msgincr;
      ETINT;
      fprintf(fop, "SG: a=%d r=%d h=%d n=%d;", nalive, knr, knh, nextdf);
      MSGMID;
      fprintf(fop, " m=%d t=%d\n", maxcos, totcos);
      BTINT;
      }

    sgdone = TRUE;
    if (result == 0)
      {
      result = -260;
      sgdone = FALSE;
      goto tail_tail;
      }
    else if (result > 0)
      { result = -2; }
    }
  else
    { 
    result = -1;        /* `default' result */
    sgdone = TRUE;            /* ok, since nothing to do! */
    }

  break;

  /* If start or redo (modes 0/2) and in an appropriate style (ie, 1st step
  will be a C-style scan), and requested (nrinsgp > 0), then scan & close
  the first nrinsgp group relators against coset 1.  Similar comments to 
  those for the subgroup generators apply here, although an overflow does
  _not_ force a restart here. */

  case 8:

  if (nrinsgp > 0)
    {
    for (i = 1; i <= nrinsgp; i++)
      {
      j = (mendel ? rellen[i]/relexp[i] : 1);
      for (k = 0; k < j; k++)
        {
        pj = &(relators[relind[i]+k]);
        pk = pj-1 + rellen[i];

        if ((result = al0_apply(1,pj,pk,TRUE,isave)) >= 0)
          { break; }
        }

      if (result >= 0)
        { break; }
      }

    if (msgctrl)
      {
      msgnext = msgincr;
      ETINT;
      fprintf(fop, "RS: a=%d r=%d h=%d n=%d;", nalive, knr, knh, nextdf);
      MSGMID;
      fprintf(fop, " m=%d t=%d\n", maxcos, totcos);
      BTINT;
      }

    if (result > 0)
      { result = -2; }
    }
  else
    { result = -1; }          /* `default' result */

  break;

  /* Do some R*-style definitions / deduction processing.  al0_rpefn() can 
  return -1 (`nothing' happened), 0 (unable to make definition), or >0 
  (finite result - potential index, needs checking).  Note the row-filling
  argument and the fact that we don't use (need?) isave, since dedn
  stacking is mandatory here. */

  case 9:

  if ((result = al0_rpefn(rfactor, rfill)) > 0)
    { result = -2; }

  break;

  /* If we get here, something's a touch awry. */

  default:
  result = -4096;
  goto tail_tail;

  /* --> restore indent */

      }                       /* end of "switch(action)" */

    /* At this point, we have just completed action in state, and are about
    to `leave' state via one of its exit paths (selected by the (state,
    result) pair).  Now is the time to perform any action specific to this
    point.  Note that the checks for the various limits (times, holes, ...)
    are done _after_ this, so we're guaranteed that the (updated) status 
    will be correct on any `early' exit. */

    switch(state)
      {
      case 32:
        if (result == -1)
          { cdapp = TRUE; }
        break;
      case 38:
        if (result == -1)
          { cdapp = TRUE; }
        break;
      case 45:
        if (result == 0)
          { isave = TRUE; }
        break;
      case 46:
        if (result == -1)
          { cdapp = TRUE; }
        break;
      case 47:
        if (result == -1)
          { cdapp = TRUE; }
        break;
      case 55:
        if (result == -1)
          { cdapp = TRUE; }
        break;
      case 56:
        if (result == -1)
          { cdapp = TRUE; }
        break;
      case 58:
        if (result == -1 || result == 0)
          { cdapp = FALSE; }
      case 59:
        if (result == -1)
          { cdapp = TRUE; }
        break;
      }

    /* Only calculate % holes if requested, since it's expensive!  We only
    treat the value as significant if we've actually defined some cosets 
    other than #1!  We ignore the case where nalive=1 and not all #1's row 
    entries are 0 (ie, some, but not necessarily all, are 1 instead). */

    if (hlimit >= 0 && nalive > 1)
      {
      if (al0_nholes() >= (double)hlimit)
        {
        result = -257;
        break;
        }
      }

    /* We have to correctly find the total accumulated time, without 
    disturbing any messaging (which must always print the elapsed time 
    since the last message).  So we _can't_ use the ETINT/BTINT macros. */

    if (tlimit >= 0)
      {
      if ((totaltime + al0_diff(begintime,al0_clock())) >= (double)tlimit)
        {
        result = -258;
        break;
        }
      }

    /* Any loop limit in force? */

    if (llimit > 0 && lcount >= llimit)
      {
      result = -259;
      break;
      }

    }                   /* end of "while(TRUE)" */

  /* We've either jumped here (finite result, overflow, error), or we've
  broken out the main loop (time / holes / iterations limit).  We simply
  update the total time for this call & return the `status'. */

  tail_tail:

  endtime    = al0_clock();
  totaltime += al0_diff(begintime,endtime);

  return(result);
  }


Generated by  Doxygen 1.6.0   Back to index