package tsp.shortestpath;

import java.util.ArrayList;
import java.util.Collections;

public class Location {
	private String     name;
	private double     latitude;
	private double     longitude;
	private Location[] neighbors;
	private Location   from;
	private double     distance;
	private int positionHeap;

	private boolean visited = false;
	
	public Location(String name, double latitude, double longitude) {
		this.name = name;
		this.latitude = (Math.PI * latitude) / 180;
		this.longitude = (Math.PI * longitude) /180;
		this.distance = Double.POSITIVE_INFINITY;
		this.positionHeap = -1;
	}
	
	public double distanceTo(Location to) {	
		return 6378 * (Math.PI/2 - Math.asin( 
				Math.sin(to.latitude) * Math.sin(latitude) + 
				Math.cos(to.longitude - longitude) * Math.cos(to.latitude) * Math.cos(latitude)));
	}
	
	public void setNeighbors(Location... neighbors) {
		this.neighbors = neighbors;
	}
	
	public double getDistance() {
		return distance;
	}
	
	public void reinit() {
		if(distance != Double.POSITIVE_INFINITY) {
			distance = Double.POSITIVE_INFINITY;

			for(int i=0; i<neighbors.length; i++)
				neighbors[i].reinit();
		}
	}
	
	private void proceedNode(LocationSet set) {
		for(int i=0; i<neighbors.length; i++) {
			Location n = neighbors[i];
			
			if(n.distance == Double.POSITIVE_INFINITY) {
				set.add(n);
			}
			
			double next = distance + distanceTo(n);
			
			if(next < n.distance) {
				n.distance = next;
				n.from = this;
			}
		}
	}
	
	public void findPathTo(Location to) {
		LocationSet set = new LocationSet();
		Location cur = this;
		
		distance = 0;
		while(cur != null && cur != to) {
			cur.proceedNode(set);
			cur = set.removeMin();
		}
		
		if(cur == null)
			System.out.println("Unable to find a path from " + name + " to " + to.name);
		else {
			System.out.println("Your trip from " + name + " to " + to.name + " in reverse order");
			for(cur=to; cur!=this; cur=cur.from) {
				System.out.println("  " + cur.name + " at " + cur.distance);
			}
		}
		
		reinit();
	}
	
	public void display() {
		System.out.println(name + " at (" + latitude + ", " + longitude + ")");
	}

	public void setDistance(double distance){
		this.distance = distance;
	}

	public int getPositionHeap(){
		return this.positionHeap;
	}

	public void setPositionHeap(int positionHeap){
		this.positionHeap = positionHeap;
	}

	public void findPathToBinaryHeap(Location to) {
		BinaryHeap binaryHeap = new BinaryHeap();
		Location cur = this;

		distance = 0;
		while(cur != null && cur != to) {
			cur.proceedNodeBinaryHeap(binaryHeap);
			cur = binaryHeap.removeMin();
		}

		if(cur == null)
			System.out.println("Unable to find a path from " + name + " to " + to.name);
		else {
			System.out.println("Your trip from " + name + " to " + to.name + " in reverse order");
			for(cur=to; cur!=this; cur=cur.from) {
				System.out.println("  " + cur.name + " at " + cur.distance);
			}
		}

		reinit();
	}

		private void proceedNodeBinaryHeap(BinaryHeap binaryHeap) {
		for(int i=0; i<neighbors.length; i++) {
			Location n = neighbors[i];

			if(n.distance == Double.POSITIVE_INFINITY) {
				binaryHeap.add(n);
			}

			double next = distance + distanceTo(n);

			if(next < n.distance) {
				n.distance = next;
				n.from = this;
				binaryHeap.updateDown(n);
			}
		}
	}

	// CI6

	@Override
	public String toString() {
		return "Location{" +
				"name='" + name + '\'' +
				", latitude=" + latitude +
				", longitude=" + longitude +
				'}';
	}

	private ArrayList<Location> getAllLocationsRec(){
		ArrayList<Location> res = new ArrayList<>();
        if (this.visited){
			return res;
		}
		this.visited = true;
		res.add(this);
		for (int i = 0; i < this.neighbors.length; i++){
			res.addAll(this.neighbors[i].getAllLocationsRec());
		}
		return res;
	}

	public ArrayList<Location> getAllLocations(){
		ArrayList<Location> res = this.getAllLocationsRec();
		// reinitialize the locations
		for (int i = 0; i < res.size(); i++){
			res.get(i).visited = false;
		}
		return res;
	}

	private ArrayList<Edge> getAllEdgesRec(){
		ArrayList<Edge> res = new ArrayList<>();
		if (this.visited){
			return res;
		}
		this.visited = true;
		for (int i = 0; i < this.neighbors.length; i++){
			if (!this.neighbors[i].visited) {
				Edge edge = new Edge(this, this.neighbors[i]);
				res.add(edge);
			}
		}
		for (int i = 0; i < this.neighbors.length; i++){
			if (!this.neighbors[i].visited) {
				res.addAll(this.neighbors[i].getAllEdgesRec());
			}
		}
		return res;
	}

	public ArrayList<Edge> getAllEdges(){
		ArrayList<Edge> res = this.getAllEdgesRec();
		// reinitialize the locations
		for (int i = 0; i < res.size(); i++){
			res.get(i).getFrom().visited = false;
			res.get(i).getTo().visited = false;
		}
		return res;
	}

	public ArrayList<Edge> getCoveringTree(){
		ArrayList<Location> nodes = this.getAllLocations();
		DisjointSets ds = new DisjointSets(nodes);
		ArrayList<Edge> edges = this.getAllEdges();
		Collections.sort(edges);
		ArrayList<Edge> coveringEdges = new ArrayList<>();
		for (int i = 0; i < edges.size(); i++){
			Edge edge = edges.get(i);
            if (!ds.haveSameRepresentatives(edge.getTo(), edge.getFrom())){
				coveringEdges.add(edge);
				ds.union(edge.getTo(), edge.getFrom());
			}
		}
		return coveringEdges;
	}

	public String getDotRepresentation(){
		ArrayList<Edge> edges = this.getAllEdges();
		StringBuilder res = getDotRepresentationFromEdges(edges);
		return res.toString();
	}

	public static StringBuilder getDotRepresentationFromEdges(ArrayList<Edge> edges) {
		StringBuilder res = new StringBuilder("graph{\n");
		for (int i = 0; i < edges.size(); i++){
			Edge edge = edges.get(i);
			res.append(edge.getFrom().name.replace(" ", "_"))
					.append(" -- ")
					.append(edge.getTo().name.replace(" ", "_"))
					.append(" [label=")
					.append(Math.floor(edge.getWeight()))
					.append("];\n");
		}
		res.append("}");
		return res;
	}

}