// Abstract base class for finding all connected regions of same color
// in an image using flood filling

abstract srecord noeq AbstractFastRegions<Img extends WidthAndHeight>(Img image) is Runnable, IImageRegions<Img> {
  int w, h; // Image size
  int runner; // Position in image currently being scanned
  gettable int size; // =w*h
  
  new IntBuffer stack; // locations as y*w+x
  gettable int[] regionMatrix; // for each pixel: region index (starting at 1)
  new IntBuffer regionPixels; // collect all pixels for regions
  
  settable bool withDiagonals; // also walk diagonally?
  
  // initialize these to use them
  
  new IntBuffer regionFirstPixel; // for each region: index of first pixel found in regionPixels
  new IntBuffer regionSize; // for each region: number of pixels
  new IntBuffer regionBounds; // for each region: bounds (x1, y1, x2, y2)
  
  // index = dual log of region size, value = region index
  new L<IntBuffer> regionsBySize;
  
  int regionCounter;
  bool verbose;
  
  // temporary
  int currentColor;
  
  double regionStep = .1; // for rendering in regionsImage
  
  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; }
  
  abstract int getColor(int pos);
  
  bool initialized() { ret regionMatrix != null; }
  
  void init {
    if (initialized()) ret;
    
    w = image.getWidth(); h = image.getHeight();
    size = w*h;
    regionMatrix = new int[size];
    
    // 0 entries are unused
    regionFirstPixel?.add(0); 
    regionSize?.add(0);
    
    regionPixels?.setSize(size);
  }
  
  // Search for all regions in scanline order
  run {
    if (initialized()) ret;
    init();
    
    while (runner < size) {
      if (regionMatrix[runner] == 0)
        makeRegion();
      ++runner;
    }
  }
  
  // returns index of new region
  int makeRegion() {
    // make a new region, get color
    int region = ++regionCounter;
    regionFirstPixel?.add(regionPixels != null ? l(regionPixels) : runner);
    currentColor = getColor(runner);
    stack.add(runner);
    int rsize = 0, x1 = w, y1 = h, x2 = 0, y2 = 0;
    ifdef FastRegions_debug
      printVars FastRegions(+region, +runner);
    endifdef

    // flood-fill region
    while (nempty(stack)) {
      int pos = stack.popLast();
      if (regionMatrix[pos] != 0) continue; // check again if set in the meantime (color has been checked before)

      // new pixel found!
      int x = x(pos), y = y(pos);
      
      // march to the left
      int lineStart = pos-x;
      int xLeft = x;
      while (xLeft > 0 && addable(lineStart+xLeft-1))
        --xLeft;
        
      // march to the right
      int xRight = x+1;
      while (xRight < w && addable(lineStart+xRight))
        ++xRight;
      
      // Now we know [xLeft; xRight) are our pixels
      // mark them in matrix
      for (x = xLeft; x < xRight; x++) {
        regionMatrix[lineStart+x] = region;
        regionPixels?.add(lineStart+x);
      }
        
      // increase region size
      rsize += xRight-xLeft;
      
      ifdef FastRegions_debug
        printVars FastRegions(+region, +rsize, +y, +xLeft, +xRight);
      endifdef
      
      // update bounds
      if (xLeft < x1) x1 = xLeft;
      if (xRight-1 > x2) x2 = xRight-1;
      if (y < y1) y1 = y;
      if (y > y2) y2 = y;
      
      // explore above & below
      int xLeft2 = withDiagonals ? max(0, xLeft-1) : xLeft;
      int xRight2 = withDiagonals ? min(w, xRight+1) : xRight;
      if (y > 0)
        addStreaks(lineStart-w, xLeft2, xRight2);
      if (y < h-1)
        addStreaks(lineStart+w, xLeft2, xRight2);
    }
    
    regionSize?.add(rsize);
    regionBounds?.addAll(x1, y1, x2+1, y2+1);
    if (regionsBySize != null) {
      int iBucket = dualLog(rsize);
      var buffer = listGetOrCreate(regionsBySize, iBucket, -> new IntBuffer);
      buffer.add(region);
    }
    
    ret region;
  }
  
  bool addable(int pos) {
    if (regionMatrix[pos] != 0) false; // touching myself (or someone else)
    if (getColor(pos) != currentColor) false; // wrong color
    true;
  }
  
  bool addToStack(int pos) {
    if (!addable(pos)) false;
    stack.add(pos);
    true;
  }
  
  void addStreaks(int lineStart, int xLeft, int xRight) {
    int x = xLeft;
    while (x < xRight) {
      if (addToStack(lineStart+x))
        while (x+1 < xRight && addable(lineStart+x+1))
          ++x;
      ++x;
    }
  }

  IBWImage regionsImage() {
    ret iBWImageFromFunction((x, y) -> {
      var region = regionMatrix[pos(x, y)];
      ret ((region-1)*regionStep) % (1.0+regionStep-0.0001);
    }, w, h);
  }
  
  public int regionCount aka nRegions() { ret regionCounter; }
  
  abstract class RegionIterator {
    int pos;
    
    abstract bool next();
    
    int pos() { ret pos; }
    int x() { ret AbstractFastRegions.this.x(pos); }
    int y() { ret AbstractFastRegions.this.y(pos); }
    
    int[] pixelsAsIntArray() { throw todo(); }
  }
  
  // returns points in no particular order
  class FloodRegionIterator > RegionIterator {
    int region;
    new IntBuffer stack; // locations as y*w+x
    BitSet seen = new(size);
    
    *(int *region) {
      int pos = regionFirstPixel.get(region);
      printVars(+region, +pos);
      seen.set(pos);
      stack.add(pos);
    }
    
    // flood-fill region
    bool next() {
      if (empty(stack)) false;
      
      pos = stack.popLast();

      // explore neighborhood
      int x = x(), y = y();
      if (x > 0)   tryPosition(pos-1);
      if (x < w-1) tryPosition(pos+1);
      if (y > 0)   tryPosition(pos-w);
      if (y < h-1) tryPosition(pos+w);

      true;
    }
    
    private void tryPosition(int p) {
      if (!seen.get(p) && regionMatrix[p] == region) {
        seen.set(p);
        stack.add(p);
      }
    }
  }
  
  class CachedRegionIterator > RegionIterator {
    int i, to;

    *(int region) {
      i = regionFirstPixel.get(region);
      to = region+1 < l(regionFirstPixel) ? regionFirstPixel.get(region+1) : l(regionPixels);
      
      ifdef FastRegions_debug
        printVars CachedRegionIterator(+region, +i, +to);
      endifdef
    }
    
    bool next() {
      if (i >= to) false;
      pos = regionPixels.get(i++);
      true;
    }
    
    int[] pixelsAsIntArray() {
      ret regionPixels.subArray(i, to);
    }
  }
  
  int regionSize(int iRegion) { ret regionSize.get(iRegion); }
  
  Pt samplePixel aka firstPixel(int iRegion) {
    ret pt(firstPixelPos(iRegion));
  }
  
  int firstPixelPos(int iRegion) {
    int i = regionFirstPixel.get(iRegion);
    ret regionPixels != null ? regionPixels.get(i) : i;
  }
  
  bool inRegion(int iRegion, int x, int y) {
    ret validPos(x, y) && regionMatrix[pos(x, y)] == iRegion;
  }
  Rect regionBounds(int iRegion) { ret rectFromPoints(
    regionBounds.get((iRegion-1)*4),
    regionBounds.get((iRegion-1)*4+1),
    regionBounds.get((iRegion-1)*4+2),
    regionBounds.get((iRegion-1)*4+3),
  ); }
  
  int regionAt(Pt p) { ret regionAt(p.x, p.y); }
  
  int regionAt(int x, int y) {
    ret !validPos(x, y) ? 0 : regionMatrix[pos(x, y)];
  }
  
  int regionAt(int pos) {
    ret regionMatrix[pos];
  }
  
  RegionIterator regionIterator(int iRegion) {
    ret regionPixels != null
      ? new CachedRegionIterator(iRegion)
      : new FloodRegionIterator(iRegion);
  }
  
  L<Pt> regionPixels(int iRegion) {
    var it = regionIterator(iRegion);
    new L<Pt> l;
    while (it.next())
      l.add(Pt(it.x(), it.y()));
    ret l;
  }
  
  // select extra features before regions are made
  // (not necessary anymore)
  
  void collectFirstPixels { /*regionFirstPixel = new IntBuffer;*/ }
  void collectBounds { /*regionBounds = new IntBuffer;*/ }
  
  BitMatrix regionBitMatrix(int iRegion) {
    ret new AbstractBitMatrix(w, h) {
      public Bool get(int x, int y) {
        ret inRegion(iRegion, x, y);
      }
    };
  }
  
  void markRegionInPixelArray(int[] pixels, int iRegion, int rgba) {
    if (iRegion <= 0) ret;
    for i over pixels:
      if (regionAt(i) == iRegion)
        pixels[i] = rgba;
  }
  
  L<Int> regionIndices() { ret virtualCountList(1, nRegions()+1); }
  
  ItIt<Int> regionsRoughlyByDecreasingSize() {
    ret nestedIterator(countIterator_inclusive_backwards(regionsBySize.size()-1, 0),
      iBucket -> iterator(regionsBySize.get(iBucket)));
  }
  
  public IImageRegion<Img> getRegion aka get(int iRegion) {
    ret new ImageRegion(iRegion);
  }
  
  public L<IImageRegion<Img>> regions aka get() {
    run();
    ret listFromFunction(i -> getRegion(i+1), nRegions());
  }
  
  record noeq ImageRegion(int iRegion) is IImageRegion<Img> {
    public int hashCode() { ret iRegion; }
    public bool equals(O o) {
      if (!o instanceof AbstractFastRegions.ImageRegion) false;
      ret ((AbstractFastRegions.ImageRegion) o).creator() == creator()
        && ((AbstractFastRegions.ImageRegion) o).iRegion == iRegion;
    }
    
    public Img image() { ret image; }
    public O creator() { ret AbstractFastRegions.this; }
    public int indexInCreator() { ret iRegion; }
    public Bool createdWithDiagonals() { ret withDiagonals; }
  
    public Rect bounds() { ret regionBounds(iRegion); }
    
    public int numberOfPixels() { ret regionSize(iRegion); }
    
    public Pt firstPixel() { ret pt(firstPixelPos()); }
    public int firstPixelPos() { ret AbstractFastRegions.this.firstPixelPos(iRegion); }
    
    public ItIt<Pt> pixelIterator() {
      var it = regionIterator(iRegion);
      ret iteratorFromFunction(-> it.next() ? pt(it.pos()) : null);
    }
    
    public int[] pixelsAsIntArray() {
      ret regionIterator(iRegion).pixelsAsIntArray();
    }
    
    public bool contains(int x, int y) { ret inRegion(iRegion, x, y); }
    
    public Color color() {
      ret toColor(rgbForRegion(this));
    }
    
    public int brightness aka firstPixelLogicalColor() {
      ret getColor(firstPixelPos());
    }
    
    toString {
      ret renderRecordVars("Region", +brightness(), +color(), pixels := numberOfPixels(), +bounds());
    }
  }
  
  abstract RGB rgbForRegion(ImageRegion r);
  
  public Img image() { ret image; }
  
  // called after scan was performed externally
  void markDone { runner = size; }
}

Began life as a copy of #1033761