// probabilistic (of course)
srecord noeq ImageSimilarityAtScale (
  IIntegralImage img1,
  IIntegralImage img2,
  int featureSize // smallest block size to be looked at (w/h in pixels)
  ) extends Probabilistic implements IF0<Double> {
  
  int channels;
  LookAtClip root;
  int blocksCalculated;
  bool verbose;
  
  record LookAtClip(LookAtClip parent, Rect r) implements Runnable {
    L<LookAtClip> children;
    
    // diffs are in range [0;255*channels*pixelsCovered]
    double initialDiff, diffsFromChildren, areaCoveredByChildren;
    double latestDiff;
    
    double latestDiff() { ret latestDiff; }
    
    double calculateLatestDiff() {
      ret latestDiff = initialDiff*(area()-areaCoveredByChildren)+diffsFromChildren;
    }
    
    run {
      // make initial guess
      
      double sum = 0;
      for channel to channels:
        sum += sqr(
          img1.rectSum(r, channel)-img2.rectSum(r, channel));
      initialDiff = sqrt(sum);
      if (verbose) printVars(+r, +initialDiff);
      ++blocksCalculated;
      updateMeAndParent();
      
      if (r.w > r.h) {
        if (r.w > featureSize)
          splitHorizontally();
      } else {
        if (r.h > featureSize)
          splitVertically();
      }
    }
    
    void splitHorizontally {
      split(asList(splitRectInHorizontalHalves(r)));
    }
    
    void splitVertically {
      split(asList(splitRectInVerticalHalves(r)));
    }
    
    void split(L<Rect> parts) {
      double p = 0.99;
      children = map(parts, r -> new LookAtClip(this, r));
      scheduleAll(p, children);
    }
    
    void updateMeAndParent() {
      calculateLatestDiff();
      if (parent != null) {
        parent.diffsFromChildren += latestDiff;
        parent.areaCoveredByChildren += area();
        parent.updateMeAndParent();
      }
    }
    
    double area() { ret rectArea(r); }
  }
  
  run {
    assertEquals("Sizes of compared images have to be equal", img1.getSize(), img2.getSize());
    assertEquals("Channel counts of compared images have to be equal", channels = img1.nChannels(), img2.nChannels());
    
    root = new LookAtClip(null, imageRect(img1));
    root.run();
  }
  
  // similarity between 0 and 1
  // it's a best guess until the calculation is complete
  public Double similarity aka get() {
    ret 1-diff();
  }
  
  // difference (1-similarity) between 0 and 1
  // (this can be more precise in floating point then similarity)
  public double diff() {
    ret root.latestDiff()/(root.area()*channels*255);
  }
  
  int blocksCalculated() { ret blocksCalculated; }
}