asclass AbstractQuadTree<A> extends WidthAndHeightImpl is Matrix<A> {
  replace Node with O.
  
  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+
      _compositeNodeCount(a) +
      _compositeNodeCount(b) +
      _compositeNodeCount(c) +
      _compositeNodeCount(d);
    }
  }
  
  Node root = defaultValue();
  
  *() {}
  *(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()); }
  
  public A 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 (A) node;
  }
  
  public void set(int x, int y, A value) {
    set(pointRect(x, y), value);
  }
  
  void set(Rect r, A value) {
    set(rootCursor(), r, value);
  }
  
  scaffolded void set(Cursor cursor, Rect r, A value) {
    // no intersection? exit
    if (!rectsIntersect(r, cursor.r)) ret;
      
    // fully contained? replace with primitive
    if (rectContains(r, cursor.r))
      cursor.replace(value);
    else {
      // partial intersection - turn into composite  
      cursor.turnIntoComposite();
      
      for (Cursor c : cursor.subCursors())
        set(c, r, value);
    }
    
    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);
  }
  
  static int _compositeNodeCount(Node n) {
    if (n cast Composite)
      ret n.compositeNodeCount();
    ret 0;
  }
  
  int compositeNodeCount() { ret _compositeNodeCount(root); }
  
  abstract A defaultValue();
}