/**********************************
 * Assignment 5: Pacman
 * Date: 5/5/2006
 *
 * Jenna Holloway: jh382, 563324
 * Benji Shultz: bas67, 1786511
 **********************************/
/******************************************************************************
 * Graph.java
 *
 * This file is part of CS211-fa06 Assignment 2
 *
 * Implement a graph in adjacency list format and some graph algorithms.
 * 
 * Requirement:
 * - Must extend AbstractGraph class. One may write additional methods or
 *   create addtional classes.
 * - Must override the default constructor (public Graph()).
 * - The implementation of each abstract method in AbstractGraph
 *   must satisfy the given asymptotic running time bound. Note that the
 *   specified bound are not necessarily tight (i.e. the optimal achievable
 *   asymptotical running time).
 *
 * Graph I/O Specification:
 *     The graph file is given as a pure text file. The first line has a
 * single integer n, which is the number of nodes in the graph. The next n lines
 * (line 2 -- n+1) each has two integers, delimited by a white space,
 * representing in order the x and y coordinates of the node. Since nodes
 * are added to graph sequentially, each node's sequence number (starting at 
 * zero) shall be its line number (in the input file) minus 2. After this,
 * the next line has a single integer m standing for the number of edges.
 * The following m lines each have three values: the first two integers are
 * the sequence numbers of the two endpoints of the edge and the third 
 * floating point number is the weight of the edge. If the third number 
 * is -1, the edge weight shall be the Euclidean distance between endpoints.
 */

package graph;
import java.util.Iterator;
import java.util.PriorityQueue;
import java.util.Comparator;
/*** 
 * YOU HAVE TO WRITE THIS!!!!!!
 * The main graph class - implements I/O, graph building, and some graph
 * algorithms.
 * 
 *
 */
public class MapGraph implements Graph {

 /* Constants */
 public static final double INFINITY = Double.POSITIVE_INFINITY;
 public static final double MAX_EDGE_WEIGHT = Double.MAX_VALUE;
 
 //assert that number of nodes is not greater than 300 
 //so load factor<1; nodes are created at the start
 //so never need to remove, or rehash
 public static int NODESIZE=503, nodeload, numNodes=0;
 public static int EDGESIZE=503, edgeload, numEdges=0;
 public static MyNode[] nodes= new MyNode[NODESIZE];
 public static MyEdge[] edges= new MyEdge[EDGESIZE];
 //assigned to node for djikstra's alg
 //used two ids so that get(x,y) and get(id) were
 //both O(1).
 private static int pathid=0;
 
 /*
  * Helper classes for Node and Edge HashTables
  * next pointers for list-colllision resolution
  */
 private class MyNode extends Node{
   MyNode next;
   public MyNode(int x, int y){
   super(0,x,y);
   }
   public MyNode(Node node){
     super(node.id, node.x, node.y);
   }
   public String toString(){
    if(this!=null){
     return "[" +x+","+y+"]" ;
    }
    else return null;
   }
   
   public boolean equals(Node mn){
     return (mn.x==this.x&&mn.y==this.y);
 }}

 private class MyEdge extends Edge{
   MyEdge next;
   public MyEdge(Node n1, Node n2){
     super(0,n1, n2, n1.distance(n2));
   }
   public MyEdge(Node n1,Node n2, double weight){
     super(0,n1,n2,weight);
   }
   public boolean equals(Edge edge){
   return ((v1.equals(edge.v1)&&v2.equals(edge.v2))
             ||(v1.equals(edge.v1)&&v2.equals(edge.v2)));
   }
   }
 
 
 /*Hash Function
  * produces node hash array location
  * */
   public static int hashFunction(int x, int y, int hashsize){
    return (3*x+7*y)%hashsize;
  }


 /* Constructors
  */
   
 public MapGraph Graph(){
  return new MapGraph();
 }
 
 public MapGraph() {
 }

 // --------- Access methods ---------

 /* Add a node to the graph. Two nodes can't have the same coordinate value.
       If the x, y coordinates already exists, do nothing and return false;
       otherwise, add the node and return true.
  */
 protected boolean addNode(Node v) {
  int i=addNode(v.x,v.y);
  if(i<0) return false;
  return true;
 }

 /* Add a node to the graph, given its x,y location.
       Return the node's id if the node is added, -1 if some node
       already exists at that location.
       - A Node object is constructed in this method.
       
     *O(1)
  */
 public int addNode(int x, int y) {
  MyNode mn1=new MyNode(x,y);
  int index=hashFunction(x,y,NODESIZE);
  MyNode mn2=nodes[index];
    
  if (mn2==null){
    nodes[index]=mn1; mn1.id=index*100;
  }
  else{
    int i=1;
    while(mn2.next!=null&&!mn1.equals(mn2)){
      i++;mn2=mn2.next;
    }
    if(mn1.equals(mn2)) return -1;
    mn2.next=mn1;
    mn1.id=index*100+i;
  }
  numNodes++;
  mn1.pathid=pathid++; //paths from(as src) and from(as dst) array index
  return mn1.id;
    
 
 }

 /* Return a node given its id.
       - Assume the id is valid.
       - This specific implementation will return null for invalid id.
  *O(1)
  */
 public MyNode getNodeById(int id) {
  int index=id/100;
  int listIts=id%100;
  if(index>nodes.length)return null;
  MyNode mn=nodes[index];
  for(int j=0; j<listIts; j++){
    if(mn!=null){
      mn=mn.next;
    }
  }
  return mn;

 }

 /* Return a node given its x-y coordinates, null if no node at such place.
  */
 public Node getNodeByCoord(int x, int y) {
  int index=hashFunction(x,y,NODESIZE);
  MyNode mn=nodes[index];
  if(mn==null)throw new IllegalArgumentException(x+":"+y);
  while(mn.next!=null&&!(mn.x==x&&mn.y==y))
    mn=mn.next;
  return mn;
 }
 

 /* Return the number of nodes in the graph
  */
 public int nodeCount() {
  return numNodes;
 }
 

 /* Add an edge to the graph, given the edge.
       Return true if edge is added, false if it already exists.
  */
 protected boolean addEdge(Edge e) {
  int i=addEdge(e.v1.id,e.v2.id,e.weight);
  if (i<0) return false;
  return true;
 }

 

 /* Add an edge to the graph, given the two end points' ids and its weight.
       Return the edge's id if the edge is added, or -1 if adding it would form
       a multiple edge (i.e. an edge already exists betwee the two endpoints)
       or a loop (i.e. the two endpoints are one and the same). In the latter
       case (i.e. where -1 is returned), the edge shall not be added.
       - Assume the two endpoints have already been added to the graph.
       - An Edge object is constructed in this method.
  *O(1)
  */
 public int addEdge(int nid1, int nid2, double weight) {
   Node n1=getNodeById(nid1);
   Node n2=getNodeById(nid2);
   MyEdge edge=new MyEdge(n1,n2,weight);
   n1.addNeighbor(n2);
   if(n1.equals(n2)) return -1;
   int index=hashFunction(nid1,nid2,EDGESIZE);
   if(edges[index]==null){
     edges[index]=edge; 
     edge.id=index*100;
   }
   else{
     int i=1;
     MyEdge edge1=edges[index];
     while(edge1.next!=null&&!edge.equals(edge1)){
       i++;edge1=edge1.next;
     }
     if(edge.equals(edge1)){
       return -1;
     }
     edge1.next=edge;
     edge.id=index*100+i;
   }
   numEdges++;
   return edge.id;
 }

 /* Add an edge to the graph, give the ids of the two end points. The weight
       of the edge is set to the distance of the two Nodes on the x-y plane.
       Return the edge's id if the edge is added, -1 if an edge already exists
       between the two endpoints.
       - Assume the two endpoints have already been added to the graph, i.e.
         nid1 and nid2 are both valid.
  */
 public int addEdgeWeighedByDistance(int nid1, int nid2) {
  return addEdge(nid1, nid2, getNodeById(nid1).distance(getNodeById(nid2)));
 }

 /* Return an edge given its id.
       - Assume the id is valid.
       - This specific implementation will return null for invalid id.
  */
 public Edge getEdgeById(int id) {
  int index=id/100;
  int listIts=id%100;
  if(index>edges.length) return null;
  MyEdge me=edges[index];
  for(int i=0;i<listIts;i++){
    if(me!=null)  me=me.next;
  }
  return me;
 }

 /* Return an edge given its two endpoints, or null if the edge dosn't exist.
       - Assume neither of v1 and v2 is null.
  */
 public Edge getEdgeByEndpoints(Node v1, Node v2) {
   int index=hashFunction(v1.id,v2.id,EDGESIZE);
   MyEdge me=edges[index];
   while(me!=null&&!(me.v1.equals(v1)&&me.v2.equals(v2)||me.v1.equals(v2)&&me.v2.equals(v1))){
     me=me.next;
   }
   return me;
 }

 /* Return the weight of an edge given its two endpoints, or INFINITY if
       the edge doesn't exist.
       - Assume neither of v1 and v2 is null.
  */
 public double getEdgeWeight(Node v1, Node v2) {
  Edge me=getEdgeByEndpoints(v1, v2);
  if(me==null) return INFINITY;
  return me.weight;
 }

 /* Return the number of edges in the graph
  */
 public int edgeCount() {
  return numEdges;

 }


 // ---------- Methods related to graph algorithms ---------

 /* Computes the weight of a given path on the graph
       - Return INFINITY if p is empty, i.e. has nodeCount() == 0 (meaning 
         path doesn't exist)
       - Assume p is not null.
  */
 public double pathWeight(Path p) {
   Iterator<Node> it=p.iterator();
   if(p.nodeCount()==0) return INFINITY;
   Node n1=it.next(), n2;
   int weight=0;
   while(it.hasNext()){
     n2=it.next();
     double e=getEdgeWeight(n1,n2);
     weight+=e;
     n1=n2;
   }    
  return weight;

 }
   
 /* Compute the shortest path from one node src to the dst on the graph
       (Dijkstra's algorithm)
       - Return an empty path (i.e. w/ no node) if src and dst are disconnected.
  */
 
 public Path shortestPath(Node src, Node dst){
  //Array contain short path weights, shortest path
  //predecessors and a flag to see if this node
  //has been visited.
  if (src==null||dst==null) return new Path();
  final double[] pathweights=new double[nodeCount()];
  Node[] predecessors=new Node[nodeCount()];
  boolean[] flags=new boolean[nodeCount()];
  Iterator<Node> it; Node mn=src, neigh;
  for(int i=0; i<nodeCount();i++){
   pathweights[i]=INFINITY;
   predecessors[i]=null;
   flags[i]=false;
  }
  pathweights[src.pathid]=0;
  
  //Comparator determines node priority
  final Comparator<Node> comp=new Comparator<Node>(){
   public int compare (Node n1, Node n2){
    if(pathweights[n1.pathid]>pathweights[n2.pathid]) return 1;
    if(pathweights[n1.pathid]<pathweights[n2.pathid]) return -1;
    return 0;
   }};
 PriorityQueue<Node> pq=new PriorityQueue<Node>(5,comp);
 pq.add(src);
 while(!mn.equals(dst)&&!pq.isEmpty()){
  mn=pq.poll();
  if(!flags[mn.pathid]){
  flags[mn.pathid]=true;
  it=mn.getNeighbors();
  while(it.hasNext()){
   neigh=it.next();
   pq.add(neigh);
   if(pathweights[neigh.pathid]>pathweights[mn.pathid]+getEdgeWeight(mn, neigh)){
    pathweights[neigh.pathid]=pathweights[mn.pathid]+getEdgeWeight(mn, neigh);
    predecessors[neigh.pathid]=mn;
    
   }
   }
  }
 }
 
     //construct this here path
   Path p=new Path();
   Node step=dst;
   while (step!=null){
     p.appendNode(step);
     step=predecessors[step.pathid];
     }
   if(!p.lastNode().equals(src))return new Path();
     return Path.reverse(p);
       
     
 }
     
     
     
        
   
   
 

///---OPTIONAL---OPTIONAL---OPTIONAL---
   
   /* The following methods are OPTIONAL, you do NOT have to
    * implement them for the assignment.  However, they
    * may make testing easier.
    */

 //---------- I/O methods ----------
   
 /* Read in the graph from a file with 'filename'.
       Return the Graph object if successful, an A5RuntimeException will be
       thrown if some error has been detected.
  */
 public static MapGraph readGraph(String filename) {
  return null;

 }

 /* load the graph by reading from a file with 'filename'. (non-static ver.)
       An A5RuntimeException will be thrown if some error has been 
       detected (e.g. the input file doesn't represent a valid graph).
       - After the call, the graph object upon which the method is 
         invoked will be updated to represent the graph specified 
         by the input file. 
  */
 public void loadGraph(String filename) {
   throw new UnsupportedOperationException(); 
 }

 /* Write the graph to file withe 'filename'.
       Throws A5RuntimeException if some error has occurred.
  */
 public static void writeGraph(MapGraph g, String filename) {
  

 }

 /* Non-static version of writeGraph
       Throws A5RuntimeException if some error has occurred.
  */
 public void saveGraph(String filename) {
  

 }

}


