gb_games.w

模拟器提供了一个简单易用的平台

  struct node_struct *hash_link; /* pointer to next \.{ABBR} in hash list */
  Vertex *vert; /* vertex corresponding to this team */
} node;

@ The data in \.{games.dat} appears in two parts. The first 120 lines
have the form
$$\hbox{\tt ABBR College Name(Team Nickname)Conference;a0,u0;a1,u1}$$
and they give basic information about the teams. An internal abbreviation code
\.{ABBR} is used to identify each team in the second part of the data.

The second part presents scores of the games, and it
contains two kinds of lines. If the first character of a line is
`\.>', it means ``change the current date,'' and the remaining
characters specify a date as a one-letter month code followed by the day
of the month. Otherwise the line gives scores of a game, using the
\.{ABBR} codes for two teams. The scores are separated by `\.@@' if
the second team was the home team and by `\.,' if both teams were on
neutral territory.

For example, two games were played on December 8, namely the annual Army-Navy
game and the California Raisin Bowl game. These are recorded in three lines
of \.{games.dat} as follows:
$$\vbox{\halign{\tt#\hfil\cr
>D8\cr
NAVY20@@ARMY30\cr
SJSU48,CMICH24\cr}}$$
We deduce that Navy played at Army's home stadium, losing 20 to~30;
moreover, San Jos\'e State played Central Michigan on neutral territory and
won, 48 to~24. (The California Raisin Bowl is traditionally a playoff between
the champions of the Big West and Mid-American conferences.)

@ In order to map \.{ABBR} codes to team names, we use a simple
hash coding scheme. Two abbreviations with the same hash address are
linked together via the |hash_link| address in their node.

The constants defined here are taken from the specific data in \.{games.dat},
because this routine is not intended to be perfectly general.

@d HASH_PRIME 1009

@<Private v...@>=
static long ma0=1451,mu0=666,ma1=1475,mu1=847;
             /* maximum poll values in the data */
static node *node_block; /* array of nodes holding team info */
static node **hash_block; /* array of heads of hash code lists */
static Area working_storage; /* memory needed only while |games| is working */
static char **conf_block; /* array of conference names */
static long m; /* the number of conference names known so far */

@ @<Read the first part of \.{games.dat} and compute team weights@>=
node_block=gb_typed_alloc(MAX_N+2,node,working_storage);
 /* leave room for string overflow */
hash_block=gb_typed_alloc(HASH_PRIME,node*,working_storage);
conf_block=gb_typed_alloc(MAX_N,char*,working_storage);
m=0;
if (gb_trouble_code) {
  gb_free(working_storage);
  panic(no_room+1); /* nowhere to copy the data */
}
if (gb_open("games.dat")!=0)
  panic(early_data_fault); /* couldn't open |"games.dat"| using
        GraphBase conventions; |io_errors| tells why */
for (k=0; k<MAX_N; k++) @<Read and store data for team |k|@>;

@ @<Read and store...@>=
{@+register node *p;
  register char *q;
  p=node_block+k;
  if (k) p->link=p-1;
  q=gb_string(p->abb,' ');
  if (q>&p->abb[6] || gb_char()!=' ')
    panic(syntax_error); /* out of sync in \.{games.dat} */
  @<Enter |p->abb| in the hash table@>;
  q=gb_string(p->name,'(');
  if (q>&p->name[24] || gb_char()!='(')
    panic(syntax_error+1); /* team name too long */
  q=gb_string(p->nick,')');
  if (q>&p->nick[22] || gb_char()!=')')
    panic(syntax_error+2); /* team nickname too long */
  @<Read the conference name for |p|@>;
  @<Read the press poll scores for |p| and compute |p->key|@>;
  gb_newline();
}

@ @<Enter |p->abb| in the hash table@>=
{@+long h=0; /* the hash code */
  for (q=p->abb;*q;q++)
    h=(h+h+*q)%HASH_PRIME;
  p->hash_link=hash_block[h];
  hash_block[h]=p;
}

@ @<Read the conference name for |p|@>=
{
  gb_string(str_buf,';');
  if (gb_char()!=';') panic(syntax_error+3); /* conference name clobbered */
  if (strcmp(str_buf,"Independent")!=0) {
    for (j=0;j<m;j++)
      if (strcmp(str_buf,conf_block[j])==0) goto found;
    conf_block[m++]=gb_save_string(str_buf);
 found:p->conf=conf_block[j];
  }
}

@ The key value computed here will be between 0 and~$2^{31}$, because of
the bound we've imposed on the weight parameters.

@<Read the press poll scores for |p| and compute |p->key|@>=
p->a0=gb_number(10);
if (p->a0>ma0 || gb_char()!=',') panic(syntax_error+4);
  /* first AP score clobbered */
p->u0=gb_number(10);
if (p->u0>mu0 || gb_char()!=';') panic(syntax_error+5);
  /* first UPI score clobbered */
p->a1=gb_number(10);
if (p->a1>ma1 || gb_char()!=',') panic(syntax_error+6);
  /* second AP score clobbered */
p->u1=gb_number(10);
if (p->u1>mu1 || gb_char()!='\n') panic(syntax_error+7);
  /* second UPI score clobbered */
p->key=ap0_weight*(p->a0)+upi0_weight*(p->u0)
        +ap1_weight*(p->a1)+upi1_weight*(p->u1)+0x40000000;

@ Once all the nodes have been set up, we can use the |gb_linksort|
routine to sort them into the desired order. It builds 128
lists from which the desired nodes are readily accessed in decreasing
order of weight, using random numbers to break ties.

We set the abbreviation code to zero in every team that isn't chosen. Then
games involving that team will be excluded when edges are generated below.
 
@<Determine the |n| teams to use in the graph@>=
{@+register node *p; /* the current node being considered */
  register Vertex *v=new_graph->vertices; /* the next vertex to use */
  gb_linksort(node_block+MAX_N-1);
  for (j=127; j>=0; j--)
    for (p=(node*)gb_sorted[j]; p; p=p->link) {
      if (v<new_graph->vertices+n) @<Add team |p| to the graph@>@;
      else p->abb[0]='\0'; /* this team is not being used */
    }
}

@ @<Add team |p| to the graph@>=
{
  v->ap=((long)(p->a0)<<16)+p->a1;
  v->upi=((long)(p->u0)<<16)+p->u1;
  v->abbr=gb_save_string(p->abb);
  v->nickname=gb_save_string(p->nick);
  v->conference=p->conf;
  v->name=gb_save_string(p->name);
  p->vert=v++;
}

@* Arcs.
Finally, we read through the rest of \.{games.dat}, adding a pair of
arcs for each game that belongs to the selected time interval
and was played by two of the selected teams.

@<Put the appropriate edges into the graph@>=
{@+register Vertex *u,*v;
  register long today=0; /* current day of play */
  long su,sv; /* points scored by each team */
  long ven; /* |HOME| if |v| is home team, |NEUTRAL| if on neutral ground */
  while (!gb_eof()) {
    if (gb_char()=='>') @<Change the current date@>@;
    else gb_backup();
    u=team_lookup();
    su=gb_number(10);
    ven=gb_char();
    if (ven=='@@') ven=HOME;
    else if (ven==',') ven=NEUTRAL;
    else panic(syntax_error+8); /* bad syntax in game score line */
    v=team_lookup();
    sv=gb_number(10);
    if (gb_char()!='\n') panic(syntax_error+9);
      /* bad syntax in game score line */
    if (u!=NULL && v!=NULL && today>=first_day && today<=last_day)
      @<Enter a new edge@>;
    gb_newline();
  }
}

@ @<Change the current...@>=
{@+register char c=gb_char(); /* month code */
  register long d; /* day of football season */
  switch(c) {
  case 'A': d=-26;@+break; /* August */
  case 'S': d=5;@+break; /* thirty days hath September */
  case 'O': d=35;@+break; /* October */
  case 'N': d=66;@+break; /* November */
  case 'D': d=96;@+break; /* December */
  case 'J': d=127;@+break; /* January */
  default: d=1000;
  }
  d+=gb_number(10);
  if (d<0 || d>MAX_DAY) panic(syntax_error-1); /* date was clobbered */
  today=d;
  gb_newline(); /* now ready to read a non-date line */
}

@ @<Private f...@>=
static Vertex *team_lookup() /* read and decode an abbreviation */
{@+register char *q=str_buf; /* position in |str_buf| */
  register long h=0; /* hash code */
  register node *p; /* position in hash list */
  while (gb_digit(10)<0) {
   *q=gb_char();
   h=(h+h+*q)%HASH_PRIME;
   q++;
  }
  gb_backup(); /* prepare to re-scan the digit following the abbreviation */
  *q='\0'; /* null-terminate the abbreviation just scanned */
  for (p=hash_block[h];p;p=p->hash_link)
    if (strcmp(p->abb,str_buf)==0) return p->vert;
  return NULL; /* not found */
}

@ We retain the convention of {\sc GB\_\,GRAPH} that the arc from |v| to |u|
appears immediately after a matching arc from |u| to |v| when |u<v|.

@<Enter a new edge@>=
{@+register Arc *a;
  if (u>v) {@+register Vertex *w; register long sw;
    w=u;@+u=v;@+v=w;
    sw=su;@+su=sv;@+sv=sw;
    ven=HOME+AWAY-ven;
  }
  gb_new_arc(u,v,su);
  gb_new_arc(v,u,sv);
  a=u->arcs; /* a pointer to the new arc */
  if (v->arcs!=a+1) panic (impossible+9); /* can't happen */
  a->venue=ven;@+(a+1)->venue=HOME+AWAY-ven;
  a->date=(a+1)->date=today;
}

@* Index. As usual, we close with an index that
shows where the identifiers of \\{gb\_games} are defined and used.