/************************************************************************************
 * Copyright (C) 2008 by Politehnica University of Bucharest and Rutgers University
 * All rights reserved.
 * Refer to LICENSE for terms and conditions of use.
 ***********************************************************************************/
package vnsim.map.object;


import java.util.Comparator;
import java.util.Random;
import java.util.Collections;
import java.util.ArrayList;
import java.util.logging.*;
import java.io.*;

import vnsim.applications.adaptiveTL.*;
import vnsim.applications.emissions.EmissionsTrafficLight;
import vnsim.map.utils.*;
import vnsim.vehicular.routePlan.selfRouted.RoadAreaUtils;
import vnsim.vehicular.simulator.intersections.*;
import vnsim.gui.*;




/**
 * @author Victor-Radu
 */
public class Map implements Serializable {
	
	/** <code>serialVersionUID</code> */
	private static final long serialVersionUID = -5883719321862303634L;
	
	/** Logger used by this class */
	private static final transient Logger logger = Logger.getLogger("vnsim.map.object.Map");
	
	public ArrayList<Road> roads = new ArrayList<Road>();

	public ArrayList<PeanoKey> peanoKeys = new ArrayList<PeanoKey>();

	public Point minPoint, maxPoint;

	public RoadAreaUtils mapSpliter;

	//all intersections
	public ArrayList<Intersection> allIntersections=new ArrayList<Intersection> ();
	
	//the indices of the intersections with traffic lights 
	//(kept here for optimization)
	public ArrayList<Integer> lightsIndices=new ArrayList<Integer> ();

	//intersections with traffic lights
	//	public ArrayList<IntersectionWithTrafficLights> intersectionsWithLights=new ArrayList<IntersectionWithTrafficLights> ();

	public Map(){
	}
	
	public Map(String rt1file, String rt2file){
		double kmNo=0;
		int j = 0;
		Point p1;
		Point p2;
		logger.info("File name is "+rt1file);
		/* load the roads vector and sort streets on id */ 
		loadRoadsFromRT1File(rt1file);
		logger.info("Done loading roads");
		/* load intermediate points for each road segment */ 
		loadPointsFromRT2File(rt2file);
		logger.info("Done loading points");
		
		/* add more points on each street using interpolation, in order to have
		 * a higher resolution and be able to map a car more accurately on the 
		 * road (Globals.MAXSEGLEN - meters - dictates this resolution) */
		for (int i = 0; i<roads.size(); i++){
			Road r = (Road)roads.get(i);
			j=0;
			while (j < r.points.size()-1){
				p1 = (Point)r.points.get(j);
				p2 = (Point)r.points.get(j+1);
				while (GPSutil.distance(p1, p2) > Globals.MAXSEGLEN){
					Point p = new Point( (p1.getLongitude() + p2.getLongitude())/ 2.0,
									(p1.getLatitude() + p2.getLatitude()) / 2.0);
					r.points.add(j+1, p);
					p1 = (Point)r.points.get(j);
					p2 = (Point)r.points.get(j+1);
				}
				j++;
			}
		}
		logger.info("Done interpolating");
			
		/* merge small segments with the same road name (a segment is between 2 
		 * consecutive intersections) into big roads with refferences to the 
		 * intersections - it's easier to apply graph algorithms*/
		mergeRoadSegments(rt1file);
		logger.info("Done merging segments - " + roads.size());
		
		/* compute distances along the road, between each point and 
		 * the start point on the segment
		 * We also compute here the PeanoKey for each point
		 */
		for (int i = 0; i<roads.size(); i++){
			Road r = (Road)roads.get(i);
			j=0;
			p1 = (Point)r.points.get(0);
			p1.setDistance(0.0);
			peanoKeys.add(new PeanoKey(p1, i, j));
			for (j = 1; j < r.points.size();j++){
				p2 = (Point)r.points.get(j);
				p2.setDistance(p1.getDistance() + GPSutil.distance(p1, p2));
				p1 = p2;
				
				peanoKeys.add(new PeanoKey(p1, i, j));
			}
			kmNo += ((Point)r.points.get(r.points.size()-1)).getDistance();
			//System.out.println("Done computing distances and Peano Keys");
			
		}
		logger.info("Done adding points, computing distances and Peano Keys");
		logger.info("Roads " + roads.size());
		logger.info("Points " + peanoKeys.size());
		logger.info("Total number of kilometers " + kmNo);
		logger.info("Average segment size " + kmNo/roads.size());
		
		/* sort the PeanoKey vector */
		Collections.sort(peanoKeys);
		
		// complete inverse reference from point to peano key 
		for (int i = 0; i < peanoKeys.size();i++){
			Road r = roads.get(peanoKeys.get(i).getRoadIndex());
			Point p = r.points.get(peanoKeys.get(i).getPointIndex());
			p.setPeanoKeyIdx(i);
		} 
		
		logger.info("Done sorting");
		
		/* add crosses
		 * for each road 
		 * 		find other roads that intersect and add them to the Crosses vector
		 * Complexity: O(n) n - number of points
		 * 			- because we just need to find equal values in the sorted PeanoKey
		 * 			vector in order to find the two equal points, that are each on a
		 * 			different street. 
		 * 			These are intersection points that come from
		 * 			the TIGER files, not from interpolation because. For a bridge over 
		 * 			another street you wouldn't have TIGER segments that end in that point
		 * 			so you can't have false intersections*/
		
		Random generator = new Random(System.currentTimeMillis());
		setLaneNoRandom(generator);
		setLaneNoExtra();
		
		addCrossroads();
		logger.info("Done adding crossroads");
		
		Globals.map=this;
		addIntersections();
		
		checkIntersections();
		
		logger.info("Done creating intersections!");
		Globals.map=this;
		for(int ll=0;ll<allIntersections.size();ll++){
			if(!allIntersections.get(ll).hasTrafficLights()){	
				((IntersectionWithoutTrafficLights)(allIntersections.get(ll))).sort(generator);
			}
		}
//		createTrafficLights(generator);

//		System.out.println("INTERSECTIONS:"+allIntersections);
		logger.info("INTERSECTIONS :"+allIntersections.size());
		//System.out.println("INTERSECTIONS WITH LIOGHTS:"+intersectionsWithLights.size());
		getMinAndMaxPoint();
	}
	
	public int connectionPoint(int rdIdx1, int rdIdx2){
	//checks to see if the road which contains rdIdx1 has an intersection with rdIdx2
	//If it has, the function returns the cross index in the 
	//array of crosses of road rdIdx1  	
			if (rdIdx1 == rdIdx2)
				return -1;
			Road r1 = (Road)roads.get(rdIdx1);
			
			for (int i=0; i<r1.crosses.size();i++){
				Cross c = (Cross)r1.crosses.get(i);
				if (c.getCrossRoadIndex() == rdIdx2)
					return i;
			}
			return -1;
		}
	
//http://maps.google.com/?ll=40.741209,-73.983092&spn=0.015315,0.029268
	public static final boolean MODIFYMAP = false;
	
	public void loadRoadsFromRT1File(String rt1file){
		/* loads segments from the RT1 file in the roads vector*/	
			DataInputStream f;
			PrintWriter g;			//I used g when I wanted to create smaller TIGER files
			//from the original TIGER files. So, to create these small
			//smaller files I comment everything in the map constructor
			//but the calls to 
			// 			loadRoadsFromRT1File
			// 			loadPointsFromRT2File

			int len;
			byte[] buffer = new byte[Globals.RT1_length];
			//rt1file = "file://" + System.getProperty("user.dir") + rt1file;
			//System.out.println("New path is "+rt1file);
			try{
				f = new DataInputStream(Utils.getInstance().openStream(rt1file));
			}catch(Exception e){
				logger.log(Level.SEVERE, "File "+rt1file+" not found!", e);
				System.exit(0);
				return;
			}

			ArrayList<Integer> ids = new ArrayList<Integer>();
			if (MODIFYMAP){
				BufferedReader br = null;
				try{
					br = new BufferedReader(new InputStreamReader(Utils.getInstance().openStream("roadids.txt"))); 
					String s;
					while ((s = br.readLine())!=null){
						ids.add(Integer.parseInt(s));
					}
					br.close();
				}catch(Exception e){
					logger.log(Level.INFO, "File roadids.txt not found", e); 
				}
				try{
					g = new PrintWriter(new BufferedWriter(new FileWriter(System.getProperty("user.home")+File.separatorChar+"downtown2.RT1")));
				}catch(IOException e){
					logger.info("File downtown2.RT1 could not be open!");
					g = null;
				}
			}

			try{
				while ((len = f.read(buffer,0,Globals.RT1_length)) != -1){
					if (len != Globals.RT1_length){
						logger.info("File " + rt1file + " invalid RT1 format!");
						System.exit(0);
					}
			
					Road r = ParsingUtil.parseRoad(buffer);
					if (r!=null){
						roads.add(r);
						if (MODIFYMAP){
							if (ids.indexOf((int)r.getId()) == -1 
									&& !r.getName().trim().equals("Lexington") 
									&& !r.getName().trim().equals("7th") 
									&& !r.getName().trim().equals("22nd") 
									&& !r.getName().trim().equals("35th") 
									){
								g.print(new String(buffer));
							}
							int last = r.points.size() - 1;
							/*if (
									(((Point)r.points.get(0)).getLatitude() < 40.751221
											&& ((Point)r.points.get(0)).getLatitude() > 40.737553
											&& ((Point)r.points.get(0)).getLongitude() < -73.978051
											&& ((Point)r.points.get(0)).getLongitude() > -73.993238)
											|| (((Point)r.points.get(last)).getLatitude() < 40.751221
													&& ((Point)r.points.get(last)).getLatitude() > 40.737553
													&& ((Point)r.points.get(last)).getLongitude() < -73.978051
													&& ((Point)r.points.get(last)).getLongitude() > -73.993238)){
								
//								g.print(new String(buffer));
							}*/
						}
							 
									
	/*					//I used this section to find out the min/max latitude/longitude of the map 					
	  					if (((Point)r.points.get(0)).getLatitude() < minl)
							minl = ((Point)r.points.get(0)).getLatitude();
						if (((Point)r.points.get(0)).getLatitude() > maxl)
							maxl = ((Point)r.points.get(0)).getLatitude();
						if (((Point)r.points.get(1)).getLatitude() < minl)
							minl = ((Point)r.points.get(1)).getLatitude();
						if (((Point)r.points.get(1)).getLatitude() > maxl)
							maxl = ((Point)r.points.get(1)).getLatitude();
						if (((Point)r.points.get(0)).getLongitude() > minL)
							minL = ((Point)r.points.get(0)).getLongitude();
						if (((Point)r.points.get(0)).getLongitude() < maxL)
							maxL = ((Point)r.points.get(0)).getLongitude();
						if (((Point)r.points.get(1)).getLongitude() > minL)
							minL = ((Point)r.points.get(1)).getLongitude();
						if (((Point)r.points.get(1)).getLongitude() < maxL)
							maxL = ((Point)r.points.get(1)).getLongitude();
	*/				}else{
						//System.out.println("-> null");
					}
				}
	/*			System.out.println("minl " + minl);
				System.out.println("maxl " + maxl);
				System.out.println("minL " + minL);
				System.out.println("maxL " + maxL);
	*/			
				f.close();
				if (MODIFYMAP){
					g.close();
				}
				Collections.sort(roads);
			}catch (IOException e){
				logger.log(Level.SEVERE, "File "+rt1file+"not found", e);
				System.exit(0);
			}
		}

	
	
//	public void loadRoadsFromRT1File(String rt1file){
//	/* loads segments from the RT1 file in the roads vector*/	
//		DataInputStream f;
//		PrintWriter g;			//I used g when I wanted to create smaller TIGER files
//		//from the original TIGER files. So, to create these small
//		//smaller files I comment everything in the map constructor
//		//but the calls to 
//		// 			loadRoadsFromRT1File
//		// 			loadPointsFromRT2File
//
//		int len;
//		byte[] buffer = new byte[Globals.RT1_length];
//		//rt1file = "file://" + System.getProperty("user.dir") + rt1file;
//		//System.out.println("New path is "+rt1file);
//		try{
//			f = new DataInputStream(Utils.getInstance().openStream(rt1file));
//		}catch(Exception e){
//			logger.log(Level.SEVERE, "File "+rt1file+" not found!", e);
//			System.exit(0);
//			return;
//		}
//
//		ArrayList<Integer> ids = new ArrayList<Integer>();
//		if (MODIFYMAP){
//			BufferedReader br = null;
//			try{
//				br = new BufferedReader(new InputStreamReader(Utils.getInstance().openStream("roadids.txt"))); 
//				String s;
//				while ((s = br.readLine())!=null){
//					ids.add(Integer.parseInt(s));
//				}
//				br.close();
//			}catch(Exception e){
//				logger.log(Level.INFO, "File roadids.txt not found", e); 
//			}
//			try{
//				g = new PrintWriter(new BufferedWriter(new FileWriter(System.getProperty("user.home")+File.separatorChar+"downtown2.RT1")));
//			}catch(IOException e){
//				logger.info("File downtown2.RT1 could not be open!");
//				g = null;
//			}
//		}
//
//		try{
//			while ((len = f.read(buffer,0,Globals.RT1_length)) != -1){
//				if (len != Globals.RT1_length){
//					logger.info("File " + rt1file + " invalid RT1 format!");
//					System.exit(0);
//				}
//		
//				Road r = ParsingUtil.parseRoad(buffer);
//				if (r!=null){
//					roads.add(r);
//					if (MODIFYMAP){
//						if (ids.indexOf((int)r.getId()) == -1 
//								&& !r.getName().trim().equals("Lexington") 
//								&& !r.getName().trim().equals("7th") 
//								&& !r.getName().trim().equals("22nd") 
//								&& !r.getName().trim().equals("35th") 
//								){
//							g.print(new String(buffer));
//						}
//						int last = r.points.size() - 1;
//						/*if (
//								(((Point)r.points.get(0)).getLatitude() < 40.751221
//										&& ((Point)r.points.get(0)).getLatitude() > 40.737553
//										&& ((Point)r.points.get(0)).getLongitude() < -73.978051
//										&& ((Point)r.points.get(0)).getLongitude() > -73.993238)
//										|| (((Point)r.points.get(last)).getLatitude() < 40.751221
//												&& ((Point)r.points.get(last)).getLatitude() > 40.737553
//												&& ((Point)r.points.get(last)).getLongitude() < -73.978051
//												&& ((Point)r.points.get(last)).getLongitude() > -73.993238)){
//							
////							g.print(new String(buffer));
//						}*/
//					}
//						 
//								
///*					//I used this section to find out the min/max latitude/longitude of the map 					
//  					if (((Point)r.points.get(0)).getLatitude() < minl)
//						minl = ((Point)r.points.get(0)).getLatitude();
//					if (((Point)r.points.get(0)).getLatitude() > maxl)
//						maxl = ((Point)r.points.get(0)).getLatitude();
//					if (((Point)r.points.get(1)).getLatitude() < minl)
//						minl = ((Point)r.points.get(1)).getLatitude();
//					if (((Point)r.points.get(1)).getLatitude() > maxl)
//						maxl = ((Point)r.points.get(1)).getLatitude();
//					if (((Point)r.points.get(0)).getLongitude() > minL)
//						minL = ((Point)r.points.get(0)).getLongitude();
//					if (((Point)r.points.get(0)).getLongitude() < maxL)
//						maxL = ((Point)r.points.get(0)).getLongitude();
//					if (((Point)r.points.get(1)).getLongitude() > minL)
//						minL = ((Point)r.points.get(1)).getLongitude();
//					if (((Point)r.points.get(1)).getLongitude() < maxL)
//						maxL = ((Point)r.points.get(1)).getLongitude();
//*/				}else{
//					//System.out.println("-> null");
//				}
//			}
///*			System.out.println("minl " + minl);
//			System.out.println("maxl " + maxl);
//			System.out.println("minL " + minL);
//			System.out.println("maxL " + maxL);
//*/			
//			f.close();
//			if (MODIFYMAP){
//				g.close();
//			}
//			Collections.sort(roads);
//		}catch (IOException e){
//			logger.log(Level.SEVERE, "File "+rt1file+"not found", e);
//			System.exit(0);
//		}
//	}
	

	
	public void loadPointsFromRT2File(String rt2file){
	/* parse RT2 file and load additional points for the segments 
	 * already read from the RT1 file*/	
		
		DataInputStream f;
		PrintWriter g;
		int len;
		byte[] buffer = new byte[Globals.RT2_length];
		
		try{
			f = new DataInputStream(Utils.getInstance().openStream(rt2file));
		}catch(Exception e){
			logger.log(Level.SEVERE, "File "+rt2file+" not found", e);
			System.exit(0);
			return;
		}
		/*try{
			f = new RandomAccessFile(rt2file,"r");
		}catch(FileNotFoundException e){
			System.out.println("File " + rt2file + " not found!");
			System.exit(0);
			return;
		}*/
		ArrayList<Integer> ids = new ArrayList<Integer>();
		if (MODIFYMAP){
			try{
				g = new PrintWriter(new BufferedWriter(new FileWriter(System.getProperty("user.home")+File.separatorChar+"downtown2.RT2")));
				//g = new PrintWriter(
				//		new BufferedWriter(new FileWriter("downtown2.RT2")));
			}catch(IOException e){
				logger.info("File downtown2.RT2 could not be open");
				//System.out.println("File NJTurnpike2.RT2 could not be open!");
				System.exit(0);
				return;
			}
			BufferedReader br = null;
			try{
				br = new BufferedReader(new FileReader(new File("roadids.txt")));
				String s;
				while ((s = br.readLine())!=null){
					ids.add(Integer.parseInt(s));
				}
				br.close();
			}catch(IOException e){
				e.printStackTrace();
			}
		}
		try{
			while ((len = f.read(buffer,0,Globals.RT2_length)) != -1){
				if (len != Globals.RT2_length){
					System.out.println("File " + rt2file + " invalid RT2 format!");
					System.exit(0);
				}
				
				Road r = new Road();
				r.setId( Long.parseLong(new String(buffer, 5, 10).trim()) );
				int idx = Collections.binarySearch(roads,r);
				if (idx >= 0){
					r = (Road)roads.get(idx);
					
					if (MODIFYMAP){
//						if (ids.indexOf((int)r.getId()) == -1){
//						g.print(new String(buffer));
//						}
						int last = r.points.size() - 1;
						if (
								(((Point)r.points.get(0)).getLatitude() < 40.751221
										&& ((Point)r.points.get(0)).getLatitude() > 40.737553
										&& ((Point)r.points.get(0)).getLongitude() < -73.978051
										&& ((Point)r.points.get(0)).getLongitude() > -73.993238)
										|| (((Point)r.points.get(last)).getLatitude() < 40.751221
												&& ((Point)r.points.get(last)).getLatitude() > 40.737553
												&& ((Point)r.points.get(last)).getLongitude() < -73.978051
												&& ((Point)r.points.get(last)).getLongitude() > -73.993238)){
//							g.print(new String(buffer));
						}
					}
					
					
					for (int i=0;i<10;i++){
						Point p = ParsingUtil.parsePoint(new String(buffer, 18 + i*19, 19).getBytes());
						if (p.getLatitude() != 0.0 && p.getLongitude() != 0.0){
							/* for multiple RT2 records, assume the points 
							 * are all ordered nicely
							 */
							r.points.add(r.points.size()-1,p);
						}
					}
				}
			}
			f.close();
			if (MODIFYMAP){
				g.close();
			}
			Collections.sort(roads);
		}catch (IOException e){
			System.out.println("File " + rt2file + " invalid format!");
			System.exit(0);
		}
	}
	
	private final void createMapsDir() {
		// create local path...
		final String dir = System.getProperty("user.home")+File.separatorChar+"maps";
		File f = new File(dir);
		if (!f.exists())
			f.mkdirs();
	}
	
	public void mergeRoadSegments(String rt1file){
	/* the goal of this function is to eliminate prev and next information in road structure
	 * by merging road segments with the same name*/
		ArrayList<Road> roads_aux = new ArrayList<Road>(); 
		int[] v = new int[roads.size()]; 
		int next,prev;
		BufferedReader f=null;
		boolean needAdjacencyFile = false;
/*	As an optimization, a file with adjacency information is created in the current 
 *	directory, and any following execution of this program will avoid O(n^2) complexity
 * 	of completing next and previous fields for each segment. The file will have the name
 *	of the RT1 file written on the first line, in order to know wich map it is associated with
 *	On each line there will be <currentRoadIndex> <NextRoadIndex> 
 */		
		try{
			f = new BufferedReader(new InputStreamReader(Utils.getInstance().openStream("/maps/adjacency.txt")));
		}catch(Exception e){
			needAdjacencyFile = true;
		}

		if (f!=null){
			
			try{
				String s = f.readLine();
				if (!rt1file.equals(s)){
					logger.info("Inconsistent adjacency file, recreating...");
					f.close();
					// create local path...
					createMapsDir();
					// delete previous existing file...
					(new File(System.getProperty("user.home")+File.separatorChar+"maps"+File.separatorChar+"adjacency.txt")).delete();
					needAdjacencyFile = true;
				}
			}catch(IOException e){
				logger.warning("Error reading file adjacency.txt");
				try {
					f.close();
					// create local path...
					createMapsDir();
					// delete previous existing file...
					(new File(System.getProperty("user.home")+File.separatorChar+"maps"+File.separatorChar+"adjacency.txt")).delete();
					needAdjacencyFile = true;
				} catch (Exception ex) {
					logger.log(Level.SEVERE, "Error creating file adjacency... ", ex);
					System.exit(0);
				}
			}
		}
			
		if (needAdjacencyFile){
			System.out.println("Adjacency file does not exist - wait while it is being built...");
			buildAdjacencyFile(rt1file);
			
			try{
				createMapsDir();
				f = new BufferedReader(new InputStreamReader(new FileInputStream(System.getProperty("user.home")+File.separatorChar+"maps"+File.separatorChar+"adjacency.txt")));
			}catch(Exception e){
				logger.log(Level.SEVERE, "Adjacency file was not built...", e);
				System.exit(0);
			}
			try{
				String s = f.readLine();
				String rt1filename=new File(rt1file).getName();
				if (!rt1filename.equals(s)){
					f.close();
					logger.severe("Error: Adjacency file was built wrong");
					System.exit(0);
				}
			}catch(IOException e){
				logger.log(Level.SEVERE, "Error reading locally built file adjacency.txt", e);
				System.exit(0);
			}
		}
		
		//complete next an prev fields for each segment
		try{
			String line;
			while ((line = f.readLine())!=null){
				//System.out.println("**" + line);
				
				int i = Integer.parseInt(line.substring(0, line.indexOf(" ")));
				int j = Integer.parseInt(line.substring(line.indexOf(" ")+1, line.length()));
				v[i] = 0;
				v[j] = 0;
				Road r1 = (Road)roads.get(i);
				Road r2 = (Road)roads.get(j);
				r1.setNextRdIdx(j);
				r2.setPrevRdIdx(i);
			}
			f.close();
		}catch(IOException e){
			logger.severe("Error reading adjacency file ");
			System.exit(0);
			return;
		}
		
//		for (int i = 0; i<roads.size(); i++)
//			v[i] = 0;
//		
		//merge segments using next & prev connections between segments
		int loops = 0;
		for (int i = 0; i<roads.size(); i++){
			if (v[i] != 0)
				continue;
			Road r = (Road)roads.get(i);
			prev = i;
			while (r.getPrevRdIdx() != i && r.getPrevRdIdx() != -1){
				prev = r.getPrevRdIdx();
				r = (Road)roads.get(prev);
			}
			roads_aux.add(r);
			if (r.getPrevRdIdx() != -1){
				v[i] = 1;
				loops++;
				continue;	//if the road has loops we will consider each road segment
			}				// a different road as if it had a different name
			v[prev] = 1;
			while ((next = r.getNextRdIdx()) != -1){
				Road r2 = (Road)roads.get(next);
				if (v[next] == 1){
					System.out.println("Error: bad road segments adjacency");
					System.exit(0);
				}
				v[next] = 1;
				
				r.setNextRdIdx(r2.getNextRdIdx());
				
				r2.points.remove(0);
				r.points.addAll(r2.points);
				
			}
		}
		roads = roads_aux;
		logger.info("Loops " + loops);
	}
	
	public void buildAdjacencyFile(String rt1file){
		/* for every two segments that have a common end and the same name 
		 * compute next and prev fields
		 */
		RandomAccessFile f;
		try{
			createMapsDir();
			// delete previous existing file...
			(new File(System.getProperty("user.home")+File.separatorChar+"maps"+File.separatorChar+"adjacency.txt")).delete();
			f = new RandomAccessFile(System.getProperty("user.home")+File.separatorChar+"maps"+File.separatorChar+"adjacency.txt","rw");	
		}catch(FileNotFoundException e){
			System.out.println("Error creating file");
			System.exit(0);
			return;
		}
		
		try{
			File ftest=new File(rt1file);

			StringBuffer sb = new StringBuffer(ftest.getName());
			sb.append("\n");
			f.writeBytes(sb.toString());
			
			for (int i = 0; i<roads.size(); i++){
				Road r1 = (Road)roads.get(i);
				Point p0 = (Point)r1.points.get(0);
				Point p1 = (Point)r1.points.get(r1.points.size()-1);
				for (int j = i+1; j<roads.size(); j++){
					Road r2 = (Road)roads.get(j);
					Point p10 = (Point)r2.points.get(0);
					Point p11 = (Point)r2.points.get(r2.points.size()-1);
					
					if (r1.getName().equals(r2.getName())){
						if (p0.equals(p11)){
							if (r1.getPrevRdIdx() == -1 && r2.getNextRdIdx() == -1){
								StringBuffer s = new StringBuffer();
								s.append(j).append(" ").append(i).append("\n");
								//System.out.println(s.toString());
								f.writeBytes(s.toString());
								r2.setNextRdIdx(i);
								r1.setPrevRdIdx(j);
							}
						}
						if (p1.equals(p10)){
							if (r1.getNextRdIdx() == -1 && r2.getPrevRdIdx() == -1){
								StringBuffer s = new StringBuffer();
								s.append(i).append(" ").append(j).append("\n");
								//System.out.println(s.toString());
								f.writeBytes(s.toString());
								r2.setPrevRdIdx(i);
								r1.setNextRdIdx(j);
							}
						}
						if (p0.equals(p10)){
						}
						if (p1.equals(p11)){
						}
					}
				}
			
			}
			f.close();

		}catch(IOException e){
			System.out.println("Error writing adjacency file!");
			System.exit(0);
		}

	}
	
	/** 
	 * add crosses for each road by traversing the sorted PeanoKey vector and 
	 * detecting equal values corresponding to points on different roads
	 **/ 
	public void addCrossroads(){
		int cno=0;
		for (int i = 0; i < peanoKeys.size(); i++){
			PeanoKey pk1 = (PeanoKey)peanoKeys.get(i);
			Road r1 = (Road)roads.get(pk1.getRoadIndex());
			int j = i+1;
			while (j<peanoKeys.size()){ 
				PeanoKey pk2 = (PeanoKey)peanoKeys.get(j);
				if (pk1.compareTo(pk2) == 0){//they have the same value
					cno ++;
					Road r2 = (Road)roads.get(pk2.getRoadIndex());
					r1.crosses.add(new Cross(pk1.getRoadIndex(), pk1.getPointIndex(), pk2.getRoadIndex(), pk2.getPointIndex()));
					r2.crosses.add(new Cross(pk2.getRoadIndex(), pk2.getPointIndex(), pk1.getRoadIndex(), pk1.getPointIndex()));
				}
				else 
					break;
				j++;	
			}
		}
		logger.info("Done building the map " + cno + " crosses");
	}
	
	public PeanoKey findClosestPeanoKey(Point gpsPoint){
		//given a gps point with latitude end longitude, the function tries to find
		//the closest point on a road on the map, by using the PeanoKey mechanism
			PeanoKey searchpk = new PeanoKey(gpsPoint);
			
			
			int idx = Collections.binarySearch(peanoKeys, searchpk);
			if (idx >= 0)
				return ((PeanoKey)peanoKeys.get(idx));
			int insertIdx = -(idx + 1);
//			System.out.println("Key " + new String(searchpk.getValue())+ " - insert at " + insertIdx);
			
			double mindist = Globals.CLOSEST_PEANOKEY_MAXDIST;
			int pkIdx = -1;
			int j = 1;
			while (j <= Globals.PEANOKEY_SEARCH_RANGE && insertIdx - j >= 0){
				PeanoKey pk = (PeanoKey)peanoKeys.get(insertIdx-j);
				Point p = (Point)((Road)roads.get(pk.getRoadIndex())).points.get(pk.getPointIndex());
				double dist = gpsPoint.distanceTo(p);
//				System.out.println("\t"+new String(pk.getValue())+" "+((Road)roads.get(pk.getRoadIndex())).getName().trim() + " - " +
//						((Road)roads.get(pk.getRoadIndex())).getId() + " - point " + 
//						pk.getPointIndex() + " / " + ((Road)roads.get(pk.getRoadIndex())).points.size()
//						+ " distance: " + dist);
				if (dist < mindist) {
					mindist = dist;
					pkIdx = insertIdx-j;
				}
				j++;
			}
			
			j = 0;
			while (j < Globals.PEANOKEY_SEARCH_RANGE && insertIdx + j < peanoKeys.size()){
				PeanoKey pk = (PeanoKey)peanoKeys.get(insertIdx+j);
				Point p = (Point)((Road)roads.get(pk.getRoadIndex())).points.get(pk.getPointIndex());
				double dist = gpsPoint.distanceTo(p);
//				System.out.println("\t"+new String(pk.getValue())+" "+((Road)roads.get(pk.getRoadIndex())).getName().trim() + " - " +
//						((Road)roads.get(pk.getRoadIndex())).getId() + " - point " + 
//						pk.getPointIndex() + " / " + ((Road)roads.get(pk.getRoadIndex())).points.size()
//						+ " distance: " + dist);
				if (dist < mindist){
					mindist = dist;
					pkIdx = insertIdx+j;
				}
				j++;
			}
			if (pkIdx == -1)
				return null;
			return (PeanoKey)peanoKeys.get(pkIdx);
	}

	/**
	 * After loading the crossroad this method is called in order to add all auxiliary intersections.
	 */
	public void addIntersections() {
		for(int i=0;i<roads.size();i++) {
			Collections.sort(roads.get(i).crosses, new Comparator<Cross>() {
				public int compare(Cross c1, Cross c2) {
					if(c1.pointIndex<c2.pointIndex)
						return -1;
					if(c1.pointIndex>c2.pointIndex)
						return 1;
					if(c1.pointIndex==c2.pointIndex) {
						//compare crossRoadIndices
						if(c1.crossRoadIndex<c2.crossRoadIndex) {
							return -1;
						} else
							return 1;
					}
					return 0;
				}
 			});
		}
		
		//init indices with -1
//		for(int i=0;i<roads.size();i++) {
//			for(int j=0;j<Globals.map.roads.get(i).crosses.size();j++) {
//				Globals.map.roads.get(i).crosses.get(j).intersectionIndex=-1;
//			}
//		}

		for(int i=0;i<roads.size();i++) {
			Road r=roads.get(i);
			for(int j=0;j<r.crosses.size();j++) {
				Cross c=r.crosses.get(j);
				if(c.intersectionIndex==-1) {
					//try to find all concurrent roads (in this intersection)
					//create a new Intersection object
					c.intersectionIndex=allIntersections.size();
					IntersectionWithoutTrafficLights inters=new IntersectionWithoutTrafficLights();
					if(c.pointIndex>0) 
						inters.addCrossingSegment(new DirectedRoadSegment(i, c.pointIndex, false));
					if(c.pointIndex<r.points.size()-1)
						inters.addCrossingSegment(new DirectedRoadSegment(i, c.pointIndex, true));
										
					Road otherRoad=roads.get(c.crossRoadIndex);
					
					for(int k=0;k<otherRoad.crosses.size();k++) {
						Cross otherCross=otherRoad.crosses.get(k);
						if(otherCross.crossRoadIndex==i && otherCross.crossPointIndex==c.pointIndex) {
							//that's the one
							otherCross.intersectionIndex=allIntersections.size();
							break;
						}
					}
					if(c.crossPointIndex>0)
						inters.addCrossingSegment(new DirectedRoadSegment(c.crossRoadIndex, c.crossPointIndex, false));
					if(c.crossPointIndex<otherRoad.points.size()-1)
						inters.addCrossingSegment(new DirectedRoadSegment(c.crossRoadIndex, c.crossPointIndex, true));

					//also check if there are other crosses in the same point
					while(j+1 < r.crosses.size()) {
						Cross c2=r.crosses.get(j+1);
						if(c2.pointIndex==c.pointIndex) {
							//also add these segments
							c2.intersectionIndex=allIntersections.size();
							if(c2.pointIndex>0) 
								inters.addCrossingSegment(new DirectedRoadSegment(i, c2.pointIndex, false));
							if(c2.pointIndex<r.points.size()-1)
								inters.addCrossingSegment(new DirectedRoadSegment(i, c2.pointIndex, true));
							
							Road otherRoad2=roads.get(c2.crossRoadIndex);
							
							for(int k=0;k<otherRoad2.crosses.size();k++) {
								Cross otherCross2=otherRoad2.crosses.get(k);
								if(otherCross2.crossRoadIndex==i && otherCross2.crossPointIndex==c2.pointIndex) {
									//that's the one
									otherCross2.intersectionIndex=allIntersections.size();
									break;
								}
							}
							if(c2.crossPointIndex>0)
								inters.addCrossingSegment(new DirectedRoadSegment(c2.crossRoadIndex, c2.crossPointIndex, false));
							if(c2.crossPointIndex<otherRoad2.points.size()-1)
								inters.addCrossingSegment(new DirectedRoadSegment(c2.crossRoadIndex, c2.crossPointIndex, true));
							j++;
						} else
							break;
					}
					//finally add the object
					allIntersections.add(inters);
					System.out.println("### Intersection no " + Globals.map.allIntersections.size()
							+ " " + Globals.map.allIntersections.toString());
				} else {
					while(j+1 < r.crosses.size()) {
						Cross c2=r.crosses.get(j+1);
						if(c2.pointIndex==c.pointIndex) {
							c2.intersectionIndex=c.intersectionIndex;
							j++;
						} else 
							break;
					}
				}
			}
		}
		
	}

	public void checkIntersections() {
		try {
			for(int i=0;i<Globals.map.roads.size();i++) {
				Road r=Globals.map.roads.get(i);
				for(int j=0;j<r.crosses.size();j++) {
					Cross c=r.crosses.get(j);
					Road crossRoad=Globals.map.roads.get(c.crossRoadIndex);
					for(int k=0;k<crossRoad.crosses.size();k++) {
						Cross otherCross=crossRoad.crosses.get(k);
						if(otherCross.pointIndex==c.crossPointIndex) {
							//that's the one;
							if(c.intersectionIndex!=otherCross.intersectionIndex) {
								logger.severe("ERROR! INTERSECTIONS WRONG!!! ");
								logger.severe("Road:"+i+";Pt="+c.pointIndex+"; INDEX="+c.intersectionIndex);
								logger.severe("Road:"+c.crossRoadIndex+";Pt="+otherCross.pointIndex+"; INDEX="+otherCross.intersectionIndex);
							}
							break;
						}
					}
				}
			}
		} catch (Exception ex) {
			logger.severe("ERROR! INTERSECTIONS WRONG!!! : "+ex.toString());
			ex.printStackTrace();
			return;
		}
		logger.info("ALL INTERSECTIONS="+allIntersections.size());
	}

	
	/* Szekeres A. START_MODIFY */
	/* Change from WirelessTrafficLights to EmissionsTrafficLights*/
	public void changeToEmissionsTrafficLights()
	{
		for(int i=0;i<allIntersections.size();i++) {
			if (allIntersections.get(i) instanceof WirelessTrafficLight)
			{
				WirelessTrafficLight in = (WirelessTrafficLight)allIntersections.get(i);
				allIntersections.set(i, 
						new EmissionsTrafficLight(in));
			}
		}
	}
	/* Szekeres A. STOP_MODIFY*/
	
	public void createTrafficLights(Random generator) {
		//ArrayList<IntersectionWithoutTrafficLights> without=new ArrayList<IntersectionWithoutTrafficLights> ();
		for(int i=0;i<allIntersections.size();i++) {
			if(allIntersections.get(i).segments.size()<=2) {
				continue;
			}
//			if(generator.nextBoolean()) {
			
			//if(true && roads.size() > 5 && !roads.get(5).getName().startsWith("New Jersey")) {
			// changed the if condition for cityPlan scenario to work
			if(roads.size()>1) {
				//change it into a traffic lights intersection
				WirelessTrafficLight newInters=new WirelessTrafficLight();
//				IntersectionWithTrafficLights newInters=new IntersectionWithTrafficLights();
				IntersectionWithoutTrafficLights oldInters=(IntersectionWithoutTrafficLights) allIntersections.get(i);
				for(int j=0;j<oldInters.segments.size();j++) {
					newInters.addCrossingSegment(oldInters.segments.get(j));
				}
				for(int j=0;j<oldInters.segments.size();j++) {
					DirectedRoadSegment seg1 = (DirectedRoadSegment)oldInters.segments.get(j);
					for (int k = 0; k < oldInters.segments.size(); k++){
						DirectedRoadSegment seg2 = (DirectedRoadSegment)oldInters.segments.get(k);
						if (k!= j){
							double angle = seg1.angle - seg2.angle;
							if (angle < 0)
								angle = 360 + angle;
							if (angle < 190 && angle > 170)
								seg1.front = seg2;
							if (angle >= 190)
								seg1.right = seg2;
							if (angle <= 170)
								seg1.left = seg2;
						}
					}
				}
//				newInters.lightInfos=new ArrayList<TrafficLightInfo> ();
				//green duration for priority roads
	//			int green=(int)(20.0+30.0*generator.nextDouble());
				int green=37;
				if (!roads.get(0).getName().startsWith("Iuliu")){
					//!apaca
					green = 30;
				}
				int time=0;
				int j = 2;
				if (roads.get(0).getName().startsWith("Dr ") && i == 1){
					green = 30;
				}
				newInters.segments.get(0).setLightInfo(new TrafficLightInfo(0, green));
				if (roads.get(0).getName().startsWith("Dr ") && i == 1){
					green = 45;
				}
				newInters.segments.get(1).setLightInfo(new TrafficLightInfo(0, green));
				time=time + green + Globals.DEFAULT_YELLOW_TIME + Globals.DEFAULT_ALL_RED;
				
				if (roads.get(0).getName().startsWith("Iuliu") && i == 1){
					newInters.segments.get(2).setLightInfo(new TrafficLightInfo(time, time + green));
					time=time + green + Globals.DEFAULT_YELLOW_TIME + Globals.DEFAULT_ALL_RED;
					newInters.segments.get(3).setLightInfo(new TrafficLightInfo(time, time + green));
					time=time + green + Globals.DEFAULT_YELLOW_TIME + Globals.DEFAULT_ALL_RED;
					j = 4;
				}				
				for(;j<oldInters.segments.size();j++) {
					if(oldInters.segments.get(j).isExitOnly()) {
						newInters.segments.get(j).setLightInfo(new TrafficLightInfo(time, time));
						if (j % 2 == 1){
							if (!oldInters.segments.get(j-1).isExitOnly());
								time=time+green+Globals.DEFAULT_YELLOW_TIME + Globals.DEFAULT_ALL_RED;
						}
						continue;
					}
//					green=(int)(10.0+10.0*generator.nextDouble());
					green = 30;
					newInters.segments.get(j).setLightInfo(new TrafficLightInfo(time, time+green));
					if (j % 2 == 0) 
						time=time+green+Globals.DEFAULT_YELLOW_TIME + Globals.DEFAULT_ALL_RED;
				}
				newInters.cycleLength=time;
				allIntersections.set(i, newInters);
				lightsIndices.add(new Integer(i));
			} 
		}
	}

	private void setLaneNoRandom(Random generator) {
		for(int i=0;i<roads.size();i++) {
			Road r=roads.get(i);
			double d;
			switch(r.roadinfo[1]) {
				case 49:
					d=generator.nextDouble();
					if(d<0.33) 
						r.laneNo=5;
					else if(d<0.66)
						r.laneNo=4;
					else r.laneNo=3;
					break;
				case 50:
					d=generator.nextDouble();
					if(d<0.33) 
						r.laneNo=4;
					else if(d<0.66)
						r.laneNo=3;
					else r.laneNo=2;
					break;
				case 51:
					d=generator.nextDouble();
					if(d<0.50) 
						r.laneNo=3;
					else r.laneNo=2;
					break;
				case 52:
					d=generator.nextDouble();
					if(d<0.33) 
						r.laneNo=2;
					else r.laneNo=1;
					break;
				default:
			}
		}
	}

	/**
	 * Sets the lower and lowest points on the map, given the earth coordinates.
	 */
	public void getMinAndMaxPoint() {
		// sets the Globals.minPoint and Globals.maxPoint
		// with the determined values
		Map currentMap;
		Point tmpPoint, minPoint, maxPoint;
		Road tmpRoad;
		int i, j;
		i = 0;
		currentMap = Globals.map;

		minPoint = new Point((double) 180, (double) 90);
		maxPoint = new Point((double) -180, (double) -90);
		while (i < currentMap.roads.size()) {
			tmpRoad = (Road) currentMap.roads.get(i);
			j = 0;
			while (j < tmpRoad.points.size()) {
				tmpPoint = (Point) tmpRoad.points.get(j);
				if (tmpPoint.getLatitude() < minPoint.getLatitude()) {
					minPoint.setLatitude(tmpPoint.getLatitude());
				}
				if (tmpPoint.getLongitude() < minPoint.getLongitude()) {
					minPoint.setLongitude(tmpPoint.getLongitude());
				}

				if (tmpPoint.getLatitude() > maxPoint.getLatitude()) {
					maxPoint.setLatitude(tmpPoint.getLatitude());
				}
				if (tmpPoint.getLongitude() > maxPoint.getLongitude()) {
					maxPoint.setLongitude(tmpPoint.getLongitude());
				}

				j++;
			}
			i++;
		}
		this.minPoint = minPoint;
		this.maxPoint = maxPoint;
	}
	
	public void setLaneNoExtra() {
//Intersection
		if (roads.get(0).getName().startsWith("Calculatoare")){
			roads.get(0).laneNo=3;
			roads.get(1).laneNo=2;
		}
		
		if (roads.get(0).getName().startsWith("Iuliu")){
//				Apaca
			roads.get(0).laneNo=3;
			roads.get(1).laneNo=4;
			roads.get(2).laneNo=3;
		}
	}
}