// The main idea behind this data structure is that it should
// allow finding regions significantly faster than directly from
// the Hi15Image.
//
// Making this index takes about 2ms per megapixel.

sclass Hi15ScanlineIndex {
  Hi15Image image;
  int w, h;
  int[] indexed;
  
  // scanlines contains 2 consecutive ints for each scanline:
  // -index of first pixel in scanline
  // -index of last pixel in scanline + 1
  //
  // Colors are not stored and have to be gathered from the
  // original image.
  
  IntBuffer scanlines;
  
  *() {}
  *(Hi15Image *image) {}
  
  run {
    int w = this.w = image.getWidth();
    int h = this.h = image.getHeight();
    short[] pixels = image.pixels;
    
    int lineStart = 0;
    var indexed = this.indexed = new int[w*h];
    int guess = 128*1024;
    var scanlines = this.scanlines = new IntBuffer(guess);

    for y to h: {
      int i = lineStart;
      int lineEnd = lineStart+w;
      
      while (i < lineEnd) {
        short color = pixels[i];
        int j = i+1;
        if (j < lineEnd && pixels[j] == color) {
          // multi-pixel scanline found
          
          do
            ++j;
          while (j < lineEnd && pixels[j] == color);
          scanlines.add(i);
          scanlines.add(j);
        }
        
        int iScanline = scanlines.size();
        while (i < j)
          indexed[i++] = iScanline;
      }
      
      lineStart = lineEnd;
    }
  }
  
  int nScanlines() { ret scanlines.size()/2; }
  
  // Render all scanlines in an image.
  // Isolated pixels (those different from their left and right
  // neighbor) will be left transparent.
  
  BufferedImage scanlinesAsImage() {
    int[] pixels = new[w*h];
    int n = nScanlines();
    for i to n: {
      int from = scanlines.get(i*2);
      int to = scanlines.get(i*2+1);
      int color = withFullAlpha(hi15ToRGBInt_clean(image.getHi15Pixel_noRangeCheck(from)));
      for (int pixel = from; pixel < to; pixel++)
        pixels[pixel] = color;
    }
    ret bufferedImageWithAlpha(w, h, pixels);
  }
  
  // run this after run() to save some memory
  void compact {
    scanlines.trimToSize();
  }
}