dmh@mit-borax.ARPA (David Harmon) (04/17/86)
Nice timing...Steve Summit's letter about jumping into blocks arrived
just as I had finished debugging a routine which I actually wrote in Pascal
and just translated into C for practice. You guessed it, it jumps into a loop,
and I honestly don't think there is a way to avoid the goto without some VERY
ugly code to keep track of the program's state. The problem is that I need
to print out all the elements of a set capable of containing or not containing
any value from 0..255. (In Pascal, a SET OF 0.255) That in itself would
be no problem given the IN operator, but I also wanted to contract adjacent
members of a set into a range syntax. Assume that the include file "nastydefs"
contains the definitions of the set type and in() function. Can any of you
figure out a way to do this elegantly without the goto? Especially this may
involve the break or continue statements...I have looked at possibilities but
I must admit I probably don't know a lot of tactics involving them.
Also, with an appropriate include file, this procedure both compiles and
passes lint.
Dave Harmon
dmh@mit-borax.arpa
dmh@borax.lcs.mit.edu
/* Assume the existence of a type named "set", which is intended to simulate
the Pascal TYPE KeySet:SET OF 0..255;
Further assume the existence of a function
in(e,l);
set *l;
char e;
which returns a boolean 1 iff _e_ is an element of _*l_.
*/
#include <stdio.h>
#include "/usr/dmh/nastydefs"
wrtlist (listp)
set *listp;
/*This routine should print out a list of the members of List, with adjacent
members shown contracted as N-M, where N and M are the bounds of a range of
members. Notice the GOTO statement which gives the effect of two *crossed*
loops with a Write and a conditional increment shared by both. Note that
the potential member 0 is not used by the application.
*/
#define MAX NUM_KEYWORDS /*The highest element in use by the application*/
{
unsigned char i;
set list;
i=0;
list= *listp;
do {
putchar(' ');
do {
if (i=MAX)
return(0);
else
i++;
}
while (in(i,&list));
cross: /*Beginning of GOTO Loop and shared section*/
printf("%d",i);
if (i=MAX)
return(0);
else
i++;
}
while (in(i,&list));
putchar('-');
while ( (i<MAX) && (in(i+1,&list) ) )
i++;
goto cross; /*End of GOTO Loop*/
} /*WriteKList*/franka@mmintl.UUCP (Frank Adams) (04/19/86)
In article <69@brl-smoke.ARPA> dmh@mit-borax.ARPA writes: > > Nice timing...Steve Summit's letter about jumping into blocks arrived >just as I had finished debugging a routine which I actually wrote in Pascal >and just translated into C for practice. You guessed it, it jumps into a >loop, and I honestly don't think there is a way to avoid the goto without >some VERY ugly code to keep track of the program's state. It just takes one variable, and isn't ugly at all. /* Assume the existence of a type named "set", which is intended to simulate Further assume the existence of a function in(e,l); set *l; char e; which returns a boolean 1 iff _e_ is an element of _*l_. */ #include <stdio.h> #include "/usr/dmh/nastydefs" wrtlist (listp) set *listp; /*This routine should print out a list of the members of List, with adjacent members shown contracted as N-M, where N and M are the bounds of a range of members. Notice the absence of any GOTO statements */ #define MAX NUM_KEYWORDS /*The highest element in use by the application*/ #define NONE -1 { unsigned char i; set list; int last = NONE; /* last is the start of the current string of consecutive members, or -1 if not in such a string */ /* loop through the possible elements of the set, seeing which are in it */ for (i = 0; i <= MAX; i += 1) { if (in(i, &list)) { /* element of set; if not in a sequence, start one */ if (last = NONE) last = i; } else { /* not an element; output preceding sequence, if any */ putrange(last, i-1); last = NONE; } } /* output sequence at end of possible range, if any */ putrange(last, MAX); return; } /* This routine outputs a sequence of consecutive elements in the set. There are three cases: 1) the sequence has no elements. In this case, start will be -1, and nothing should be output 2) the sequence has a single element. In this case, start will equal end, and should be output. 3) the sequence has more than one element. In this case, start should be output, followed by a dash, then end. */ static void putrange(start, end) int start, end; { if (start != NONE) { printf(" %d", start); if (start != end) { printf("-%d", end); } } return; } There. That's not only better structured than your program, it's shorter. Disclaimer: I have not attempted to compile the above program, nor run it through lint. It may, therefore, contain errors. Frank Adams ihnp4!philabs!pwa-b!mmintl!franka Multimate International 52 Oakland Ave North E. Hartford, CT 06108
jpn@teddy.UUCP (John P. Nelson) (04/19/86)
>Can any of you >figure out a way to do this elegantly without the goto? Wow! That code was UGLY! How about this: #include "nastydefs" #define MAX NUM_KEYWORDS /* This routine should print out a list of the members of List, with adjacent * members shown contracted as N-M, where N and M are the bounds of a range of * members. */ wrtlist(listp) register set *listp; { register int i; /* scan entire set */ for (i = 1; i < MAX; ++i) /* note: could just as easily start at 0 */ { if (in(i, listp)) { /* this is the start of a run (potential 1 element run) */ printf("%d", i); /* check for two in a row */ if (++i < MAX && in(i, listp)) { /* at least two in the run - scan to the end */ for (++i; i < MAX; ++i) if (!in(i, listp)) break; printf("-%d", i - 1); } } /* current i is known to NOT be in the set */ } } I assumed that the "in" function was expensive - any element is only checked ONCE. The secret is that the outermost level loop index is modified. A version with an auxiliary index is also possible, which is possibly slightly cleaner.
guido@boring.UUCP (04/19/86)
Dave Harmon obviously doesn't know C and didn't bother to test the C
version of his example: it contains i=MAX instead of i==MAX and
while(in(..)) instead of while(!in(...)) -- the latter no doubt stemming
from a slavish translation of Pascal's until <condition>.
Nevertheless, his problem is not one that's solved better with the use
of goto's. Here's my code (tested -- it didn't need debugging :-).
wrtlist(s) set *s; {
int count= 0; /* Counts elements in range currently being printed */
int e;
for (e= 0; e <= MAX; ++e) {
if (in(e, s)) {
if (count == 0)
printf(" %d", e);
++count;
}
else {
if (count > 1) printf("-%d", e-1);
count= 0;
}
}
}
--
Guido van Rossum, CWI, Amsterdam <guido@mcvax.UUCP>chris@umcp-cs.UUCP (Chris Torek) (04/20/86)
In article <6879@boring.UUCP> guido@mcvax.UUCP (Guido van Rossum) writes: >Here's my code (tested -- it didn't need debugging :-). Oh? What does yours print when all elements (0 through MAX inclusive) are members of the set? (Your code works if MAX is beyond the last member of the set and `in' handles an out-of-range value; but you did not say whether that was indeed the case.) -- In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 1415) UUCP: seismo!umcp-cs!chris CSNet: chris@umcp-cs ARPA: chris@mimsy.umd.edu
HARGED%ti-eg.csnet@CSNET-RELAY.ARPA (04/21/86)
To Dave Harmon:
I've got a couple of comments about the code you posted to the net
last week.
I wish you had compiled and run the code you posted. There are some
vestigal remnants of its previous incarnation as a Pascal program that keep
it from compiling and running correctly. Listed below is the version I used
in my tests.
/*************************************************************************/
static int wrtlist (list)
set list;
{
unsigned int i=0;
do {
putchar (' ');
do {
if (i == MAX) /* please note equality operator */
return (0);
else
i++;
}
while (!in (i, list)); /* both looping forms iterate */
/* when the condition is TRUE */
cross:
printf ("%d", i);
if (i == MAX)
return (0);
else
i++;
}
while (!in (i, list));
putchar ('-');
while ((i < MAX) && (in (i+1, list))) i++;
goto cross;
}
/*************************************************************************/
Below is a version I came up with that is structured; i.e. all control
constructs are single-entry, single-exit. Please note the absence of
boolean state variables.
/*************************************************************************/
static void wrtlist2 (list)
set list;
{
/* Scan the set represented by list, printing the members that
* are present. If two or more consecutive members are present
* then print them as a range represented by X-Y where X is
* the first member and Y is the last member of the range.
*/
unsigned int i=0;
while (i < MAX) { /* scan whole set */
if (in (i++, list)) { /* matching member found */
printf ("%d", i-1); /* print first member */
if (in (i, list)) { /* we have a range */
putchar ('-'); /* range seperator */
while (in (++i, list)); /* skip internal members */
printf ("%d", i-1); /* print last member */
}
i++; /* avoid redundant check */
putchar (' ');
}
}
}
/*************************************************************************/
Now for the comparison: using small-model Lattice C, v 2.14, on a
TI-PC, your routine compiled to a size of 0xCB bytes, mine 0xCC bytes.
While I didn't gather execution times, an informal analysis indicates that
both routines are a few assignments, comparisons, three calls to in (), and
calls to putchar and printf. Since the number of calls made to putchar and
printf are equl for both routines, they will be ignored. It appears that
the bulk of the remaining execution time will involve the calls to in ().
Therefore counting the number of calls to in () will give us a ballpark
estimate of the execution time differences. For a 100 element set with the
following members present [ 0 2 5-6 10-12 16-19 22-27 99 ] your routine
called in () 104 times, mine 101. I call the two routines even in terms of
size and execution speed.
Beyond this, I think my version has some added benifits. My version
can recognize member 0 of the set. I think my version is more intuitive; it
models the process a human would follow when doing the same thing. And
while I took advantage of the prefix/postfix ++ operators, the algorithm I
followed is very general (it doesn't require multiple return statements or
the ability to jump into a loop).
Please don't confuse me with a structured programming purist. I have
no problem using the goto in its many forms (i.e., at least single-entry,
mulitiple-exit control constucts) when the situation requires it. Just
remember that its use can cause problems for code optimizers, both human
and machine.
regards,
Richard Hargrove CSNET: harged@ti-eg
Texas Instruments, Inc. ARPA: harged%ti-eg@csnet-relay
----------------------- -------------------------------mouse@mcgill-vision.UUCP (der Mouse) (04/21/86)
In article <69@brl-smoke.ARPA>, dmh@mit-borax.ARPA (David Harmon) writes: > [...] I need to print out all the elements of a set capable of containing > or not containing any value from 0..255. > [...] but I also wanted to contract adjacent members of a set into a range > syntax. > > /* Assume the existence of a type named "set", which is intended to simulate > the Pascal TYPE KeySet:SET OF 0..255; > Further assume the existence of a function > in(e,l); > set *l; > char e; > which returns a boolean 1 iff _e_ is an element of _*l_. > */ > [48-line example, using obscure goto, deleted] I once wrote some code which did something similar; adapting this to your problem.... As far as I can tell from your code (it's not the easiest thing in the world to understand), you want spaces instead of commas. For example, you want 1 3 5-10 not 1,3,5-10 I am also taking the liberty of producing a leading space, that is, this code produces " 1 3 5-10" instead of "1 3 5-10" This can be fixed with two more lines (a boolean variable and some code to use it). This is only 26 lines (saving of 22), and it is understandable (by comparison). Five more lines can be trimmed out if you are willing to sacrifice a smidgen of speed by calling in() more often than is really necessary: - delete the declarations of isin and oldin - delete the initialization of oldin - delete the oldin=isin assignment - change these three lines { isin = (i==MAX) ? 0 : in(listp,i); if (isin != oldin) { if (isin) to these two { if (((i==MAX)?0:in(listp,i)) != ((i==0)?0:in(listp,i-1))) { if ((i==MAX)?0:in(listp,i)) The messy `?:' operators in the last change above (and in the original assignment to isin) can be eliminated if in() is guaranteed to return 0 for out-of-bounds values of e. Just replace the entire `?:' expression with the call to in() contained in the `else' part. Without further ado, here is the code: #define MAX NUM_KEYWORDS /*The highest element in use by the application*/ wrtlist(listp) set *listp; { int i; int j; int isin; int oldin; oldin = 0; for (i=0;i<=MAX;i++) { isin = (i==MAX) ? 0 : in(listp,i); if (isin != oldin) { if (isin) { printf(" %d",i); j = i; } else { if (j < i-1) { printf("-%d",i-1); } } } oldin = isin; } } -- der Mouse USA: {ihnp4,decvax,akgua,utzoo,etc}!utcsri!mcgill-vision!mouse philabs!micomvax!musocs!mcgill-vision!mouse Europe: mcvax!decvax!utcsri!mcgill-vision!mouse mcvax!seismo!cmcl2!philabs!micomvax!musocs!mcgill-vision!mouse ARPAnet: utcsri!mcgill-vision!mouse@uw-beaver.arpa Wizard: One who can find and fix bugs in an emergency (such as during a site visit by funding agencies).
jso@edison (04/30/86)
In respose to the program by > Dave Harmon > dmh@mit-borax.arpa > dmh@borax.lcs.mit.edu where he asks for a way to avoid a goto in his loop (translated from Pascal). How about something like..... #include <stdio.h> #include "/usr/dmh/nastydefs" #define MAX NUM_KEYWORDS /*The highest element in use by the application*/ wrtlist (listp) set *listp; { unsigned char i; set list; list = *listp; for (i=0; i <= MAX; i++) { if (in(i,&list)) { unsigned char save_i; printf(" %d",i); save_i = i; while (++i <= MAX && in(i,&list)) ; if (i > save_i + 1) printf("-%d",i-1); /* doesn't matter that we'll i++ here, since we know !in(i,&list) */ } } printf("\n"); return(0); } [No guarantees, but you get the idea.] John Owens edison!jso%virginia@CSNet-Relay.ARPA General Electric Company Phone: (804) 978-5726 Factory Automation Products Division Compuserve: 76317,2354 houxm!burl!icase!uvacs ...!{ decvax!mcnc!ncsu!uvacs }!edison!jso gatech!allegra!uvacs