persistable sclass ScanlineBitMatrix extends AbstractMatrix<Bool> is BitMatrix {
  int bx1 = Int.MAX_VALUE, by1, bx2, by2; // bounding box of positive bits
  
  // format for each line: start x, end x (excl.), start x, end x, ...
  new IntBuffer scanlineData;
  
  // pointer into scanlineData for each line
  new IntBuffer 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;
    lineLoop: for (int y = by1; y < by2; y++) {
      scanlineStarts.add(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);
        if (x < bx1) bx1 = x;
        if (x2 > bx2) bx2 = x2;
        x = x2;
      }
    }
  }
  
  public Bool get(int x, int y) {
    if (x < bx1 || y < by1 || x >= bx2 || y >= by2) false;
    int ptr = scanlineStarts.get(y-by1);
    
    int end = y == by2-1 ? scanlineData.size() : scanlineStarts.get(y-by1+1);

    // linear search for now
    while (ptr < end) {
      int x1 = scanlineData.get(ptr++);
      if (x < x1) false;
      int x2 = scanlineData.get(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); }
}