# Dijkstra's algorithm

def get_min(D):
    """

    returns the (value, key) pair that minimizes
    the value within the dictionary D

    this is linear (it would be faster if it were cleverer... maybe)

    ** ALSO removes the returned data from D **
    
    """
    if len(D) == 0:
        raise ValueError, "Call of getMin from {}"
    
    min_value = 1.0e200 # good enough for now...
    min_key = "no key"
    
    for key in D:
        val = D[key]
        if val < min_value:
            min_key = key
            min_value = val

    D.pop(min_key)
    return min_value, min_key


def dijkstra(G,start,end=None):
    """
    Find shortest paths from the start vertex to all
    vertices nearer than or equal to the end.

    If end is None, it will find the single-source shortest
    paths to all vertices reachable from start.
    
    The graph G should be a dictionary whose keys are the
      source vertices and whose values are dictionaries of
      destination vertices and costs. See test().
    G[v][w] returns the distance from v to w.

    Adapted from http://code.activestate.com/recipes/119466-dijkstras-algorithm-for-shortest-paths/
    by David Eppstein, UC Irvine, 4 April 2002
    
    ... but different because this does not require support
    code outside of Python's standard library (but it's slower)
    """
    D = {}  # dictionary of final distances
    P = {}  # dictionary of predecessors
    Q = {}  # our partially-explored nodes, not yet finalized
    # we'll pay the linear cost of finding the min each time...
    Q[start] = 0

    while True:
        if len(Q) == 0:
            break # all vertices reached
        
        dist, v = get_min(Q) # get next nearest node to expand
        D[v] = dist # finalized distance
        if v == end: break # found the one we wanted
   
        for w in G[v]:  # for each neighbor of v
            vwLength = D[v] + G[v][w] # dist to w through v
            if w in D:
                if vwLength < D[w]:
                    raise ValueError, "Dijkstra: found better path to already-final vertex"
            elif w not in Q or vwLength < Q[w]: # it's better!
                Q[w] = vwLength  # update best dist to w so far
                P[w] = v         # update w's predecessor

    return (D,P)
     

def test1():
    """
    test of shortest path on a known graph
    the graph
    """
    G = {'s':{'u':10, 'x':5},
         'u':{'v':1, 'x':2},
         'v':{'y':4},
         'x':{'u':3, 'v':9, 'y':2},
         'y':{'s':7, 'v':6}}
    # the shortest path from 's' to 'v' should be 's','x','u','v' == 9
    start = 's'
    end = 'v'
    D, P = dijkstra(G,start,end)
    # D are all the distances (as far as 'v') (by vertex)
    # P are all the predecessors (by vertex)
    print "distances are", D
    print "predecessors are", P
    # get the path
    path = []
    while end != start:
        path.append(end)
        end = P[end]
    path.append(start)
    path.reverse()
    print "path is", path




def binary_search(lo, hi, f):
    """
    binary search adapted from
    http://stackoverflow.com/questions/212358/binary-search-in-python
    
    this one searches within the integers [lo,hi] to find the
    largest value, mid, such that f(mid) is true

    if no values work, lo is returned
    """
    best = lo
    while lo <= hi:
        #print "lo,hi:", lo, hi
        mid = (lo+hi)/2 # won't overflow in Python
        if f(mid):
            best = mid # mid did work
            lo = mid+1
        else:
            hi = mid-1 # mid didn't work...
    return best

def test2():
    """
    test of binary search
    """
    for answer in range(-1,1002):
        if answer != binary_search(0, 1000, lambda x: x <= answer):
            print "Failed for", answer
    print "Done!"




def convex_hull(points):
    """Computes the convex hull of a set of 2D points.
 
    Input: an iterable sequence of (x, y) pairs representing the points.
    Output: a list of vertices of the convex hull in counter-clockwise order,
            starting from the vertex with the lexicographically smallest coordinates.

    Implements Andrew's monotone chain algorithm. O(n log n) complexity.

    Taken from http://www.algorithmist.com/index.php/Monotone_Chain_Convex_Hull.py
    """
    points = sorted(set(points))  # sort & remove duplicates
 
    if len(points) <= 1:  # trivial convex hull
        return points
 
    # 2D cross product of OA and OB vectors,
    # i.e. z-component of their 3D cross product.
    # Returns a positive value, if OAB makes a counter-clockwise turn,
    # negative for clockwise turn, and zero if the points are collinear.
    def cross(o, a, b):
        return (a[0] - o[0]) * (b[1] - o[1]) - \
               (a[1] - o[1]) * (b[0] - o[0])
 
    # Build lower hull 
    lower = []
    for p in points:
        while len(lower) >= 2 and \
              cross(lower[-2], lower[-1], p) <= 0: # need to retract?
            lower.pop() # retract
        lower.append(p) # else append the next point
 
    # Build upper hull
    upper = []
    for p in reversed(points):
        while len(upper) >= 2 and \
              cross(upper[-2], upper[-1], p) <= 0: # need to retract?
            upper.pop() # retract
        upper.append(p) # else append the next point
 
    # Concatenation of the lower and upper hulls gives the convex hull.
    # Last point of each list is omitted
    # because it is repeated at the beginning of the other list. 
    return lower[:-1] + upper[:-1]

def test3():
    """
    Example: convex hull of a 10-by-10 grid.
    """
    print "         ", convex_hull([(i/10, i%10) for i in range(100)])
    print "should be", [(0, 0), (9, 0), (9, 9), (0, 9)]