// Optimal many-translucent-circles painter
// [ O(w*h) + O(n*r) ]
//
// with
//   w = image width
//   h = image height
//   n = # circles
//   r = average height of a circle
//
// Comparison:
// - Naive painting is O(w*h) + O(n*r*r)
// - Naive raytracing is O(w*h*n)
//
// Loose proof of optimality:
// - A term of O(w*h) is always required just to paint each pixel.
// - And n*r is the minimum number of steps you have to do to actually
//   figure out each circle's shape (either by walking around it
//   or by calculating its width on each line).

sclass ManyCirclePainter is MakesBufferedImage {
  settable int w;
  settable int h;
  settable new L<Circle> circles;
  int[] pixels;

  L<Circle>[] startCircle, stopCircle;
  bool ran;
  
  srecord Circle(Pt center, int radius) {}
  
  public int getWidth() { ret w; }
  public int getHeight() { ret h; }
  
  selfType addCircle(int x, int y, int radius) {
    circles.add(new Circle(pt(x, y), radius));
    this;
  }

  run {
    if (ran) ret;
    set ran;
    pixels = new int[w*h];
    if (pixels.length == 0) ret;
    int nCircles = l(circles);
    
    startCircle = new L[h];
    stopCircle = new L[h];
    for (circle : circles) {
      int y1 = max(0, circle.center.y-circle.radius);
      int y2 = circle.center.y+circle.radius+1;
      if (y1 >= y2) continue;
      startCircle[y1] = addOrCreate(startCircle[y1], circle);
      if (y2 < h)
        stopCircle[y2] = addOrCreate(stopCircle[y2], circle);
    }
    
    int[] startStop = new[w];
    new Set<Circle> liveCircles;
    int iPixel = 0;
    
    for y to h: {
      fillArray(startStop, 0);
      addAll(liveCircles, startCircle[y]);
      removeAll(liveCircles, stopCircle[y]);
      for (c : liveCircles) {
        // width of circle at this line
        int width = iround(sqrt(sqr(c.radius)-sqr(y-c.center.y)));
        int x1 = c.center.x-width, x2 = c.center.x+width+1;
        if (x1 > w || x2 <= 0) continue; // not visible at all at this row
        startStop[max(x1, 0)]++;
        if (x2 < w)
          startStop[x2]--;
      }
      
      int count = 0;
      for x to w: {
        count += startStop[x];
        pixels[iPixel++] = countToColor(count, nCircles);
      }
    }
  }
  
  int countToColor(int count, int nCircles) {
    ret rgbIntFromBrightness(doubleRatio(count, min(nCircles, 8)));
  }
  
  public BufferedImage getBufferedImage aka get() {
    run();
    ret bufferedImageWithoutAlpha(w, h, pixels);
  }
}