import java.awt.Canvas;
import java.awt.Color;
import java.awt.Graphics2D;
import java.awt.event.MouseEvent;
import java.awt.event.MouseListener;
import java.awt.event.MouseMotionListener;
import java.awt.image.BufferStrategy;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

import javax.swing.JFrame;


public class PathFinderTest {

   public static void main(String[] args) {
      new PathFinderTest();
   }

   public static final int MAX_UNIT_SIZE_X = 2;
   public static final int MAX_UNIT_SIZE_Y = 3;

   public BufferStrategy buffer;
   public int width = 1000;
   public int height = 600;
   public int size = 50;
   public int[][] grid = new int[width / size][height / size];
   public int[][] xclearance = new int[width / size][height / size];
   public int[][] yclearance = new int[width / size][height / size];
   public boolean dragged;
   public long time = 0;
   public long totalTime = 0;
   public long trials = 0;

   public int unitSizeX = MAX_UNIT_SIZE_X;
   public int unitSizeY = MAX_UNIT_SIZE_Y;

   public PathFinderTest() {
      JFrame frame = new JFrame("Path Finder Test");
      frame.setSize(width, height);
      Canvas canvas = new Canvas();
      frame.setIgnoreRepaint(true);
      canvas.setIgnoreRepaint(true);
      canvas.addMouseMotionListener(new MouseMotionListener() {

         int lastX;
         int lastY;

         @Override
         public void mouseDragged(MouseEvent e) {
            int x = e.getX() / size;
            int y = e.getY() / size;
            if (x < 0 || x >= grid.length || y < 0 || y >= grid[x].length)
               return;
            if (e.getModifiers() == MouseEvent.BUTTON2_MASK && (lastX != x || lastY != y)) {
               grid[x][y] = grid[x][y] == 3 ? 0 : 3;
               dragged = true;
               calculate();
            }
            lastX = x;
            lastY = y;
         }

         @Override
         public void mouseMoved(MouseEvent arg0) {
            
         }
         
      });
      canvas.addMouseListener(new MouseListener() {

         Thread thread;

         @Override
         public void mouseClicked(MouseEvent e) {
         }

         @Override
         public void mouseEntered(MouseEvent arg0) {
            // TODO Auto-generated method stub
            
         }

         @Override
         public void mouseExited(MouseEvent arg0) {
            // TODO Auto-generated method stub
            
         }

         @Override
         public void mousePressed(MouseEvent e) {
         }

         @Override
         public void mouseReleased(MouseEvent e) {
            if (dragged) {
               dragged = false;
               return;
            }
            int x = e.getX() / size;
            int y = e.getY() / size;
            if (e.getButton() == MouseEvent.BUTTON1) {
               for (int i = 0; i < grid.length; i++)
                  for (int j = 0; j < grid[i].length; j++)
                     if (grid[i][j] == 1)
                        grid[i][j] = 0;
               grid[x][y] = grid[x][y] == 1 ? 0 : 1;
            } else if (e.getButton() == MouseEvent.BUTTON3) {
               for (int i = 0; i < grid.length; i++)
                  for (int j = 0; j < grid[i].length; j++)
                     if (grid[i][j] == 2)
                        grid[i][j] = 0;
               grid[x][y] = grid[x][y] == 2 ? 0 : 2;
            } else if (e.getButton() == MouseEvent.BUTTON2) {
               grid[x][y] = grid[x][y] == 3 ? 0 : 3;
            }
            if (thread != null)
               thread.interrupt();
            thread = new Thread() {
               @Override
               public void run() {
                  try {
                     calculate();
                  } catch (Exception e) {
                     e.printStackTrace();
                  }
               }
            };
            thread.start();
         }
         
      });
      canvas.setSize(frame.getSize());
      frame.add(canvas);
      frame.setResizable(false);
      frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
      frame.pack();
      frame.setVisible(true);
      canvas.createBufferStrategy(2);
      buffer = canvas.getBufferStrategy();
      calculate();
      while (true) {
         try {
            
            do {

               do {
                  Graphics2D g = (Graphics2D) buffer.getDrawGraphics();

                  g.setColor(Color.black);
                  g.fillRect(0,0,width,height);

                  paint(g);

                  g.dispose();

               } while (buffer.contentsRestored());

               buffer.show();

            } while (buffer.contentsLost());

         } catch (Exception e) {
            e.printStackTrace();
         }
         try {
            Thread.sleep(20);
         } catch (InterruptedException e) {
            e.printStackTrace();
         }
      }
   }

   public void calculate() {
      int startX = -1;
      int startY = -1;
      int endX = -1;
      int endY = -1;

      int offset = MAX_UNIT_SIZE_Y - MAX_UNIT_SIZE_X;
      for (int i = 0; i < grid.length; i++)
         for (int j = 0; j < grid[i].length; j++) {
            if (grid[i][j] != 3) {
               if (grid[i][j] == 4)
                  grid[i][j] = 0;
               int n;
               main: for (n = 1; n < MAX_UNIT_SIZE_X && n + i < grid.length && n + j + offset < grid[n].length; n++) {
                  int yoff = n + offset;
                  if (grid[i + n][j + yoff] == 3)
                     break;
                  for (int x = i; x < i + n; x++) {
                     if (grid[x][j + yoff] == 3)
                        break main;
                  }
                  for (int y = j; y < j + yoff; y++) {
                     if (grid[i + n][y] == 3) 
                        break main;
                  }
               }
               xclearance[i][j] = n;
               yclearance[i][j] = n + offset;
            }
            if (grid[i][j] == 1) {
               startX = i;
               startY = j;
            } else if (grid[i][j] == 2) {
               endX = i;
               endY = j;
            }
         }


      if (startX != -1 && endX != -1) {
         long startTime = System.nanoTime();
         end = new Node(endX, endY, null);
         Node start = new Node(startX, startY, null);
         open.add(start);
         Node current = null;
         while (!open.isEmpty()) {
            for (Iterator<Node> it$ = open.iterator(); it$.hasNext(); ) {
               Node node = it$.next();
               if (current == null) {
                  current = node;
               } else if (node.cost < current.cost)
                     current = node;
            }
            if (current == null)
               break;
            if (current.equals(end) || ((unitSizeX > 1 || unitSizeY > 1) && current.inReach(end, unitSizeX, unitSizeY))) {
               Node parent = current;
               while (parent != start) {
                  if (unitSizeX == 1 && unitSizeY == 1)
                     grid[parent.x][parent.y] = 4;
                  else {
                     for (int x = 0; x < unitSizeX; x++)
                        for (int y = 0; y < unitSizeY; y++)
                           grid[parent.x + x][parent.y + y] = 4;
                     grid[start.x][start.y] = 1; 
                     grid[end.x][end.y] = 2; 
                  }
                  parent = parent.parent;
               }
               break;
            }
            closed.add(current);
            open.remove(current);
            Node[] nodes = getSurrounding(current);
            for (int i = 0; i < nodes.length; i++) {
               if (!nodes[i].traversible || xclearance[nodes[i].x][nodes[i].y] < unitSizeX || yclearance[nodes[i].x][nodes[i].y] < unitSizeY)
                  continue;
               boolean inClosed = closed.contains(nodes[i]);
               boolean inOpen = open.contains(nodes[i]);

               int cost = 10;
               if (nodes[i].x != current.x && nodes[i].y != current.y)
                  cost = 14;

               float traversal = current.cost + cost;

               if (!inOpen && !inClosed) {
                  nodes[i].parent = current;
                  nodes[i].cost = traversal;

                  if (inClosed) {
                     closed.remove(nodes[i]);
                  }
                  if (!inOpen) {
                     open.add(nodes[i]);
                  }
               }
            }
            current = null;
         }
         open.clear();
         closed.clear();
         long endTime = System.nanoTime();
         time = (endTime - startTime) / 1000000;
         totalTime += time;
         trials++;
      }
   }

   public Node[] getSurrounding(Node n) {
      return new Node[] {
            new Node(n.x + 1, n.y, n),
            new Node(n.x - 1, n.y, n),
            new Node(n.x, n.y - 1, n),
            new Node(n.x, n.y + 1, n),

            new Node(n.x + 1, n.y + 1, n),
            new Node(n.x + 1, n.y - 1, n),
            new Node(n.x - 1, n.y + 1, n),
            new Node(n.x - 1, n.y - 1, n)
      };
   }

   public void paint(Graphics2D g) {
      for (int x = 0; x < grid.length; x++) {
         for (int y = 0; y < grid[x].length; y++) {
            Color color = null;
            switch (grid[x][y]) {
            case 0:
               color = Color.white;
               break;
            case 1:
               color = Color.green;
               break;
            case 2:
               color = Color.red;
               break;
            case 3:
               color = Color.blue;
               break;
            case 4:
               color = Color.black;
               break;
            case 5:
               color = Color.pink;
               break;
            }
            g.setColor(color);
            g.fillRect(x * size, y * size, size, size);
            g.setColor(Color.cyan);
            g.drawRect(x * size, y * size, size, size);
            if (color == Color.black)
               g.setColor(Color.white);
            else g.setColor(Color.black);
            g.drawString(xclearance[x][y] + ", " + yclearance[x][y], x * size, y * size + 11);
         }
      }
      /*g.setColor(Color.white);
      g.fillRect(3, 3, 150, 24);
      g.setColor(Color.red);
      g.drawString("Last calcuation time: " + time, 5, 12);
      g.drawString("Average time: " + (totalTime / (float) trials), 5, 24);
      g.drawString("Last calcuation time: " + time, 6, 12);
      g.drawString("Average time: " + (totalTime / (float) trials), 6, 24);*/
   }

   public Set<Node> open = new HashSet<Node>();
   public Set<Node> closed = new HashSet<Node>();
   public Node end;

   class Node {

      public Node(int x, int y, Node parent) {
         this.x = x;
         this.y = y;
         this.parent = parent;

         if (x < 0 || x >= grid.length || y < 0 || y >= grid[x].length)
            traversible = false;
         else
            traversible = grid[x][y] != 3;

      }

      public boolean traversible = true;

      public final int x;
      public final int y;

      public Node parent;
      public float cost;

      @Override
      public boolean equals(Object other_) {
         if (this == other_)
            return true;
         if (other_ == null)
            return false;
         if (other_ instanceof Node) {
            Node other = (Node) other_;
            return other.x == x && other.y == y;
         }
         return false;
      }

      @Override
      public int hashCode() {
         return x * size + y;
      }

      public boolean inReach(Node other, int sizeX, int sizeY) {
         return (x - other.x == 0 &&  y - other.y == 0) ||  (x + --sizeX - other.x == 0 &&  y + --sizeY - other.y == 0)
               || (x + - other.x == 0 &&  y + sizeY - other.y == 0) || (x + sizeX - other.x == 0 &&  y - other.y == 0);
      }

   }

}