class SpaceGrid {
  
  private int width, height;
  private double gridSize, gridSizeSq;
  private Vector[][] space;
  
  SpaceGrid(int screenWid, int screenHei, double gSize) {
    width = (int)(screenWid/gSize);
    height = (int)(screenHei/gSize);
    gridSize = gSize;
    gridSizeSq = gSize*gSize;
    space = new Vector[width][height];
    for (int i=0;i<space.length;i++) for (int j=0;j<space[i].length;j++) space[i][j]=new Vector();
  }
  
  public void add(Particle p) {
    space[screenToIndex(p.pos.X)][screenToIndex(p.pos.Y)].add(p);
  }
  
  public void remove(Particle p) {
    space[screenToIndex(p.pos.X)][screenToIndex(p.pos.Y)].remove(p);
  }
  
  public void show(Particle p) {
    rectMode(CORNER);
    rect((float)(screenToIndex(p.pos.X)*gridSize),(float)(screenToIndex(p.pos.Y)*gridSize),(float)gridSize,(float)gridSize);
  }
  
  public int screenToIndex(double xy) {
    return ((int)(xy/gridSize));
  }
  
  public Vector getNeighbours(Particle p) {
    Vector out = new Vector();
    int i = screenToIndex(p.pos.X);
    int j = screenToIndex(p.pos.Y);
    for (int io=-1;io<=1;io++) for (int jo=-1;jo<=1;jo++) {
      int ii=i+io, jj=j+jo;
      if (ii>=0&&ii<width&&jj>=0&&jj<height) {
        for (int n=0;n<space[ii][jj].size();n++) {
          Particle pSpace = (Particle)space[ii][jj].elementAt(n);
          double dx = p.pos.X-pSpace.pos.X;
          double dy = p.pos.Y-pSpace.pos.Y;
          double distanceSq = dx*dx+dy*dy;
          double touchDistanceSq = (p.INFLUENCE_RADIUS+pSpace.INFLUENCE_RADIUS)*(p.INFLUENCE_RADIUS+pSpace.INFLUENCE_RADIUS);
          if (pSpace!=p&&distanceSq<touchDistanceSq) {
            out.add(pSpace);
          }
        }
      }
    }
    return out;
  }
  
  public void clear() {
    for (int i=0;i<space.length;i++) for (int j=0;j<space[i].length;j++) space[i][j].clear();
  }
  
}