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

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

/* Global vars */
int number_of_reports=8;
int events_per_report=100;
int num_white=25;
int num_agents=50;

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


/* 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);
void get_parameters();
void initialize_arrays();

void main() {
  int i;
  int report;
  int events_in_report;
  int event=0;
  int moves_this_period=0;
  
  /* Get parameter settings */
  get_parameters();

  /* Allocate memory for agent lists */
  initialize_arrays();
  
  /* 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);
}


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;
}
     
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);
}
  
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;
  }  

}

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] = -1;
      neighbor_loc[l][1] = -1;
      neighbor_loc[l][2] = -1;
    }
    /* 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;
    }
  } 

}  



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

  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;
  char str[3]={'.','@','#'};
    
  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(" %c ",str[0]);
      else 
	printf(" %c ",str[color[occupant[address]]+1]);
      address++;
    }
    printf("\n");
  }
  printf("\n");

}



void get_parameters() {
  /* Read in several parameters before running sim */
  int temp=0;

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

  while(!temp) {
    printf("Input number of agents (0-64): ");
    scanf("%d",&temp);
    if(temp<=0 || temp>=64) {
      printf("Number of agents must be between 0-64\n");
      temp=0;
    } else {
      num_agents=temp;
    }
  }
  temp=0;
  
  while(!temp) {
    printf("Number of white agents (1-%d): ",num_agents-1);
    scanf("%d",&temp);
    if(temp<=0 || temp>=num_agents) {
      printf("Number of white agents must be between 1-%d\n",num_agents);
      temp=0;
    } else {
      num_white=temp;
    }
  }
  temp=0;
  
  while(!temp) {
    printf("Number of reports to print: ");
    scanf("%d",&temp);
    if(temp<=0) {
      printf("Number of reports must be positive\n");
      temp=0;
    } else {
      number_of_reports=temp;
    }
  }
  temp=0;
  
  while(!temp) {
    printf("Number of events per report: ");
    scanf("%d",&temp);
    if(temp<=0) {
      printf("Number of events must be positive\n");
      temp=0;
    } else {
      events_per_report=temp;
    }
  }

}

void initialize_arrays() {
  /* Allocate memory for the color and location arrays */
  color=calloc(num_agents,sizeof(int));
  location=calloc(num_agents,sizeof(int));

}