// WythoffApp.java
import java.awt.*;
import java.awt.event.*;
import java.net.*;
import java.io.*;

public class WythoffApp extends Frame implements ActionListener, KeyListener,
                                                 FocusListener, Runnable
{
   private static final int MAXTESTSIZE = 1000;
   private int length = 14, colSize = 14;
   private TextArea textArea;
   private TextField textLength, xArea, yArea, whoseTurn;
   private Button compute, reset, move;
   private WythoffStarter ws = null; 
   private boolean runsFromApplet, posArray[][], gamePosArray[][];
   private Board board;
   private Image image;
   private Thread runner;

   public WythoffApp(WythoffStarter _ws, boolean _runsFromApplet)
   {
      super("Wythoff's Nim");
      ws = _ws;
      runsFromApplet = _runsFromApplet;
      setBackground(SystemColor.control);

      try
      {
         if (ws != null)
         {
            URL url = new URL(ws.getCodeBase() + "Images/smile.gif");
            trackImage(getToolkit().getImage(url));
         }
         else
            trackImage(getToolkit().getImage("Images/smile.gif"));
      }
      catch (MalformedURLException mfe)
      {
         System.err.println("Error: " + mfe);
      }

      textLength = new TextField(4);
      textLength.addKeyListener(this);
      textLength.addFocusListener(this);

      textArea = new TextArea();
      textArea.setEditable(false);
      textArea.setBackground(Color.white);

      compute = new Button("OK");
      compute.addActionListener(this);
      reset = new Button("Reset");
      reset.addActionListener(this);
      move = new Button("Move!");
      move.addActionListener(this);
      move.setEnabled(false);

      xArea = new TextField(2);
      xArea.setEditable(false);
      xArea.setBackground(SystemColor.control);
      yArea = new TextField(2);
      yArea.setEditable(false);
      yArea.setBackground(SystemColor.control);
      whoseTurn = new TextField(8);
      whoseTurn.setEditable(false);
      whoseTurn.setBackground(SystemColor.control);

      Panel optionPanel = new Panel();
      optionPanel.setLayout(new FlowLayout());
      optionPanel.add(new Label("Player up:", Label.RIGHT));
      optionPanel.add(whoseTurn);
      optionPanel.add(new Label("X:", Label.RIGHT));
      optionPanel.add(xArea);
      optionPanel.add(new Label("Y:", Label.RIGHT));
      optionPanel.add(yArea);
      optionPanel.add(new Label(""));
      optionPanel.add(move);
      optionPanel.add(reset);

      board = new Board(image, 14);
      board.setChangeable(false);
      Panel boardPanel = new Panel();
      boardPanel.setLayout(new FlowLayout());
      boardPanel.add(board);

      Panel bottomPanel = new Panel();
      bottomPanel.setLayout(new BorderLayout());
      bottomPanel.add("North", boardPanel);
      bottomPanel.add("South", optionPanel);

      Label title = new Label("Wythoff's Nim", Label.CENTER);
      title.setFont(new Font("sansserif", Font.BOLD, 30));

      Panel labelPanel = new Panel();
      labelPanel.setLayout(new FlowLayout()); 
      labelPanel.add(new Label(
                     "Enter length of board to test (up to " + MAXTESTSIZE + "):",
                     Label.RIGHT));
      labelPanel.add(textLength);
      labelPanel.add(new Label(""));
      labelPanel.add(compute);

      Panel titlePanel = new Panel();
      titlePanel.setLayout(new FlowLayout());
      titlePanel.add(title);

      Panel topPanel = new Panel();
      topPanel.setLayout(new BorderLayout()); 
      topPanel.add("Center", titlePanel);
      topPanel.add("South", new Box(labelPanel, 
                                    "Test for Losing Positions", Box.LEFT));

      setLayout(new BorderLayout()); 
      add("North", topPanel);
      add("Center", textArea);
      add("South", new Box(bottomPanel, "Game", Box.LEFT));

      addWindowListener(new WindowAdapter()
      {
         public void windowClosing(WindowEvent e)
         {
            if (runsFromApplet)
               ws.close();
            else
               System.exit(0);
         }
      });

      String dummy = displayLosingPositions();
      makePosCopy();

      validate(); 
      pack();
      setResizable(false);
      Dimension d = Toolkit.getDefaultToolkit().getScreenSize();
      Point p = new Point((int)((d.getWidth() - this.getWidth())/2),
                          (int)((d.getHeight() - this.getHeight())/2));
      setLocation(p);
      textLength.requestFocus();
      setVisible(true);
   }

   public void delay()
   {
      try
      {
         runner.sleep(2000);
      }
      catch (InterruptedException ie)
      {
         System.err.println("Error: " + ie);
      }
   }

   public void start()
   {
      stop();
      if (runner == null)
      {
         runner = new Thread(this);
         runner.start();
      }
   }

   public void stop()
   {
      if (runner != null)
        runner = null;
   }

   private void makePosCopy()
   {
      gamePosArray = new boolean[length][length];
      for(int x = 0; x < length; x++)
        for(int y = 0; y < length; y++)
          gamePosArray[x][y] = posArray[x][y];
   }

   private int randomize()
   {
      int x = 0;
      while (x < colSize/2)
        x = (int)(Math.random() * colSize);
      return x;
   }

   private void trackImage(Image _image)
   {
      image = _image;
      MediaTracker tracker = new MediaTracker(this);
      tracker.addImage(image, 0);
      try
      {
         tracker.waitForAll();
      }
      catch(InterruptedException ie)
      {
         System.err.println("Image loading interrupted: " + ie);
      }
   }

   private String displayLosingPositions()
   {
      /* Method for determining all the losing positions within the N x N array
         of possible positions.
         Define the sequences an and bn as follows:
         
         * a0 = 0, b0 = 0
         * For each n > 0
           * let an = the smallest positive integer not in
             {a0, b0, a1, b1,..., an-1, bn-1}
           * let bn = an + n

      */
      StringBuffer pos = new StringBuffer();
      pos.append("If a player can move from the current position to a " +
                 "pre-existing" + "\n" + "losing position, then the " +
                 "current position is not a losing position." + "\n\n" +
                 "The following ordered pairs are losing positions:" + "\n");
      posArray = new boolean[length][length];
      for(int i = 0; i < length; i++)
        for(int j = 0; j < length; j++)
          posArray[i][j] = true;
      posArray[0][0] = false;      // base case
      Node head = new Node(0);     // insert 0 in the list of integers
      int maxElement = 0, n = 1;
      while (maxElement < length)  // while in the board of size "length"
      {
         int ct = 0;
         boolean found = false;
         Node ptr = head, backPtr = null;
         while ((ptr != null) && (!found)) // find the smallest integer
           if (ptr.data != ct)             // not in the list
              found = true;
           else
           {
              ct += 1;
              backPtr = ptr;
              ptr = ptr.next;
           }
         int x = ct, y = ct + n;  // get the values for that ordered pair
         if (y < length)          // if within size of board, insert it in list
         {
            Node a = new Node(x); // insert x coordinate
            backPtr.next = a;
            a.next = ptr;
            backPtr = a;
            ptr = a.next;
            while (ptr != null)   // go to end of list if not already there
            {
               backPtr = ptr;
               ptr = ptr.next;
            }
            Node b = new Node(y);    // insert y coordinate 
            backPtr.next = b;
            posArray[x][y] = false;  // update array of booleans
            posArray[y][x] = false;
         }
         n += 1;
         maxElement = y;
      }
      for(int x = 0; x < length; x++)
        for(int y = 0; y < length; y++)
          if (!posArray[x][y])
            pos.append("(" + x + ", " + y + ")" + "\n");
            // append coordinates to string
      return pos.toString();
   }

   private void computerPlay()
   {
      int x = board.getX();
      int y = board.getY();
      if (gamePosArray[x][y] == false)
        if ((x > 0) && (y > 0))
          board.setCoords(x - 1, y - 1);
        else if (x > 0)
          board.setCoords(x - 1, y);
        else
          board.setCoords(x, y - 1);
      else
      {
         boolean found = false;
         if (x == y)
         {
            x = 0;
            y = 0;
            found = true;
         }
         else
         {
            int i = y - 1;
            while ((!found) && (i >= 0))
              if (gamePosArray[x][i] == false)
              {
                 y = i;
                 found = true;
              }
              else
                 i -= 1;
              if (!found)
              {
                 int j = x - 1;
                 while ((!found) && (j >= 0))
                   if (gamePosArray[j][y] == false)
                   {
                      x = j;
                      found = true;
                   }
                   else
                      j -= 1;
                 if (!found)
                 {
                    int min, k = 1;
                    if (x < y)
                      min = x;
                    else
                      min = y;
                    while ((!found) && (k <= min))
                      if (gamePosArray[x - k][y - k] == false)
                      {
                         x -= k;
                         y -= k;
                         found = true;
                      }
                      else
                         k += 1;
                 }
             }
         }
         board.setCoords(x, y);
      }   
   }

   private void beginGame()
   {
      whoseTurn.setBackground(Color.white);
      whoseTurn.setText("You!");
      xArea.setText("");
      xArea.setEditable(true);
      xArea.setBackground(Color.white);
      yArea.setText("");
      yArea.setEditable(true);
      yArea.setBackground(Color.white);
      move.setEnabled(true);
      xArea.requestFocus();
   }

   private void endGame()
   {
      whoseTurn.setText("");
      xArea.setText("");
      yArea.setText("");
      whoseTurn.setBackground(SystemColor.control);
      xArea.setEditable(false);
      xArea.setBackground(SystemColor.control);
      yArea.setEditable(false);
      yArea.setBackground(SystemColor.control);
      move.setEnabled(false);
   }

   public void run()
   {
      int x = board.getX();
      int y = board.getY();
      int newX = -1, newY = -1;
      boolean finished = false, gameWon = false;

      if ((x != 0) || (y != 0))
      {
         if (xArea.getText().equals(""))
         {
            MessageBox mb = new MessageBox(ws, this, "Error",
                            "Cannot set X coordinate: no value entered.",
                            "exclaim.gif");
         }
         else if (yArea.getText().equals(""))
         {
            MessageBox mb = new MessageBox(ws, this, "Error",
                            "Cannot set Y coordinate: no value entered.",
                            "exclaim.gif");
         }
         else
         {
            try
            {
               String s = xArea.getText().trim();
               xArea.setText(s);
               newX = Integer.parseInt(s);
               s = yArea.getText().trim();
               yArea.setText(s);
               newY = Integer.parseInt(s);
               if ((newX > x) || (newY > y))
               {
                  MessageBox mb = new MessageBox(ws, this, "Error",
                     "New coordinates must be of lesser value than " +
                     "current coordinates.", "exclaim.gif");
               }
               else if ((newX == x) && (newY == y))
               {
                  MessageBox mb = new MessageBox(ws, this, "Error",
                     "New coordinates cannot equal current coordinates.",
                     "exclaim.gif");
               }
               else if ((newX < 0) || (newY < 0))
               {
                  MessageBox mb = new MessageBox(ws, this, "Error",
                     "Coordinates are out of bounds.", "exclaim.gif");
               }
               else if ((newX != x) && (newY != y))
               {
                  if ((x - newX) != (y - newY))
                  {
                     MessageBox mb = new MessageBox(ws, this, "Error",
                        "You must move both coordinates the same distance.",
                        "exclaim.gif");
                  }
                  else
                     finished = true;
               }
               else
                  finished = true;
            }
            catch (NumberFormatException nfe)
            {
               MessageBox mb = new MessageBox(ws, this, "Error",
                               "Invalid input for coordinates.", "exclaim.gif");
            }
         }
         xArea.setText("");
         yArea.setText("");
         xArea.requestFocus();
         if ((finished) && (runner != null))
         {
            board.setCoords(newX, newY);
            if ((newX == 0) && (newY == 0))
            {
               gameWon = true;
               endGame();
               MessageBox mb = new MessageBox(ws, this, "Information",
                               "You won the game!", "information.gif");
            }
            else
            {
               whoseTurn.setText("Computer");
               delay();
               computerPlay();
               if ((board.getX() == 0) && (board.getY() == 0) && (runner != null))
               {
                  gameWon = true;
                  endGame();
                  MessageBox mb = new MessageBox(ws, this, "Information",
                                  "The computer won the game!",
                                  "information.gif");
               }
               else
                  whoseTurn.setText("You!");
            }
            reset.requestFocus();
         }
         if (!gameWon)
         {
            xArea.select(0, xArea.getText().length());
            xArea.requestFocus();
         }
      }
   }

   public void focusGained(FocusEvent fe){}

   public void focusLost(FocusEvent fe)
   {
      textLength.select(0, 0);
   }

   private void processCommand()
   {
      if (textLength.getText().trim().equals(""))
      {
         textLength.requestFocus();
         textLength.selectAll();
         MessageBox mb = new MessageBox(ws, this, "Error",
                         "Cannot compute losing positions: no length entered.",
                         "exclaim.gif");
      }
      else 
      {
         try
         {
            String s = textLength.getText().trim();
            textLength.setText(s);
            textLength.requestFocus();
            textLength.selectAll();
            length = Integer.parseInt(s);
            if (length <= 0)
            {
               MessageBox mb = new MessageBox(ws, this, "Error",
                               "Length must be greater than 0.", "exclaim.gif");
            }
            else if (length > MAXTESTSIZE)
            {
               MessageBox mb = new MessageBox(ws, this, "Error",
                               "Length exceeds the " + MAXTESTSIZE + " limit.",
                               "exclaim.gif");
            }
            else
               textArea.setText(displayLosingPositions());
         }
         catch (NumberFormatException nfe)
         {
            MessageBox mb = new MessageBox(ws, this, "Error",
                            "Invalid input for length of board.", "exclaim.gif");
         }
      }
   }

   public void keyPressed(KeyEvent ke)
   {
      if (ke.getKeyText(ke.getKeyCode()).equals("Enter"))
        processCommand();
   }

   public void keyReleased(KeyEvent ke){}

   public void keyTyped(KeyEvent ke){}

   public void actionPerformed(ActionEvent ae)
   {
      if (ae.getSource() == compute)
         processCommand();
      else if (ae.getSource() == reset)
      {
         board.setCoords(randomize(), randomize());
         beginGame();
      }
      else if (ae.getSource() == move)
         start();
   }

   public static void main(String[] args)
   {
      WythoffApp wa = new WythoffApp(null, false);
   }

}