Determining the current state of a URL from a list of states containing required and optional items in Python/Flask
Question: I'd like to specify a list of possible states a URL can be in by declaring
required and optional query string parameters. Here's some pseudo code to
maybe illustrate what I mean...

    
    
    sm.add('state1').args.required('name').optional('phone')
    sm.add('state2').args.required('name', 'address').optional('phone')
    

I'd then like to figure out which state is the closest match to Flask's
`request.args` object with an API such as...

    
    
    sm.best_match(request.args)
    

I'm assuming sets will be involved, but I'm rather clueless.


Answer: In pseudo-Python code:

    
    
    from bisect import bisect_left, bisect_right, insort
    from collections import namedtuple
    from itertools import islice
    
    # Not a finished product, just some ideas of the data structures
    # you would need to get this working.
    
    # States is a (name, set(required, fields), set(optional, fields)) tuple
    states = namedtuple('States', 'name required optional')
    heap = []
    
    def add_to_tree(state, heap=heap):
        total_required = len(state.required)
        total_optional = len(state.optional)
        total = total_required + total_optional
    
        # When store states on the heap ordered by how many
        # required / optional arguments they have
        insort(heap, (total_required, total_optional, state))
    
    INF = float('inf')
    MIN_STATE = states('', set(), set())
    
    # Need custom comparators here for string and set
    # that always compare greater than what they are compared against
    def biggest(type):
        # Left as an exercise for the reader.
    
    MAX_STATE = states(biggest(str), biggest(set), biggest(set))
    
    def best_match(args, heap=heap):
        total_args = len(args)
        first_match = bisect_left(heap, (0, total_args, MIN_STATE))
        last_match = bisect_right(heap, (total_args, INF, MAX_STATE), low=first_match)
        potential_matches = islice(heap, last_match, first_match, -1)
        for _r, _o, state in potential_matches:
            if is_match(args, state):
                return state
    
    def is_match(args, state):
        # TODO: implement this
    

