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

  }

}