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

  }

}