Determining the current state of a URL from a list of states containing required and optional items in Python/Flask [closed]

Question

Closed. This question needs to be more focused. It is not currently accepting answers.

---

Want to improve this question? Update the question so it focuses on one problem only by editing this post.

Closed 8 years ago.

Improve this 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 1

You really do not need some arguments like optional, because with string types it not have sense. My simplified example:

class StateMatcher(dict):

    def best_match(self, obj):
        for state, params in sorted(self.items(),
                                    key=lambda item: len(item[1]),
                                    reverse=True):
            for param in params:
                if param not in obj:
                    break
            else:
                return state
         return None


sm = StateMatcher([
    ('state1', ['name']),
    ('state2', ['name', 'address']),
])

state = sm.best_match(request.args)

If you need you always can make own builder to build right structure for check. If you need smart algorithm to get best match you must implement it yourself. If you need more complex properties with type validation and etc you can try wrap something like jsonscheme.

Answer 2

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