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.zip.*;
import java.util.*;
import java.awt.*;
import java.awt.image.*;
import java.util.List;
import javax.imageio.*;




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());
  }
} // image classes
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) {
    setInnerSize(img.getWidth(), img.getHeight());
  }
  
  void setInnerSize(int w, int h) {
    double zoom = surfaces[0].getZoomX();
    frame.setSize((int) (w*zoom)+20, (int) (h*zoom*n)+40); // todo...
  }
  
  void setZoom(double zoom) {
    for (ImageSurface s : surfaces) s.setZoom(zoom);
  }
}
 // FrameWithImages

public class main {
  static RGBImage originalImage;
  static int imageWidth = 200;
  
  static FrameWithImages frame;
  
  // XXX - main reproduce function
  static Reproducer reproducer =
    /*new Layers(
      new RandomSolid())
      .add(2, RandomBox.class)
    .varyBest;*/
    //new OptimizeIndividual(new RandomBox());
    new ProduceIndividual(new RandomBox());
    
  static abstract class Img {
    RGBImage img;
    
    Img(RGBImage img) {
  this.img = img;}
    
    int getWidth() { return img.getWidth(); }
    int getHeight() { return img.getHeight(); }
    //abstract void setPixel(int x, int y, int rgb);
    
    abstract void setPixel(int x, int y, RGB rgb);/* {
      setPixel(x, y, rgb.asInt());
    }*/
  }
  
  static class Painting extends Img {
    Painting(RGBImage img) { super(img); }
    
    void setPixel(int x, int y, RGB rgb) {
      img.setPixel(x, y, rgb);
    }
  }
    
  static class Diffing extends Img {
    int pixelsDiffed;
    double totalDiff;
    double[] diffed;
    
    Diffing(RGBImage img) {
      super(img);
      diffed = new double[img.getWidth()*img.getHeight()];
      for (int i = 0; i < diffed.length; i++) diffed[i] = -1;
    }

    void setPixel(int x, int y, RGB rgb) {
      int w = img.getWidth(), h = img.getHeight();
      if (x < 0 || y < 0 || x >= w || y >= h) return;
      double old = diffed[x+y*w];
      if (old >= 0)
        totalDiff -= old;
      else
        pixelsDiffed++;
      double diff = pixelDiff(img.getPixel(x, y), rgb);
      diffed[x+y*w] = diff;
      totalDiff += diff;
    }
    
    double getScore() {
      int totalPixels = img.getWidth()*img.getHeight();
      int emptyPixels = totalPixels-pixelsDiffed;
      double innerQuality = totalDiff/Math.max(pixelsDiffed, 1);
      double outerQuality = 0.8; // makes objects shrink or grow
      double result = mix(innerQuality, outerQuality, emptyPixels/(double) totalPixels);
      //System.out.println("inner=" + innerQuality + ", outer=" + outerQuality + ", pixels diffed=" + pixelsDiffed + ", result=" + result);
      return result;
    }
  }

  static abstract class Base {
    abstract Base copy();
    
    abstract void vary();
    
    Base copyVary() {
      Base copy = copy();
      copy.vary();
      return copy;
    }
  }
  
  static abstract class Overlay extends Base {
    abstract Overlay copy();
    abstract void renderOn(Img image);
  }
  
  // Params must be immutable!
  static abstract class Params extends Base {
    RGBImage originalImage;
    abstract Params copy();
    abstract RGBImage render();

    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 Box extends Overlay {
    double cx, cy, w, h;
    RGB color;

    Box copy() {
      Box p = new Box();
      p.cx = cx;
      p.cy = cy;
      p.w = w;
      p.h = h;
      p.color = color;
      return p;
    }
    
    public String toString() {
      return "Box " + cx + " " + cy + " " + w + " " + h + " " + color;
    }

    void renderOn(Img image) {
      box(image, this);
    }
    
    void vary() {
      int s = random(5);
      if (s == 0)
        cx = vary01(cx);
      else if (s == 1)
        cy = vary01(cy);
      else if (s == 2)
        w = vary01(w);
      else if (s == 3)
        h = vary01(h);
      else
        color = varyColor(color);
    }
  }
  
  static class Solid extends Overlay {
    RGB col;
    
    Solid() {}
    Solid(RGB col) {
  this.col = col;}
    
    Solid copy() {
      Solid p = new Solid();
      p.col = col;
      return p;
    }
    
    public String toString() {
      return "Solid " + col;
    }

    void renderOn(Img image) {
      int w = image.getWidth(), h = image.getHeight();
      for (int y = 0; y < h; y++)
        for (int x = 0; x < w; x++)
          image.setPixel(x, y, col);
    }
    
    void vary() {
      col = varyColor(col);
    }
  }
  
  interface Reproducer {
    public Params reproduce(RGBImage original);
  }
  
  interface OverlayReproducer {
    public Overlay reproduce(RGBImage original);
  }
  
  static class RandomBox implements OverlayReproducer {
    int n = -1;
    public Overlay reproduce(RGBImage original) {
      ++n;
      Box p = new Box();
      p.cx = random();
      p.cy = random();
      p.w = random()*0.1;
      p.h = random()*0.1;
      if (n % 2 == 0)
        p.color = randomColor();
      else
        p.color = probeRandomPixel(original);
      return p;
    }
  }
  
  static class RandomSolid implements OverlayReproducer {
    int n = -1;
    public Overlay reproduce(RGBImage original) {
      ++n;
      Solid p = new Solid();
      if (n % 2 == 0) {
        p.col = randomColor();
      } else {
        p.col = probeRandomPixel(original);
      }
      return p;
    }
  }
  
  static class WhiteSolid implements OverlayReproducer {
    public Overlay reproduce(RGBImage original) {
      Solid p = new Solid();
      p.col = new RGB(Color.white);
      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 = (Params) best.copyVary();
      //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;
    }
    
    void reset() {
      best = null;
    }
  }
  
  static class Layered extends Params {
    Layers myMaker;
    Overlay[] list;
    
    Layered(Layers myMaker, Overlay... list) {
      this.myMaker = myMaker;
      this.list = list;
    }
    
    Layered copy() {
      Layered p = new Layered(myMaker, new Overlay[list.length]);
      baseClone(p);
      for (int i = 0; i < list.length; i++)
        p.list[i] = (Overlay) list[i].copy();
      return p;
    }
    
    public String toString() {
      StringBuilder buf = new StringBuilder("layered{");
      for (int i = 0; i < list.length; i++) {
        if (i != 0)
          buf.append(", ");
        buf.append(list[i]);
      }
      return buf + "}";
    }

    RGBImage render() {
      RGBImage image = new RGBImage(originalImage.getWidth(), originalImage.getHeight(), Color.white);
      Painting img = new Painting(image);
      for (int i = 0; i < list.length; i++)
        list[i].renderOn(img);
      return image;
    }
    
    void vary() {
      int i = random(list.length);
      if (random(2) == 0 || myMaker == null) {
        //System.out.println("Varying layer " + i);
        list[i] = (Overlay) list[i].copyVary();
      } else {
        //double score = getScore();
        OverlayReproducer maker = myMaker.list[i];
        list[i] = maker.reproduce(originalImage);
        //System.out.println("Exchanging layer " + i + " from " + maker + ", improvement: " + (score-getFreshScore()));
      }
    }
  }

  static class Layers implements Reproducer {
    OverlayReproducer[] list;
    long ntry = -1;
    int stepTime = 0/*500*/;
    VaryBest varyBest = new VaryBest(this);
    
    Layers(OverlayReproducer... list) {
  this.list = list;}
    
    Layers add(int n, Class<? extends OverlayReproducer> xClass) { try {
 
      OverlayReproducer l[] = new OverlayReproducer[list.length+n];
      System.arraycopy(list, 0, l, 0, list.length);
      for (int i = 0; i < n; i++)
        l[list.length+i] = xClass.newInstance();
      list = l;
      return this;
    
} catch (Throwable __e) { throw __e instanceof RuntimeException ? (RuntimeException) __e : new RuntimeException(__e); }}
    
    public Params reproduce(RGBImage original) {
      ++ntry;
      int n = this.list.length;
      if (stepTime != 0) {
        // build up image gradually to optimize lower layers first
        n = (int) Math.min(n, ntry/stepTime+1);
        varyBest.reset();
      }
      Overlay[] list = new Overlay[n];
      for (int i = 0; i < n; i++)
        list[i] = this.list[i].reproduce(original);
      Layered result = new Layered(this, list);
      result.originalImage = original;
      return result;
    }
  }
  
  static Params reproduce(RGBImage original) {
    int w = original.getWidth(), h = original.getHeight();
    return reproducer.reproduce(original);
  }
  
  static class ProduceIndividual implements Reproducer {
    OverlayReproducer producer;

    ProduceIndividual(OverlayReproducer producer) {
  this.producer = producer;}

    public Params reproduce(RGBImage original) {
      Overlay overlay = producer.reproduce(original);
      Layered result = new Layered(null, new Solid(new RGB(Color.white)), overlay);
      result.originalImage = original;
      return result;
    }
  }
  
  static class OptimizeIndividual implements Reproducer {
    OverlayReproducer producer;
    double bestScore;
    Overlay best;
    
    OptimizeIndividual(OverlayReproducer producer) {
  this.producer = producer;}

    public Params reproduce(RGBImage original) {
      Overlay overlay = producer.reproduce(original);
      //System.out.println("overlay: " + overlay);
      double score = scoreOverlay(overlay, original);
      if (best == null || score <= bestScore) {
        best = overlay;
        bestScore = score;
      }
      Layered result = new Layered(null, new Solid(new RGB(Color.black)), best);
      result.originalImage = original;
      return result;
    }
  }
  
  static double scoreOverlay(Overlay overlay, RGBImage original) {
    Diffing d = new Diffing(original);
    overlay.renderOn(d);
    return d.getScore();
  }
  
  static class HoldBest implements Reproducer {
    Reproducer base;
    Params best;
    HoldBest(Reproducer base) {
  this.base = base;}
    
    public Params reproduce(RGBImage original) {
      Params p = base.reproduce(original);
      if (best == null || p.isBetterThan(best))
        best = p;
      return best;
    }
  }

  static class BestHolder {
    Params best;

    public boolean receive(Params p) {
      if (best == null || p.isBetterThan(best)) {
        best = p;
        return true;
      }
      return false;
    }
  }

  public static void main(String[] args) throws Exception {
    String imageID = "#1000332"; // Picture of two coins
    
    for (int i = 0; i < args.length; i++) {
      String arg = args[i];
      if (arg.equals("width"))
        imageWidth = Integer.parseInt(args[++i]);
      else if (isSnippetID(arg))
        imageID = arg;
    }
    
    final String _imageID = imageID;
    
    frame = new FrameWithImages(3);
    frame.frame.setVisible(true);
    exitOnFrameClose(frame.frame);
    
    new Thread() {
      public void run() {
        originalImage = loadImage(_imageID);
        originalImage = resizeToWidth(originalImage, imageWidth);
        frame.setImage(frame.n-1, originalImage);
        
        reproduceOpenEnd(originalImage);
      }
    }.start();
  }
  
  static void reproduceOpenEnd(RGBImage original) {
    BestHolder bestHolder = new BestHolder();
    
    long lastPrint = 0, lastN = 0;
    for (long ntry = 1; ; ntry++) {
      Params p = reproduce(original);
      frame.setImage(0, p.getImage());
      
      if (bestHolder.receive(p))
        frame.setImage(1, bestHolder.best.getImage());
      
      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)";
        System.out.println(s + ", score: " + formatDouble(p.getScore()*100, 2) + "%, structure size: " + structureSize(p, Params.class));
      }

      if (p != null && p.getScore() == 0.0)
        break; // perfect result, end
    }
  }
  
    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));
  }
  
    static void box(Img img, Box p) {
    int w = img.getWidth(), h = img.getHeight();
    double x1 = normalize(p.cx-p.w), x2 = normalize(p.cx+p.w);
    double y1 = normalize(p.cy-p.h), y2 = normalize(p.cy+p.h);
    int xx1 = round(x1*(w-1)), xx2 = round(x2*(w-1));
    int yy1 = round(y1*(h-1)), yy2 = round(y2*(h-1));
    
    for (int yy = yy1; yy <= yy2; yy++)
      for (int xx = xx1; xx <= xx2; xx++)
        img.setPixel(xx, yy, p.color);
  }
  
 // box painting function

  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;
    }
  }

  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;
  }

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

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;
}
}