//---------------------------------------------------------------------------
class Node {  
  public int x,y,size;  
  public int[] value = new int[4];
  public Node[] child = new Node[4];
  public Node parent = null;
  public boolean isVisible = true;
  public boolean isEmpty = false;
  public long cost = -1;

  public void drawTree(boolean isGrid, int maxLevel) {
    _drawTree(isGrid,maxLevel,0);
  }
  
  private void _drawTree(boolean isGrid, int maxLevel, int level) {
    boolean koniec = false;
    
    for (int i = 0; i < 4; i++) {
        if (child[i] == null) koniec = true;
    }

    if (level == 0) {
      for (int i = 0; i < img.width; i++) {
        for (int j = 0; j < img.height; j++) {
          img.set(i,j, color(#ffffff));    
        }
      }  
    }

    if (level == maxLevel || koniec || !child[0].isVisible) {
      drawBeamlet(this,img);
    }

    if (level < maxLevel && !koniec && child[0].isVisible) {
      if (isGrid && size > 2) {
        int tmp = size >> 1;

        for (int i = 0; i < size; i++) {
          img.set(x + tmp,y + i, color(166,202,240));
          img.set(x + i,y + tmp, color(166,202,240));
        }
      }

      for (int i = 0; i < 4; i++) {
        child[i]._drawTree(isGrid,maxLevel,level+1);
      }
    }   

    if (level == 0) {
      img.updatePixels();
    }
  }
  
  void bottomUp() {
    if (child[0] != null) {
      for (int i = 0; i < 4; i++) {
        child[i].bottomUp();
      }

      long tmp = 0;

      for (int i = 0; i < 4; i++) {
        tmp += child[i].getCost();
      }

      if (tmp < getCost()) {         
        cost = tmp;                       
      } else {
        for (int i = 0; i < 4; i++) {
          child[i].isVisible = false;
        }
      }
    }
  }

  void makeAllNodesVisible() {
    isVisible = true;
    cost = -1;

    if (child[0] != null){
      for (int i = 0; i < 4; i++) {
        child[i].makeAllNodesVisible();
      }
    }
  }

  long getCost() {
    if (cost < 0) {
      for (int i = x; i < x + size; i++) {
        for (int j = y; j < y + size; j++) {
          img_tmp.set(i,j, color(#ffffff)); 
        }
      }      

      drawBeamlet(this,img_tmp);
      cost = CMD(this,img_orig,img_tmp);      
    }    
    return cost;      
  }
}
//---------------------------------------------------------------------------
public Node createTree() {  
  return _createTree(null, 0, 0, 0);
}
//---------------------------------------------------------------------------
private Node _createTree(Node parent, int x, int y, int level) {
  int size = img_orig.width >> level;

  Node node = new Node();
  node.parent = parent;
  node.x = x;
  node.y = y;
  node.size = size;

  crateBeamlet(node);

  if (size > 1 && !node.isEmpty) {
    size = img_orig.width >> ++level;
    node.child[0] = _createTree(node, x, y, level);
    node.child[1] = _createTree(node, x+size, y, level);
    node.child[2] = _createTree(node, x, y+size, level);
    node.child[3] = _createTree(node, x+size, y+size, level);
  }
  
  return node;
}
//---------------------------------------------------------------------------
private void crateBeamlet(Node node) {
  node.isEmpty = false;
  Point v1 = new Point(0,0);
  Point v2 = new Point(0,0);

  int size = node.size;
  int x = node.x;
  int y = node.y;

  long s0 = 0, s1 = 0, s2 = 0, t0 = 0, t1 = 0;

  double a0 = 0.0, a1 = 0.0;

  for (int i = 0; i < size; i++) {
    for (int j = 0; j < size; j++) {
      if (img_orig.get(node.x+i,node.y+j) == color(0,0,0)) s0++;
    }
  }

  //boolean search_better = false;
  if (s0 == 0) {
    node.isEmpty = true;
  }
  else if (size > 1) {
    //obliczenie beamleta --> aproksymacja liniowa metodą najmniejszych kwadratów
    for (int i = 0; i < size; i++) {
      for (int j = 0; j < size; j++) {
        if (img_orig.get(node.x+i,node.y+j) == color(0,0,0)) {
          s1 += i;
          s2 += (i * i);
          t0 += j;
          t1 += (i * j);
        }
      }
    }
    
    if (s0*s2!=s1*s1) {
      a0 = (double)(t0*s2 - t1*s1)/(double)(s0*s2-s1*s1);
      a1 = (double)(t1*s0 - t0*s1)/(double)(s0*s2-s1*s1);

      int _size = size - 1;

      if (a1 == 0) {
        v1 = new Point(0,(int)(a0+0.5));
        v2 = new Point(_size,(int)(a0+0.5));
      }
      else if (a0 < 0) {
        v1 = new Point((int)(-a0/a1+0.5),0);

        if (a0 + a1 * _size > _size) v2 = new Point((int)((_size-a0)/a1+0.5),_size);
        else v2 = new Point(_size,(int)(a0+a1*_size+0.5));
      } 
      else if (a0 > _size) {
        v1 = new Point((int)((_size-a0)/a1+0.5),_size);

        if (a0 + a1 * _size < 0) v2 = new Point((int)(-a0/a1+0.5),0);
        else v2 = new Point(_size,(int)(a0+a1*_size+0.5));
      }
      else {
        v1 = new Point(0,(int)(a0+0.5));

        if (a0 + a1 * _size < 0) v2 = new Point((int)(-a0/a1+0.5),0);
        else if (a0 + a1 * _size > _size) v2 = new Point((int)((_size-a0)/a1+0.5),_size);
        else v2 = new Point(_size,(int)(a0+a1*_size+0.5));
      }

      //search_better = true;
    }
    else {
      int tmp_a = (int)((double)(s1)/(double)(s0) + 0.5);
      v1 = new Point(tmp_a,0);
      v2 = new Point(tmp_a,size-1);
      //search_better = true;
    }
  }

  node.value[0] = pointToInt(v1,size);
  node.value[1] = pointToInt(v2,size);

  //if (search_better)
  //  search_better_beamlet(drzewo, image, image_tmp);
 
  if (size == 1) {
    if (node.isEmpty) {
      node.value[0] = 1;
      node.value[1] = 1;
    } else {
      node.value[0] = 1;
      node.value[1] = 2;
    }
  }                   
    
  if (s0 == 1) {
    for (int i = 0; i < size; i++) {
      for (int j = 0; j < size; j++) {
        if ((i == 0 || i == size - 1 || j == 0 || j == size - 1) && img_orig.get(node.x+i,node.y+j) == color(0,0,0)) {
          node.value[0] = pointToInt(new Point(i,j),size);
          node.value[1] = node.value[0]; 
        }
      }
    }
  }             
}
//---------------------------------------------------------------------------
private void drawBeamlet(Node node, PImage im) {
  if (!node.isEmpty) {
    Point v1 = intToPoint(node.value[0],node.size);
    Point v2 = intToPoint(node.value[1],node.size);
    _drawBeamlet(v1,v2,node,im, false);
  }
}
//---------------------------------------------------------------------------
private void _drawBeamlet(Point v1, Point v2, Node node, PImage im, boolean clear) {
  if (clear) {        
    for (int i = node.x; i < node.x + node.size; i++) {
      for (int j = node.y; j < node.y + node.size; j++) {
        im.set(i,j, color(#ffffff));         
      }
    }
  }
               
  if (node.size == 1) {
    im.set(node.x,node.y, color(#000000)); 
  } else {
    BresenhamLine(im, node.x + v1.x, node.y + v1.y, node.x + v2.x, node.y + v2.y, color(#000000));
  } 
}
//---------------------------------------------------------------------------
public long CMD(Node node, PImage im1, PImage im2) {
  // obliczamy odległość między obrazami metodą CMD
  int size = node.size;
  int x = node.x;
  int y = node.y;

  long c1 = 0;

  for (int i = 0; i < size; i++) {
    for (int j = 0; j < size; j++) {
      if (im1.get(node.x+i,node.y+j) != im2.get(node.x+i,node.y+j)) c1++;
    }
  }
      
  return c1;
}
//---------------------------------------------------------------------------