# -*- coding: iso-8859-1 -*-
#
# Code to handle the RoutePlanner RPL3 database format
# (Designed to be easily parsable in Python and humanly grokable too)
#
# Copyright (C) 1996-2004 Chris Lawrence
# This file may be freely distributed under the terms of the RoutePlanner
# license.  A copy should appear as 'LICENSE' in the archive that this
# file was included in.
#
# db = rpdbase.RPDatabase(filename) - Load a database
# db.Open(filename) - Replace the database by loading another
# db.Save(filename) - Write the database
#
# db.cities - The list of city instances
# db.routes - The list of route instances
#
# $Id: rpdbase.py,v 1.12 2004/10/02 12:36:28 lordsutch Exp $

from __future__ import division

import rpcity, rproute, string, time, os, re, sys, rpunits
from rpunits import UNITS_METRIC, UNITS_US, UNITS_IMPERIAL, UNITS

try:
    import gzip
except ImportError:
    gzip = None

VERID = "##VERSION##"
VERSION = "RoutePlanner ##VERSION##" 
COPYRIGHT = '(C) 1994-2003 Chris Lawrence'

classifications = {
    'XX/Other (speed)' : 0,
    'XX/Other (time in minutes)' : 1,
    'US/Freeway/Rural' : 2,
    'US/Freeway/Suburban' : 3,
    'US/Freeway/Urban' : 4,
    'US/Highway/Rural/4 Lane' : 5,
    'US/Highway/Rural/2 Lane' : 6,
    'US/Highway/Suburban' : 7,
    'US/Road/Suburban' : 8,
    'US/Road/Urban' : 9,
    # US/Rural Freeway (55) - Now handled by speedcode
    'US/Freeway/Urban Metro' : 11,
    'CA/Freeway/Rural' : 12,
    'CA/Freeway/Urban' : 15,
    'CA/Highway/Rural/4 Lane' : 14,
    'CA/Highway/Rural/2 Lane' : 13,
    'CA/Highway/Suburban' : 16,
    'CA/Road/Urban' : 17,
    # "Super 2"s are undivided freeways
    'CA/Super 2/Rural' : 18,
    'US/Super 2/Rural' : 19,
    }

declassify = ['']*(max(classifications.values())+1)
for name, num in classifications.items():
    declassify[num] = name

classify = classifications.keys()
classify.sort()

defspeed = [0, 0, 65, 55, 40, 52, 45, 40, 30, 25, 60, 30, 62, 50, 60,
            50, 35, 30, 55, 55]
defeff = [0, 0, 22, 21, 19, 20, 19, 17, 16, 15, 21, 17, 22, 21, 21,
          18, 17, 17, 21, 21]
defpref = [0, 0, 100, 80, 60, 75, 65, 30, 25, 20, 90, 40, 100, 80, 70,
           50, 40, 30, 80, 80]
defmpg = 18

invalidformat = 'rpdbase.invalidformat'

LEAST_DISTANCE = 0
LEAST_TIME     = 1
PREFERRED      = 2
LEAST_FUEL     = 3

methods = ['Shortest distance', 'Shortest time', 'Preferred', 'Least fuel']

MAXDIST = 2**30

def ConvertToTime(road, cunits, codetable):
    if road.time:
        return road.time
    else:
        try:
            spcode = rpunits.Distance(codetable[road.speedcode], cunits)
        except IndexError:
            spcode = rpunits.Distance(defspeed[road.speedcode], UNITS_US)
            
        speed = rpunits.Distance(spcode, cunits) + \
                rpunits.Distance(road.speed, road.distance.units)
        return 60.0 * (float(road.distance) / float(speed))

def Efficiency(distance, units, speedcode, mpg, defmpg):
    distance = float(distance.AsUnit(units))
    if speedcode >= 2:
        our_mpg = mpg[speedcode]
    else:
        our_mpg = defmpg

    if units == UNITS_METRIC:
        try:
            return our_mpg * distance / 100
        except ZeroDivisionError, text:
            print 'Zero distance on segment: %s' % text
            return 0
    else:
        try:
            return distance / our_mpg
        except ZeroDivisionError, text:
            print 'Warning: MPG is 0 for speedcode %d: %s' % (speedcode, text)
            return 0

def Least_Distance(road, tunits, codetable, prefertable, defaultprefer,
                   flagbonus, mpgtable, defmpg):
    return road.i_distance

def Least_Time(road, tunits, codetable, prefertable, defaultprefer, flagbonus,
               mpgtable, defmpg):
    return ConvertToTime(road, tunits, codetable)

def Least_Fuel(road, tunits, codetable, prefertable, defaultprefer, flagbonus,
               mpgtable, defmpg):
    return Efficiency(road.distance, tunits, road.speedcode, mpgtable, defmpg)

def Preferred(road, tunits, codetable, prefertable, defaultprefer, flagbonus,
              mpgtable, defmpg):
    if road.speedcode >= 2:
        try:
            pref = prefertable[road.speedcode]
        except IndexError:
            pref = defpref[road.speedcode]
    else:
        pref = defaultprefer

    if flagbonus:
        for flag in road.flagmap.keys():
            pref = pref + flagbonus.get(flag, 0)

    if pref < 0: pref = 0
    dist = road.i_distance or road.speed
    return dist * 101.0 / (pref+1.0)

def IsSameRoute(route1, route2):
    if route1 == route2: return True
    #if '/' in route1: return 0
    if '&' in route2: return False
    if not '/' in route2: return False

    # Common case: dissimilar multiplex (i.e. I-70/US 40)
    routes = string.split(route2, '/')
    if route1 in routes: return True

    # Similar multiplex
    match = re.match(r'([A-Za-z]+)([- ])(\d+)$', route1)
    if match:
        #print match.groups()
        type, usedchar, num = match.groups()

        start = end = None
        for i in range(len(routes)):
            if re.match(type+usedchar, routes[i]):
                start = i
            elif start and re.match(r'[^\d]+', routes[i]):
                end = i
                break

        if start is not None:
            if not end:
                end = i

            #print routes[start:end+1], num, num in routes[start:end+1]

            if num in routes[start:end+1]: return True

    # Weird case
    return False

##    # Ok, we're looking for 'BIT-n/n/BIT/n/n' or 'BIT a/BIT/b/c'
##    # or the like.
##    routechars = r"[\s\w]"
##    rexp = r"%s\%s(%s+/)*%s(/%s+)*$" % (re.escape(type), usedchar,
##                                        routechars, re.escape(num),
##                                        routechars)
##    #print "'"+route1+"'", route2, rexp
##    #print route1, route2, re.match(rexp, route2)
##    print rexp
##    return re.match(rexp, route2) is not None

class RPDatabase:
    def __init__(self, filename=None, quiet=0, progressbar=None):
        self.routes = []
        if filename:
            self.Open(filename, quiet, progressbar)
        else:
            self.cities = []
            self.filename = ''
            self.cityhash = {}
            self.author = self.author_email = self.comment = ''
            self.units  = UNITS_US
            self.classifications = []
            self.speed  = []
            self.mpg    = []
            self.prefer = []
            self.defmpg = defmpg
            self.defprf = 50

    def __del__(self):
        if self.routes:
            del self.routes

    def Open(self, filename, quiet=0, progressbar=None):
        if filename[-3:] == '.gz' and gzip:
            fh = gzip.GzipFile(filename, 'rb')
        else:
            fh = open(filename, 'r', -1)

        lines = string.split(fh.read(), os.linesep)
        stuff = lines.pop(0)
        if not stuff.startswith('RPL3') and not stuff.startswith('RPL4'):
            raise invalidformat, filename+' is not a valid RoutePlanner file'
        unicodefmt = stuff.startswith('RPL4')
        
        self.comment = string.strip(stuff[4:])
        if not self.comment:
            self.comment = ''

        cities = int(lines.pop(0))
        citylist = [None]*cities
        cityhash = {}
        if not quiet:
            sys.stdout.write('\nCities: ')
            sys.stdout.flush()

        if progressbar:
            progressbar.set_max(cities)
            progressbar.set_label('Loading Cities')
            progressbar.set_current(0)

        for i in range(cities):
            data = lines.pop(0)
            if unicodefmt:
                data = data.decode('UTF-8')
            else:
                data = data.decode('iso-8859-1')
                
            fields = data.split('|')
            
            x = rpcity.City( fields )
            name = unicode(x)
            cityhash[ name ] = cityhash[ name.lower() ] = (x, i)
            citylist[ i ] = x
            if not (i % 100):
                if not quiet:
                    sys.stdout.write('.')
                    sys.stdout.flush()
                if progressbar:
                    progressbar.set_current(i)

        routes = int(lines.pop(0))
        routelist = [None]*routes
        if not quiet:
            sys.stdout.write('\nRoutes: ')
            sys.stdout.flush()

        if progressbar:
            progressbar.set_max(routes)
            progressbar.set_label('Loading Routes')
            progressbar.set_current(0)

        for i in range(routes):
            data = lines.pop(0)
            if unicodefmt:
                data = data.decode('UTF-8')
            else:
                data = data.decode('iso-8859-1')

            fields = data.split('|')
            routelist[ i ] = rproute.Route( fields, cityhash )
            if not (i % 100):
                if not quiet:
                    sys.stdout.write('.')
                    sys.stdout.flush()
                if progressbar:
                    progressbar.set_current(i)
        
        if not quiet:
            sys.stdout.write('\n')
            sys.stdout.flush()

        self.cities = citylist
        # self.cities.sort(lambda x, y: cmp(
        #                  string.lower(str(x)), string.lower(str(y)) ))

        self.filename = filename
        self.cityhash = cityhash
        self.routes = routelist
        self.author = string.strip(lines.pop(0))
        self.author_email = string.strip(lines.pop(0))

        # The following are raw data stored in the file as defaults that
        # can be overridden by the user (using a prefs file)
        self.units  = string.strip(lines.pop(0))
        self.classifications = eval(lines.pop(0))
        self.speed  = eval(lines.pop(0))
        self.mpg    = eval(lines.pop(0))
        self.prefer = eval(lines.pop(0))
        self.defmpg = eval(lines.pop(0))
        self.defprf = eval(lines.pop(0))
        fh.close()

    def Sort(self):
        self.cities.sort()
        self.routes.sort()
        self.Rehash()
        
    def Save(self, filename, comment=None, progressbar=None):
        if not comment:
            comment = self.comment

        if progressbar:
            progressbar.set_label('Sorting...')
            progressbar.set_max(len(self.cities)+len(self.routes)+1)
            progressbar.show()
            progressbar.set_current(0)
        
        self.Sort()
        
        if os.path.exists(filename):
            os.rename(filename, filename+'~')

        if filename[-3:] == '.gz' and gzip:
            fh = gzip.GzipFile(filename, 'wb')
        else:
            fh = open(filename, 'w', -1)

        print >> fh, 'RPL4', comment

        print >> fh, len(self.cities)
        if progressbar:
            progressbar.set_label('Writing cities...')
            progressbar.set_current(1)

        for city in self.cities:
            print >> fh, city.utf8()

        print >> fh, len(self.routes)
        if progressbar:
            progressbar.set_label('Writing cities...')
            progressbar.set_current(len(self.cities)+1)

        for route in self.routes:
            print >> fh, route.utf8()

        print >> fh, self.author
        print >> fh, self.author_email
        print >> fh, self.units
        print >> fh, self.classifications
        print >> fh, self.speed
        print >> fh, self.mpg
        print >> fh, self.prefer
        print >> fh, self.defmpg
        print >> fh, self.defprf
        fh.close()

    def Rehash(self):
        for (i, city) in enumerate(self.cities):
            self.cityhash[unicode(city)] = (city, i)

    def CitiesMatching(self, pat):
        return [self.cities[x] for x in self.CitiesMatchIndex(pat)]

    def CitiesMatchIndex(self, pat, visible=()):
        x = self.cityhash.get(pat)
        if x:
            return [x[1]]       
        
        matching = []
        
        if ',' in pat:
            city, state = re.split('\s*,\s*', pat, 1)
            state = expand_state(state)
            exp = re.compile(re.escape(city)+'[^,]*, '+re.escape(state), re.I)
        else:
            exp = re.compile(re.escape(pat), re.I)
        
        if not visible:
            visible = range(len(self.cities))

        for i in visible:
            if exp.match(str(self.cities[i])):
                matching.append(i)

        return matching
    
    # The following routine is adapted from a C algorithm created by
    # Jim Butterfield and placed in the public domain.
    #
    # It is apparently based on Dijkstra's algorithm for shortest
    # paths; it is O(n^2)
    def OldNavigate(self, start, end, method=LEAST_DISTANCE, units=None,
                    codetable=None, prefertable=None, defaultprefer = None,
                    flagbonus=None, mpgtable=None, defmpg=None):
        if not units:         units = self.units
        if not codetable:     codetable = self.speed
        if not prefertable:   prefertable = self.prefer
        if not defaultprefer: defaultprefer = self.defprf
        if not mpgtable:      mpgtable = self.mpg
        if not defmpg:        defmpg = self.defmpg
        
        # Fake an enumeration
        WORKLIST, NEXTCITY, MINDIST = 0, 1, 2

        citydict = {}
        weightings = {}

        for city in self.cities:
            citydict[id(city)] = [None, None, MAXDIST]

        elink = end
        minival = 0

        usefunc = [Least_Distance, Least_Time, Preferred, Least_Fuel]
        methodfunc = usefunc[method]

        citydict[ id(end) ] = [None, None, 0]
        thisdist, searchcity = MAXDIST, end

        startstr = id(start)
        startcityinf = citydict[startstr]

        while searchcity:
            searchstr = id(searchcity)
            searchcityinf = citydict[searchstr]

            if (searchcityinf[MINDIST] < startcityinf[MINDIST]):
                minival = searchcityinf[MINDIST]
                #print 'At %s, distance %d' % (searchstr, minival)

                for (nextroute, nextcol, othercity) in searchcity.roads:
                    rtestr = repr(nextroute)
                    dist = weightings.get(rtestr)
                    if not dist:
                        dist = methodfunc(nextroute, units, codetable,
                                          prefertable, defaultprefer,
                                          mpgtable, defmpg)
                        weightings[rtestr] = dist

                    othercitystr = id(othercity)
                    othercityinf = citydict[othercitystr]
                    
                    travel = minival + dist

                    # New shortest distance
                    if othercityinf[MINDIST] > travel:
                        othercityinf[MINDIST] = travel
                        othercityinf[NEXTCITY] = searchcity

                        if (not othercityinf[WORKLIST] and
                            elink is not othercity):
                            (blink, flink) = (searchcity,
                                              searchcityinf[WORKLIST])
                            
                            if flink:
                                flinkstr = id(flink)
                                flinkinf = citydict[flinkstr]

                            while flink and travel > flinkinf[MINDIST]:
                                (blink, flink) = (flink, flinkinf[WORKLIST])
                                if flink:
                                    flinkstr = id(flink)
                                    flinkinf = citydict[flinkstr]

                            blinkstr = id(blink)
                            blinkinf = citydict[blinkstr]
                            blinkinf[WORKLIST] = othercity
                            othercityinf[WORKLIST] = flink
                            
                            if not flink:
                                elink = othercity

                    thisdist = min(travel, thisdist)

            searchcity = searchcityinf[WORKLIST]
            searchcityinf[WORKLIST] = None
        
        trail = []
        searchcity, flink = start, startcityinf[NEXTCITY]
        while flink:
            for i in range( len(searchcity.roads) ):
                if (searchcity.roads[i][0].city[1-searchcity.roads[i][1]]
                    is flink):
                    route = (searchcity.roads[i][0], 1-searchcity.roads[i][1])
            trail.append( route )
            searchcity, flink = flink, citydict[id(flink)][NEXTCITY]

        return trail

    # New navigation routine; based on example by
    # Aaron Watters <aaron@cs.rutgers.edu> posted to comp.lang.python 
    # 12/22/1997
    #
    # His example used his kjbuckets C extension for graphs; I'm using
    # another representation (they benchmarked the same).  kjSet seems
    # to buy some performance over a straight dictionary, so it is used
    # if available.
    #
    # Interestingly enough, PQEquivMax seems to be faster than PQueue;
    # no idea why...
    #
    # Adapted to use the PQueue extension class by Andrew Snare
    # on 1/3/2000
    def OldNavigate2(self, start, end, method=LEAST_DISTANCE, units=None,
                     codetable=None, prefertable=None, defaultprefer=None,
                     flagbonus=None, mpgtable=None, defmpg=None):
        if start is end:
            return []

        if not units:         units = self.units
        if not codetable:     codetable = self.speed
        if not prefertable:   prefertable = self.prefer
        if not defaultprefer: defaultprefer = self.defprf
        if not mpgtable:      mpgtable = self.mpg
        if not defmpg:        defmpg = self.defmpg
        
        usefunc = [Least_Distance, Least_Time, Preferred, Least_Fuel]
        methodfunc = usefunc[method]
        weightings = {}

        try:
            from pqueue import PQueue
            Q = PQueue()
        except:
            # Use pure Python implementation
            from pq3 import PQ0
            Q = PQ0()
            Q.insert = Q.addelt
            Q.pop = Q.popsmallest

        reverse_path = {start : start}
        costs = {start : 0}
        seen = {}

        for neighbor in start.roads:
            pair = start, neighbor[2]
            wt = weightings.get(pair)
            if not wt:
                c0, c1 = pair
                road = neighbor[0]
                dist = methodfunc(road, units, codetable, prefertable,
                                  defaultprefer, flagbonus, mpgtable, defmpg)
                wt = weightings[pair] = dist, road, neighbor[1]
                weightings[(c1,c0)] = dist, road, 1-neighbor[1]

            Q.insert(wt[0], pair)
            seen[pair] = True

        while len(Q):
            (priority, (left, right)) = Q.pop()
            if priority < costs.get(right, MAXDIST):
                reverse_path[right] = left
                costs[right] = priority
                if right is end:
                    # We are done
                    path = []
                    this = right
                    pair = (right, reverse_path[right])
                    while this is not start:
                        if this is not end: path.append(weightings[pair][1:])
                        pair = (this, reverse_path[this])
                        this = pair[1]

                    path.append(weightings[pair][1:])
                    path.reverse()
                    return path

                for neighbor in right.roads:
                    pair = (right, neighbor[2])
                    if pair not in seen:
                        wt = weightings.get(pair)
                        if not wt:
                            c0, c1 = pair
                            road = neighbor[0]
                            dist = methodfunc(road, units, codetable,
                                              prefertable, defaultprefer,
                                              flagbonus, mpgtable, defmpg)
                            wt = weightings[pair] = dist, road, neighbor[1]
                            weightings[(c1,c0)] = dist, road, 1-neighbor[1]
                        newwt = wt[0]+priority
                        Q.insert(newwt, pair)
                        seen[pair] = True
                        # Also add the reverse
                        pair = (pair[1], pair[0])
                        Q.insert(newwt, pair)
                        seen[pair] = True
        
        raise ValueError, "start unreachable from end"

    # New navigation routine; based on example by
    # Aaron Watters <aaron@cs.rutgers.edu> posted to comp.lang.python 
    # 12/22/1997
    #
    # Revised to make use of heapq module in Python 2.3+
    def NewNavigate(self, start, end, method=LEAST_DISTANCE, units=None,
                    codetable=None, prefertable=None, defaultprefer=None,
                    flagbonus=None, mpgtable=None, defmpg=None):
        from heapq import heappush, heappop
        
        if start is end:
            return []

        if not units:         units = self.units
        if not codetable:     codetable = self.speed
        if not prefertable:   prefertable = self.prefer
        if not defaultprefer: defaultprefer = self.defprf
        if not mpgtable:      mpgtable = self.mpg
        if not defmpg:        defmpg = self.defmpg
        
        usefunc = [Least_Distance, Least_Time, Preferred, Least_Fuel]
        methodfunc = usefunc[method]
        weightings = {}

        heap = []

        reverse_path = {start : start}
        costs = {start : 0}
        seen = {}

        for neighbor in start.roads:
            pair = start, neighbor[2]
            wt = weightings.get(pair)
            if not wt:
                c0, c1 = pair
                road = neighbor[0]
                dist = methodfunc(road, units, codetable, prefertable,
                                  defaultprefer, flagbonus, mpgtable, defmpg)
                wt = weightings[pair] = dist, road, neighbor[1]
                weightings[(c1,c0)] = dist, road, 1-neighbor[1]

            heappush(heap, (wt[0], pair))
            seen[pair] = True

        while len(heap):
            (priority, (left, right)) = heappop(heap)
            if priority < costs.get(right, MAXDIST):
                reverse_path[right] = left
                costs[right] = priority
                if right is end:
                    # We are done
                    path = []
                    this = right
                    pair = (right, reverse_path[right])
                    while this is not start:
                        if this is not end: path.append(weightings[pair][1:])
                        pair = (this, reverse_path[this])
                        this = pair[1]

                    path.append(weightings[pair][1:])
                    path.reverse()
                    return path

                for neighbor in right.roads:
                    pair = (right, neighbor[2])
                    if pair not in seen:
                        wt = weightings.get(pair)
                        if not wt:
                            c0, c1 = pair
                            road = neighbor[0]
                            dist = methodfunc(road, units, codetable,
                                              prefertable, defaultprefer,
                                              flagbonus, mpgtable, defmpg)
                            wt = weightings[pair] = dist, road, neighbor[1]
                            weightings[(c1,c0)] = dist, road, 1-neighbor[1]
                        newwt = wt[0]+priority
                        heappush(heap, (newwt, pair))
                        seen[pair] = True
                        # Also add the reverse
                        pair = (pair[1], pair[0])
                        heappush(heap, (newwt, pair))
                        seen[pair] = True
        
        raise ValueError, "start unreachable from end"

# End of RPDatabase

def NicerTime(min):
    return '%2d:%02d' % divmod(min, 60)

def ProduceTrail(trail, db, units, mpg, defmpg, speed):
    displist = []

    for leg in trail:
        tlist = []
        entry = None
        for segment in leg:
            preventry = entry
            entry = ( segment[0].city[1-segment[1]],
                      segment[0].city[segment[1]],
                      segment[0].name,
                      segment[0].exits[segment[1]],
                      float(segment[0].distance.AsUnit(units)),
                      ConvertToTime(segment[0], units, speed),
                      Efficiency(segment[0].distance, units,
                                 segment[0].speedcode, mpg, defmpg) )
            if preventry:
                if IsSameRoute(preventry[2], entry[2]):
                    del tlist[-1]
                    entry = (preventry[0], entry[1], preventry[2],
                             entry[3], entry[4]+preventry[4],
                             entry[5]+preventry[5], entry[6]+preventry[6])

            tlist.append(entry)

        displist.append(tlist)

    return displist

def FormatRoute(route, path, units):
    if units == UNITS_METRIC:
        units = 'km'
        mpgunits = 'l'
    else:
        units = 'mi'
        mpgunits = 'gal'

    totals = (0,0,0)
    text = ""
    for i in range(len(route)):
        if i: text = text+'\n'
        text = text + 'From '+str(path[i])+' to '+str(path[i+1])+'\n'
        text = text + '-'*60 + '\n'

        leg = (0,0,0)
        for segment in route[i]:
            inc = segment[0].country != segment[1].country

            text = text + NicerTime(segment[5]) + ' ' + \
                   str(segment[2]) +' to ' + segment[1].printable(inc)
                
            if segment[3]:
                text = text + ' [Exit '+segment[3]+']'

            text = text + ' (%.0f %s)\n' % (segment[4], units)
            leg = (leg[0] + segment[5], leg[1] + segment[4],
                   leg[2] + segment[6])

        if len(route) > 1:
            text = text + 'Leg totals: %.0f %s; %s (%.1f %s)\n' % (
                leg[1], units, NicerTime(leg[0]), leg[2],
                mpgunits)

        totals = (totals[0]+leg[0], totals[1]+leg[1], totals[2]+leg[2])

    return text + '\nTotal route: %.0f %s; %s (%.1f %s)' % (
        totals[1], units, NicerTime(totals[0]),
        totals[2], mpgunits)

statecodes = { 'us': {
    "AL" : "Alabama",
    "AK" : "Alaska",
    "AZ" : "Arizona",
    "AR" : "Arkansas",
    "CA" : "California",
    "CO" : "Colorado",
    "CT" : "Connecticut",
    "DE" : "Delaware",
    "FL" : "Florida",
    "GA" : "Georgia",
    "HI" : "Hawaii",
    "ID" : "Idaho",
    "IL" : "Illinois",
    "IN" : "Indiana",
    "IA" : "Iowa",
    "KS" : "Kansas",
    "KY" : "Kentucky",
    "LA" : "Louisiana",
    "ME" : "Maine",
    "MD" : "Maryland",
    "MA" : "Massachusetts",
    "MI" : "Michigan",
    "MN" : "Minnesota",
    "MS" : "Mississippi",
    "MO" : "Missouri",
    "MT" : "Montana",
    "NE" : "Nebraska",
    "NV" : "Nevada",
    "NH" : "New Hampshire",
    "NJ" : "New Jersey",
    "NM" : "New Mexico",
    "NY" : "New York",
    "NC" : "North Carolina",
    "ND" : "North Dakota",
    "OH" : "Ohio",
    "OK" : "Oklahoma",
    "OR" : "Oregon",
    "PA" : "Pennsylvania",
    "RI" : "Rhode Island",
    "SC" : "South Carolina",
    "SD" : "South Dakota",
    "TN" : "Tennessee",
    "TX" : "Texas",
    "UT" : "Utah",
    "VT" : "Vermont",
    "VA" : "Virginia",
    "WA" : "Washington",
    "WV" : "West Virginia",
    "WI" : "Wisconsin",
    "WY" : "Wyoming",
    "DC" : "District of Columbia",
    }, 'um' : {
    "AS" : "American Samoa",
    "FM" : "Federated States of Micronesia",
    "GU" : "Guam",
    "MH" : "Marshall Islands",
    "MP" : "Northern Mariana Islands",
    "PW" : "Palau",
    "TT" : "Trust Territories",
    "VI" : "Virgin Islands",
    }, 'pr' : {
    "PR" : "Puerto Rico",
    }, 'ca' : {
    "AB" : "Alberta",
    "BC" : "British Columbia",
    "MB" : "Manitoba",
    "NB" : "New Brunswick",
    "NF" : "Newfoundland and Labrador",
    "NS" : "Nova Scotia",
    "NT" : "Northwest Territories",
    "NU" : "Nunavut",
    "ON" : "Ontario",
    "PE" : "Prince Edward Island",
    "PQ" : "Qubec", # Older abbreviation for Quebec
    "QU" : "Qubec",
    "SA" : "Saskatchewan",
    "YT" : "Yukon",
    }, 'mx' : {
    "AG" : "Aguascalientes",
    "BN" : "Baja California North",
    "BS" : "Baja California South",
    "CH" : "Chihuahua",
    "CI" : "Coahuila",
    "CL" : "Colima",
    "CM" : "Campeche",
    "CS" : "Chiapas",
    "DF" : "Distrito Federal",
    "DU" : "Durango",
    "GR" : "Guerrero",
    "GT" : "Guanajuato",
    "HG" : "Hidalgo",
    "JA" : "Jalisco",
    "MC" : "Michoacan",
    "ML" : "Morelos",
    "MX" : "Mxico",
    "NA" : "Nayarit",
    "NL" : "Nuevo Len",
    "OA" : "Oazaca",
    "PU" : "Puebla",
    "QE" : "Queretaro",
    "QR" : "Quintana Roo",
    "SI" : "Sinaloa",
    "SL" : "San Luis Potosi",
    "SO" : "Sonora",
    "TA" : "Tamaulipas",
    "TB" : "Tabasco",
    "TL" : "Tlaxcala",
    "VC" : "Vera Cruz",
    "YC" : "Yucatan",
    "ZA" : "Zacatecas",
    }
}

combined_codes = {}
for state in statecodes.keys():
    combined_codes.update( statecodes[state] )

def expand_state(state):
    return combined_codes.get(string.upper(state), state)

CANADIAN = statecodes['ca'].values()
MEXICAN = statecodes['mx'].values()

country_for_state = {}
for state in statecodes.keys():
    for abbrev, name in statecodes[state].items():
        country_for_state[name] = state

def autodetect_country(state):
    return country_for_state.get(state)