// img must be square with width/height being a power of 2

static Pair<BWImage> bwImageContrastQuadtree(BWImage img) {

  int w = img.getWidth(), h = img.getHeight();

  assertEquals("width/height", w, h);

  if (!isPowerOf2(w)) fail("image size not a power of 2: " + w);

  BWImage min = new(w, h);

  BWImage max = new(w, h);

  bwImageContrastQuadtree_make(img, min, max, 0, 0, w);

  ret pair(min, max);

}

svoid bwImageContrastQuadtree_make(BWImage img, BWImage min, BWImage max, int x, int y, int w) {

  int val = img.getInt(x, y);

  if (w == 1) {

    min.setInt(x, y, val);

    max.setInt(x, y, val);

  } else {

    int r = w/2;

    // process 4 subsquares

    bwImageContrastQuadtree_make(img, min, max, x+r, y+r, r);

    bwImageContrastQuadtree_make(img, min, max, x+r, y, r);

    bwImageContrastQuadtree_make(img, min, max, x, y+r, r);

    bwImageContrastQuadtree_make(img, min, max, x, y, r);

    // bottom right square is ok, process the 3 other ones

    int minTR, maxTR, minBL, maxBL,

      minBR = min.getInt(x+r, y+r),

      maxBR = max.getInt(x+r, y+r);

    min.setInt(x+r, y, minTR = min(min.getInt(x+r, y), minBR));

    max.setInt(x+r, y, maxTR = max(max.getInt(x+r, y), maxBR));

    min.setInt(x, y+r, minBL = min(min.getInt(x, y+r), minBR));

    max.setInt(x, y+r, maxBL = max(max.getInt(x, y+r), maxBR));

    min.setInt(x, y, min3(min.getInt(x, y), minTR, minBL));

    max.setInt(x, y, max3(max.getInt(x, y), maxTR, maxBL));

  }

}