package com.invis.route;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigDecimal;
import java.sql.Connection;
import java.sql.PreparedStatement;
import java.sql.ResultSet;
import java.util.Enumeration;
import java.util.Hashtable;
import java.util.Vector;

import javax.swing.JOptionPane;

import com.invis.map.db.Database;

//This class represent one node and stores the following properties
//Name of the node
//Previous node in the shortest path
// Adjacent nodes 
// Distance from one node to the next node


public class Dijkstra_App {


class Node {
	int	delta_plus;	/* edge starts from this node */
	int	delta_minus;	/* edge terminates at this node */
	double	dist;		/* distance from the start node */
	int	prev;		/* previous node of the shortest path */
	int	succ,pred;	/* node in Sbar with finite dist. */
	int	pw;
	int	dx;
	int	dy;
	String	name;
}

class Edge {
	int	rndd_plus;	/* initial vertex of this edge */
	int	rndd_minus;	/* terminal vertex of this edge */
	int	delta_plus;	/* edge starts from rndd_plus */
	int	delta_minus;	/* edge terminates at rndd_minus */
	double	len;		/* length */
	String	name;
}
	int	n,m;
	int	u,snode,dNode,startNode;
	double shortDist;	/* start node */
	int	pre_s_first, pre_s_last;
	boolean	isdigraph;
	
	int countw=400;
	int counth=300;
	
	int	iteration, step;
	Node	v[] = new Node[15000];
	Edge	e[] = new Edge[28000];
	Hashtable ht=new Hashtable();
	Hashtable htNode=new Hashtable();
	
	Vector retVect=new Vector();
	private static Connection c=null;
 	private static String sql="";
	private  static  PreparedStatement ps=null;
 	private static  ResultSet rs=null;
	
	public Dijkstra_App() {
		
		init_db();
		readNodes();
		rdb();
		init_sub();
	
	}

	


   void rdb() {
		int	i,k;

		
		for (i=0; i<m; i++) {
			k = e[i].rndd_plus;
			if (v[k].delta_plus == -1)
				v[k].delta_plus = i;
			else {
				k = v[k].delta_plus;
				while(e[k].delta_plus >= 0)
					k = e[k].delta_plus;
				e[k].delta_plus = i;
			}
			k = e[i].rndd_minus;
			if (v[k].delta_minus == -1)
				v[k].delta_minus = i;
			else {
				k = v[k].delta_minus;
				while(e[k].delta_minus >= 0)
					k = e[k].delta_minus;
				e[k].delta_minus = i;
			}
		}
	}

	void append_pre_s(int i) {
		v[i].succ = v[i].pred = -1;
		if (pre_s_first<0)
			pre_s_first = i;
		else
			v[pre_s_last].succ = i;
		v[i].pred = pre_s_last;
		pre_s_last = i;
	}

	void remove_pre_s(int i) {
		int	succ = v[i].succ;
		int	pred = v[i].pred;

		if (succ>=0)
			v[succ].pred = pred;
		else
			pre_s_last = pred;
		if (pred>=0)
			v[pred].succ = succ;
		else
			pre_s_first = succ;
	}

	void step1() {		/* initialize */
		u = snode;
		for (int i=0; i<n; i++) {
			v[i].succ = v[i].pred = -2;
			v[i].prev =-1;
			 v[i].dist = -1;
		}
		v[u].succ = -3;
		v[u].dist = 0;
		pre_s_first = pre_s_last = -1;
	}

	void step2() {		/* replace labels */
		int i,j;

		j = v[u].delta_plus;
		while (j>=0) {
			i = e[j].rndd_minus;
			if ((v[i].succ>=-2)&&((v[i].dist<0)||
				(v[i].dist>v[u].dist+e[j].len))) {
				if (v[i].dist<0)
					append_pre_s(i);
				v[i].dist = v[u].dist + e[j].len;
				v[i].prev = u;	  /* label */
			}
			j = e[j].delta_plus;
		}
		if (!isdigraph) {
		j = v[u].delta_minus;
		while (j>=0) {
			i = e[j].rndd_plus;
			if ((v[i].succ>=-2)&&((v[i].dist<0)||
				(v[i].dist>v[u].dist+e[j].len))) {
				if (v[i].dist<0)
					append_pre_s(i);
				v[i].dist = v[u].dist + e[j].len;
				v[i].prev = u;	  /* label */
			}
			j = e[j].delta_minus;
		}
		}
		v[u].succ = -4;
	}

	void step3() {		/* find the shortest node in Sbar */
		int i;
		double rho;

		rho = -1;
		for (i = pre_s_first; i>=0; i = v[i].succ) {
			if ((rho < 0)||(rho>v[i].dist)) {
				rho = v[i].dist;
				u = i;
			}
		}
		remove_pre_s(u);
		v[u].succ = -3;
	}

	void step4() {
		v[u].succ = -4;
	}

	void init_sub() {
		int x[] = {1, 0, -1, 1, 0, -1};
		int y[] = {1, 1, 1, -1, -1, -1};
		int 	i,j,k;
		double	w,z;
	}

	public Vector printRoadId() {
		retVect=new Vector();
		for (int i=0; i<n; i++)
		{
			
			if ( (v[i].succ<-2) && (v[i].name.equals("u"+(String)Integer.toString(dNode))) )
			{
				//System.out.println("shortest distance from "+v[snode].name+" to"+v[i].name+"="+v[i].dist);
				shortDist=v[i].dist;
				counth +=20;
				Node t=v[i];
				int tempv=0;
				//System.out.println(ht.get("u20-u6"));
				while(! t.name.equals(v[snode].name))
				{
					tempv++;
					
					//System.out.println("Shortest path "+t.name+"-"+(v[t.prev]).name);
					if( ((String)ht.get(t.name+"-"+(v[t.prev]).name)) != null)
					{
							String st=(String)ht.get(t.name+"-"+(v[t.prev]).name);
							Integer intSt=new Integer(st);
							retVect.addElement(intSt);
							
							
							
					}
					else
					{
							//System.out.println(ht.get((v[t.prev]).name+"-"+t.name));
					 		String st1=(String)ht.get((v[t.prev]).name+"-"+t.name);	
							Integer intSt1=new Integer(st1);	
							retVect.addElement(intSt1);
												
					}
					t=v[t.prev];
					counth +=20;
	
				}//End WHILE Loop
				
				break;
				
			}//End IF
	
		}//End FOR Loop
		return retVect;
		
	}//End Function

	

	public void iterationProcess()
	{
		//System.out.println("To be snode="+"u"+Integer.toString(startNode));
		snode=(int)Integer.parseInt((String)htNode.get("u"+Integer.toString(startNode)));
		//System.out.println("snode="+snode);
		//paint();
		for(int kl=0;kl<1;)
		{
			if (iteration==0) {
			
				step1();
				iteration++;
				step = 2;
			} else if (iteration>=n) {
			
				step4();
				iteration = 0;
				break;
			} else {
				if (step == 2) {
					step2();
					step = 3;
				} else {
				
					step3();
					iteration++;
					step = 2;
				}
    		}
		}//End For Loop
	
		
	}
	
	public void init_db()
	{
		try
		{
	    
			//System.out.println("connecting to db...");
  			c=Database.connect();
			if( c != null)return;
				//System.out.println("Data base connected");
			
  	    }catch(Exception e){
   		JOptionPane.showMessageDialog(null, "Exception");
  	 	}
	}


	public void readNodes()
	{
		try
		{
	   
	   		// sql="Select distinct fnode_ from Roads_temp where fnode_ >= "+startNode+" and  fnode_ <= "+dNode+" or fnode_ <= "+startNode+" and fnode_ >= "+dNode;
	   		sql="Select distinct fnode_ from Roads_temp";
			
   	   		ps=c.prepareStatement(sql);
	  
			  // System.out.println(sql);
      		 rs=ps.executeQuery();
	  		 //System.out.println("query executed");
	  		 rs.last();
	  		 n=rs.getRow();
	  		 rs.first();
	  		// System.out.println(n);
			//System.out.println("Loading.....................");	
	   		for (int i = 0; i<n; i++) {
				Node node = new Node();
				node.name = "u"+rs.getInt("FNODE_");
				htNode.put(node.name,Integer.toString(i));
				//node.x = (int)st.nval;
				//node.y = (int)st.nval;
				v[i] = node;
				v[i].succ = v[i].pred = -2;
				v[i].prev =-1;
				 v[i].dist = -1;
				v[i].pw = 0;
				rs.next();
				v[i].delta_plus = v[i].delta_minus = -1;
				// System.out.println(node.name);
				//JOptionPane.showMessageBoxDialog(null,"test");
			}
	
			//sql="Select distinct ROADID, FNODE_,TNODE_,LENGTH from Roads_temp where fnode_ >= "+startNode+" and  fnode_ <= "+dNode+" or fnode_ <= "+startNode+" and fnode_ >= "+dNode;
			sql="Select distinct ROADID, FNODE_,TNODE_,LENGTH from Roads";
			//System.out.println(sql);
   			ps=c.prepareStatement(sql);
    		rs=ps.executeQuery();
			rs.last();
			m=rs.getRow();
			rs.first();
			//System.out.println("m="+m);
			String tempEdgePlus,tempEdgeMinus,tempRoadId;
		
			for (int i = 0; i<m; i++) {
				Edge edge = new Edge();
				edge.name =""; 
				
				tempEdgePlus="u"+Integer.toString(rs.getInt("FNODE_"));
				//System.out.println(tempEdgePlus);
				//edge.rndd_plus = findNode(tempEdgePlus);
				edge.rndd_plus = Integer.parseInt((String)htNode.get(tempEdgePlus));
				
				tempEdgeMinus="u"+Integer.toString(rs.getInt("TNODE_"));	
				//System.out.println("From Data base "+tempEdgePlus+"-"+tempEdgeMinus);
			
				//edge.rndd_minus = findNode(tempEdgeMinus);
				edge.rndd_minus = Integer.parseInt((String)htNode.get(tempEdgeMinus));
					
			
				tempRoadId=Integer.toString(rs.getInt("ROADID"));
			    // System.out.println("From Data base "+tempEdgePlus+"-"+tempEdgeMinus+"-"+tempRoadId);
				ht.put(tempEdgePlus+"-"+tempEdgeMinus,tempRoadId);
				
				//System.out.println(ht.get(tempEdgePlus+"-"+tempEdgeMinus));
		
				
				edge.len = rs.getFloat("LENGTH");
				//System.out.println("length="+edge.len);
				e[i] = edge;
				rs.next();
				e[i].delta_plus = e[i].delta_minus = -1;
			}
		
		   // System.out.println("****Loading completed****");
			iteration = step = 0;
			isdigraph=false;
   		
  	 	
  		
   		}catch(Exception e){
   			//JOptionPane.showMessageDialog(null, e.printStackTrace(););
			e.printStackTrace();
   		}
	}


	public void readData(int s,int s1)
	{
		
		startNode=s;
		dNode=s1;
	
	}

	public double getShortestDistance()
	{
		 //shortDist*100;
		//Double d=null;
		shortDist=shortDist*100;
	//	nu=nu.divide(nu,BigDecimal.ROUND_CEILING);
	double intPart=Math.floor(shortDist);
	double unroundPart=shortDist-intPart;
	double roundpart=Math.round(unroundPart*100);
	roundpart=roundpart/100;
	shortDist=intPart+roundpart;
	/*roundPart=(Math.floor(roundPart*100))/100;
	shortDist=intPart+roundPart;*/
		return shortDist;
		
	}
	
	public static void main(String h[])
	{
		Dijkstra_App objDijkstra=new Dijkstra_App();
	
	
		BufferedReader bfReader=new BufferedReader(new InputStreamReader(System.in));
		String s1,s;
	
	
		objDijkstra.readData(7611,7653);
		
		objDijkstra.iterationProcess();
		Vector v=objDijkstra.printRoadId();
		double shortDist=objDijkstra.getShortestDistance();
	
		Enumeration e=v.elements();
		/*System.out.println("Shortest path road ids");
		while(e.hasMoreElements())
		{
			System.out.println((Integer)e.nextElement());
		}
	   */// System.out.println("Shortest Distance="+shortDist);
	
			
		System.exit(0);
		
	}	
 
}