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

public class Queens_Sort extends Applet implements Runnable {
/************************************************************************/
/*									*/
/*   Class Queens_Sort: N Queens / Sort Problem Solver			*/
/*									*/
/*		Copyright (C) 1996 by Yasusi Kanada			*/
/*									*/
/*	This program can be freely distributed under the GNU General	*/
/*	Public License.							*/
/*									*/
/* Initial Version = "ver 1.00, 1996-8-13";				*/
   String Version = "ver 1.05, 1996-11-23";
/*									*/
/************************************************************************/

/*======================================================================*/
/*	Class global objects and methods				*/
/*======================================================================*/
   protected int n = 8;			/* default: eight queens	*/

   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 TextField n_box;		/* to specify n (#queens)	*/

   private void init_widgets() {
      setLayout(new FlowLayout());
      add(new Label
             ("N Queens / Sort using CCM (Chemical Casting Model) -- " +
              Version));
      add(new Button("Stop"));
      add(new Button("Restart"));

      Panel option_panel_1 = new Panel();
      option_panel_1.add(new Label("Options: N ="));
      n_box = new TextField("8    ");
      option_panel_1.add(n_box);
      init_speed_choice(option_panel_1);
      init_frustration_choice(option_panel_1);
      add(option_panel_1);

      Panel option_panel_2 = new Panel();
      init_catalyst_choice(option_panel_2);
      init_problem_choice(option_panel_2);
      add(option_panel_2);

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

   public boolean action(Event e, Object arg) {
      message_box.setText("");
      if (speed_action(arg) || catalyst_action(arg) ||
	  problem_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 rps)", "Medium speed (20 rps)",
       "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 MOVING rule",
       "No catalyst swapping rule (running forever...)",
       "Single catalyst swapping rule", "Double catalyst swapping 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;
      };
   }


/* Order degree control (Problem control): */

   final int Queens_index = 0;
   final int Sort_index     = 1;

   final int[] Problems =
      {Queens_index, Sort_index};

   final int Problem_default_index = Queens_index;

   final String[] Problem_choice_labels =
      {"N Qneens problem LOD", "Sort LOD"};

   private int problem_selected_index;
   private Choice problem_choice;

   private void init_problem_choice(Panel p) {
   /* problem choice is created and initialized.		*/
      problem_choice =
         new_choice(Problem_choice_labels, Problem_default_index, p);
      problem_selected_index = Problem_default_index;
   }

   private boolean problem_action(Object arg) {
      int index = find_index(arg, Problem_choice_labels);
      if (index >= 0) {		/* found	*/
         problem_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;
      };
   }


/*======================================================================*/
/*	Queens viewer							*/
/*======================================================================*/
   protected boolean display_switch = true;
					/* To display the map or not	*/

   final int Common_offset = 8;

   protected int x_offset = 0;
   protected int y_offset = 180;
   protected int drawn_n;
   protected int queen_x_offset, queen_y_offset;
   int drawing_size, drawing_step, queen_size;

   private void init_view() {
   }

   private void start_view() {
      drawing_step =
         (min(size().width - x_offset, size().height - y_offset) -
          2 * Common_offset) / n;
      if (drawing_step <= 0) {
         message_box.setText("Applet size too small! ");
         drawing_step = 0;
      };
      drawing_size = drawing_step * n;
      queen_x_offset = Common_offset + x_offset;
      queen_y_offset = Common_offset + y_offset;
      queen_size = drawing_step * 4 / 5;
   }

   public void paint(Graphics g) {
      int x0 = x_offset + Common_offset;
      int y0 = y_offset + Common_offset;
      /* if (drawn_n != n) {
         g.clearRect(x0, y0, size().width, size().height);
         drawn_n = n;
      }; */
      for (int i = 0; i <= n; i++) {
         int grid_coord = i * drawing_step;
         g.drawLine(x0, y0 + grid_coord,
                    x0 + drawing_size - 1, y0 + grid_coord);
         g.drawLine(x0 + grid_coord, y0,
                    x0 + grid_coord, y0 + drawing_size - 1);
      };
      x0 = x0 + drawing_step / 10;
      y0 = y0 + drawing_step / 10;
      g.setColor(Color.magenta);
      for (int i = 0; i < n; i++) {
         g.fillOval(x0 + column_wm[i] * drawing_step,
                    y0 + row_wm[i] * drawing_step,
                    queen_size, queen_size);
      };
   }


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

   /* Working memory: */
   private int[] column_wm, row_wm;
   private double[] frustration_wm;
   private int wm_size;

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

   /* Order degree: */
   private int order(int row1, int col1, int row2, int col2) {
      if (problem_selected_index == Queens_index) {
         return (row1 != row2 && col1 != col2 &&
                 row1 - row2 != col1 - col2 &&
                 row1 - row2 != col2 - col1 ? 1 : 0);
      } else {	/* problem_selected_index == Sort_index */
         int value1 = row1;
         int index1 = col1;
         int value2 = row2;
         int index2 = col2;
         /* return index1 >= index2 ? (value1 > value2 ? 0 : 1)
                                 : (value1 >= value2 ? 1 : 0); */
         return (index1 - index2) * (value1 - value2) >= 0 ? 0 : 1;
      };
   }

   private double mean_order() {
   /* Returns the mean order degree of the current WM.	*/
      int total_order = 0;
      for (int i = 0; i < wm_size; i++) {
         for (int j = 0; j < i; j++) {
            total_order += order(row_wm[i], column_wm[i],
                                       row_wm[j], column_wm[j]);
         };
      };
      return 2 * total_order / (double)(wm_size * (wm_size - 1));
   }

   private void init_solver() {
   }


/* Random color/index generators */

   private Random selector = new Random();

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

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

/* Rules */

   private void swap0() {
   /* No catalyst swapping rule	*/
      int index1, index2;
      n_tests++;

   /* Select queens to apply the rule:	*/
      index1 = random(wm_size);
      do {
         index2 = random(wm_size);
      } while (index2 == index1);

   /* Compute LODs: */

      swap(index1, index2, -1, -1);
   }


   private void swap1() {
   /* Single catalyst swapping rule	*/
      int index1, index2, index3;
      n_tests++;

   /* Select queens to apply the rule:	*/
      index1 = random(wm_size);
      do {
         index2 = random(wm_size);
      } while (index2 == index1);
      do {
         index3 = random(wm_size);
      } while (index3 == index1 || index3 == index2);

   /* Compute LODs: */
      int old_order =
         order(row_wm[index1], column_wm[index1],
               row_wm[index3], column_wm[index3]) +
         order(row_wm[index2], column_wm[index2],
               row_wm[index3], column_wm[index3]) +
         order(row_wm[index1], column_wm[index1],	/* for sort	*/
               row_wm[index2], column_wm[index2]) - 3;
      int new_order =
         order(row_wm[index1], column_wm[index2],
               row_wm[index3], column_wm[index3]) +
         order(row_wm[index2], column_wm[index1],
               row_wm[index3], column_wm[index3]) +
         order(row_wm[index1], column_wm[index2],	/* for sort	*/
               row_wm[index2], column_wm[index1]) - 3;

      swap(index1, index2, old_order, new_order);
   }


   private void swap2() {
   /* Double catalyst swapping rule	*/
      int index1, index2, index3, index4;
      n_tests++;

   /* Select queens to apply the rule:	*/
      index1 = random(wm_size);
      do {
         index2 = random(wm_size);
      } while (index2 == index1);
      do {
         index3 = random(wm_size);
      } while (index3 == index1 || index3 == index2);
      do {
         index4 = random(wm_size);
      } while (index4 == index1 || index4 == index2 || index4 == index3);

   /* Compute LODs: */
      int old_order =
         order(row_wm[index1], column_wm[index1],
               row_wm[index3], column_wm[index3]) +
         order(row_wm[index2], column_wm[index2],
               row_wm[index3], column_wm[index3]) +
         order(row_wm[index1], column_wm[index1],
               row_wm[index4], column_wm[index4]) +
         order(row_wm[index2], column_wm[index2],
               row_wm[index4], column_wm[index4]) +
         order(row_wm[index1], column_wm[index1],	/* for sort	*/
               row_wm[index2], column_wm[index2]) - 5;
      int new_order =
         order(row_wm[index1], column_wm[index2],
               row_wm[index3], column_wm[index3]) +
         order(row_wm[index2], column_wm[index1],
               row_wm[index3], column_wm[index3]) +
         order(row_wm[index1], column_wm[index2],
               row_wm[index4], column_wm[index4]) +
         order(row_wm[index2], column_wm[index1],
               row_wm[index4], column_wm[index4]) +
         order(row_wm[index1], column_wm[index2],	/* for sort	*/
               row_wm[index2], column_wm[index1]) - 5;

      swap(index1, index2, old_order, new_order);
   }


   private void move() {
   /* Variable catalyst moving rule	*/
      n_tests++;

   /* Select a queen to apply the rule:	*/
      int index = random(wm_size);
      int new_column = random(wm_size);

   /* Compute LODs: */
      int old_order = 0;
      int new_order = 0;
      for (int i = 0; i < n; i++) {
         if (i != index) {
            old_order += order(row_wm[index], column_wm[index],
                               row_wm[i], column_wm[i]) - 1;
            new_order += order(row_wm[index], new_column,
                               row_wm[i], column_wm[i]) - 1;
         };
      };

      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;
         column_wm[index] = new_column;
         if (display_switch) {
            repaint();
            try {solver.sleep(Sleep_time[speed_selected_index]);}
            catch (InterruptedException e) {};
         };
         frustration_wm[index] = initial_frustration;
      };
   }


/* Solver main part: */

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

      try {
         n = Integer.parseInt(n_box.getText());	/* Get n from the widget */
      } catch (NumberFormatException e) {
         message_box.setText("Format error -- n ");
         n = 8;
      };
      if (n < 4) {
         message_box.setText("The value of N must be 4 or larger! ");
         n = 8;
      };
      n_box.setText("" + n);
      init_wm(n);

      start_view();
      repaint();
      try {solver.sleep(200);}
      catch (InterruptedException e) {};

      message_box.setText("Running...");
      initial_time = System.currentTimeMillis();
      n_tests = 0;
      n_reactions = 0;
      n_failed_tests = 0;
      while (true) {
         switch (catalyst_selected_index) {
         case No_catalyst_index:
            swap0();
            break;
         case Single_catalyst_index:
            swap1();
            break;
         case Double_catalyst_index:
            swap2();
            break;
         case Variable_catalyst_index:
            move();
            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 % 10000 == 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
         ("Stopped.  #tests = " + n_tests +
          "  #reactions = " + n_reactions +
          "  MOD = " + order + (order < 1 ? "  *** Failed! ***" : "") +
          "  Time = " + (System.currentTimeMillis() - initial_time) / 1000.0);
      repaint();
   };


/*======================================================================*/
/*	Working memory (Initial queen layout) generation		*/
/*======================================================================*/
   private void init_wm(int n) {
      wm_size = n;
      column_wm = new int[wm_size];
      row_wm = new int[wm_size];
      frustration_wm = new double[wm_size];

      for (int i = 0; i < wm_size; i++) {
         row_wm[i] = i;
         column_wm[i] = i;	/* or random(n);	*/
         frustration_wm[i] = initial_frustration;
      };
   }


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

   public void start() {
      solver = new Thread(this);
      solver.start();
   }

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

}