static char acRcs[] =
    "$Id: power.c,v 1.2 2004/04/26 23:13:05 jzap Exp $";

#include <sys/types.h>
#include <sys/stat.h>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <malloc.h>
#include <string.h>

#define tPGM		"power"			/* program name */
#define nITER		20			/* default # of iterations */
#define nTEAM		30			/* # teams in league */
#define nGAME		82			/* # games played by each team */
#define nBUFBYT		5000			/* text-buffer size */
#define nRESCOL		3			/* # cols for printing results */

#define FINAL		1			/* regulation win */
#define F_OT		2			/* overtime win or tie */
#define F_OT_EN		3			/* empty-net ot win */

typedef FILE*		pFILE;
typedef char		*TEXT, **pTEXT;
typedef unsigned int	UINT, *pUINT, **ppUINT;

typedef struct attr	ATTR, *pATTR, **ppATTR;
typedef struct team	TM, *pTM, **ppTM;
typedef struct game	GM, *pGM, **ppGM;

/*
    struct attr can be any one of three attributes:  goals-for minus goals-against,
    points-for minus points-against, or points per game.  (see struct team.)
*/
struct attr
{   double	dAttr;				/* team's adjusted per-game attr */
    double	dAttrOpp;			/* opponents' average attribute */
    double	dAttrPrev;			/* team's attr from previous iter */
};

struct team
{   char	acName[ 4];			/* 3-char team abbr */
    int		iTeam;				/* index: 0 .. (nTEAM - 1) */
    int		nGame;				/* # games played by team */
    pGM		pgmHeadHome, pgmTailHome;	/* linked list of home games */
    pGM		pgmHeadAway, pgmTailAway;	/* linked list of away games */
    pATTR	pattr;				/* ptr to current attribute */
    ATTR	attrGfGa;			/* goals-for minus goals-against */
    ATTR	attrPfPa;			/* points-for minus points-against */
    ATTR	attrPpg;			/* points-per-game */
};

struct game
{   pTM		ptmHome, ptmAway;		/* ptrs to home, away teams */
    pGM		pgmNextHome;			/* link to home-team's next game */
    pGM		pgmNextAway;			/* link to away-team's next game */
    int		iGameNumLeague;			/* league game number 1 .. 1230 */
    int		iGameNumHome;			/* home-team's game # 1 .. 82 */
    int		iGameNumAway;			/* away-team's game # 1 .. 82 */
    int		nPointHome, nPointAway;		/* points for home & away teams */
    int		nGoalHome, nGoalAway;		/* goals by home & away teams */
    int		iGameDate;			/* eg, 20021225 for 2002 Dec 25 */
    int		iFinalOtEn;			/* final, f/ot, f/ot/en */
    double	dAttrHome;			/* attr (GF-GA, PF-PA, or PPG) ... */
    double	dAttrAway;			/* ... for home and away teams */
};

int			nGameGbl;		/* # games in score database */
int			nTeamGbl;		/* # teams w/ scores in database */
int			nIterGbl = nITER;	/* # iterations (cmd-line arg) */
pTM			aptmIndex[ nTEAM];	/* array of ptrs to team structs */
pTM			aptmHash[ 1 << (3 * 6)]; /* hash tbl allowing fast ... */
						/* ... lookup of team by abbr name */

double			dGameConst = 0.0;	/* "time const" (# games) for ... */
						/* ... exp derating (cmd-line arg) */
double			adWeight[ nGAME];	/* pre-computed exp-derating table */
double			dBiasExpGbl;		/* expected weighted-avg attr */
TEXT			tResModDate = "(unknown)";
pTEXT			ptResult;

/*
    Hash according to six bits <6,4:0> from each of the three characters
    in the team's name.  This should be a non-colliding hash.  The size
    of the hash table (above) is therefore 2 ^ (3 * 6) = 256K words = 1 MB.
    If team not found, allocate a new team struct and enter it into hash table.
*/
pTM
ptmHash(
    register TEXT	tTeam)		/* ptr to 3-char array (abbr team name) */
{   register UINT	uChar;		/* each char, registered for fast shifting */
    register UINT	uHash;		/* resulting hash value */
    pTM			ptm;		/* ptr to team struct */

    uChar = tTeam[ 0];
    uHash = (uChar & 0x40) >> 1;
    uHash |= uChar & 0x1F;
    uChar = tTeam[ 1];
    uHash <<= 6;
    uHash |= (uChar & 0x40) >> 1;
    uHash |= uChar & 0x1F;
    uChar = tTeam[ 2];
    uHash <<= 6;
    uHash |= (uChar & 0x40) >> 1;
    uHash |= uChar & 0x1F;

    ptm = aptmHash[ uHash];
    if( ptm)
	return ptm;

    ptm = malloc( sizeof( TM));
    bzero( ptm, sizeof( TM));
    strcpy( ptm->acName, tTeam);
    ptm->iTeam = nTeamGbl++;
    aptmIndex[ ptm->iTeam] = ptm;
    aptmHash[ uHash] = ptm;
    return ptm;
}

void
LinkGame(
    register pGM	pgm)
{   register pTM	ptmHome;
    register pTM	ptmAway;
    int			iTeamOpp;
    ppGM		ppgmHead, ppgmTail;

    ptmHome = pgm->ptmHome;
    ptmAway = pgm->ptmAway;

    if( ptmHome->pgmHeadHome == 0)
	ptmHome->pgmHeadHome = ptmHome->pgmTailHome = pgm;
    else
	ptmHome->pgmTailHome = ptmHome->pgmTailHome->pgmNextHome = pgm;

    if( ptmAway->pgmHeadAway == 0)
	ptmAway->pgmHeadAway = ptmAway->pgmTailAway = pgm;
    else
	ptmAway->pgmTailAway = ptmAway->pgmTailAway->pgmNextAway = pgm;
}

void
ReadResults(
    TEXT		tFile)
{   pFILE		pfile;
    int			nScan, iGameDate, iGameNumLeague;
    int			nGoalHome, nGoalAway, iFinalOtEn;
    char		acBuf[ nBUFBYT];
    char		acHome[ nBUFBYT];
    char		acAway[ nBUFBYT];
    char		acFinalOtEn[ nBUFBYT];
    pTM			ptmHome, ptmAway;
    pGM			pgm;
    struct stat		st;
    struct tm		*ptime;
    static char		acModDate[ nBUFBYT];
    TEXT		tCtime, tNl;

    pfile = fopen( tFile, "r");
    fstat( fileno( pfile), &st);
    ptime = localtime( &st.st_mtime);
    tCtime = ctime( &st.st_mtime);
    (tNl = strchr( tCtime, '\n')) && (*tNl = 0);
    sprintf( tResModDate = acModDate, "%s %s",
	tCtime, ptime->tm_isdst ? "PDT" : "PST");

    while( fgets( acBuf, nBUFBYT, pfile))
    {   /* 20011003 0002 col 3 pit 1 final */
	nScan = sscanf( acBuf, "%d %d %s %d %s %d %s",
	    &iGameDate, &iGameNumLeague,
	    acAway, &nGoalAway,
	    acHome, &nGoalHome,
	    acFinalOtEn);
	if( nScan != 7)
	    continue;
	nGameGbl++;

	ptmHome = ptmHash( acHome);
	ptmAway = ptmHash( acAway);
	pgm = malloc( sizeof( GM));

	pgm->ptmHome = ptmHome;
	pgm->ptmAway = ptmAway;
	pgm->iGameNumHome = ++ptmHome->nGame;
	pgm->iGameNumAway = ++ptmAway->nGame;
	pgm->iGameNumLeague = iGameNumLeague;
	pgm->iFinalOtEn = iFinalOtEn =
	    strstr( acFinalOtEn, "/en") ? F_OT_EN :
	    strstr( acFinalOtEn, "/ot") ? F_OT : FINAL ;
	pgm->nPointHome =
	    nGoalHome > nGoalAway ? 2 :
	    iFinalOtEn == F_OT    ? 1 : 0 ;
	pgm->nPointAway =
	    nGoalAway > nGoalHome ? 2 :
	    iFinalOtEn == F_OT    ? 1 : 0 ;
	pgm->nGoalHome = nGoalHome;
	pgm->nGoalAway = nGoalAway;
	pgm->iGameDate = iGameDate;

	LinkGame( pgm);
    }
}

/*
    Perform one iteration of computing adjusted GF-GA for all teams:
    1.  Copy each team's dAttr to dAttrPrev.
    2.  For each team:
	a.  Clear running totals of team's attr, opps' attr, and game weight.
	b.  For each game (home & away):
	    1.  Get game weight (between 0.0 and 1.0).
	    2.  Scale game's attr by weight, add to total.
	    3.  Scale opp's (dAttrPrev - dBiasExpGbl) by weight, add to total.
	    4.  Add weight to total.
	c.  Add team's attr total to total of opps' (dAttrPrev - dBiasExpGbl),
		then scale by total weight and assign to team's new dAttr.
	d.  Scale total of opps' (dAttrPrev - dBiasExpGbl) by total weight,
		assign to team's new dAttrOpp (for informational printing).
    3.  Prevent systematic drift by keeping avg of all teams' attr equal to
	    dBiasExpGbl.  (Avg is weighted by each team's number of games.)
	a.  Zero running total of bias.
	b.  For each team, multiply team's new dAttr by team's number of games,
		add to running total of bias.
	c.  Scale bias by twice the total number of games to get a per-team
		weighted avg, then subtract dBiasExpGbl.  Note that each game
		has contributed to the bias total twice, once for the home team
		and once for the away team.
	d.  Subtract residual bias from each team's new dAttr.
*/
void
AttrIteration()
{   int			iTeam;
    pTM			ptm;
    pGM			pgm;
    int			nGame;
    double		dBias, dBiasTot;
    double		dAttrTot, dAttrOppTot;
    double		dWeight, dWeightTot;

    for( iTeam = 0; iTeam < nTeamGbl; iTeam++)
    {   ptm = aptmIndex[ iTeam];
	ptm->pattr->dAttrPrev = ptm->pattr->dAttr;
    }

    for( iTeam = 0; iTeam < nTeamGbl; iTeam++)
    {   ptm = aptmIndex[ iTeam];
	nGame = ptm->nGame;
	dAttrTot = dAttrOppTot = dWeightTot = 0.0;
	for( pgm = ptm->pgmHeadHome; pgm; pgm = pgm->pgmNextHome)
	{   dWeight = adWeight[ nGame - pgm->iGameNumHome];
	    dAttrTot += dWeight * pgm->dAttrHome;
	    dAttrOppTot += dWeight *
		(pgm->ptmAway->pattr->dAttrPrev - dBiasExpGbl);
	    dWeightTot += dWeight;
	}
	for( pgm = ptm->pgmHeadAway; pgm; pgm = pgm->pgmNextAway)
	{   dWeight = adWeight[ nGame - pgm->iGameNumAway];
	    dAttrTot += dWeight * pgm->dAttrAway;
	    dAttrOppTot += dWeight *
		(pgm->ptmHome->pattr->dAttrPrev - dBiasExpGbl);
	    dWeightTot += dWeight;
	}
	ptm->pattr->dAttr = (dAttrTot + dAttrOppTot) / dWeightTot;
	ptm->pattr->dAttrOpp = dAttrOppTot / dWeightTot;
    }

    dBiasTot = 0.0;
    for( iTeam = 0; iTeam < nTeamGbl; iTeam++)
    {   ptm = aptmIndex[ iTeam];
	dBiasTot += ptm->nGame * ptm->pattr->dAttr;
    }

    dBias = dBiasTot / (2 * nGameGbl) - dBiasExpGbl;
    for( iTeam = 0; iTeam < nTeamGbl; iTeam++)
    {   ptm = aptmIndex[ iTeam];
	ptm->pattr->dAttr -= dBias;
    }
}

/*
    Comparison function for qsort to sort by
    ascending adjusted per-game GF-GA.
*/
int
iCmpAttr(
    ppTM		pptm1,
    ppTM		pptm2)
{
    return
	(*pptm1)->pattr->dAttr > (*pptm2)->pattr->dAttr ? -1 :
	(*pptm1)->pattr->dAttr < (*pptm2)->pattr->dAttr ? +1 : 0 ;
}

void
PrintAttr()
{   int			iCol, iRow, nRow, iTeam;
    pTM			ptm, aptm[ nTEAM];
    char		cOpp;
    double		dOpp;

    bcopy( aptmIndex, aptm, sizeof aptm);
    qsort( aptm, nTeamGbl, sizeof( pTM), iCmpAttr);

    ptResult = (pTEXT) malloc( nTEAM * sizeof( TEXT));
    for( iTeam = 0; iTeam < nTEAM; iTeam++)
    {   ptm = aptm[ iTeam];
	if( ptm->pattr->dAttrOpp >= 0.0)
	{   cOpp = '+';
	    dOpp = ptm->pattr->dAttrOpp;
	}
	else
	{   cOpp = '-';
	    dOpp = - ptm->pattr->dAttrOpp;
	}
	sprintf( ptResult[ iTeam] = (TEXT) malloc( 40),
	    "%3d  %3s %5.2f (%c%04.2f)",
	    iTeam + 1, ptm->acName, ptm->pattr->dAttr, cOpp, dOpp);
    }
}

void
InitWeight()
{   static int		aiShow[] =
			    { 1, 2, 3, 5, 7, 10, 15, 20, 30, 40, 60, 82 };
    int			iGame, iShow, nShow = sizeof aiShow / sizeof( int);

    for( iGame = 0; iGame < nGAME; iGame++)
	adWeight[ iGame] =
	    dGameConst == 0.0 ? 1.0 : exp( -iGame / dGameConst);

    printf( "Nth Prev Game");
    for( iShow = 0; iShow < nShow; iShow++)
	printf( " %4d", aiShow[ iShow]);
    printf( "\nGame Weight  ");
    for( iShow = 0; iShow < nShow; iShow++)
    {   iGame = aiShow[ iShow] - 1;
	printf( " %4.2f", adWeight[ iGame]);
    }
    printf( "\n\n");
}

void
InitGfGa()
{   int			iTeam;
    pTM			ptm;
    pGM			pgm;

    for( iTeam = 0; iTeam < nTeamGbl; iTeam++)
    {   ptm = aptmIndex[ iTeam];
	ptm->pattr = &ptm->attrGfGa;
	ptm->pattr->dAttr = 0.0;

	for( pgm = ptm->pgmHeadHome; pgm; pgm = pgm->pgmNextHome)
	    pgm->dAttrHome = pgm->nGoalHome - pgm->nGoalAway;
	for( pgm = ptm->pgmHeadAway; pgm; pgm = pgm->pgmNextAway)
	    pgm->dAttrAway = pgm->nGoalAway - pgm->nGoalHome;
    }
    dBiasExpGbl = 0.0;
}

void
InitPfPa()
{   int			iTeam;
    pTM			ptm;
    pGM			pgm;

    for( iTeam = 0; iTeam < nTeamGbl; iTeam++)
    {   ptm = aptmIndex[ iTeam];
	ptm->pattr = &ptm->attrPfPa;
	ptm->pattr->dAttr = 0.0;

	for( pgm = ptm->pgmHeadHome; pgm; pgm = pgm->pgmNextHome)
	    pgm->dAttrHome = pgm->nPointHome - pgm->nPointAway;
	for( pgm = ptm->pgmHeadAway; pgm; pgm = pgm->pgmNextAway)
	    pgm->dAttrAway = pgm->nPointAway - pgm->nPointHome;
    }
    dBiasExpGbl = 0.0;
}

void
InitPpg()
{   int			iTeam, nGame;
    pTM			ptm;
    pGM			pgm;
    double		dAttr, dAttrTot;
    double		dWeight, dWeightTot;

    dAttrTot = dWeightTot = 0.0;
    for( iTeam = 0; iTeam < nTeamGbl; iTeam++)
    {   ptm = aptmIndex[ iTeam];
	ptm->pattr = &ptm->attrPpg;
	ptm->pattr->dAttr = 0.0;

	nGame = ptm->nGame;
	for( pgm = ptm->pgmHeadHome; pgm; pgm = pgm->pgmNextHome)
	{   dAttr = pgm->nPointHome;
	    dWeight = adWeight[ nGame - pgm->iGameNumHome];
	    dAttrTot += dWeight * dAttr;
	    dWeightTot += dWeight;
	    pgm->dAttrHome = dAttr;
	}
	for( pgm = ptm->pgmHeadAway; pgm; pgm = pgm->pgmNextAway)
	{   dAttr = pgm->nPointAway;
	    dWeight = adWeight[ nGame - pgm->iGameNumAway];
	    dAttrTot += dWeight * dAttr;
	    dWeightTot += dWeight;
	    pgm->dAttrAway = dAttr;
	}
    }
    dBiasExpGbl = dAttrTot / dWeightTot;
}

void
Usage()
{
    fprintf( stderr, "usage: %s [ exp-time-const [ #iter ] ]\n", tPGM);
    exit( -1);
}

static void DoIterations();

int
main( nArg, atArg)
int			nArg;
char*			atArg[];
{   int			i;
    extern double	atof();

    if( nArg >= 2)
	dGameConst = atof( atArg[ 1]);
    if( nArg >= 3)
	nIterGbl = atoi( atArg[ 2]);
    if( nArg > 3 || dGameConst < 0.0 || nIterGbl < 1)
	Usage();

    ReadResults( "Year/game-res");

    printf( "\n");
    printf( "Score <a href='/game-res.txt'>database</a> includes %d games, last updated %s.\n",
	nGameGbl, tResModDate);
    printf( "The numbers in parentheses indicate the component of the ranking\n");
    printf( "due to the strength (+) or weakness (-) of the team's opposition.\n");

    printf( "\n");
    printf( "Doing %d iterations, time-constant = %g %s:\n",
	nIterGbl, dGameConst, dGameConst == 0.0 ? "(flat)" : "games");
    InitWeight();

    DoIterations();

    return 0;
}

static void
DoIterations()
{
    int iInit, iIter, iTeam;
    typedef void (*P)();
    static P apInit[] = { InitGfGa, InitPfPa, InitPpg, };
#define nINIT (sizeof( apInit) / sizeof( P))
    static TEXT atHdr[] = {
	"Goals-For Minus Goals-Against:\n",
	"Points-For Minus Points-Against:\n",
	"Points Per Game:\n",
    };
    static TEXT aatHdr[ nINIT][ 2] = {
	"Goals-For Minus",
	"Goals-Against:",
	"Points-For Minus",
	"Points-Against:",
	"Points",
	"Per Game:",
    };
    pTEXT aptResult[ nINIT];

    for( iInit = 0; iInit < nINIT; iInit++)
    {   (*apInit[ iInit])();
	for( iIter = 0; iIter < nIterGbl; iIter++)
	    AttrIteration();
	PrintAttr();
	aptResult[ iInit] = ptResult;
    }

    for( iTeam = 0; iTeam < 2; iTeam++)
    {   for( iInit = 0; iInit < nINIT; iInit++)
	    printf( "      %-20s", aatHdr[ iInit][ iTeam]);
	printf( "\n");
    }
    printf( "\n");

    for( iTeam = 0; iTeam < nTEAM; iTeam++)
    {   for( iInit = 0; iInit < nINIT; iInit++)
	    printf( "    %s", aptResult[ iInit][ iTeam]);
	printf( "\n");
    }
    printf( "\n");
}