/*
 *  CELLS       An Implementation of the WireWorld cellular automata
 *              as described in Scientific American, Jan 1990.
 *
 *              Copyright 1990 by Davide P. Cervone.
 *  You may use this code, provided this copyright notice is kept intact.
 *  See the CELLS.HELP file for complete information on distribution conditions.
 */

/*
 *  File:   cCells.c        Handles cellular finite-state machine.
 *                          To change the propagation rules, change this file.
 */


#include "Cells.h"
#include "cMemory.h"

 
static int ErrorReported;                   /* only give error once */
int GenerationDelay = 6;                    /* Delay() time between updates */


/*
 *  The electron head and tail cells are stored in a linked list so that
 *  the entire array need not be scanned during each generation.  This 
 *  structure holds the position of the cell, and a pointer to the next cell.
 */

struct Electron
{
   struct Electron *Next;
   short x,y;
};

static struct Electron *FreeList;   /* the list of free Electron structures */
static struct Electron *HeadList;   /* the list of Electron Head cells */
static struct Electron *TailList;   /* the List of Electron Tail cells */
static struct Electron *NewHead;    /* the new list of electron head cells */

/*
 *  Offsets used to find the adjacent cells to a given electron head
 */

short OffX[] = {-1,  0,  1,  1,  1,  0, -1, -1};
short OffY[] = {-1, -1, -1,  0,  1,  1,  1,  0};


/*
 *  NewElectron()
 *
 *  Get a new Electron structure.  First check to see if one is available 
 *  in the free list (the free electron list is used to prevent unnecessary
 *  memory-management overhead), and if none is available, allocate a new
 *  structure.  If we couldn't get a new electron (an no error was already
 *  reported) put up a message about low memory, otherwise set the electron
 *  X and Y values, and add it to the specified electron list.
 */

static void NewElectron(X,Y,theList)
short X,Y;
struct Electron **theList;
{
   struct Electron *theElectron;

   if (FreeList)
   {
      theElectron = FreeList;
      FreeList = FreeList->Next;
   } else {
      NEWSTRUCT(Electron,theElectron);
   }

   if (theElectron)
   {
      theElectron->x = X;
      theElectron->y = Y;
      theElectron->Next = *theList;
      *theList = theElectron;
   } else  if (ErrorReported == FALSE) {
      DoError("Can't get Memory for Electron");
      ErrorReported = TRUE;
   }
}


/*
 *  FreeEntireList()
 *
 *  Frees every electron in an electron list, and sets the list
 *  pointer to NULL.
 */

static void FreeEntireList(theList)
struct Electron **theList;
{
   struct Electron *theElectron;
   
   while (*theList)
   {
      theElectron = *theList;
      *theList = (*theList)->Next;
      FREESTRUCT(Electron,theElectron);
   }
}


/*
 *  ClearLists()
 *
 *  Clears the Electron Head, Electron Tail and New Electron Head lists.
 *  If the ClearFreeList flag is set, then also clear all free electrons
 *  as well (e.g., as part of the clean-up operations when the program
 *  exits).  Clear the cirucit boundary values to their minimum (no circuit)
 *  in preparation for searching a grid for non-blank cells.
 */

void ClearLists(ClearFreeList)
int ClearFreeList;
{
   if (FreeList && ClearFreeList) FreeEntireList(&FreeList);
   if (HeadList) FreeEntireList(&HeadList);
   if (TailList) FreeEntireList(&TailList);
   if (NewHead)  FreeEntireList(&NewHead);
}


/*
 *  SetupLists()
 *
 *  Clear any old lists, then look through the specified grid for
 *  non-blank cells.  Add them into the boundary values, and add HEAD and
 *  TAIL cells into their proper lists.
 */

void SetupLists(Grid)
UBYTE Grid[];
{
   short X,Y;
   short i = 0;
   
   ClearLists(FALSE);
   for (Y=0,i=0; Y<MAXGRIDH; Y++)
   {
      for (X=0; X<MAXGRIDW; X++,i++)
      {
         switch(Grid[i])
         {
            case TAIL:
               NewElectron(X,Y,&TailList);
               break;

            case HEAD:
               NewElectron(X,Y,&HeadList);
               break;
         }
      }
   }
}


/*
 *  CheckWire()
 *
 *  Attempt to propagate an Electron Head cell to an adjacent wire cell.
 *  First check to see that the cell had not already been turned into
 *  an electron head (the NewGen cell must still be a wire).  If not, then
 *  look at the cells adjacent to the wire cell and count how many Electron
 *  Head cells there are.  If there are more than two, stop counting and
 *  set the count to 0.  If there were 1 or 2 adjacent Electron Head cells, 
 *  the set the cell to an Electron Head in the new generation grid, and
 *  add the cell to the new Electron Head list.
 */

static void CheckWire(X,Y)
short X,Y;
{
   short i;
   short count = 0;

   if (CellColor(NewGen,X,Y) == WIRE)
   {
      for (i=0; i<8; i++)
      {
         if (CellColor(CurGen,X+OffX[i],Y+OffY[i]) == HEAD)
            if (++count > 2) {i = 8; count = 0;}
      }
      if (count)
      {
         SetCell(NewGen,X,Y,HEAD);
         NewElectron(X,Y,&NewHead);
      }
   }
}


/*
 *  PropagateHead()
 *
 *  Check the cells adjacent to the Electron Head.  If any are wire cells,
 *  then check attempt to propagate the electron into those cells.
 */

static void PropagateHead(X,Y)
short X,Y;
{
   short i;
   short x,y;
   
   for (i=0; i<8; i++)
   {
      x = X + OffX[i];
      y = Y + OffY[i];
      if (CellColor(CurGen,x,y) == WIRE) CheckWire(x,y);
   }
}


/*
 *  UpdateGrid()
 *
 *  For every cell in the Tail list, set the new generation cell to WIRE
 *  For every cell in the Head list, set the new generation cell to TAIL
 *  and attempt to propagate the Electron Head to adjacent Wire cells.
 */

static void UpdateGrid(OldGrid,NewGrid)
UBYTE OldGrid[],NewGrid[];
{
   struct Electron *theElectron;
   
   for (theElectron=TailList; theElectron; theElectron=theElectron->Next)
      SetCell(NewGrid,theElectron->x,theElectron->y,WIRE);

   for (theElectron=HeadList; theElectron; theElectron=theElectron->Next)
   {
      SetCell(NewGrid,theElectron->x,theElectron->y,TAIL);  
      PropagateHead(theElectron->x,theElectron->y);
   }
}


/*
 *  UpdateElectrons()
 *
 *  For each cell in the list,
 *    get the cell's array posoition (guaranteed to be in range?)
 *    set the screen cell to the specified color
 *    update the current cell state
 *  return the last electron in the list
 */

static struct Electron *UpdateElectrons(theElectron)
struct Electron *theElectron;
{
   register short i;
   register struct Electron *LastElectron = NULL;

   while (theElectron)
   {
      i = theElectron->x + theElectron->y * MAXGRIDW;
      ColorScreenCell(theElectron->x-GridX,theElectron->y-GridY,NewGen[i]);
      CurGen[i] = NewGen[i];
      LastElectron = theElectron;
      theElectron = theElectron->Next;
   }
   return(LastElectron);
}


/*
 *  UpdateBoard()
 *
 *  Update the cells in the Tail List, the Head List and the New Head List
 *  (these are exactly the cells that have changed since the last generation).
 *  Add the Electron Tail list to the Free List.
 *  Turn the Electron Head list into the Electron Tail list, and the
 *  New Electron Head list into the current Electron Head list.
 *  Update the screen to show the new changes.
 */

static void UpdateBoard()
{
   struct Electron *LastElectron = NULL;
   
   LastElectron = UpdateElectrons(TailList);
   UpdateElectrons(HeadList);
   UpdateElectrons(NewHead);
   if (LastElectron)
   {
      LastElectron->Next = FreeList;
      FreeList = TailList;
   }
   TailList = HeadList;
   HeadList = NewHead;
   NewHead = NULL;
   UpdateScreen();
}


/*
 *  RunCells()
 *
 *  Clear the error flag so that the first memory error will be displayed.
 *  Copy the current state of the grid to the new generation grid (only the
 *  electron cells will be changed).  Idea:  Hold onto the NewHead, HeadList,
 *  and TailList lists and use them to update the screen instead; this
 *  should speed things up even more, and would mean we don't need to worry
 *  about the boundary stuff.
 *  Setup the electron lists and get the boundary or the circuit.
 *
 *  While we are still running,
 *    propagate the electrons
 *    update the screen
 *    delay if necessary
 *    check to see if any button have been pressed
 *    if there are no tails left (i.e., there were no heads during the
 *      last generation) then stop running
 *  Clear all lists (including the free list)
 */

short RunCells(NotDone)
short NotDone;
{
   ErrorReported = FALSE;
   CopyGrid(CurGen,NewGen);
   SetupLists(CurGen);
   while (NotDone && Running)
   {
      UpdateGrid(CurGen,NewGen);
      UpdateBoard(CurGen,NewGen);
      if (GenerationDelay > 0) Delay(GenerationDelay);
      NotDone = CheckForAction(NotDone);
      if (TailList == NULL) SetStopped();
   }
   ClearLists(TRUE);
   return(NotDone);
}


/*
 *  StepCells()
 *
 *  Clear the error flag so that the first memory error will be reported.
 *  Setup the new generation (only electron cells are modified)
 *  Setup the electron lists
 *  Propagate the electrons
 *  Update the screen
 *  Clear all the electron lists
 */

void StepCells()
{
   ErrorReported = FALSE;
   CopyGrid(CurGen,NewGen);
   SetupLists(CurGen);
   UpdateGrid(CurGen,NewGen);
   UpdateBoard(CurGen,NewGen);
   ClearLists(TRUE);
}