// Abstract base class for tiling an image (G22Tiling)

abstract srecord noeq G22AbstractTiler<Img extends WidthAndHeight>(Img image) is Runnable, Steppable {
  delegate Tile to G22Tiling.
  
  int w, h, runner;
  gettable int size; // =w*h
  
  event tileStarted(GrowingTile tile);
  event tileDone(GrowingTile tile);
  
  // iterator that provides points to be looked at
  // (e.g. a WeightlessShuffledIterator)
  IndexIterator pointIterator;
  
  // Temporary stack of points to be looked at
  // (e.g. neighbors of a tile just discovered).
  // May or may not be used.
  new IntBuffer stack;

  G22Tiling<Img> tiling; // the tiling we are making
  
  int tileCounter;
  GrowingTile growingTile; // tile currently being grown
  
  bool verbose;
  
  // The one method subclasses need to override.
  // The exact meaning of a "color" is not defined,
  // the tiler just treats different int value as different colors.
  abstract int getColor(int pos);
  
  // calculations for positions (pixel index)
  int x(int pos) { ret pos % w; }
  int y(int pos) { ret pos / w; }
  int pos(int x, int y) { ret y*w+x; }
  Pt pt(int pos) { ret Pt(x(pos), y(pos)); }
  bool validPos(int x, int y) { ret x >= 0 && y >= 0 && x < w && y < h; }
  
  int getColor(int x, int y) { ret getColor(pos(x, y)); }
  
  class GrowingTile is Steppable {
    Tile tile;
    int color;
    
    // Still growing in any of the 4 directions?
    bool growingN = true;
    bool growingE = true;
    bool growingS = true;
    bool growingW = true;
    
    *(int pos) {
      int x = x(pos), y = y(pos);
      color = getColor(x, y);
      int iTile = tileCounter++;
      tile = tiling.new Tile(iTile, color, rect(x, y, 1, 1));
      tiling.tiles.add(tile);
    }
    
    // put tile into tileMatrix
    void finish {
      Rect r = tile.position();
      int rx = r.x, ry = r.y, rw = r.w, rh = r.h;
      int[] matrix = tiling.tileMatrix;
      int iTile = tile.index;
      for y to rh:
        for x to rw: {
          int pos = (ry+y)*w+(rx+x);
          if (matrix[pos] != 0)
            fail("Overlapping tiles!");
          matrix[pos] = iTile+1;
        }
      tiling.pixelsCovered += rw*rh;
    }
    
    public bool step() {
      Rect r = nextRect();
      if (r == null) {
        finish();
        false;
      }
      
      tile.position(r);
      true;
    }
    
    // Is this pixel in the image and the tile's color
    // and not in a tile?
    bool isContinuation(int x, int y) {
      ret validPos(x, y) && isContinuation_impl(x, y);
    }
    
    bool isContinuation_impl(int x, int y) {
      ret tiling.tileMatrix[pos(x, y)] == 0 && getColor(x, y) == color;
    }
    
    // Is this rectangle completely in the image and the tile's color
    // and not in a tile?
    bool isContinuation(int x1, int y1, int w, int h) {
      if (!validPos(x1, y1) || !validPos(x1+w-1, y1+h-1)) false;
      for y to h:
        for x to w:
          if (!isContinuation_impl(x1+x, y1+y))
            false;
      true;
    }
    
    Rect nextRect() {
      Rect r = tile.position();
      
      // Check the 4 sides for possible growth
      growingN = growingN && isContinuation(r.x, r.y-1, r.w, 1);
      growingS = growingS && isContinuation(r.x, r.y2(), r.w, 1);
      growingW = growingW && isContinuation(r.x-1, r.y, 1, r.h);
      growingE = growingE && isContinuation(r.x2(), r.y, 1, r.h);
      
      // Check the corners too (including the adjacent sides)
      bool cornerNW = growingN && growingW && isContinuation(r.x-1, r.y-1);
      bool cornerNE = growingN && growingE && isContinuation(r.x2(), r.y-1);
      bool cornerSW = growingS && growingW && isContinuation(r.x-1, r.y2());
      bool cornerSE = growingS && growingE && isContinuation(r.x2(), r.y2());
      
      // Corners are the best case, so try those first
      if (cornerNW) {
        int x2 = r.x2(), y2 = r.y2(); // Default case: Grow to NE only
        
        if (cornerSW && cornerNE && cornerSE) {
          // Best case - grow in all 4 directions
          x2++; y2++;
        } else if (cornerNE)
          // At least grow to the right too
          x2++;
        else if (cornerSW)
          // At least grow to the south too
          y2++;

        ret rectFromPoints(r.x-1, r.y-1, x2, y2);
      } else if (cornerNE) {
        // Can't grow NW but will grow NE. So only south growth to decide
        int y2 = r.y2();
        
        if (cornerSE)
          // Grow south too
          y2++;
          
        ret rectFromPoints(r.x, r.y-1, r.x2()+1, y2);
      } else if (cornerSW) {
        // Can't grow NW or NE but will grow SW. So only east growth to decide
        int x2 = r.x2();
        
        if (cornerSE)
          // Grow east too
          x2++;
          
        ret rectFromPoints(r.x-1, r.y, x2, r.y2()+1);
      } else if (cornerSE) {
        // Only growable corner is SE, so just do it
        ret rectFromPoints(r.x, r.y, r.x2()+1, r.y2()+1);
      } else {
        // No growable corners. Try growing west/east or north/south
        
        if (growingW || growingE)
          ret rectFromPoints(r.x-(growingW ? 1 : 0), r.y,
            r.x2()+(growingE ? 1 : 0), r.y2());
        else if (growingN || growingS)
          ret rectFromPoints(r.x, r.y-(growingN ? 1 : 0),
            r.x2(), r.y2()+(growingS ? 1 : 0));
      }
      
      // No more growth possible
      null;
    }
  }
  
  run { stepAll(this); }
  
  public bool step() {
    init();
    
    // Currently growing a tile? Continue that
    if (growingTile != null) {
      if (growingTile.step()) true;
      tileDone(growingTile);
      growingTile = null; // Done growing this tile
    }
    
    int pos = pointIterator.nextIndex();
    if (pos < 0) false;
    
    // Is point already covered by a tile?
    if (tiling.tileMatrix[pos] != 0) true;
    
    // Create new tile
    growingTile = new GrowingTile(pos);
    tileStarted(growingTile);
    
    true;
  }
  
  void init {
    if (tiling != null) ret;
    w = image.getWidth(); h = image.getHeight();
    size = w*h;
    tiling = new G22Tiling(image);
    tiling.initTileMatrix();
    
    pointIterator = WeightlessShuffledIterator(size);
  }
  
  G22Tiling<Img> get() {
    if (tiling == null) run();
    ret tiling;
  }
}

Began life as a copy of #1034520