#include <stdio.h>
#include <math.h>
#include <stdlib.h>

/* Schelling's model of segregation. C code by Benedikt Stefansson January 1998
   based on original Pascal code by Tom Belding and Robert Axelrod */

/* Define constants */
#define number_of_reports 8
#define events_per_report 100
#define num_white 25
#define num_agents 50

/* Declare arrays */
static int occupant[64];
static int color[num_agents];
static int location[num_agents];
static int neighbor_loc[64][8];


/* Declare subroutines */ 
int content(int i);
void random_move(int i);
int get_random_location();
void initial_output();
void initialize_agent_color();
void initialize_agent_location();
void initialize_neighbor_list();
void periodic_output(int event,int moves);


/*The main function*/

void main() {
  int i;
  int report;
  int events_in_report;
  int event=0;
  int moves_this_period=0;
  
  /* Initialize lattice and neighborhood list */
  initial_output();
  initialize_agent_color();
  initialize_agent_location();
  initialize_neighbor_list();
  periodic_output(0,0);

  /* Count timesteps or events */
  event = 0;
  i = 0;

  /* Outer event loop */
  for (report=0;report<number_of_reports;report++) {
    /* Count of actual moves */
    moves_this_period = 0;

    /* Inner event loop */
    for (events_in_report = 0;events_in_report < events_per_report;events_in_report++) {
      event++;
      /* Work our way through the agent list */
      if (i > num_agents)
	i = 0;
      if (!content(i)) {
	/* If agent is not content then move it*/
	moves_this_period++;
	random_move(i);
      }
      i++;
    }
    /* Print out report */
    periodic_output(event,moves_this_period);   
  } 

  exit(0);
}

/*The content() function*/

int content(int i) {
  /* Calculate if agent i is content and
     return 1 if he is and 0 if not */
  int n;
  int result;
  int neighboor;
  int address;
  int neighborhood_cell;
  int same_color_count=0;
  int occupied_count=0;

  address=location[i];
 
  for(n=0;n<8;n++) {
    /* Check if neighborhood cell is on map and occupied */
    neighborhood_cell=neighbor_loc[address][n];
    if(neighborhood_cell!=-1 && occupant[neighborhood_cell]!=-1) {
      /* There is someone there */
      occupied_count++;
      /* But is he of the right color? */
      if(color[occupant[neighborhood_cell]]==color[i]) 
	same_color_count++;
    }
  }

  /* Content if more than 1/3 of neighbors are same color */
 if(same_color_count*3 > occupied_count)
   result=1;
 else
   result=0;

 return result;
}


/*Functions to find random location*/

void random_move(int i) {    
      int trial_location;
      int look=0;

      /* Choose random locations until you
	 manage to find an empty one */
      do{
	trial_location=get_random_location();
      } while(occupant[trial_location]!=-1);

      /* OK - found empty location so move */
      /* First remove agent at old location */
      occupant[location[i]]=-1;
      /* Then add him at the new location */
      occupant[trial_location]=i;
      /* Finally update location info for agent */
      location[i]=trial_location;
     
}

int get_random_location() {
  float p;
  
  p=((float)rand()/(float)RAND_MAX);

  return (int)(p*64.0);
}

/*Initialization routines*/

void initialize_agent_color() {
  /* Give each agent a color 0 or 1 */
  int i;

  for(i=0;i<num_agents;i++) {
    if(i< num_white) 
      color[i]=0;
    else
      color[i]=1;
  }
}

void initialize_agent_location() {
  int i;
  int trial_location;

  for(i=0;i<64;i++) {
    occupant[i]=-1;
  }
  
  for(i=0;i<num_agents;i++) {
    do {
      trial_location=get_random_location();
    }while(occupant[trial_location]!=-1);

    occupant[trial_location]=i;
    location[i]=trial_location;
  }  

}
/*Generation of neighborhoods*/

void initialize_neighbor_list() {
  /* Precalculates Moore neighborhoods
     for each location on map */
  int l;

  for (l = 0; l < 64; l++) {
    /* First calculate general case */
    neighbor_loc[l][0] = l - 9; /* NW */
    neighbor_loc[l][1] = l - 8; /* N  */
    neighbor_loc[l][2] = l - 7; /* NE */
    neighbor_loc[l][3] = l - 1; /* W  */
    neighbor_loc[l][4] = l + 1; /* E  */
    neighbor_loc[l][5] = l + 7; /* SW */
    neighbor_loc[l][6] = l + 8; /* S  */
    neighbor_loc[l][7] = l + 9; /* SE */
    
    /* Correct for top row */
    if (l < 8) { 
      neighbor_loc[l][0] = 0;
      neighbor_loc[l][1] = 0;
      neighbor_loc[l][2] = 0;
    }
    /* Correct for bottom row */
    if (l > 55) { 
      neighbor_loc[l][5] = -1;
      neighbor_loc[l][6] = -1;
      neighbor_loc[l][7] = -1;
    }
    /* Correct for right side */
    if ((l % 7) == 0) {   
      neighbor_loc[l][2] = -1;
      neighbor_loc[l][4] = -1;
      neighbor_loc[l][7] = -1;
    }
    /* Correct for left side */
    if ((l % 8) == 0) { 
      neighbor_loc[l][0] = -1;
      neighbor_loc[l][3] = -1;
      neighbor_loc[l][5] = -1;
    }
  } 

}  


/*Output functions*/

void initial_output() {
  /* Prints some information at beginning of run */

  printf("Schelling's segregation model, coded by Benedikt Stefansson\n
          based on Pascal program by by Robert Axelrod and Ted Belding\n");

  printf("Parameters:\n");
  printf("   Number of agents=%3d\n",num_agents);
  printf("   Number of agents with color 0=%3d\n",num_white);

}

void periodic_output(int event,int moves) {
  /* Prints out periodic state of map */
  int line;
  int address;
  int column;
    
  if(event==0) 
    printf("Initial state of map\n");
  else
    printf("Event %3d. Moves this period %3d\n",event,moves);  
  
  address=0;
  for(line=0;line<8;line++) {
    for(column=0;column<8;column++) {
      /* Output agent map */
      if(occupant[address]==-1) 
	printf(" . ");
      else 
	printf("%3d",occupant[address]);
      address++;
    }
    /* Rewind and put space between */
    address-=8;
    printf("     ");
    for(column=0;column<8;column++) {
      /* Output color map */
      if(occupant[address]==-1)
	printf(" . ");
      else {
	if(color[occupant[address]]==0)
	  printf(" @ ");
	if(color[occupant[address]]==1)
	  printf(" # ");
      }
      address++;
    }
    printf("\n");
  }
  printf("\n");

}