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