from functools import reduce


def best_match(match_list, request_list):
    """
    @param match_list: Ordered list of available entries
    @param request_list: Ordered list of requested entries
    @return: first entry in the request list that is available in the match list

    Based on U{http://www.w3.org/Protocols/rfc2616/rfc2616-sec14.html}, we search in the following order:
    1. Find an exact match

    2. If the match field has a semicolon in it, truncate it and look for an exact match on anything without
       an asterisk

    3. Look for a match on 'x/*'
    4. Look for */*
    """
    ordered_request_list = {k:v for k,v in zip(request_list, range(0,len(request_list)))}
    matches = {} # Map from key to request_order / rule order (for tie breaker)
    # exact match
    for m in match_list:
        if m in ordered_request_list:
            matches[m]=(ordered_request_list[m],0)
    # match up to ';'
    for m in match_list:
        if m not in matches and ';' in m:
            mp = m[0:m.index(';')]
            if mp in ordered_request_list:
                matches[m] = (ordered_request_list[mp],1)
    # x/* match
    for m in match_list:
        if m not in matches and '/' in m:
            mp = m[0:m.index('/')+1] + '*'
            if mp in ordered_request_list:
                matches[m] = (ordered_request_list[mp],2)
    # */* match
    if '*/*' in ordered_request_list:
        for m in match_list:
            if m not in matches:
                matches[m] = (ordered_request_list['*/*'],3)
                break
    if len(matches):
        return reduce(lambda k1, k2: k1 if k1[1] <= k2[1] else k2, matches.items())[0]
    return None