import java.awt.*;
import java.applet.*;
import java.util.*;

public class USAmap_color extends Applet implements Runnable {
/************************************************************************/
/*									*/
/*   Class USAmap_color: USA Map Coloring Problem Solver		*/
/*									*/
/*		Copyright (C) 1996 by Yasusi Kanada			*/
/*									*/
/*	This program can be freely distributed under the GNU General	*/
/*	Public License.							*/
/*									*/
/* Initial Version = "ver 1.0, 1996-8-13";				*/
   String Version = "ver 1.13, 1996-11-23";
/*									*/
/************************************************************************/

/*======================================================================*/
/*	Class global objects and methods				*/
/*======================================================================*/
   protected int n_colors = 4;		/* default: 4 colors		*/
   protected int n_states = 48;
			/* number of states (except Alaska and Hawaii)	*/

   private Thread solver;

   private int min(int x, int y) {
      return x <= y ? x : y;
   }


/*======================================================================*/
/*	Widget handler							*/
/*======================================================================*/
   private TextField message_box;	/* public inside the class	*/

   private void init_widgets() {
      setLayout(new FlowLayout());
      add(new Label
             ("USA Mainland Coloring using CCM (Chemical Casting Model) -- " +
              Version + " --"));
      add(new Button("Stop"));
      add(new Button("Restart"));

      init_frustration_choice(this);

      Panel major_option_panel = new Panel();
      major_option_panel.add(new Label("Major options:"));
      init_speed_choice(major_option_panel);
      init_catalyst_choice(major_option_panel);
      add(major_option_panel);

      message_box = new TextField(72);
      add(message_box);
   }

   public boolean action(Event e, Object arg) {
      message_box.setText("");
      if (speed_action(arg) || catalyst_action(arg) ||
	  frustration_action(arg)) {
         return true;
      } else if ("Restart".equals(arg)) {
         stop();
         start();
         return true;
      } else if ("Stop".equals(arg)) {
         stop();
         return true;
      } else {
         return false;
      };
   }


/* Choice extension: */

   private Choice new_choice(String[] labels, int default_index,
                             Panel p) {
      Choice c = new Choice();
      for (int i = 0; i < labels.length; i++) {
         c.addItem(labels[i]);
      };
      c.select(default_index);
      p.add(c);
      return c;
   }

   private int find_index(Object arg, String[] labels) {
      for (int i = 0; i < labels.length; i++) {
         if (labels[i].equals(arg)) {
            return i;
         };
      };
      return -1;	/* not found */
   }


   final String Dangerous_string =
      "Combination of `no catalyst' and `fast speed' is inhibited, " +
      "because you may loose control! ";


/* Speed control: */

   final int[] Sleep_time = {333, 50, 0};	/* in mili seconds	*/
   final int Medium_speed_index = 1;
   final int Fast_speed_index = 2;
   final int Full_speed_index = 3;
   final int Speed_default_index = Medium_speed_index;
   final String[] Speed_choice_labels =
      {"Slow speed (3 reactions/sec)", "Medium speed (20 reactions/sec)",
       "Fast speed", "Full speed"};

   private int speed_selected_index;
   private Choice speed_choice;

   private void init_speed_choice(Panel p) {
   /* Speed choice is created and initialized.	*/
      speed_choice =
         new_choice(Speed_choice_labels, Speed_default_index, p);
      speed_selected_index = Speed_default_index;
   }

   private boolean speed_action(Object arg) {
   /* Event handler for speed control choice.				*/
   /* Warning: This function is called not only when the event is	*/
   /*	caused by the speed control choice.				*/
      int index = find_index(arg, Speed_choice_labels);
      if (index >= 0) {		/* found	*/
         if (index == Full_speed_index &&
	     catalyst_selected_index == No_catalyst_index) {
            message_box.setText(Dangerous_string);
            speed_choice.select(Speed_choice_labels[speed_selected_index]);
            return false;
         } else if (index == Full_speed_index || index == Fast_speed_index) {
            display_switch = false;	/* no display while executing	*/
            speed_selected_index = index;
            return true;
         } else {
            display_switch = true;
            speed_selected_index = index;
            return true;
         };
      } else {			/* not found	*/
         return false;
      };
   }


/* Catalyst control: */

   final int Variable_catalyst_index = 0;
   final int No_catalyst_index     = 1;
   final int Single_catalyst_index = 2;
   final int Double_catalyst_index = 3;

   final int[] Catalysts =
      {Variable_catalyst_index, No_catalyst_index,
       Single_catalyst_index, Double_catalyst_index};

   final int Catalyst_default_index = Variable_catalyst_index;

   final String[] Catalyst_choice_labels =
      {"Variable catalyst rule", "No catalyst rule (running forever...)",
       "Single catalyst rule", "Double catalyst rule"};

   private int catalyst_selected_index;
   private Choice catalyst_choice;

   private void init_catalyst_choice(Panel p) {
   /* Catalyst control choice is created and initialized.		*/
      catalyst_choice =
         new_choice(Catalyst_choice_labels, Catalyst_default_index, p);
      catalyst_selected_index = Catalyst_default_index;
   }

   private boolean catalyst_action(Object arg) {
      int index = find_index(arg, Catalyst_choice_labels);
      if (index >= 0) {		/* found	*/
         if (index == No_catalyst_index &&
             speed_selected_index == Full_speed_index) {
            message_box.setText(Dangerous_string);
            catalyst_choice.select
               (Catalyst_choice_labels[catalyst_selected_index]);
            return false;
         } else {
            catalyst_selected_index = index;
            return true;
         };
      } else {
         return false;
      };
   }


/* Frustration control: */

   final int With_frustration_index = 0;
   final int Without_frustration_index     = 1;

   final int[] Frustrations =
      {With_frustration_index, Without_frustration_index};

   final double[] Frustration_values = {1e-5, 0.0};

   final int Frustration_default_index = With_frustration_index;

   final String[] Frustration_choice_labels =
      {"Frustration ON", "Frustration OFF"};

   private int frustration_selected_index;
   private Choice frustration_choice;

   private void init_frustration_choice(Panel p) {
   /* frustration choice is created and initialized.		*/
      frustration_choice =
         new_choice(Frustration_choice_labels, Frustration_default_index, p);
      frustration_selected_index = Frustration_default_index;
   }

   private boolean frustration_action(Object arg) {
      int index = find_index(arg, Frustration_choice_labels);
      if (index >= 0) {		/* found	*/
         frustration_selected_index = index;
	 initial_frustration = Frustration_values[index];
         return true;
      } else {
         return false;
      };
   }


/*======================================================================*/
/*	Map viewer							*/
/*======================================================================*/
   protected int size_factor;
			/* Actual drawing size = size_factor * coord.	*/
   protected boolean display_switch = true;
					/* To display the map or not	*/

   private Polygon[] state_polygons = new Polygon[n_states];
			/* Border polygons of the U.S. states.		*/
   private int[] painted_color = new int[n_states];
   protected Color[] id2color =
			/* Color ID to Color class constant conversion	*/
      {Color.yellow, Color.blue, Color.red, Color.cyan, Color.orange,
       Color.magenta, Color.green, Color.white};

   private Polygon create_polygon(int[] indices, int[] X, int[] Y) {
      int[] x_coords = new int[indices.length];
      int[] y_coords = new int[indices.length];
      for (int i = 0; i < indices.length; i++) {
         x_coords[i] = size_factor * X[indices[i]];
         y_coords[i] = size_factor * (Y[indices[i]] - 11);
				/* -11: adjust offset	*/
      };
      return new Polygon(x_coords, y_coords, indices.length);
   }

   private void init_view() {
      int[] X =		/* X coordinate indices for polygons	*/
	{ 17, 15, 23, 26, 12, 17, 21, 10, 11, 13, 11, 13, 15, 21, 22,
          16, 23, 26, 30, 33, 30, 28, 29, 31, 33, 30, 27, 31, 41, 41,
          43, 40, 41, 41, 43, 43, 43, 35, 39, 41, 51, 51, 52, 52, 53,
          52, 54, 54, 45, 45, 53, 54, 39, 43, 51, 51, 55, 55, 59, 57,
          59, 61, 58, 59, 59, 60, 60, 59, 61, 63, 63, 59, 61, 62, 62,
          61, 59, 65, 65, 62, 61, 65, 64, 68, 72, 75, 73, 63, 69, 71,
          72, 70, 70, 68, 70, 63, 63, 73, 73, 69, 64, 66, 67, 70, 75,
          75, 76, 79, 77, 77, 83, 84, 81, 73, 77, 77, 81, 77, 77, 70,
          71, 75, 75, 78, 79, 81, 77, 77, 83, 86, 89, 85, 85, 85, 83,
          80, 79, 83, 83, 85, 85, 87, 85, 87, 89, 87, 87, 89, 89, 87,
          92, 89, 67, 66, 67, 50, 54, 56, 60, 66, 68, 70, 72, 80, 82,
          84, 86, 64, 68, 70, 74, 78, 82, 84, 88, 64, 68, 70, 72, 66,
          68, 70, 74, 82, 84, 50, 54, 56, 60, 64, 68, 70, 74, 82, 84,
          52, 54, 56, 58, 66, 68, 70, 72, 78, 82, 84, 88, 70, 74, 64,
          68 };
      int[] Y =		/* Y coordinate indices for polygons	*/
	{ 33, 37, 41, 34, 43, 46, 47, 47, 51, 51, 53, 59, 64, 65, 61,
          51, 57, 49, 49, 45, 45, 42, 35, 59, 53, 52, 69, 69, 46, 44,
          39, 54, 50, 60, 60, 57, 55, 70, 70, 62, 45, 40, 52, 50, 50,
          56, 61, 57, 63, 65, 69, 63, 75, 75, 80, 76, 75, 70, 50, 47,
          44, 42, 42, 57, 55, 52, 63, 65, 65, 63, 62, 69, 67, 78, 76,
          73, 73, 52, 48, 47, 45, 53, 66, 66, 65, 63, 63, 75, 54, 52,
          49, 49, 47, 46, 44, 44, 42, 61, 59, 59, 60, 75, 73, 73, 57,
          52, 61, 57, 57, 56, 63, 61, 59, 66, 64, 66, 67, 74, 70, 77,
          75, 77, 79, 81, 83, 80, 51, 53, 53, 54, 53, 52, 50, 49, 45,
          47, 49, 56, 55, 58, 57, 49, 44, 50, 49, 52, 55, 51, 47, 43,
          42, 37, 46, 49, 51, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,
          16, 16, 18, 18, 18, 18, 18, 18, 18, 18, 20, 20, 20, 20, 22,
          22, 22, 22, 22, 22, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
          26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 19, 19, 23,
          23 };
      int[][] border_points =	/* Border point coordinates of polygons */
         {{0, 1, 2, 3, 0}, 
          {1, 4, 5, 6, 2, 1}, 
          {4, 7, 8, 9, 10, 11, 12, 13, 14, 15, 5, 4},
          {5, 15, 14, 16, 17, 6, 5},
          {3, 2, 6, 17, 18, 19, 20, 21, 22, 3},
          {17, 16, 23, 24, 25, 18, 17},
          {16, 14, 13, 26, 27, 23, 16},
          {22, 21, 20, 19, 28, 29, 30, 22},
          {19, 18, 25, 24, 31, 32, 28, 19}, 
          {24, 23, 33, 34, 35, 36, 31, 24},		/* 10 */
          {23, 27, 37, 38, 39, 33, 23},
          {30, 29, 40, 41, 30},
          {29, 28, 32, 42, 43, 44, 40, 29},
          {32, 31, 36, 35, 45, 42, 32},
          {35, 34, 46, 47, 45, 35},
          {33, 39, 48, 49, 50, 51, 46, 34, 33},
          {39, 38, 37, 52, 53, 54, 55, 56, 57, 50, 49, 48, 39}, 
          {41, 40, 44, 58, 59, 60, 61, 62, 41}, 
          {43, 42, 45, 47, 63, 64, 65, 58, 44, 43},
          {47, 46, 51, 66, 67, 68, 69, 70, 63, 47},	/* 20 */
          {51, 50, 57, 71, 72, 68, 67, 66, 51},
          {57, 56, 73, 74, 75, 76, 71, 57},
          {60, 59, 58, 65, 77, 78, 79, 80, 60},
          {65, 64, 63, 70, 100, 81, 77, 65},
          {69, 68, 72, 82, 83, 84, 85, 86, 69}, 
          {72, 71, 76, 75, 74, 87, 82, 72}, 
          {96, 80, 79, 78, 152, 153, 154, 81, 88, 89, 90, 91, 92,
           93, 94, 95, 96},
          {81, 100, 99, 88, 81},
          {100, 70, 69, 86, 97, 98, 99, 100},
          {82, 87, 101, 102, 103, 83, 82},		/* 30 */
          {89, 88, 99, 98, 104, 105, 89},
          {104, 98, 97, 106, 107, 108, 109, 104},
          {107, 106, 97, 86, 85, 110, 111, 112, 107}, 
          {85, 84, 113, 114, 115, 116, 110, 85}, 
          {83, 103, 117, 118, 113, 84, 83},
          {102, 101, 119, 120, 121, 122, 123, 124, 125, 117, 
           103, 102},
          {113, 118, 116, 115, 114, 113},
          {135, 136, 126, 127, 128, 129, 130, 131, 132, 133, 
           134, 135},
          {105, 104, 109, 137, 138, 128, 127, 126, 105},
          {109, 108, 107, 112, 139, 137, 109},		/* 40 */
          {138, 137, 139, 140, 138},
          {134, 133, 141, 142, 134}, 
          {133, 132, 143, 147, 144, 141, 133},
          {132, 131, 145, 143, 132},
          {128, 138, 140, 146, 129, 128},
          {143, 145, 147, 143},
          {142, 141, 144, 148, 149, 142},
          {149, 148, 150, 151, 149}};

      for (int i = 0; i < painted_color.length; i++) {
         painted_color[i] = -1;	/* equal to no color	*/
      };
      size_factor = min(size().width / 100, size().height / 80);
      if (size_factor < 1) {
         size_factor = 1;
      };
      for (int i = 0; i < border_points.length; i++) {
         state_polygons[i] = create_polygon(border_points[i], X, Y);
      };
   }

   private void paint_state(int state_id, Graphics g) {
      g.setColor(id2color[color_wm[state_id]]);
      g.fillPolygon(state_polygons[state_id]);
      g.setColor(Color.black);
      g.drawPolygon(state_polygons[state_id]);
   }

   public void paint(Graphics g) {
      for (int i = 0; i < n_states; i++) {
         paint_state(i, g);
         painted_color[i] = color_wm[i];
      };
   }

   public void update(Graphics g) {
      paint(g);
   }


/*======================================================================*/
/*	Solver								*/
/*======================================================================*/
   double initial_frustration = 1.0e-5;
   double frustration_factor = 2.0;

   /* Working memory: */
   private int[] color_wm, id_wm;
   private double[] frustration_wm;
   private int[] n_neighbors;
   private int[][] neighbors_wm;
   private int wm_size;

   private int n_tests;
   private int n_reactions;
   private int n_failed_tests;

   /* Order degree: */
   private int vertex_order(int color_i, int color_j) {
      return color_i != color_j ? 1 : 0;
   }

   private double mean_order() {
   /* Returns the mean order degree of the current WM.	*/
      int total_order = 0;
      int n_edges = 0;
      for (int i = 0; i < wm_size; i++) {
         for (int j = 0; j < n_neighbors[i]; j++) {
            total_order +=
               vertex_order(color_wm[i], color_wm[neighbors_wm[i][j]]);
            n_edges++;
         };
      };
      return total_order / (double)n_edges;
   }

   private void init_solver(int size) {
   /* Allocate working memory */
      color_wm = new int[size];
      id_wm = new int[size];
      frustration_wm = new double[size];
      n_neighbors = new int[size];
      neighbors_wm = new int[size][];

      init_wm();
   }


/* Random color/index generators */

   private Random selector = new Random();

   private int random(int max) {
      return (selector.nextInt() & 0x7FFFFFFF) % max;
   }

   private int select_color(int index) {
      int old_color = color_wm[index];
      int new_color;
      do {
         new_color = random(n_colors);
      } while (new_color == old_color);
      return new_color;
   }

   private void reaction(int index, int old_order, int new_order,
                         int new_color) {
      int old_color = color_wm[index];
      if (old_order >= 0) {	/* A local termination condition holds	*/
         n_failed_tests++;
      } else if (((double)old_order - frustration_wm[index]) > new_order) {
						/* not to be reacted	*/
         n_failed_tests++;
         frustration_wm[index] *= frustration_factor;
      } else {
         n_reactions++;
         n_failed_tests = 0;
         color_wm[index] = new_color;		/* Change color	*/
         if (display_switch) {
            repaint();
            try {solver.sleep(Sleep_time[speed_selected_index]);}
            catch (InterruptedException e) {};
         };
         frustration_wm[index] = initial_frustration;
      };
   }

/* Rules */

   private void change_color() {
   /* Variable catalyst rule	*/
      int index = random(wm_size);
				/* select a vertex to apply the rule	*/
      int old_color = color_wm[index];
      int new_color = select_color(index);

      n_tests++;

   /* Compute LODs: */
      int old_order = 0;
      int new_order = 0;
      for (int i = 0; i < n_neighbors[index]; i++) {
         int neighbor_color = color_wm[neighbors_wm[index][i]];
         if (neighbor_color == old_color) {
             old_order -= 1;
         };
         if (neighbor_color == new_color) {
             new_order -= 1;
         };
      };

      reaction(index, old_order, new_order, new_color);
   }

   private void change_color0() {
   /* No catalyst rule		*/
      int index = random(wm_size);
				/* select a vertex to apply the rule	*/
      n_tests++;

      reaction(index, -1, -1, select_color(index));
   }

   private void change_color1() {
   /* Variable catalyst rule	*/
      int index1 = random(wm_size);
				/* select a vertex to apply the rule	*/
      if (n_neighbors[index1] == 0) {		/* selection failed	*/
         n_failed_tests++;
         return;
      };
      int index2 = neighbors_wm[index1][random(n_neighbors[index1])];
	/* select a neighbor vertex (index2 is the index in neighbors_wm) */

      int new_color = select_color(index1);
      n_tests++;

   /* Compute LODs: */
      int old_order = vertex_order(color_wm[index1], color_wm[index2]) - 1;
      int new_order = vertex_order(new_color, color_wm[index2]) - 1;

      reaction(index1, old_order, new_order, new_color);
   }

   private void change_color2() {
   /* Variable catalyst rule	*/
      int index1 = random(wm_size);
				/* select a vertex to apply the rule	*/
      if (n_neighbors[index1] <= 1) {		/* selection failed	*/
         n_failed_tests++;
         return;
      };
      int i = random(n_neighbors[index1]);
      int index2 = neighbors_wm[index1][i];
	/* select a neighbor vertex (index2 is the index in neighbors_wm) */
      int j;
      do {
         j = random(n_neighbors[index1]);
      } while (i == j);
      int index3 = neighbors_wm[index1][j];

      int old_color = color_wm[index1];
      int new_color = select_color(index1);
      n_tests++;

   /* Compute LODs: */
      int old_order = vertex_order(old_color, color_wm[index2]) +
                      vertex_order(old_color, color_wm[index3]) - 2;
      int new_order = vertex_order(new_color, color_wm[index2]) +
                      vertex_order(new_color, color_wm[index3]) - 2;

      reaction(index1, old_order, new_order, new_color);
   }


/* Solver main part: */

   public void run() {
      long initial_time;
      int max_tests = 1000;
      int max_tests_20 = 20 * max_tests;

      for (int i = 0; i < n_states; i++) {
         color_wm[i] = 0;	/* or random(n_colors); */
      };
      message_box.setText("Running...");
      repaint();

      initial_time = System.currentTimeMillis();
      n_tests = 0;
      n_reactions = 0;
      n_failed_tests = 0;
      while (true) {
         switch (catalyst_selected_index) {
         case No_catalyst_index:
            change_color0();
            break;
         case Single_catalyst_index:
            change_color1();
            break;
         case Double_catalyst_index:
            change_color2();
            break;
         case Variable_catalyst_index:
            change_color();
            break;
         };

         if (n_failed_tests >= max_tests) {	/* termination condition */
            if (n_tests < max_tests_20) {
               break;
            };
            max_tests_20 = 2 * max_tests_20;
            max_tests = max_tests_20 / 20;
         };
         if (speed_selected_index != Full_speed_index &&
	     n_tests % 7500 == 0) {
            message_box.setText
               ("Running... #tests = " + n_tests +
                "  #reactions = " + n_reactions + "  MOD = " + mean_order() +
                "  Time = " +
                (System.currentTimeMillis() - initial_time) / 1000.0);
            repaint();
            try {solver.sleep(50);}
            catch (InterruptedException e) {};
         };
      };
      double order = mean_order();
      message_box.setText
         ("Stoppped.  #tests = " + n_tests +
          "  #reactions = " + n_reactions +
          "  MOD = " + order + (order < 1 ? "  *** Failed! ***" : "") +
          "  Time = " + (System.currentTimeMillis() - initial_time) / 1000.0);
      repaint();
   };


/*======================================================================*/
/*	Working memory (USA Graph) generation				*/
/*======================================================================*/
   private void count_edge(int[] edge_count, int n_vertices, int to_count) {
      if (0 <= to_count && to_count < n_vertices) {
         edge_count[to_count]++;
      } else {
         /* Exception must be raised! */
      };
   }

   private void graph_setup(int[] edge_sources, int[] edge_destinations,
                            int n_vertices) {
      int n_edges = edge_sources.length; /* = edge_destinations.length	*/
      int[] edge_counts = new int[n_vertices];
      for (int i = 0; i < n_edges; i++) {  /* count edges for allocation */
         count_edge(edge_counts, n_vertices, edge_sources[i]);
         count_edge(edge_counts, n_vertices, edge_destinations[i]);
      };
      for (int i = 0; i < n_vertices; i++) {	/* Make vertices	*/
         id_wm[i] = i;
         frustration_wm[i] = initial_frustration;
         neighbors_wm[i] = new int[edge_counts[i]];
      };
      wm_size = n_vertices;
      for (int i = 0; i < n_edges; i++) {	/* Make edges (links)	*/
         int index;
         index = edge_destinations[i];
         neighbors_wm[index][n_neighbors[index]++] = edge_sources[i];
         index = edge_sources[i];
         neighbors_wm[index][n_neighbors[index]++] = edge_destinations[i];
      };
   }

   private void init_wm() {
      int[] edge_sources =
         { 0,  0,  1,  1,  1,  2,  2,  3,  3,  3,  4,  4,  4,  5,  5,
	   5,  6,  7,  7,  7,  8,  8,  8,  9,  9,  9,  9, 10, 10, 11,
	  11, 12, 12, 12, 13, 13, 13, 14, 14, 14, 15, 15, 15, 16, 16,
	  17, 17, 18, 18, 18, 19, 19, 19, 19, 20, 20, 20, 21, 22, 22,
	  23, 23, 24, 24, 24, 24, 24, 24, 25, 26, 26, 27, 27, 28, 28,
	  28, 29, 29, 30, 30, 31, 31, 31, 32, 32, 33, 33, 34, 34, 37,
	  37, 37, 37, 37, 38, 38, 38, 39, 40, 41, 41, 42, 42, 42, 43,
	  46};
      int[] edge_destinations =
	 { 1,  4,  2,  3,  4,  3,  6,  4,  5,  6,  5,  7,  8,  6,  8,
	   9, 10,  8, 11, 12,  9, 12, 13, 10, 13, 14, 15, 15, 16, 12,
	  17, 13, 17, 18, 14, 18, 19, 15, 18, 19, 16, 19, 20, 20, 21,
	  18, 22, 19, 22, 23, 20, 23, 24, 28, 21, 24, 25, 25, 23, 26,
	  27, 28, 25, 28, 29, 32, 33, 34, 29, 27, 30, 28, 30, 30, 31,
	  32, 34, 35, 31, 38, 32, 38, 39, 33, 39, 34, 36, 35, 36, 38,
	  41, 42, 43, 44, 39, 40, 44, 40, 44, 42, 46, 43, 45, 46, 45,
	  47};
      graph_setup(edge_sources, edge_destinations, n_states);
   }


/*======================================================================*/
/*	Dispatchers							*/
/*======================================================================*/
   public void init() {
      init_solver(n_states);
      init_widgets();
      init_view();
   }

   public void start() {
      solver = new Thread(this);
      /* solver.setPriority(Thread.MIN_PRIORITY); */
      solver.start();
   }

   public void stop() {
      solver.stop();
   }

}