sclass QuadTreeBitMatrix > WidthAndHeightImpl is BitMatrix {
  sclass Node {
    int compositeNodeCount() { ret 0; }
  }
  sclass Prim > Node {}
  sclass On  > Prim {} static new On  on;
  sclass Off > Prim {} static new Off off;
  
  sclass Composite > Node {
    Node a, b, c, d;
    
    void set(int idx, Node n) {
      if (idx == 0) a = n;
      if (idx == 1) b = n;
      if (idx == 2) c = n;
      if (idx == 3) d = n;
    }
    
    *(Node n) {
      a = b = c = d = n;
    }
    
    bool simplifiable() {
      ret allEq(a, b, c, d);
    }
    
    int compositeNodeCount() { ret 1+
      a.compositeNodeCount() +
      b.compositeNodeCount() +
      c.compositeNodeCount() +
      d.compositeNodeCount();
    }
  }
  
  Node root = off;
  
  *() {}
  *(int *width, int *height) {}
  
  int half(int x) { ret roundUpToPowerOfTwo((x+1)/2); }
  int halfX(Rect r) { ret r.x+half(r.w); }
  int halfY(Rect r) { ret r.y+half(r.h); }
  
  Rect rectA(Rect r) { ret rect(r.x, r.y, half(r.w), half(r.h)); }
  Rect rectB(Rect r) { ret rectFromPoints(r.x+half(r.w), r.y, r.x2(), halfY(r)); }
  Rect rectC(Rect r) { ret rectFromPoints(r.x, r.y+half(r.h), r.x+half(r.w), r.y2()); }
  Rect rectD(Rect r) { ret rectFromPoints(r.x+half(r.w), r.y+half(r.h), r.x2(), r.y2()); }
  
  // have to return Bool (not bool) to satisfy BitMatrix interface
  public Bool get(int x, int y) {
    Node node = root;
    Rect r = rect(0, 0, width, height);
    while (node cast Composite) {
      int hx = halfX(r), hy = halfY(r);
      if (y < hy)
        if (x < hx) {
          node = node.a; r = rectA(r);
        } else {
          node = node.b; r = rectB(r);
        }
      else
        if (x < hx) {
          node = node.c; r = rectC(r);
        } else {
          node = node.d; r = rectD(r);
        }
      ifdef QuadTreeBitMatrix_debug
        printVars(+x, +y, +hx, +hy);
      endifdef
    }
    ret node == on;
  }
  
  public void set(int x, int y, Bool b default true) {
    set(pointRect(x, y), b);
  }
  
  void set(Rect r, bool b) {
    set(rootCursor(), r, b);
  }
  
  scaffolded void set(Cursor cursor, Rect r, bool b) {
    // no intersection? exit
    if (!rectsIntersect(r, cursor.r)) ret;
      
    // fully contained? replace with primitive
    if (rectContains(r, cursor.r))
      cursor.replace(b ? on : off);
    else {
      // partial intersection - turn into composite  
      cursor.turnIntoComposite();
      
      for (Cursor c : cursor.subCursors())
        set(c, r, b);
    }
    
    cursor.simplify();
  }
  
  class Cursor {
    settable Composite parent;
    settable int indexInParent;
    
    settable Rect r;
    settable Node node;
    
    L<Cursor> subCursors() {
      if (node cast Composite)
        ret ll(
          subCursor(0, node.a, rectA(r)),
          subCursor(1, node.b, rectB(r)),
          subCursor(2, node.c, rectC(r)),
          subCursor(3, node.d, rectD(r)));
      ret emptyList();
    }
    
    Cursor subCursor(int idx, Node n, Rect r) {
      ret new Cursor().r(r).node(n)
        .parent((Composite) node).indexInParent(idx);
    }
    
    scaffolded void turnIntoComposite {
      if (!node instanceof Composite)
        replace(new Composite(node));
    }
    
    scaffolded void replace(Node n) {
      if (node == n) ret;
      node = n;
      if (parent == null)
        root = n;
      else
        parent.set(indexInParent, n);
    }
    
    // opposite of turnIntoComposite
    scaffolded void simplify {
      if (node cast Composite && node.simplifiable())
        replace(node.a);
    }
    
    /*toString {
      ret stdToString(this);
    }*/
  }
  
  Cursor rootCursor() {
    ret new Cursor().r(bounds()).node(root);
  }
  
  int compositeNodeCount() { ret root.compositeNodeCount(); }
}