import java.security.NoSuchAlgorithmException;
import java.security.MessageDigest;
import java.lang.reflect.*;
import java.net.*;
import java.io.*;
import javax.swing.*;
import java.util.regex.*;
import java.util.*;

import java.awt.*;
import java.awt.image.*;
import javax.imageio.*;
import static java.lang.Math.*;

class RGB {
  public final float r, g, b;

  public RGB(float r, float g, float b) {
    this.r = r;
    this.g = g;
    this.b = b;
  }

  public RGB(double r, double g, double b) {
    this.r = (float) r;
    this.g = (float) g;
    this.b = (float) b;
  }

  public RGB(double brightness) {
    this.r = this.g = this.b = (float) brightness;
  }

  public RGB(Color color) {
    this.r = color.getRed()/255f;
    this.g = color.getGreen()/255f;
    this.b = color.getBlue()/255f;
  }

  public RGB(String hex) {
    r = Integer.parseInt(hex.substring(0, 2), 16)/255f;
    g = Integer.parseInt(hex.substring(2, 4), 16)/255f;
    b = Integer.parseInt(hex.substring(4, 6), 16)/255f;
  }

  public float getComponent(int i) {
    return i == 0 ? r : i == 1 ? g : b;
  }

  public Color getColor() {
    return new Color(r, g, b);
  }

  public static RGB newSafe(float r, float g, float b) {
    return new RGB(Math.max(0, Math.min(1, r)), Math.max(0, Math.min(1, g)), Math.max(0, Math.min(1, b)));
  }

  public int asInt() {
    return getColor().getRGB() & 0xFFFFFF;
  }

  public float getBrightness() {
    return (r+g+b)/3.0f;
  }

  public String getHexString() {
    return Integer.toHexString(asInt() | 0xFF000000).substring(2).toUpperCase();
  }

  @Override
  public boolean equals(Object o) {
    if (this == o) return true;
    if (!(o instanceof RGB)) return false;

    RGB rgb = (RGB) o;

    if (Float.compare(rgb.b, b) != 0) return false;
    if (Float.compare(rgb.g, g) != 0) return false;
    if (Float.compare(rgb.r, r) != 0) return false;

    return true;
  }

  @Override
  public int hashCode() {
    int result = (r != +0.0f ? Float.floatToIntBits(r) : 0);
    result = 31 * result + (g != +0.0f ? Float.floatToIntBits(g) : 0);
    result = 31 * result + (b != +0.0f ? Float.floatToIntBits(b) : 0);
    return result;
  }

  public boolean isBlack() {
    return r == 0f && g == 0f && b == 0f;
  }

  public boolean isWhite() {
    return r == 1f && g == 1f && b == 1f;
  }

  public String toString() {
    return getHexString();
  }
}

class RGBImage {
  private BufferedImage bufferedImage;
  private File file;
  private int width, height;
  private int[] pixels;

  // color returned when getPixel is called with out-of-bounds position
  private int background = 0xFFFFFF;

  public RGBImage(BufferedImage image) {
    this(image, null);
  }

  public RGBImage(BufferedImage image, File file) {
    this.file = file;
    bufferedImage = image;
    width = image.getWidth();
    height = image.getHeight();
    pixels = new int[width*height];
    PixelGrabber pixelGrabber = new PixelGrabber(image, 0, 0, width, height, pixels, 0, width);
    try {
      if (!pixelGrabber.grabPixels())
        throw new RuntimeException("Could not grab pixels");
      cleanPixels(); // set upper byte to 0
    } catch (InterruptedException e) {
      throw new RuntimeException(e);
    }
  }

  /** We assume it's a file name to load from */
  public RGBImage(String file) throws IOException {
    this(new File(file));
  }

  public RGBImage(Dimension size, Color color) {
    this(size.width, size.height, color);
  }

  public RGBImage(Dimension size, RGB color) {
    this(size.width, size.height, color);
  }

  private void cleanPixels() {
    for (int i = 0; i < pixels.length; i++)
      pixels[i] &= 0xFFFFFF;
  }

  public RGBImage(int width, int height, int[] pixels) {
    this.width = width;
    this.height = height;
    this.pixels = pixels;
  }

  public RGBImage(int w, int h, RGB[] pixels) {
    this.width = w;
    this.height = h;
    this.pixels = asInts(pixels);
  }

  public static int[] asInts(RGB[] pixels) {
    int[] ints = new int[pixels.length];
    for (int i = 0; i < pixels.length; i++)
      ints[i] = pixels[i] == null ? 0 : pixels[i].getColor().getRGB();
    return ints;
  }

  public RGBImage(int w, int h, RGB rgb) {
    this.width = w;
    this.height = h;
    this.pixels = new int[w*h];
    int col = rgb.asInt();
    if (col != 0)
      for (int i = 0; i < pixels.length; i++)
        pixels[i] = col;
  }

  public RGBImage(RGBImage image) {
    this(image.width, image.height, copyPixels(image.pixels));
  }

  public RGBImage(int width, int height, Color color) {
    this(width, height, new RGB(color));
  }

  public RGBImage(File file) throws IOException {
    this(javax.imageio.ImageIO.read(file));
  }

  private static int[] copyPixels(int[] pixels) {
    int[] copy = new int[pixels.length];
    System.arraycopy(pixels, 0, copy, 0, pixels.length);
    return copy;
  }

  public int getIntPixel(int x, int y) {
    if (inRange(x, y))
      return pixels[y * width + x];
    else
      return background;
  }

  public static RGB asRGB(int packed) {
    int r = (packed >> 16) & 0xFF;
    int g = (packed >> 8) & 0xFF;
    int b = packed & 0xFF;
    return new RGB(r / 255f, g / 255f, b / 255f);
  }

  public RGB getRGB(int x, int y) {
    if (inRange(x, y))
      return asRGB(pixels[y * width + x]);
    else
      return new RGB(background);
  }

  /** alias of getRGB - I kept typing getPixel instead of getRGB all the time, so I finally created it */
  public RGB getPixel(int x, int y) {
    return getRGB(x, y);
  }

  public int getWidth() {
    return width;
  }

  public int getHeight() {
    return height;
  }

  /** Attention: cached, i.e. does not change when image itself changes */
  /** @NotNull */
  public BufferedImage getBufferedImage() {
    if (bufferedImage == null) {
      bufferedImage = new BufferedImage(width, height, BufferedImage.TYPE_INT_RGB);
      //bufferedImage.setData(Raster.createRaster(new SampleModel()));
      for (int y = 0; y < height; y++)
        for (int x = 0; x < width; x++)
          bufferedImage.setRGB(x, y, pixels[y*width+x]);
    }
    return bufferedImage;
  }

  public RGBImage clip(Rectangle r) {
    r = fixClipRect(r);
    int[] newPixels;
    try {
      newPixels = new int[r.width*r.height];
    } catch (RuntimeException e) {
      System.out.println(r);
      throw e;
    }
    for (int y = 0; y < r.height; y++) {
      System.arraycopy(pixels, (y+r.y)*width+r.x, newPixels, y*r.width, r.width);
    }
    return new RGBImage(r.width, r.height, newPixels);
  }

  private Rectangle fixClipRect(Rectangle r) {
    r = r.intersection(new Rectangle(0, 0, width, height));
    if (r.isEmpty())
      r = new Rectangle(r.x, r.y, 0, 0);
    return r;
  }

  public File getFile() {
    return file;
  }

  /** can now also do GIF (not just JPEG) */
  public static RGBImage load(String fileName) {
    return load(new File(fileName));
  }

  /** can now also do GIF (not just JPEG) */
  public static RGBImage load(File file) {
    try {
      BufferedImage bufferedImage = javax.imageio.ImageIO.read(file);
      return new RGBImage(bufferedImage);
    } catch (IOException e) {
      throw new RuntimeException(e);
    }
  }

  public int getInt(int x, int y) {
    return pixels[y * width + x];
  }

  public void save(File file) throws IOException {
    String name = file.getName().toLowerCase();
    String type;
    if (name.endsWith(".png")) type = "png";
    else if (name.endsWith(".jpg") || name.endsWith(".jpeg")) type = "jpeg";
    else throw new IOException("Unknown image extension: " + name);
    javax.imageio.ImageIO.write(getBufferedImage(), type, file);
  }

  public static RGBImage dummyImage() {
    return new RGBImage(1, 1, new int[] {0xFFFFFF});
  }

  public int[] getPixels() {
    return pixels;
  }

  public void setPixel(int x, int y, RGB rgb) {
    if (x >= 0 && y >= 0 && x < width && y < height)
      pixels[y*width+x] = rgb.asInt();
  }

  public void setPixel(int x, int y, Color color) {
    setPixel(x, y, new RGB(color));
  }

  public void setPixel(int x, int y, int rgb) {
    if (x >= 0 && y >= 0 && x < width && y < height)
      pixels[y*width+x] = rgb;
  }

  public RGBImage copy() {
    return new RGBImage(this);
  }

  public boolean inRange(int x, int y) {
    return x >= 0 && y >= 0 && x < width && y < height;
  }

  public int getBackground() {
    return background;
  }

  public void setBackground(int background) {
    this.background = background;
  }

  public Dimension getSize() {
    return new Dimension(width, height);
  }

  @Override
  public boolean equals(Object o) {
    if (this == o) return true;
    if (o == null || getClass() != o.getClass()) return false;

    RGBImage rgbImage = (RGBImage) o;

    if (height != rgbImage.height) return false;
    if (width != rgbImage.width) return false;
    if (!Arrays.equals(pixels, rgbImage.pixels)) return false;

    return true;
  }

  @Override
  public int hashCode() {
    int result = width;
    result = 31 * result + height;
    result = 31 * result + Arrays.hashCode(pixels);
    return result;
  }

  public String getHex(int x, int y) {
    return getPixel(x, y).getHexString();
  }

  public RGBImage clip(int x, int y, int width, int height) {
    return clip(new Rectangle(x, y, width, height));
  }

  public RGBImage clipLine(int y) {
    return clip(0, y, width, 1);
  }

  public int numPixels() {
    return width*height;
  }
}

abstract class Surface extends JPanel {


  public Object AntiAlias = RenderingHints.VALUE_ANTIALIAS_ON;
  public Object Rendering = RenderingHints.VALUE_RENDER_SPEED;
  public AlphaComposite composite;
  public Paint texture;
  public BufferedImage bimg;
  public int imageType;
  public String name;
  public boolean clearSurface = true;
  // Demos using animated gif's that implement ImageObserver set dontThread.
  public boolean dontThread;

  protected long sleepAmount = 50; // max20 fps

  private long orig, start, frame;
  private Toolkit toolkit;
  private boolean perfMonitor, outputPerf;
  private int biw, bih;
  private boolean clearOnce;
  private boolean toBeInitialized = true;


  public Surface() {
    setDoubleBuffered(false);
    toolkit = getToolkit();
    name = this.getClass().getName();
    name = name.substring(name.indexOf(".", 7)+1);
    setImageType(0);

    // To launch an individual demo with the performance str output  :
    //    java -Djava2demo.perf= -cp Java2Demo.jar demos.Clipping.ClipAnim
    try {
      if (System.getProperty("java2demo.perf") != null) {
        perfMonitor = outputPerf = true;
      }
    } catch (Exception ex) { }
  }


    /*protected Image getImage(String name) {
        return DemoImages.getImage(name, this);
    }


    protected Font getFont(String name) {
        return DemoFonts.getFont(name);
    }*/


  public int getImageType() {
    return imageType;
  }


  public void setImageType(int imgType) {
    if (imgType == 0) {
      imageType = 1;
    } else {
      imageType = imgType;
    }
    bimg = null;
  }


  public void setAntiAlias(boolean aa) {
    AntiAlias = aa
      ? RenderingHints.VALUE_ANTIALIAS_ON
      : RenderingHints.VALUE_ANTIALIAS_OFF;
  }


  public void setRendering(boolean rd) {
    Rendering = rd
      ? RenderingHints.VALUE_RENDER_QUALITY
      : RenderingHints.VALUE_RENDER_SPEED;
  }


  public void setTexture(Object obj) {
    if (obj instanceof GradientPaint) {
      texture = new GradientPaint(0, 0, Color.white,
        getSize().width*2, 0, Color.green);
    } else {
      texture = (Paint) obj;
    }
  }


  public void setComposite(boolean cp) {
    composite = cp
      ? AlphaComposite.getInstance(AlphaComposite.SRC_OVER, 0.5f)
      : null;
  }


  public void setMonitor(boolean pm) {
    perfMonitor = pm;
  }


  public void setSleepAmount(long amount) {
    sleepAmount = amount;
  }


  public long getSleepAmount() {
    return sleepAmount;
  }


  public BufferedImage createBufferedImage(Graphics2D g2,
                                           int w,
                                           int h,
                                           int imgType) {
    BufferedImage bi = null;
    if (imgType == 0) {
      bi = (BufferedImage) g2.getDeviceConfiguration().
        createCompatibleImage(w, h);
    } else if (imgType > 0 && imgType < 14) {
      bi = new BufferedImage(w, h, imgType);
    } else if (imgType == 14) {
      bi = createBinaryImage(w, h, 2);
    } else if (imgType == 15) {
      bi = createBinaryImage(w, h, 4);
    } else if (imgType == 16) {
      bi = createSGISurface(w, h, 32);
    } else if (imgType == 17) {
      bi = createSGISurface(w, h, 16);
    }
    biw = w;
    bih = h;
    return bi;
  }


  // Lookup tables for BYTE_BINARY 1, 2 and 4 bits.
  static byte[] lut1Arr = new byte[] {0, (byte)255 };
  static byte[] lut2Arr = new byte[] {0, (byte)85, (byte)170, (byte)255};
  static byte[] lut4Arr = new byte[] {0, (byte)17, (byte)34, (byte)51,
    (byte)68, (byte)85,(byte) 102, (byte)119,
    (byte)136, (byte)153, (byte)170, (byte)187,
    (byte)204, (byte)221, (byte)238, (byte)255};


  private BufferedImage createBinaryImage(int w, int h, int pixelBits) {
    int bytesPerRow = w * pixelBits / 8;
    if (w * pixelBits % 8 != 0) {
      bytesPerRow++;
    }
    byte[] imageData = new byte[h * bytesPerRow];
    IndexColorModel cm = null;
    switch (pixelBits) {
      case 1:
        cm = new IndexColorModel(pixelBits, lut1Arr.length,
          lut1Arr, lut1Arr, lut1Arr);
        break;
      case 2:
        cm = new IndexColorModel(pixelBits, lut2Arr.length,
          lut2Arr, lut2Arr, lut2Arr);
        break;
      case 4:
        cm = new IndexColorModel(pixelBits, lut4Arr.length,
          lut4Arr, lut4Arr, lut4Arr);
        break;
      default:
      {new Exception("Invalid # of bit per pixel").printStackTrace();}
    }

    DataBuffer db = new DataBufferByte(imageData, imageData.length);
    WritableRaster r = Raster.createPackedRaster(db, w, h, pixelBits, null);
    return new BufferedImage(cm, r, false, null);
  }

  private BufferedImage createSGISurface(int w, int h, int pixelBits) {
    int rMask32 = 0xFF000000;
    int rMask16 = 0xF800;
    int gMask32 = 0x00FF0000;
    int gMask16 = 0x07C0;
    int bMask32 = 0x0000FF00;
    int bMask16 = 0x003E;

    DirectColorModel dcm = null;
    DataBuffer db = null;
    WritableRaster wr = null;
    switch (pixelBits) {
      case 16:
        short[] imageDataUShort = new short[w * h];
        dcm = new DirectColorModel(16, rMask16, gMask16, bMask16);
        db = new DataBufferUShort(imageDataUShort, imageDataUShort.length);
        wr = Raster.createPackedRaster(db, w, h, w,
          new int[] {rMask16, gMask16, bMask16},
          null);
        break;
      case 32:
        int[] imageDataInt = new int[w * h];
        dcm = new DirectColorModel(32, rMask32, gMask32, bMask32);
        db = new DataBufferInt(imageDataInt, imageDataInt.length);
        wr = Raster.createPackedRaster(db, w, h, w,
          new int[] {rMask32, gMask32, bMask32},
          null);
        break;
      default:
      {new Exception("Invalid # of bit per pixel").printStackTrace();}
    }

    return new BufferedImage(dcm, wr, false, null);
  }

  public Graphics2D createGraphics2D(int width,
                                     int height,
                                     BufferedImage bi,
                                     Graphics g) {

    Graphics2D g2 = null;

    if (bi != null) {
      g2 = bi.createGraphics();
    } else {
      g2 = (Graphics2D) g;
    }

    g2.setBackground(getBackground());
    g2.setRenderingHint(RenderingHints.KEY_ANTIALIASING, AntiAlias);
    g2.setRenderingHint(RenderingHints.KEY_RENDERING, Rendering);

    if (clearSurface || clearOnce) {
      g2.clearRect(0, 0, width, height);
      clearOnce = false;
    }

    if (texture != null) {
      // set composite to opaque for texture fills
      g2.setComposite(AlphaComposite.SrcOver);
      g2.setPaint(texture);
      g2.fillRect(0, 0, width, height);
    }

    if (composite != null) {
      g2.setComposite(composite);
    }

    return g2;
  }

  public abstract void render(int w, int h, Graphics2D g);


  /**
   * It's possible to turn off double-buffering for just the repaint
   * calls invoked directly on the non double buffered component.
   * This can be done by overriding paintImmediately() (which is called
   * as a result of repaint) and getting the current RepaintManager and
   * turning off double buffering in the RepaintManager before calling
   * super.paintImmediately(g).
   */
  public void paintImmediately(int x,int y,int w, int h) {
    RepaintManager repaintManager = null;
    boolean save = true;
    if (!isDoubleBuffered()) {
      repaintManager = RepaintManager.currentManager(this);
      save = repaintManager.isDoubleBufferingEnabled();
      repaintManager.setDoubleBufferingEnabled(false);
    }
    super.paintImmediately(x, y, w, h);

    if (repaintManager != null) {
      repaintManager.setDoubleBufferingEnabled(save);
    }
  }


  public void paint(Graphics g) {

    Dimension d = getSize();

    if (imageType == 1)
      bimg = null;
    else if (bimg == null || biw != d.width || bih != d.height) {
      bimg = createBufferedImage((Graphics2D)g,
        d.width, d.height, imageType-2);
      clearOnce = true;
      toBeInitialized = true;
    }

    if (toBeInitialized) {
      toBeInitialized = false;
      startClock();
    }

    Graphics2D g2 = createGraphics2D(d.width, d.height, bimg, g);
    render(d.width, d.height, g2);
    g2.dispose();

    if (bimg != null)  {
      g.drawImage(bimg, 0, 0, null);
      toolkit.sync();
    }

  }


  public void startClock() {
    orig = System.currentTimeMillis();
    start = orig;
    frame = 0;
  }

  private static final int REPORTFRAMES = 30;


  public static void setAlpha(Graphics2D g, float alpha) {
    g.setComposite(AlphaComposite.getInstance(AlphaComposite.SRC_OVER, alpha));
  }
}

class ImageSurface extends Surface {
  private BufferedImage image;
  private double zoomX = 1, zoomY = 1;
  private Rectangle selection;

  public ImageSurface() {
    this(new RGBImage(1, 1, new int[] { 0xFFFFFF }));
  }

  public ImageSurface(RGBImage image) {
    this(image.getBufferedImage());
  }

  public ImageSurface(BufferedImage image) {
    clearSurface = false;
    this.image = image;

    /*addMouseMotionListener(new MouseAdapter() {
      public void mouseMoved(MouseEvent e) {
        getMousePosition()

      }
    });*/
  }

  public ImageSurface(RGBImage image, double zoom) {
    this(image);
    setZoom(zoom);
  }

  public void render(int w, int h, Graphics2D g) {
    g.setColor(Color.white);
    g.fillRect(0, 0, w, h);
    if (image != null)
      g.drawImage(image, 0, 0, getZoomedWidth(), getZoomedHeight(), null);

    if (selection != null) {
      // drawRect is inclusive, selection is exclusive, so... whatever, tests show it's cool.
      drawSelectionRect(g, selection, Color.green, Color.white);
    }
  }

  public void drawSelectionRect(Graphics2D g, Rectangle selection, Color green, Color white) {
    g.setColor(green);
    int top = (int) (selection.y * zoomY);
    int bottom = (int) ((selection.y+selection.height) * zoomY);
    int left = (int) (selection.x * zoomX);
    int right = (int) ((selection.x+selection.width) * zoomX);
    g.drawRect(left-1, top-1, right-left+1, bottom-top+1);
    g.setColor(white);
    g.drawRect(left - 2, top - 2, right - left + 3, bottom - top + 3);
  }

  public void setZoom(double zoom) {
    setZoom(zoom, zoom);
  }

  public void setZoom(double zoomX, double zoomY) {
    this.zoomX = zoomX;
    this.zoomY = zoomY;
    revalidate();
    repaint();
  }

  public Dimension getMinimumSize() {
    int w = getZoomedWidth();
    int h = getZoomedHeight();
    Dimension min = super.getMinimumSize();
    return new Dimension(Math.max(w, min.width), Math.max(h, min.height));
  }

  private int getZoomedHeight() {
    return (int) (image.getHeight() * zoomY);
  }

  private int getZoomedWidth() {
    return (int) (image.getWidth() * zoomX);
  }

  public void setImage(RGBImage image) {
    setImage(image.getBufferedImage());
  }

  public void setImage(BufferedImage image) {
    this.image = image;
    revalidate();
    repaint();
  }

  public BufferedImage getImage() {
    return image;
  }

  public double getZoomX() {
    return zoomX;
  }

  public double getZoomY() {
    return zoomY;
  }

  public Dimension getPreferredSize() {
    return new Dimension(getZoomedWidth(), getZoomedHeight());
  }

  /** returns a scrollpane with the scroll-mode prevent-garbage-drawing fix applied */
  public JScrollPane makeScrollPane() {
    JScrollPane scrollPane = new JScrollPane(this);
    scrollPane.getViewport().setScrollMode(JViewport.BACKINGSTORE_SCROLL_MODE);
    return scrollPane;
  }

  public void zoomToDisplaySize() {
    if (image == null) return;
    Dimension display = getDisplaySize();
    double xRatio = display.width/(double) image.getWidth();
    double yRatio = display.height/(double) image.getHeight();
    setZoom(Math.min(xRatio, yRatio));
    revalidate();
  }

  /** tricky magic to get parent scroll pane */
  private Dimension getDisplaySize() {
    Container c = getParent();
    while (c != null) {
      if (c instanceof JScrollPane)
        return c.getSize();
      c = c.getParent();
    }
    return getSize();
  }

  public void setSelection(Rectangle r) {
    selection = r;
    repaint();
  }

  public Rectangle getSelection() {
    return selection;
  }

  public RGBImage getRGBImage() {
    return new RGBImage(getImage());
  }
}
class FrameWithImages {
  JFrame frame;
  ImageSurface[] surfaces;
  int n;
  
  FrameWithImages(int numImages) {
    frame = new JFrame("A JavaX Frame");
    
    n = numImages;
    JPanel grid = new JPanel(new GridLayout(n, 1));
    surfaces = new ImageSurface[n];
    for (int i = 0; i < n; i++)
      grid.add(surfaces[i] = new ImageSurface());
    
    frame.add(grid);
    frame.setBounds(100, 100, 100+400+20, 100+600);
  }
  
  void hop() {
    frame.setVisible(true);
    main.exitOnFrameClose(frame);
  }
  
  void setImage(int i, RGBImage img) {
    if (i >= 0 && i < n)
      surfaces[i].setImage(img);
  }
  
  void setInnerSize(RGBImage img) {
    double zoom = surfaces[0].getZoomX();
    frame.setSize((int) (img.getWidth()*zoom)+20, (int) (img.getHeight()*zoom)+40); // todo...
  }
  
  void setZoom(double zoom) {
    for (ImageSurface s : surfaces) s.setZoom(zoom);
  }
}


class P { double x, y; P(double x, double y) {
  this.y = y;
  this.x = x;} }

interface Reproducer {
  public main.Params reproduce(RGBImage original);
}
  
interface ReproducerMaker {
  public Reproducer make();
}

public class main {
  static int imageWidth = 200;
  
    static RGB probeRandomPixel(RGBImage image) {
    int x = (int) (random()*(image.getWidth()-1));
    int y = (int) (random()*(image.getHeight()-1));
    return image.getPixel(x, y);
  }
  
  static RGB randomColor() {
    return new RGB(random(), random(), random());
  }
  
  static RGBImage resizeToWidth(RGBImage image, int w) {
    return resize(image, w, (int) ((image.getHeight()*(double) w)/image.getWidth()));
  }
  
  public static RGBImage resize(RGBImage image, int w, int h) {
    if (w == image.getWidth() && h == image.getHeight()) return image;

    int[] pixels = new int[w*h];
    for (int y = 0; y < h; y++)
      for (int x = 0; x < w; x++)
        pixels[y*w+x] = image.getInt(x*image.getWidth()/w, y*image.getHeight()/h);
    return new RGBImage(w, h, pixels);
  }

  static Random _random = new Random();
  static double random() {
    return _random.nextInt(100001)/100000.0;
  }
  
  static int random(int max) {
    return _random.nextInt(max);
  }
  
  static double random(double min, double max) {
    return min+random()*(max-min);
  }
  
  static double normalize(double d) {
    return Math.max(0, Math.min(1, d));
  }
  
  static int round(double d) {
    return (int) Math.round(d);
  }
  
  static double mix(double a, double b, double bishness) {
    return a+(b-a)*bishness;
  }
  
  public static double pixelDiff(RGB a, RGB b) {
    return (Math.abs(a.r-b.r) + Math.abs(a.g-b.g) + Math.abs(a.b-b.b))/3;
  }

  public static double diff(RGBImage image, RGBImage image2) {
    int w = image.getWidth(), h = image.getHeight();
    double sum = 0;
    for (int y = 0; y < h; y++)
      for (int x = 0; x < w; x++)
        sum += pixelDiff(image.getRGB(x, y), image2.getRGB(x, y));
    return sum/(w*h);
  }
  
  public static void copy(RGBImage src, int srcX, int srcY, RGBImage dst, int dstX, int dstY, int w, int h) {
    for (int y = 0; y < h; y++)
      for (int x = 0; x < w; x++)
        dst.setPixel(dstX+x, dstY+y, src.getPixel(srcX+x, srcY+y));
  }
  
  static float varyChannel(float x) {
    return Math.max(0f, Math.min(1f, (float) (x+random(-0.1, 0.1))));
  }
  
  static double vary01(double x) {
    return Math.max(0, Math.min(1, x+random(-0.1, 0.1)));
  }
  
  static RGB varyColor(RGB rgb) {
    int s = random(3);
    if (s == 0)
      return new RGB(varyChannel(rgb.r), rgb.g, rgb.b);
    else if (s == 1)
      return new RGB(rgb.r, varyChannel(rgb.g), rgb.b);
    else
      return new RGB(rgb.r, rgb.g, varyChannel(rgb.b));
  }
 // helper functions for image reproduction
  
  static double pi = PI;
  
  static double rotate_x(P p, double angle) {
    angle = angle*pi/180;
    return p.x*cos(angle)-p.y*sin(angle);
  }
  
  static class Magnet extends Params {
    double cx, cy, angle;
    RGB col1 = new RGB(Color.black), col2 = new RGB(Color.white);
    
    RGB def(double x, double y) {
      P p = new P(x-cx, y-cy);
      x = rotate_x(p, -angle);
      return x < 0 ? col1 : col2;
    }
    
    Magnet copy() {
      Magnet p = new Magnet();
      baseClone(p);
      p.cx = cx;
      p.cy = cy;
      p.angle = angle;
      p.col1 = col1;
      p.col2 = col2;
      return p;
    }
    
    public String toString() {
      return "M " + formatDouble(cx, 2) + " " + formatDouble(cy, 2) + " " + (int) angle + " " + col1 + " " + col2;
    }

    RGBImage render() {
      int w = originalImage.getWidth(), h = originalImage.getHeight();
      RGBImage image = new RGBImage(w, h, Color.white);
      paint(image, this);
      return image;
    }
  }

  static abstract class Params {
    RGBImage originalImage;
    abstract RGBImage render();
    abstract Params copy();
    
    void baseClone(Params p) {
      p.originalImage = originalImage;
    }
    
    RGBImage rendered;
    RGBImage getImage() {
      if (rendered == null)
        rendered = render();
      return rendered;
    }
    
    double score = 2.0;
    double getScore() {
      if (score == 2.0)
        score = calcScore();
      return score;
    }
    
    double calcScore() {
      return diff(originalImage, getImage());
    }
    
    boolean isBetterThan(Params p) {
      return getScore() < p.getScore();
    }
  }
  
  static class SlantedSplit extends Params {
    double splitPointL, splitPointR;
    RGB col1, col2;
    boolean swap;
    
    SlantedSplit copy() {
      SlantedSplit p = new SlantedSplit();
      baseClone(p);
      p.splitPointL = splitPointL;
      p.splitPointR = splitPointR;
      p.col1 = col1;
      p.col2 = col2;
      p.swap = swap;
      return p;
    }
    
    public String toString() {
      return (swap ? "SlantedHSplit " : "SlantedVSplit ") + splitPointL + " " + splitPointR + " " + col1 + " " + col2;
    }

    RGBImage render() {
      int w = originalImage.getWidth(), h = originalImage.getHeight();
      RGBImage image = new RGBImage(w, h, Color.white);
      slantedSplit(image, this);
      return image;
    }
  }
  
  static class RandomMagnet implements Reproducer {
    int n = -1;
    public Params reproduce(RGBImage original) {
      ++n;
      Magnet p = new Magnet();
      p.originalImage = original;
      p.cx = random();
      p.cy = random();
      p.angle = random()*360;
      if (n % 2 == 0) {
        p.col1 = randomColor();
        p.col2 = randomColor();
      } else {
        p.col1 = probeRandomPixel(original);
        p.col2 = probeRandomPixel(original);
      }
      return p;
    }
  }
  
  static class RandomSlantedSplit implements Reproducer {
    int n = -1;
    public Params reproduce(RGBImage original) {
      ++n;
      SlantedSplit p = new SlantedSplit();
      p.swap = random(2) == 0;
      p.originalImage = original;
      p.splitPointL = random();
      p.splitPointR = random();
      if (n % 2 == 0) {
        p.col1 = randomColor();
        p.col2 = randomColor();
      } else {
        p.col1 = probeRandomPixel(original);
        p.col2 = probeRandomPixel(original);
      }
      return p;
    }
  }
  
  static class VaryBest implements Reproducer {
    Reproducer base;
    Params best;
    
    VaryBest(Reproducer base) {
      this.base = base;
    }
    
    public Params reproduce(RGBImage original) {
      Params p = base.reproduce(original);
      if (best == null || p.isBetterThan(best))
        best = p;
      Params variation = vary(best);
      //System.out.println("Best: " + best.getScore() + ", variation: " + variation.getScore());
      if (variation.isBetterThan(best)) {
        //System.out.println("Using variation, diff=" + (best.getScore()-variation.getScore()));
        best = variation;
      }
      return best;
    }
    
    Params vary(Params p) {
      if (p instanceof SlantedSplit) {
        SlantedSplit n = ((SlantedSplit) p).copy();
        int s = random(3);
        if (s == 0)
          varySplitPoint(n);
        else if (s == 1)
          n.col1 = varyColor(n.col1);
        else
          n.col2 = varyColor(n.col2);
        return n;
      }
      
      if (p instanceof Magnet) {
        Magnet n = ((Magnet) p).copy();
        int s = random(3);
        if (s == 0) {
          s = random(3);
          if (s == 0)
            n.cx = varyN(n.cx);
          else if (s == 1)
            n.cy = varyN(n.cy);
          else {
            //double old = n.angle;
            n.angle = (n.angle+360+random(-5, 5)) % 360;
            //System.out.println("angle: " + formatDouble(old, 1) + " -> " + formatDouble(n.angle, 1));
          }
        } else if (s == 1)
          n.col1 = varyColor(n.col1);
        else
          n.col2 = varyColor(n.col2);
        return n;
      }
      
      return null;
    }
    
    void varySplitPoint(SlantedSplit p) {
      if (random(2) == 0)
        p.splitPointL = Math.max(0, Math.min(1, p.splitPointL+random(-0.1, 0.1)));
      else
        p.splitPointR = Math.max(0, Math.min(1, p.splitPointR+random(-0.1, 0.1)));
    }
    
    double varyN(double x) {
      return Math.max(0, Math.min(1, x+random(-0.1, 0.1)));
    }
    
    float varyChannel(float x) {
      return Math.max(0f, Math.min(1f, (float) (x+random(-0.1, 0.1))));
    }
    
    RGB varyColor(RGB rgb) {
      int s = random(3);
      if (s == 0)
        return new RGB(varyChannel(rgb.r), rgb.g, rgb.b);
      else if (s == 1)
        return new RGB(rgb.r, varyChannel(rgb.g), rgb.b);
      else
        return new RGB(rgb.r, rgb.g, varyChannel(rgb.b));
    }
  }

  static class Gridded extends Params {
    int w, h;
    Params[] array;
    
    Gridded(int w, int h) {
      this.w = w;
      this.h = h;
      array = new Params[w*h];
    }
    
    Gridded copy() {
      Gridded p = new Gridded(w, h);
      baseClone(p);
      for (int i = 0; i < w*h; i++)
        p.array[i] = array[i].copy();
      return p;
    }
    
    public String toString() {
      StringBuilder buf = new StringBuilder("grid{");
      for (int i = 0; i < w*h; i++) {
        if (i != 0)
          buf.append(", ");
        buf.append(array[i]);
      }
      return buf + "}";
    }
    
    public RGBImage render() {
      int ow = originalImage.getWidth(), oh = originalImage.getHeight();
      RGBImage img = new RGBImage(ow, oh, Color.white);
      for (int y = 0; y < h; y++)
        for (int x = 0; x < w; x++) {
          int x1 = x*ow/w, y1 = y*oh/h;
          int x2 = (x+1)*ow/w, y2 = (y+1)*oh/h;
          RGBImage part = array[y*w+x].render();
          main.copy(part, 0, 0, img, x1, y1, part.getWidth(), part.getHeight());
        }
      return img;
    }
  }
  
  static class Grid implements Reproducer {
    int w, h;
    Reproducer[] bases;
    
    Grid(ReproducerMaker maker, int w, int h) {
      this.w = w;
      this.h = h;
      bases = new Reproducer[w*h];
      for (int i = 0; i < w*h; i++)
        bases[i] = maker.make();
    }
    
    RGBImage getGridElement(RGBImage originalImage, int i) {
      int ow = originalImage.getWidth(), oh = originalImage.getHeight();
      int y = i / w;
      int x = i % w;
      int x1 = x*ow/w, y1 = y*oh/h;
      int x2 = (x+1)*ow/w, y2 = (y+1)*oh/h;
      return originalImage.clip(x1, y1, x2-x1, y2-y1);
    }
      
    public Params reproduce(RGBImage original) {
      Gridded gridded = new Gridded(w, h);
      gridded.originalImage = original;
      for (int i = 0; i < w*h; i++) {
        RGBImage img = getGridElement(original, i);
        Params p = bases[i].reproduce(img);
        if (p == null)
          return null;
        gridded.array[i] = p;
      }
      return gridded;
    }
  }
  
  static ReproducerMaker baseMaker = new ReproducerMaker() {
    public Reproducer make() {
      //return new VaryBest(new RandomSlantedSplit());
      return new VaryBest(new RandomMagnet());
    }
  };
    
  // main reproduce function
  static Reproducer reproducer;

  static String imageID = "#1000326"; // Bryan Cranston!
  static RGBImage originalImage;
  static FrameWithImages fwi;
  static double zoom = 1;
    
  public static void main(String[] args) throws Exception {
    for (int i = 0; i < args.length; i++) {
      String arg = args[i];
      if (isSnippetID(arg))
        imageID = arg;
      else if (arg.equals("zoom"))
        zoom = Double.parseDouble(args[++i]);
      else if (arg.equals("w") || arg.equals("width")) {
        String w = args[++i];
        imageWidth = w.equals("original") ? -1 : Integer.parseInt(w);
      } else
        System.out.println("Unknown argument: " + arg);
    }

    fwi = new FrameWithImages(1);
    fwi.hop();
    
    Thread _t = new Thread() {
public void run() {
try {

      originalImage = loadImage(imageID);
      if (imageWidth < 0)
        imageWidth = originalImage.getWidth();
      else
        originalImage = resizeToWidth(originalImage, imageWidth);
      fwi.setZoom(zoom);
      fwi.setInnerSize(originalImage);
      
      int gx = originalImage.getWidth()/8, gy = originalImage.getHeight()/8;
      reproducer = new Grid(baseMaker, gx, gy);
      
      reproduceOpenEnd(originalImage);
    } catch (Exception _e) {
  throw _e instanceof RuntimeException ? (RuntimeException) _e : new RuntimeException(_e); } }
};
_t.start();
    
    /*
    Magnet m = new Magnet();
    m.cx = m.cy = 0.5;
    m.angle = 30;
    
    while (true) {
      m.angle = (m.angle+1) % 360;
      //System.out.println("Angle: " + m.angle);
      RGBImage img = new RGBImage(100, 100, Color.gray);
      paint(img, m);
      fwi.setImage(0, img);
    }
    */
  }
  
  
  static void reproduceOpenEnd(RGBImage original) {
    Params best = null;
    long lastPrint = 0, lastN = 0;
    for (long ntry = 1; ; ntry++) {
      long now = System.currentTimeMillis();
      if (now >= lastPrint+1000) {
        long tps = (ntry-lastN)*1000/(now-lastPrint);
        lastPrint = now;
        lastN = ntry;
        String s = "Try " + ntry + "(" + tps + "/s)";
        if (best == null)
          System.out.println(s);
        else {
          System.out.println("Best: " + best);
          System.out.println(s + ", score: " + formatDouble(best.getScore()*100, 3) + "%, structure size: " + structureSize(best, Params.class));
        }
      }
      Params p = reproducer.reproduce(original);
      if (best == null || p != null && p.getScore() < best.getScore()) {
        //System.out.println("New best! " + p.getScore());
        best = p;
        fwi.setImage(0, p.getImage());
      }
      
      if (p != null && p.getScore() == 0.0)
        break;
    }
  }
  
  static void paint(RGBImage img, Magnet m) {
    int w = img.getWidth(), h = img.getHeight();
    for (int y = 0; y < h; y++)
      for (int x = 0; x < w; x++) {
        double nx = x/(double)(w-1);
        double ny = y/(double)(h-1);
        img.setPixel(x, y, m.def(nx, ny));
      }
  }
  
  static void slantedSplit(RGBImage img, SlantedSplit p) {
    int w = img.getWidth(), h = img.getHeight();
    for (int yy = 0; yy < h; yy++)
      for (int xx = 0; xx < w; xx++) {
        double x = ((double) xx)/(w-1);
        double y = ((double) yy)/(h-1);
        if (p.swap) {
          double temp = x; x = y; y = x;
        }
        double splitPoint = mix(p.splitPointL, p.splitPointR, x);
        RGB col = y <= splitPoint ? p.col1 : p.col2;
        img.setPixel(xx, yy, col);
      }
  }

  public static boolean isSnippetID(String s) {
    try {
      parseSnippetID(s);
      return true;
    } catch (RuntimeException e) {
      return false;
    }
  }

  static void exitOnFrameClose(JFrame frame) {
    frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
  }


  static Class<?> getClass(String name) {
    try {
      return Class.forName(name);
    } catch (ClassNotFoundException e) {
      return null;
    }
  }

  static void set(Class c, String field, Object value) {
    try {
      Field f = set_findStaticField(c, field);
      f.setAccessible(true);
      f.set(null, value);
    } catch (Exception e) {
      throw new RuntimeException(e);
    }
  }
  
  static Field set_findStaticField(Class<?> c, String field) {
    for (Field f : c.getDeclaredFields())
      if (f.getName().equals(field) && (f.getModifiers() & Modifier.STATIC) != 0)
        return f;
    throw new RuntimeException("Static field '" + field + "' not found in " + c.getName());
  }

  public static String formatDouble(double d, int digits) {
    String format = "0.";
    for (int i = 0; i < digits; i++) format += "#";
    return new java.text.DecimalFormat(format, new java.text.DecimalFormatSymbols(Locale.ENGLISH)).format(d);
  }


  static boolean loadImage_useImageCache = true;
  
  static RGBImage loadImage(String snippetID) {
   try {
    // TODO: androidify
    File dir = new File(System.getProperty("user.home"), ".tinybrain/image-cache");
    if (loadImage_useImageCache) {
      dir.mkdirs();
      File file = new File(dir, snippetID + ".png");
      if (file.exists() && file.length() != 0)
        try {
          return new RGBImage(ImageIO.read(file));
        } catch (Throwable e) {
          e.printStackTrace();
          // fall back to loading from sourceforge
        }
    }

    String imageURL = loadImage_getImageURL(parseSnippetID(snippetID));
    System.err.println("Loading image: " + imageURL);
    BufferedImage image = ImageIO.read(new URL(imageURL));

    if (loadImage_useImageCache) {
      File tempFile = new File(dir, snippetID + ".tmp." + System.currentTimeMillis());
      ImageIO.write(image, "png", tempFile);
      tempFile.renameTo(new File(dir, snippetID + ".png"));
      //Log.info("Cached image.");
    }

    //Log.info("Loaded image.");
    return new RGBImage(image);
   } catch (IOException e) {
    throw new RuntimeException(e);
   }
  }

  static String loadImage_getImageURL(long snippetID) throws IOException {
    String url;
    if (snippetID == 1000010 || snippetID == 1000012)
      url = "http://tinybrain.de:8080/tb/show-blobimage.php?id=" + snippetID;
    else
      url = "http://eyeocr.sourceforge.net/filestore/filestore.php?cmd=serve&file=blob_" + snippetID
        + "&contentType=image/png";
    return url;
  }

  public static int structureSize(Object o, Class baseClass) {
    return structureSize(o, baseClass, new IdentityHashMap());
  }
  
  static int structureSize(Object o, Class baseClass,
    IdentityHashMap seen) {
    if (o == null || seen.containsKey(o)) return 0;
    seen.put(o, Boolean.TRUE);
    int size = 1;
    Class c = o.getClass();
    if (c.isArray()) {
      int n = Array.getLength(o);
      for (int i = 0; i < n; i++)
        size += structureSize(Array.get(o, i), baseClass, seen);
    } else
      while (c != Object.class && c != baseClass) {
        Field[] fields = c.getDeclaredFields();
        for (Field field : fields) {
          if ((field.getModifiers() & Modifier.STATIC) != 0)
            continue;
          if (field.getType().isPrimitive())
            ++size;
          else {
            Object value = null;
            try {
              value = field.get(o);
            } catch (IllegalAccessException e) {
              throw new RuntimeException(e);
            }
            size += structureSize(value, baseClass, seen);
          }
        }
        c = c.getSuperclass();
      }
    return size;
  }

  static boolean preferCached = false;

  public static String loadSnippet(String snippetID) throws IOException {
    return loadSnippet(parseSnippetID(snippetID), preferCached);
  }

  public static String loadSnippet(String snippetID, boolean preferCached) throws IOException {
    return loadSnippet(parseSnippetID(snippetID), preferCached);
  }

  public static long parseSnippetID(String snippetID) {
    return Long.parseLong(shortenSnippetID(snippetID));
  }

  private static String shortenSnippetID(String snippetID) {
    if (snippetID.startsWith("#"))
      snippetID = snippetID.substring(1);
    String httpBlaBla = "http://tinybrain.de/";
    if (snippetID.startsWith(httpBlaBla))
      snippetID = snippetID.substring(httpBlaBla.length());
    return snippetID;
  }

  public static String loadSnippet(long snippetID, boolean preferCached) throws IOException {
    if (preferCached) {
      initSnippetCache();
      String text = DiskSnippetCache_get(snippetID);
      if (text != null)
        return text;
    }

    String text;
    try {
      URL url = new URL("http://tinybrain.de:8080/getraw.php?id=" + snippetID);
      text = loadPage(url);
    } catch (FileNotFoundException e) {
      throw new IOException("Snippet #" + snippetID + " not found or not public");
    }

    try {
      initSnippetCache();
      DiskSnippetCache_put(snippetID, text);
    } catch (IOException e) {
      System.err.println("Minor warning: Couldn't save snippet to cache ("  + DiskSnippetCache_getDir() + ")");
    }

    return text;
  }

  static File DiskSnippetCache_dir;

  public static void initDiskSnippetCache(File dir) {
    DiskSnippetCache_dir = dir;
    dir.mkdirs();
  }

  public static synchronized String DiskSnippetCache_get(long snippetID) throws IOException {
    return loadTextFile(DiskSnippetCache_getFile(snippetID).getPath(), null);
  }

  private static File DiskSnippetCache_getFile(long snippetID) {
    return new File(DiskSnippetCache_dir, "" + snippetID);
  }

  public static synchronized void DiskSnippetCache_put(long snippetID, String snippet) throws IOException {
    saveTextFile(DiskSnippetCache_getFile(snippetID).getPath(), snippet);
  }

  public static File DiskSnippetCache_getDir() {
    return DiskSnippetCache_dir;
  }

  public static void initSnippetCache() {
    if (DiskSnippetCache_dir == null)
      initDiskSnippetCache(new File(System.getProperty("user.home"), ".tinybrain/snippet-cache"));
  }
  

  public static String loadPage(String url) throws IOException {
    if (url.indexOf("://") < 0)
      url = "http://" + url;
    return loadPage(new URL(url));
  }
  
  public static String loadPage(URL url) throws IOException {
    System.out.println("Loading: " + url.toExternalForm());
    URLConnection con = url.openConnection();
    return loadPage(con, url);
  }

  public static String loadPage(URLConnection con, URL url) throws IOException {
    String contentType = con.getContentType();
    if (contentType == null)
      throw new IOException("Page could not be read: " + url);
    //Log.info("Content-Type: " + contentType);
    String charset = loadPage_guessCharset(contentType);
    Reader r = new InputStreamReader(con.getInputStream(), charset);
    StringBuilder buf = new StringBuilder();
    while (true) {
      int ch = r.read();
      if (ch < 0)
        break;
      //Log.info("Chars read: " + buf.length());
      buf.append((char) ch);
    }
    return buf.toString();
  }
  
  static String loadPage_guessCharset(String contentType) {
    Pattern p = Pattern.compile("text/html;\\s+charset=([^\\s]+)\\s*");
    Matcher m = p.matcher(contentType);
    /* If Content-Type doesn't match this pre-conception, choose default and hope for the best. */
    return m.matches() ? m.group(1) : "ISO-8859-1";
  }


  /** writes safely (to temp file, then rename) */
  public static void saveTextFile(String fileName, String contents) throws IOException {
    File file = new File(fileName);
    File parentFile = file.getParentFile();
    if (parentFile != null)
      parentFile.mkdirs();
    String tempFileName = fileName + "_temp";
    FileOutputStream fileOutputStream = new FileOutputStream(tempFileName);
    OutputStreamWriter outputStreamWriter = new OutputStreamWriter(fileOutputStream, "UTF-8");
    PrintWriter printWriter = new PrintWriter(outputStreamWriter);
    printWriter.print(contents);
    printWriter.close();
    if (file.exists() && !file.delete())
      throw new IOException("Can't delete " + fileName);

    if (!new File(tempFileName).renameTo(file))
      throw new IOException("Can't rename " + tempFileName + " to " + fileName);
  }

  public static String loadTextFile(String fileName, String defaultContents) throws IOException {
    if (!new File(fileName).exists())
      return defaultContents;

    FileInputStream fileInputStream = new FileInputStream(fileName);
    InputStreamReader inputStreamReader = new InputStreamReader(fileInputStream, "UTF-8");
    return loadTextFile(inputStreamReader);
  }

  public static String loadTextFile(Reader reader) throws IOException {
    StringBuilder builder = new StringBuilder();
    try {
      BufferedReader bufferedReader = new BufferedReader(reader);
      String line;
      while ((line = bufferedReader.readLine()) != null)
        builder.append(line).append('\n');
    } finally {
      reader.close();
    }
    return builder.length() == 0 ? "" : builder.substring(0, builder.length()-1);
  }
}