#! /usr/bin/env python
# A validator for results

from math import sqrt

# Class for one map node
class Node_t:
    # Init:
    # Arguments: node coordinates
    def __init__(self, x, y):
        self.x = x
        self.y = y
        # A set of nodes to which this node is connected
        self.edges=set([])

    # Creates an edge between nodes A and B
    def connect(A,B):
        if A not in B.edges:
            B.edges = B.edges | set([A])
        if B not in A.edges:
            A.edges = A.edges | set([B])

    # Is this node connected to the target?
    def connected_to(self, targ):
        return (targ in self.edges)

    # Distance between two nodes
    def distance(A,B):
        return sqrt( pow(A.x - B.x,2) +
                     pow(A.y - B.y,2) )

class Map_t:
    # File is a file stream to load a map from
    def __init__(self, File=None):
        # A dictionary of Node_t's, keyed by index
        self.Nodes={}

        if File:
            self.load_from(File)
            
    def load_from(self,File):
        # FIXME: This is very fragile
        firstline=File.readline().split()
        num_nodes = int(firstline[0])
        num_edges = int(firstline[1])
        for i in range(num_nodes):
            nodeline=File.readline().split()
            index=int(nodeline[0])
            self.Nodes[index]=Node_t(
                int(nodeline[1]),
                int(nodeline[2])
                )
        for i in range(num_edges):
            edgeline=File.readline().split()
            a=int(edgeline[0])
            b=int(edgeline[1])
            Node_t.connect(self.Nodes[a], self.Nodes[b])

# Takes (one) output of the proj3 thingy and returns a dictionary
# (an output is two lines)
# Dictionary has the following keys: 'start','end', 'distance', 'path'
# 'start' and 'end' are indices
# 'distance' is the distance measured along the path (according to the logfile)
# 'path' is a list of indices along the way
# Returns "none" if there isn't anything left to read
def create_path_from(File):
    firstline=File.readline().split()
    secondline=File.readline().split()
    if not firstline or not secondline:
        return None

    ret={}
    # The start node is the 6th word in the first line
    ret['start'] = int(firstline[5])
    # The end node is the 9th word in the first line
    ret['end'] = int(firstline[8])
    # The distance is the 11th word in the first line (strip the period)
    ret['distance'] = int(firstline[10].strip('.'))

    # Discard the first 10 words of the second line
    secondline=secondline[10:]

    # Start iterating through the line; every other word (starting with the
    # first) is assumed to be a node index
    ret['path']=[]
    for i in range(0,len(secondline),2):
        ret['path'].append(int(secondline[i]))

    return ret

# Make sure a path is valid across the map m
def validate_path(m, path):
    route=path['path']
    # Make sure the start and end nodes match with the path
    if ( (path['start'] != route[0]) or
         (path['end'] != route[-1]) ):
        print 'Route does not match start/end'
        print path
        return False

    # Make sure the start node is present in the map
    if not path['start'] in m.Nodes:
        print 'Start node',path['start'],'does not exist in map'
        print path
        return False

    # Iterate along the path, making sure that each node is in the map and
    # that it connects to the next
    distance=0
    prevnodeID=route[0]
    for curnodeID in route[1:]:
        # Node in map?
        if not curnodeID in m.Nodes:
            print 'Failed to find',curnodeID, 'in map'
            print path
            return False
        # Previous node has a connection to this?
        if not m.Nodes[curnodeID] in m.Nodes[prevnodeID].edges:
            print 'Failed to connect',prevnodeID,'to',curnodeID
            print path
            return False
        # Tally up the distance
        distance = distance + int(Node_t.distance( m.Nodes[curnodeID],
                                                   m.Nodes[prevnodeID] ))
        # Update prevnode
        prevnodeID=curnodeID

    # Does the distance match?
    if distance != path['distance']:
        print 'Failed validate on distance'
        print 'Calculated', distance, ' read ', path['distance']
        print path
        return False

    # Wow! It's right! Hurray!
    return True

import sys

# TODO: Make the argument checking more bulletproof??
if len(sys.argv) != 3:
    sys.stderr.write('USAGE: %s map_file results_file\n' % sys.argv[0])
    sys.exit(2)

mapfile = file(sys.argv[1],'r')
resultsfile = file(sys.argv[2],'r')

#print 'Validator: loading map'
the_map = Map_t(mapfile)

# Load and check each query
nextres=create_path_from(resultsfile)
cur=1
while nextres:
    #print nextres
    #print 'Validtor:checking query ',cur
    if not validate_path(the_map, nextres):
        sys.exit(1)
    nextres=create_path_from(resultsfile)
    cur += 1

sys.exit(0)