%classpath add mvn tech.tablesaw tablesaw-core 0.10.0
%import tech.tablesaw.api.Table

// Basic setups
fileName = "../resources/data/UScity.csv";
startCity = "Brooklyn";
endCity = "Carson City";

// show data in table
table = Table.read().csv(fileName);

// simple ploting by city coordinates
import com.twosigma.beakerx.fileloader.CSV;

def cities = new CSV().read(fileName)
map = new Plot(title: "US City Map", yLabel: "Latitude", xLabel: "Longitude");
map << new Rasters(x: [-132], y: [56], width: [66], height: [32], opacity:[0.8], filePath: "../resources/img/USmapbg.png");
map << new Points(y: cities.latitude, x: cities.longitude);
map

// calculate shortest path

import com.twosigma.beakerx.fileloader.CSV;

class ShortestPathAlgoritm {
    def graph, start, destination    
    def unsettledNodes = new PriorityQueue<String>(500, new Comparator<String>() {
       public int compare(String node1, String node2) {
            shortestDistance(node1).compareTo(shortestDistance(node2))
        }
    });
    def shortestDistances = [:]
    def predecessors = [:]
    def settledNodes = [] as Set

    ShortestPathAlgoritm(graph, start, destination) {
        this.graph = graph
        this.start = start
        this.destination = destination

        unsettledNodes.add(start)
        shortestDistances[(start)] = 0
    }

    double shortestDistance(node) {
        shortestDistances.containsKey(node) ? shortestDistances[node] : Integer.MAX_VALUE
    }

    def extractMin() {
        unsettledNodes.poll()
    }

    def unsettledNeighbours(node) {
        graph.findAll { edge ->
            edge.node1 == node && !settledNodes.contains(edge.node2)
        }
    }

    def relaxNeighbours(node) {
        unsettledNeighbours(node).each { edge ->
            if (shortestDistance(edge.node2) > shortestDistance(edge.node1) + edge.distance) {
                shortestDistances[edge.node2] = shortestDistance(edge.node1) + edge.distance
                predecessors[edge.node2] = edge.node1
                if (!unsettledNodes.contains(edge.node2)) {
                    unsettledNodes.add(edge.node2)
                }
            }
        }
    }

    def calculateShortestPath() {
        while (!unsettledNodes.isEmpty()) {
            String node = extractMin()
            if (node == destination) {
                break
            }
            settledNodes += node
            relaxNeighbours(node)
        }
        shortestDistances[destination]
    }

    def getShortestPath(node, path) {
        node == start ? [node]+path : getShortestPath(predecessors[node], [node]+path)
    }
    
    def getShortestPath() {
        getShortestPath(destination, []) 
    }
}

class Edge {
    String node1, node2
    double distance
}

double getDistance(double x1,double y1, double x2, double y2){
    return Math.sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1))
}

cities = new CSV().read(fileName)
n = cities.size;
def graph = new Edge[n * n];
def graphidx = 0;

// build a graph
for (int i = 0; i < n; i++){
    for (int j = 0; j < n; j++){
        def dist = getDistance(cities.longitude[i], cities.latitude[i], cities.longitude[j], cities.latitude[j]);
        if (dist > 7){
            dist = Integer.MAX_VALUE 
            // view as unreachable because they are too far away from each other
            // there should be shorter ways in between
        }
        graph[graphidx++] = new Edge(node1: cities.city[i], node2: cities.city[j], distance: dist);
    }
}

// calculate shortest path
dijkstra = new ShortestPathAlgoritm(graph, startCity, endCity)
dist = dijkstra.calculateShortestPath();
dijkstra.shortestPath

// plot path on the graph
import com.twosigma.beakerx.fileloader.CSV;

newmap = new Plot(title: "Shortest Path", yLabel: "Latitude", xLabel: "Longitude");
// all cities
newmap << new Points(y: cities.latitude, x: cities.longitude);

def ps = dijkstra.shortestPath.size();
def pathy = new double[ps];
def pathx = new double[ps];
def pathc = new String[ps];
for (int i = 0; i < ps; i++){
    for (int j = 0 ; j < n; j++){
        if (cities.city[j] == dijkstra.shortestPath[i]){
            pathx[i] = cities.longitude[j];
            pathy[i] = cities.latitude[j];
            pathc[i] = cities.city[j];
        }
    }
}
newmap << new Rasters(x: [-132], y: [56], width: [66], height: [32], opacity:[0.8], filePath: "../resources/img/USmapbg.png");

// start and end points
newmap << new Points(y: [pathy[0]], x:[pathx[0]], shape: ShapeType.CIRCLE, color: Color.orange, outlineColor: Color.red)
newmap << new Points(y: [pathy[ps - 1]], x:[pathx[ps - 1]], shape: ShapeType.DIAMOND, color: Color.green, outlineColor: Color.red)
for (int i = 0; i < ps; i ++){
  newmap << new Text(y: pathy[i], x:pathx[i], text: pathc[i],  pointerAngle: -i/1.5)
}

// path
newmap << new Line(y: pathy, x:pathx); 
newmap

// final visualization of everything 

import com.twosigma.beakerx.jvm.object.TabbedOutputContainerLayoutManager;
import com.twosigma.beakerx.jvm.object.OutputContainer;

def layout = new TabbedOutputContainerLayoutManager()
layout.setBorderDisplayed(false)
def o = new OutputContainer()
o.setLayoutManager(layout)
o.addItem(table, "City info")
o.addItem(map, "US City Map")
o.addItem(newmap, "Shortest Path")
o.addItem(dijkstra.shortestPath, "Path Detail")
o