package simulator;

import utils.*;
import java.util.*;
import java.awt.geom.*;

public class EmbeddedNetwork {
  double net_radius;
  Hashtable nodes;
  Hashtable[][] locals;
  int gridsize;

  public EmbeddedNetwork(double r) {
    net_radius = r;
    nodes = new Hashtable(1000,(float)0.25); // create a nice, roomy hashtable
    gridsize = (int)Math.ceil(1.0/r);
    locals = new Hashtable[gridsize][gridsize];
    for(int i=0;i<gridsize;i++)
      for(int j=0;j<gridsize;j++)
        locals[i][j] = new Hashtable();
  }

  synchronized public void removeNode(Object p) {
    NetNode n = (NetNode)nodes.remove(p);
    for(int i=0;i<locals.length;i++)
      for(int j=0;j<locals.length;j++)
        locals[i][j].remove(p);
    // now remove it from all of its neighbors neighborhoods
    if(n!=null) {
      Iterator i = n.neighbors.iterator();
      while(i.hasNext()) {
        NetNode nbr = (NetNode)nodes.get(i.next());
        nbr.neighbors.remove(p);
      }
    }
  }

  synchronized public void addNode(Object p, double x, double y) {
    NetNode n = new NetNode(p,x,y);
    nodes.put(p,n);
    int gridx = (int)Math.floor(x/net_radius);
    int gridy = (int)Math.floor(y/net_radius);
    // ******* NEED TO FIGURE OUT WHY +/-2 is needed!!!!!
    for(int i=gridx-2;i<gridx+2;i++) { // excessive...
      if(i<0||i>=gridsize) continue;
      for(int j=gridy-2;j<gridy+2;j++) { // excessive...
        if(j<0||j>=gridsize) continue;
        Enumeration e = locals[i][j].elements();
        while(e.hasMoreElements()) {
          NetNode nbr = (NetNode)e.nextElement();
          double dist = Math.sqrt(((n.x-nbr.x)*(n.x-nbr.x))+
                                  ((n.y-nbr.y)*(n.y-nbr.y)));
          if(dist < net_radius) {
            nbr.neighbors.add(n.p); // add the node's object only
            n.neighbors.add(nbr.p); // add the node's object only
          }
        }
      }
    }
    locals[gridx][gridy].put(p,n);
  }

  // searches outward from the point in a spiral pattern
  // when a hit is found, a search of the next layer of
  // the spiral confirms the hit is best
  private Pair bestingrid(double x, double y, Hashtable g) {
    double bestDist = Double.NaN;
    Object bestNode = null;
    Enumeration e = g.elements();
    while(e.hasMoreElements()) {
      NetNode n = (NetNode)e.nextElement();
      double dist = Math.sqrt(((n.x-x)*(n.x-x))+
                              ((n.y-y)*(n.y-y)));
      if(Double.isNaN(bestDist) || dist < bestDist) {
        bestDist = dist;
        bestNode = n;
      }
    }
    return new Pair(bestNode,new Double(bestDist));
  }
  synchronized public Object nearestNode(double x, double y) {
    double bestDist = Double.NaN;
    Object bestNode = null;
    Pair t = null;

    // try it the easy way first...
    int gridx = (int)Math.floor(x/net_radius);
    int gridy = (int)Math.floor(y/net_radius);
    // first, check the local
    t = bestingrid(x,y,locals[gridx][gridy]);
    bestDist = ((Double)t.cdr()).doubleValue();
    bestNode = t.car();
    boolean newtest = (bestNode == null);
    int search_radius = 1;
    while(newtest && search_radius < gridsize) {
      newtest = false;
      for(int i=-search_radius+1;i<search_radius;i++) {
        int cx,cy;
        cx = gridx+i; cy = gridy-search_radius; // top
        if(cx>0&&cx<=gridsize&&cy>0&&cy<=gridsize) {
          t = bestingrid(x,y,locals[cx][cy]);
          if(t.car() != null && bestDist>((Double)t.cdr()).doubleValue()) {
            bestDist = ((Double)t.cdr()).doubleValue();
            bestNode = t.car(); newtest = true;
          }
        }
        cx = gridx+i; cy = gridy+search_radius; // bottom
        if(cx>0&&cx<=gridsize&&cy>0&&cy<=gridsize) {
          t = bestingrid(x,y,locals[cx][cy]);
          if(t.car() != null && bestDist>((Double)t.cdr()).doubleValue()) {
            bestDist = ((Double)t.cdr()).doubleValue();
            bestNode = t.car(); newtest = true;
          }
        }
        cy = gridy+i; cx = gridx-search_radius; // left
        if(cx>0&&cx<=gridsize&&cy>0&&cy<=gridsize) {
          t = bestingrid(x,y,locals[cx][cy]);
          if(t.car() != null && bestDist>((Double)t.cdr()).doubleValue()) {
            bestDist = ((Double)t.cdr()).doubleValue();
            bestNode = t.car(); newtest = true;
          }
        }
        cy = gridy+i; cx = gridx+search_radius; // right
        if(cx>0&&cx<=gridsize&&cy>0&&cy<=gridsize) {
          t = bestingrid(x,y,locals[cx][cy]);
          if(t.car() != null && bestDist>((Double)t.cdr()).doubleValue()) {
            bestDist = ((Double)t.cdr()).doubleValue();
            bestNode = t.car(); newtest = true;
          }
        }
      }
      search_radius++;
    }
    if(bestNode != null) return ((NetNode)bestNode).p; else return null;
  }

  synchronized public Enumeration getNeighbors(Object p) {
    NetNode n = (NetNode)nodes.get(p);
    if(n==null)
      return (new Vector()).elements();
    else
      return n.neighbors.elements();
  }

  synchronized public boolean isNeighbor(Object a, Object b) {
    NetNode n = (NetNode)nodes.get(a);
    if(n==null) return false;
    else return n.neighbors.contains(b);
  }

  synchronized public Point2D getLocation(Object p) {
    NetNode n = (NetNode)nodes.get(p);
    return new Point2D.Double(n.x,n.y);
  }

  synchronized public Enumeration getNodes() { return nodes.keys(); }
  synchronized public Set getNodeSet() { return nodes.keySet(); }
}

class NetNode {
  Object p;
  double x;
  double y;
  Vector neighbors; // contains objects, not netnodes
  public NetNode(Object p, double x, double y) {
    this.p = p; this.x = x; this.y = y; neighbors = new Vector();
  }
  public String toString() {
    return "("+x+", "+y+", "+p.toString()+")";
  }
}
