import java.util.Arrays;
static Snippet[] snippets;
static int numsnippets=1;
private static int[] spaces_x,spaces_y;
static int space_x,space_y;

void reinit() {
  snippets=new Snippet[16];
  numsnippets=1;
  for (int i=0;i<snippets.length;i++)
    snippets[i]=new Snippet();
  spaces_x=new int[snippets.length*2+2];
  spaces_y=new int[snippets.length*2+2];
}

void setup() {
  frameRate(25);
  size(720,360);
  reinit();
}

private static int roundup(float a) {
  if (a>0) return int(a)+1;
  else return int(a)-1;
}

final static float DECOLLIDE_X=0.5, DECOLLIDE_Y=0.6;
static boolean decollide() {
  boolean collide=false;
  for (int i=0;i<numsnippets;i++)
    for (int j=i+1;j<numsnippets;j++) {
      Snippet si=snippets[i];
      Snippet sj=snippets[j];
      if (si.overlaps(sj)) {
        collide=true;
        int dx=sj.cx()-si.cx();
        int dy=sj.cy()-si.cy();
        sj.x+=dx>0 ? 1 : -1;
        si.x-=dx>0 ? 1 : -1;
        sj.y+=dy>0 ? 1 : -1;
        si.y-=dy>0 ? 1 : -1;

        si.constrain();
        sj.constrain();
      }
    }
  return collide;
}

static boolean space_taken(int x0, int y0, int x1, int y1) {
  for (int i=0;i<numsnippets;i++) {
    // is the space inside this snippet?
    Snippet s=snippets[i];
    if (x0>=s.x && x1<=s.x+s.w && y0>=s.y && y1<=s.y+s.h) {
      return true;
    }
  }
  return false;
}

void find_biggest_space() {
  space_x=-1;
  space_y=-1;
  // get all the split poitns
  for (int i=0;i<numsnippets;i++) {
    Snippet s=snippets[i];
    spaces_x[i*2  ]=s.x;
    spaces_y[i*2  ]=s.y;
    spaces_x[i*2+1]=s.x+s.w;
    spaces_y[i*2+1]=s.y+s.h;
  }
  spaces_x[numsnippets*2]=0;
  spaces_y[numsnippets*2]=0;
  spaces_x[numsnippets*2+1]=width;
  spaces_y[numsnippets*2+1]=height;
  Arrays.sort(spaces_x,0,numsnippets*2+2);
  Arrays.sort(spaces_y,0,numsnippets*2+2);

  int free_minx=-1,free_miny=-1;
  int space_area=0;
  for (int y=0;y<numsnippets*2+1;y++) {
    int y0=spaces_y[y],y1=spaces_y[y+1];
    for (int x=0;x<numsnippets*2+1;x++) {
      int x0=spaces_x[x],x1=spaces_x[x+1];
      if (space_taken(x0,y0,x1,y1)) {
        free_minx=-1;
        free_miny=-1;
      }
      else {
        if (free_minx==-1 || free_miny==-1) {
          free_minx=x0;
          free_miny=y0;
        }
        int area=(y1-free_miny)*(x1-free_minx);
        if (area>space_area) {
          space_x=(x1+free_minx)/2;
          space_y=(y1+free_miny)/2;
          space_area=area;
        }
      }
    }
  }
  free_minx=-1;
  free_miny=-1;
  for (int x=0;x<numsnippets*2+1;x++) {
    int x0=spaces_x[x],x1=spaces_x[x+1];
    for (int y=0;y<numsnippets*2+1;y++) {
      int y0=spaces_y[y],y1=spaces_y[y+1];
      if (space_taken(x0,y0,x1,y1)) {
        free_minx=-1;
        free_miny=-1;
      }
      else {
        if (free_minx==-1 || free_miny==-1) {
          free_minx=x0;
          free_miny=y0;
        }
        int area=(y1-free_miny)*(x1-free_minx);
        if (area>space_area) {
          space_x=(x1+free_minx)/2;
          space_y=(y1+free_miny)/2;
          space_area=area;
        }
      }
    }
  }
}

void mousePressed() {
  reinit();
}

void draw() {
  Thread.yield();
  background(33);
  fill(192,192,192);
  stroke(128,128,128);
  if (!decollide() && numsnippets<snippets.length) {
    find_biggest_space();
    Snippet newsnip=snippets[numsnippets];
    newsnip.x=space_x-newsnip.w/2;
    newsnip.y=space_y-newsnip.h/2;
    numsnippets++;
  }
  for (int i=0;i<numsnippets;i++) snippets[i].render();
  /*
    for (int i=0;i<numsnippets*2+2;i++) {
      line(spaces_x[i],0,spaces_x[i],height);
      line(0,spaces_y[i],width,spaces_y[i]);
    }
  ellipse(space_x,space_y,20,20);
  */
}