import re

def loadMiles():
     f = open('/mnt/nfs/netapp1/fs3/sriram/python/miles.dat', 'r')
     return readGraph(f, 500)

# Reads from a file, specified by the argument "fileref," formatted as miles.dat and 
# builds a graph from this data. 
# The graph that is built has the following structure:
#  { cityName: [stateName, latitude, longitude, population, {neighbor1: distance1, neighbor2: distance2, ...},
#    cityName: [stateName, latitude, longitude, population, {neighbor1: distance1, neighbor2: distance2, ...},
#    ...
#    ...}
# The second argumemt t specifies a threshold; only edges of length t or less are kept.
def readGraph(fileref, t):
    cities = []
    graph = {}

    neighborIdx = 0
    currentCity = None
    for line in fileref.readlines():
        if re.match('\*', line):    # comment (ignore it)
            pass
        elif re.match('[a-zA-Z]', line):    # line defining a city
            # fill this in later
            data = re.split('[\[,\]]', line)
            data[1] = data[1].lstrip()                 # state abbrev
            data[2] = int(data[2]) / 100.0         # longitude
            data[3] = int(data[3]) / 100.0         # latitude
            data[4] = int(data[4])                         # population

            currentCity = data[0] + ', ' + data[1]

            cities.append(currentCity)
            neighborIdx = len(cities) -2

            graph[currentCity] = data[:5]
            graph[currentCity].append({})

        else:
            dists = line.split()
            for dist in dists:
                dist = int(dist)

                if(dist <= t):
                    neighborCity = cities[neighborIdx]
                    graph[currentCity][5][neighborCity] = dist
                    graph[neighborCity][5][currentCity] = dist

                neighborIdx -= 1

    return graph


def getMinDistanceVertex(distances, finalized):
  minDistance = 2**20 #Initialize minDistance to a large number

  # Scan distance-values of not yet finalized vertices
  for v in distances.keys():
    if((not finalized[v]) and (distances[v] < minDistance)):
      minDistance = distances[v]
      minVertex = v

  return minVertex

# Returns the smaller of two comparable quantities
def min(x, y):
  if(x <= y):
    return x
  else:
    return y


# Takes a graph and a source vertex and computes distances of all 
# vertices from the source. Uses Dijkstra's shortest path algorithm to do this.
# The function returns a size-2 list with the first item in the list being a list
# of shortest path distances from source to all vertices and the second item is a
# representation of the shortest path tree in which each vertex points to its
# predecessor in the shortest path.
def DijkstraShortestPath(g, source):
  n = len(g)

  # Initializes the distances of all vertices from the source to n.
  # Note that n is larger than the largest valid distance.
  # Also initializes the shortest path tree
  distances = {}
  tree = {}
  for v in g.keys():
    distances[v] = 2**20
    tree[v] = v

  distances[source] = 0

  # Initializing the array the indicates whether a vertex's distance-value has been finalized
  finalized = {}
  numFinalized = 0
  for v in g.keys():
    finalized[v] = 0

  # Repeatedly process the vertex at the front of the queue
  while(numFinalized < n):
    u = getMinDistanceVertex(distances, finalized)
    #printNow(u)
    finalized[u] = 1
    numFinalized = numFinalized + 1
    #printNow(numFinalized)
    nbrs = getNeighbors(g, u)
    #printNow(nbrs)

    # Scan all neighbors of u
    # If a neighbor v has already been finalized, ignore it.
    # Otherwise, check if the distance to that be
    for v in nbrs.keys():
      if(not finalized[v]):
        if(distances[u] + getEdgeWeight(g, u, v) < distances[v]):
          distances[v] = distances[u] + getEdgeWeight(g, u, v)
          tree[v] = u

  return [distances, tree]

def shortestPath(g, source, dest):
    [lengths, tree] = DijkstraShortestPath(g, source)

    path = [dest]
    cur = dest
    while(cur != tree[cur]):
        cur = tree[cur]
        path.append(cur)

    path.reverse()
    return path


def getNeighbors(graph, v):
    return graph[v][5]

def isEdge(graph, u, v):
    return (u in graph[v][5])

def getEdgeWeight(graph, u, v):
    return graph[u][5][v]

def writePathKML(g, path, filename):
    outfile = open(filename, "wt")
    outfile.write('<?xml version="1.0" encoding="UTF-8"?>\n')
    outfile.write('<kml xmlns="http://www.opengis.net/kml/2.2">\n')
    outfile.write('<Document>')
    outfile.write('<Style id="smallLine">\n')
    outfile.write('<LineStyle>\n')
    outfile.write('<color>7f00007f</color>\n')
    outfile.write('<width>1</width>\n')
    outfile.write('</LineStyle>\n')
    outfile.write('<PolyStyle>\n')
    outfile.write('<color>7f00007f</color>\n')
    outfile.write('</PolyStyle>\n')
    outfile.write('</Style>\n')
    src = path[0]
    dst = path[-1]

    # Write info. corresponding to each vertex in the graph
    for city in path:
        outfile.write('<Placemark>\n')
        outfile.write('<name>' + city + '</name>\n')
        outfile.write('<description>' + city + '</description>\n')
        outfile.write('<Point>\n')
        outfile.write('<coordinates>' + str(-1*g[city][3]) + ', ' + str(g[city][2]) + ', ' + '0</coordinates>\n')
        outfile.write('</Point>\n')
        outfile.write('</Placemark>\n')

    # Ready to plot the path line
    outfile.write('<Placemark>\n')
    outfile.write('<name>' + src + ' - ' + dst + '</name>\n')
    outfile.write('<description>')
    outfile.write('Path from ' + src + ' to ' + dst)
    outfile.write('</description>\n')
    outfile.write('<styleUrl>#smallLine</styleUrl>\n')
    outfile.write('<LineString>\n')
    outfile.write('<extrude>1</extrude>\n')
    outfile.write('<tessellate>1</tessellate>\n')
    outfile.write('<altitudeMode>absolute</altitudeMode>\n')
    outfile.write('<coordinates>')
    for city in path:
        outfile.write(str(-1*g[city][3]) + ', ' + str(g[city][2]) + ', ' + '0 ')
    outfile.write('</coordinates>\n')
    outfile.write('</LineString>\n')
    outfile.write('</Placemark>\n')
    outfile.write('</Document>')
    outfile.write('</kml>')
    outfile.close()

# Takes a graph whose vertices have associated longitude, latitude info. and
# write this into a given kml file
def writeVerticesKML(g, filename):
    outfile = open(filename, "wt")
    outfile.write('<?xml version="1.0" encoding="UTF-8"?>\n')
    outfile.write('<kml xmlns="http://www.opengis.net/kml/2.2">\n')
    outfile.write('<Document>')
    outfile.write('<Style id="smallLine">\n')
    outfile.write('<LineStyle>\n')
    outfile.write('<color>7f00ffff</color>\n')
    outfile.write('<width>1</width>\n')
    outfile.write('</LineStyle>\n')
    outfile.write('<PolyStyle>\n')
    outfile.write('<color>7f00ff00</color>\n')
    outfile.write('</PolyStyle>\n')
    outfile.write('</Style>\n')
    cities = g.keys()
    # Write info. corresponding to each vertex in the graph
    for i in range(len(cities)):
        src = cities[i]
        outfile.write('<Placemark>\n')
        outfile.write('<name>' + src + '</name>\n')
        outfile.write('<description>' + src + '</description>\n')
        outfile.write('<Point>\n')
        outfile.write('<coordinates>' + str(-1*g[src][3]) + ', ' + str(g[src][2]) + ', ' + '0</coordinates>\n')
        outfile.write('</Point>\n')
        outfile.write('</Placemark>\n')

    outfile.write('</Document>')
    outfile.write('</kml>')
    outfile.close()