//  class hashVec
//  by Flux 05

//  The class hashVec is an extended hash table utility to store my
//  vector information. A hash table is a lookup table with objects
//  identified by a key (can be a String or a pointer or other things)

//  Here I divide space into an infinitely expandable grid, simply by
//  rounding the (x,y) of any point to the nearest grid size.

//  The hash key is constructed by converting the rounded x and y values
//  into a string, then concatenating them into one string.

//  The key points to an object called vecListing. vecListing holds
//  an array of pointers to other masses in that particular grid.
//  This allows every grid on the screen to "know" which point is where.

//  The process ultimately will return a list of neighbors, given a 
//  point in space, for comparison. This cuts down the number of
//  calculations required dramatically.

class hashVec
{
  Hashtable h;                                                            //  The hash table, a java util.
  float gridSize=15;                                                      //  The defined spatial grid size. Can be variable and even
                                                                          //  changed on the fly.
                                                                          
  hashVec()                                                               //  Constructor
  {
    h=new Hashtable();
  }
  
  int getHX(vec cv)                                                       //  Returns the rounded down grid space x value.
  {
    return int((floor(cv.x/gridSize))*gridSize);
  }
  int getHY(vec cv)                                                       //  Returns the rounded down grid space y value.
  {
    return int((floor(cv.y/gridSize))*gridSize);  
  }
  String getHashKey(vec cv)                                               //  Returns hash key in the format x+y string    
  {                                                                       //  eg point(101,204) will return "101204".
    if(cv==null)
      return "";
    int hx=getHX(cv);
    int hy=getHY(cv);
    String hk=str(hx)+str(hy);  
    return hk;
  }
  void clearHashTable()                                                   //  Clears the hash table.
  {
    h.clear();
  }
  void add(vec cv)                                                        //  Adds a point to the hash table for organization.
  {                                                                      
    if(cv==null)                                                          //  First check if the given point is bogus.
      return;
      
    String hashKey=getHashKey(cv);                                        //  Get the hash key for this point in space.
    if(h.get(hashKey)==null)                                              //  Find out whether or not a vecListing for this hash key already exists.
    {
      vecListing vl=new vecListing();                                     //  If not, create a new listing at this hash key and add this point.
      vl.add(cv);
      h.put(hashKey,vl);     
    }
    else
    {
      vecListing vl=(vecListing)h.get(hashKey);                           //  Otherwise simply add it to the already existing vector list.
      vl.add(cv);
    }
  }
  vec[] neighborsOf(vec cv)                                               //  This is the GOLD. Give this function a point and it will                    
  {                                                                       //  return a (hopefully) small list of neighbors to compare to.
    
    String hashKey=getHashKey(cv);                                        //  Get the hash key for the point in question.
    vecListing vl=(vecListing)h.get(hashKey);                             //  Also, try to get the vector list for the grid position it's in.
    
    if(vl==null)                                                          //  If the point is not found in a vector listing, you've got trouble...
    {
      return null;
    }
    else
    {      
      int hx=getHX(cv);                                                    
      int hy=getHY(cv);        
      
      vec t=new vec(hx,int(hy-gridSize));                                 //  Here we gather the vector list from the neighboring eight grid
      vec b=new vec(hx,int(hy+gridSize));                                 //  spaces as well as the space it is in. This helps the accuracy from
      vec l=new vec(int(hx-gridSize),hy);                                 //  a worst possible scenario: if a point is at the edge of its grid
      vec r=new vec(int(hx+gridSize),hy);                                 //  and another point is at the edge of the next grid, but they are not
      vec tl=new vec(int(hx-gridSize),int(hy-gridSize));                  //  being tested. This is a hack, and it is slower. If you know a better      
      vec tr=new vec(int(hx+gridSize),int(hy-gridSize));                  //  way to do this besides using two hash tables, please mail me at         
      vec bl=new vec(int(hx-gridSize),int(hy+gridSize));                  //  mflux@ucla.edu to share. Thanks :]
      vec br=new vec(int(hx+gridSize),int(hy+gridSize));               
      vec c=new vec(int(hx),int(hy));

      vec region[]={c,t,b,l,r,tl,tr,bl,br};                               //  Gather the test locations into a nice list so we can loop through it.
      vec[] neighbors=new vec[0];      
      for(int s=0;s<region.length;s++)
      {
        hashKey=getHashKey(region[s]);                                    //  Get the vector listing for the region/grid space in question.
        vl=(vecListing)h.get(hashKey);
        if(vl!=null)                                                      //  Make sure it exists before we do anything.
        {
          for(int i=0;i<vl.vlist.size();i++)                              //  Now add these neighbors in the listing into a final list.
          {                                                               //  Keep expanding this list as we get more neighbors from surrounding          
            vec temp[]=new vec[neighbors.length+1];                       //  regions.
            System.arraycopy(neighbors,0,temp,0,neighbors.length);
            temp[neighbors.length]=(vec)vl.vlist.get(i);
            neighbors=temp;
          }
        }
      }
      return neighbors;                                                   //  Return a list of neighbors for distance comparison.
    }
  }
  class vecListing                                                        //  vecListing simply contains a list of vectors.
  {                                                                       //  These are the objects hashed and referred to by a key on the grid space.
    Vector vlist=new Vector();
    vecListing()
    {}
    void add(vec cv)                                                      //  Adds a vector position into the list.
    {
      if(cv==null)
        return;
      vlist.add(cv);
    }
  }  
}