persistable sclass ScanlineBitMatrix extends AbstractMatrix<Bool> is BitMatrix {

  int bx1 = Int.MAX_VALUE, by1, bx2, by2; // bounding box of positive bits

  int pixels; // number of set bits

  // format for each line: start x, end x (excl.), start x, end x, ...

  int[] scanlineData;

  // pointer into scanlineData for each line

  int[] scanlineStarts;

  *(BitMatrix m) {

    super(m.getWidth(), m.getHeight());

    // find upper and lower bounding line

    while (by1 < h && bitMatrixRowEmpty(m, by1)) by1++;

    by2 = h;

    while (by2 > by1 && bitMatrixRowEmpty(m, by2-1)) by2--;

    int ptr = 0, pixels = 0;

    scanlineStarts = new int[by2-by1];

    new IntBuffer scanlineData;

    lineLoop: for (int y = by1; y < by2; y++) {

      scanlineStarts[y-by1] = l(scanlineData);

      for (int x = 0; x < w; ) {

        while (!m.get(x, y))

          if (++x >= w)

            continue lineLoop;

        int x2 = x+1;

        while (x2 < w && m.get(x2, y)) ++x2;

        scanlineData.add(x);

        scanlineData.add(x2);

        pixels += x2-x;

        if (x < bx1) bx1 = x;

        if (x2 > bx2) bx2 = x2;

        x = x2;

      }

    }

    this.scanlineData = scanlineData.toArray();

    this.pixels = pixels;

  }

  public Bool get(int x, int y) {

    if (x < bx1 || y < by1 || x >= bx2 || y >= by2) false;

    int ptr = scanlineStarts[y-by1];

    int end = y == by2-1 ? scanlineData.length : scanlineStarts[y-by1+1];

    // linear search for now

    while (ptr < end) {

      int x1 = scanlineData[ptr++];

      if (x < x1) false;

      int x2 = scanlineData[ptr++];

      if (x < x2) true;

    }

    false;

  }

  public void set(int x, int y, Bool a) { unimplemented(); }

  Rect boundingBoxOfTrueBits() { ret bx1 >= bx2 ? null : rect(bx1, by1, bx2, by2); }

  int nRuns() { ret scanlineData.length/2; }

  ItIt<Rect> runs() {

    ret new ItIt<Rect> {

      int y = 0, ptr = 0;

      public bool hasNext() { ret ptr < l(scanlineData); }

      public Rect next() {

        while (y < scanlineStarts.length-1

          && ptr >= scanlineStarts[y+1])

            ++y;

        int x1 = scanlineData[ptr++];

        int x2 = scanlineData[ptr++];

        ret rect(x1, by1+y, x2-x1, 1);

      }

    };

  }

  int pixelCount() { ret pixels; }

}