util0.c Colin Ramsay (cram@itee.uq.edu.au) 20 Dec 00
ADVANCED COSET ENUMERATOR, Version 3.001
Copyright 2000 Centre for Discrete Mathematics and Computing, Department of Mathematics and Department of Computer Science & Electrical Engineering, The University of Queensland, QLD 4072. (http://staff.itee.uq.edu.au/havas)
/****************************************************************** We seem to need sys/types.h & time.h (for the system call time()). On other flavours of Unix, we might need sys/time.h.
******************************************************************/
Gets the system date/time, and converts it to ASCII string. Note that this includes a trailing '\n'.
******************************************************************/
char *al0_date(void)
{
time_t t = time(NULL); return ctime(&t);
}
clock() returns the actual cpu time used, in seconds, since this process started. It's equivalent to the `user' time in the `time' system command. Type clock_t is usually defined as a (signed) long, but seems to actually be a 32-bit unsigned - we try our best to preserve all information over a variety of machines! Note that 64-bit machines may sign extend, hence the truncation. CLOCKS_PER_SEC (usually 1000000, but may be 100 on a PC) converts clock() to seconds. Note that, even if CLOCKS_PER_SECOND > 100, resolution may only be 10mS (i.e., 100Hz system clock).
******************************************************************/
We assume that c1/c2 are values from al0_clock(). This routine finds the difference between two times, by assuming that either 0 or 1 `overflow' has taken place. double's are used for all timing to allow (long) times to be properly processed. Provided that the run is `short' (w.r.t. to the normal rollover interval of 71m35s) or that progress messages are output `frequently', then the difference will be correct. On long runs with few messages, then the difference may be incorrect.
******************************************************************/
One-off initialisation of the Level 0 stuff. Ensures a valid initial state, and sets defaults (default setting is roughly equivalent to the "def" option of Level 2). Does _not_ allocate / free memory, so it's up to the user (in practice, usually the Level 1 wrapper routines) to make sure memory's allocated and to properly free it to prevent memory leakage. It's not really necessary to set _everything_ here, but we do anyway, since we adhere to the P^3 Principle (ie, paranoia prevents problems)!
******************************************************************/
Remove unused rows from the coset table, by closing up all used rows to the front. (This is _not_ the same as putting the table into its canonic form!) To maintain data-structure consistency, the pdq is cleared & any stored deductions/coincidences should be discarded. The pdq entries don't matter, but throwing away unprocessed deductions or coincidences is _not_ a good thing. It is the _caller's_ responsibility to ensure that this routine isn't called when there are outstanding deductions/coincidences or, if it is, that `appropriate' action is taken. We return TRUE if we actually did any compaction, else FALSE.
In fact, we fully process all coincidences immediately. So, outside of the coincidence processing routine, the coinc queue is always empty. Since al0_compact isn't called during coincidence handling, we're ok there. As for deductions, we _could_ work thro the queue repeatedly as we compact, resetting the stored coset numbers to their adjusted values, but we don't (v. expensive). We just throw any outstanding deductions away, noting this in disded. We worry later (if we get a finite result) about whether or not we have to do any extra work to check whether this cavalier attitude was `justified'.
Note that this routine is called `on-the-fly' by some of the Level 2 options. It can also be called directly by the rec[over] option.
******************************************************************/
Logic al0_compact(void)
{ int i, j, irow, col; int knra, knha;
/* Table is already compact, do nothing. */ if (nalive == nextdf-1)
{ return(FALSE); }
/* Clear any preferred definitions on their queue. */
toppd = botpd = 0;
This companion programme to _compact() puts the table into standard form. This form is based on the order of the generators in the table, but is otherwise fixed for a given group/subgroup; it's independant of the details of an enumeration. It allows canonic rep'ves to be picked off by back-tracing (see al1_bldrep()). We chose _not_ to combine _stdct() & _compact() into one routine, since the core enumerator may compact (more than once) & we don't want to impact it's speed with `unnecessary' work. After an enumeration completes, a single call of _compact() & then of _stdct() gives a hole-free, standardised table. We can standardise holey-tables, but the result is only unique up to the set of coset labels in use.
Similar remarks to those in _compact() regarding pdefns, dedns, coincs, etc., etc. apply here. We return true if we actually change anything, else false. We do the work in two stages, since we want to avoid (possibly) throwing away dedns if we can avoid it. Note that we have to do some work even if the table is already standardised, since there is no quick way to check this. However, the termination condition is next=nextdf, and this occurs generally before we scan up to row=nextdf,
******************************************************************/
next = 1; do
{ next++; } while (next < nextdf && COL1(next) < 0);
if (next == nextdf)
{ return(FALSE); } /* table is in standard form */
/* Find 1st non-std entry, if it exists */
for (row = 1; row < nextdf; row++)
{ if (COL1(row) >= 0)
{ for (col = 1; col <= ncol; col++)
{ if ((cos = CT(row,col)) > 0)
{ if (cos < next)
{ ; } /* ok */ elseif (cos == next)
{ /* new next value; maybe finish */ do
{ next++; } while (next < nextdf && COL1(next) < 0); if (next == nextdf)
{ return(FALSE); }
} else
{ goto non_std; } /* table is non-std */
}
}
}
}
return(FALSE); /* Table is standard. Never get here ?! */
non_std:
/* Table is non-std, so we'll be changing it. Clear the preferred definition queue, and throw away (after logging) any outstanding
deductions. */
toppd = botpd = 0;
if (topded >= 0)
{
disded = TRUE;
topded = -1;
}
/* Now work through the table, standardising it. For simplicity, we
`continue' the loops used above, restarting the inner (column) loop. */
for ( ; row < nextdf; row++)
{ if (COL1(row) >= 0)
{ for (col = 1; col <= ncol; col++)
{ if ((cos = CT(row,col)) > 0)
{ if (cos < next)
{ ; } elseif (cos == next)
{ do
{ next++; } while (next < nextdf && COL1(next) < 0); if (next == nextdf)
{ return(TRUE); }
} else
{ /* At this point, cos > next and we have to swap these rows. Note that all entries in rows <row are <next, and will not be effected. We process x/X pairs in one hit (to prevent any nasties), so we skip over any 2nd (in order) occurrence of a generator. Warning: trying to understand this code can cause
wetware malfunction! */
On flute, this processes `active' rows at ~ 5.10^6 entries/sec. Note the use of knh to cut down the amount of work as much as possible. Can be called by the TBA option of Level 2? Worst-case complexity, in terms of the number of table accesses, is r(c+1); where r/c are the number of rows/cols in the table.
Warning: possible int overflow of k for large tables.
******************************************************************/
double al0_nholes(void)
{ int i,j,k;
k = 0; for (i = knh; i < nextdf; i++)
{ if (COL1(i) >= 0)
{ for (j = 1; j <= ncol; j++)
{ if (CT(i,j) == 0)
{ k++; }
}
}
}
Counts knh up to the next incomplete row, skipping redundants. We either bail out at an empty table slot, or reach nextdf. During an enumeration knh is maintained by C-style, due to its overloaded meaning (ie, knh & knc). If we can't guarantee that the table is hole-free in an R-style finite result, we have to run this check to make sure. Worst-case complexity is r(c+1).
Note: this should not be called carelessly during an enumeration, since it is important that knh-based C-style hole filling & deduction stacking / processing are done together, due to the overloading of knh's meaning & the fact that it triggers a finite result if it hits nextdf. This should really only be called when we _know_ we have a finite result (to check whether the table is hole-free), or when we _know_ that all definitions have been applied (perhaps in a C-style lookahead).
******************************************************************/
void al0_upknh(void)
{ int col;
for ( ; knh < nextdf; knh++)
{ if (COL1(knh) >= 0)
{ for (col = 1; col <= ncol; col++)
{ if (CT(knh,col) == 0)
{ return; }
}
}
}
}
/****************************************************************** void al0_dedn(int cos, int gen)
Handling the deduction stack is a pain. The best option, in many cases, seems to be to throw deductions away if we get too many at any one time (where `too many' can be quite `small', eg, <1000), and run an "RA:" or a "CL:" check. However, dedmode #4 (which is the default) allows a special stack-handling function to be called if we try to stack a deduction & can't.
Currently, in this mode our aim is _never_ to lose any deductions, so we expand the stack space to accomodate the new element. We take the opportunity to eliminate redundancies from the stack. The code is essentially that used in dedmod #2 in _coinc() (which emulates ACE2).
Note the messaging code, since we're interested in what the stack actually `looks' like when it overflows! Some ad hoc tests show that redundancies are common (in collapses). Duplicates (incl. `inverted' duplicates) are not, and it's expensive to process these, so we don't bother trying to track them.
Warning: this is the _only_ place in the core enumerator where we make a system call (apart from o/p & date calls; if these fail we've got real problems), and it's one which could fail. There is _no_ mechanism in ACE Level 0 for handling these sorts of errors, so we do the best we can to recover. Note also that there is no cap on the amount of space which we'll (try to) allocate; so this could all come crashing down in a heap!
******************************************************************/
void al0_dedn(int cos, int gen)
{ int i,j; int dead = 0;
dedsiz *= 2; /* Best way to go? */ if ( (dedrow = (int *)realloc(dedrow, dedsiz*sizeof(int))) == NULL ||
(dedcol = (int *)realloc(dedcol, dedsiz*sizeof(int))) == NULL )
{ /* Our attempt to allocate more space failed, and we lost the existing stack. Print out a nasty message (if messaging is on), and tidy up. Note that the enumerator works correctly with dedsiz=0, but discards
_all_ deductions (& does so forever, since 2*0 = 0!). */
if (msgctrl)
{ fprintf(fop, "DS: Unable to grow, all deductions discarded\n"); }
return;
}
/* Is is actually _worth_ doing this? In a big collapse, the proportion of coinc dedns can be high; but these are skipped over when encountered in _cdefn(), so why go to the expense of a (linear) pass & data move. It might keep the stack size down and prevent one doubling, so we have a time vs mempry trade-off (maybe). We could also be cleverer, and move non-redundants from the top to redundant slots at the bottom, cutting the
number of data moves. */
j = -1;
i = 0; while (i <= topded && COL1(dedrow[i]) >= 0)
{ j++; i++; } for ( ; i <= topded; i++)
{ if (COL1(dedrow[i]) >= 0)
{
dedrow[++j] = dedrow[i];
dedcol[j] = dedcol[i];
} else
{ dead++; } /* Track no. redundancies discarded. */
}
topded = j;
/* Now add the original cause of the problem. There's no need to check for an overflow, since we're guaranteed to have enough space at this point. Note however that we do need to take care to update sdmax
correctly if the stats package is on. */
Dump out the internals of Level 0 of ACE, working through al0.h more or less in order. We could do more here in terms of pretty- printing the data; or we could introduce further arguments controlling the level of detail; or we could incorporate checks for consistency; or ensure that this is only called when there's valid data; or ... These are left as exercises for the reader; the output is intended for debugging, and obscurity & information overload are part of the game!
******************************************************************/
¤ Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.0.40Bemerkung:
(vorverarbeitet)
¤
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung ist noch experimentell.
