Path: csiph.com!optima2.xanadu-bbs.net!xanadu-bbs.net!feeder.erje.net!1.eu.feeder.erje.net!newsfeed.xs4all.nl!newsfeed8.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
MIME-Version: 1.0
In-Reply-To: <85bnfcve7w.fsf@benfinney.id.au>
References: <85k2u0vpis.fsf@benfinney.id.au> <mo7fco$tme$1@ger.gmane.org> <85bnfcve7w.fsf@benfinney.id.au>
Date: Thu, 16 Jul 2015 16:21:22 +1000
Subject: Re: Mapping, with sequence as key, wildcard and subsequence matching
From: Chris Angelico <rosuav@gmail.com>
Cc: "python-list@python.org" <python-list@python.org>
Content-Type: text/plain; charset=UTF-8
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.560.1437027691.3674.python-list@python.org>
Lines: 35
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:93900

On Thu, Jul 16, 2015 at 3:55 PM, Ben Finney <ben+python@benfinney.id.au> wrote:
> Thanks. The part which puzzle me though: How do we teach the mapping
> type about that matching behaviour?

I'm not sure you really need a mapping type per se. The benefit of
something like Python's dict is that it gives really fast lookups via
the hash table... but with the "match any" concept, there's actually a
potential for ambiguities, which means you need a sequential
(strictest first) check. In any case, it's virtually impossible to
hash a tuple of strings such that it can match multiple targets, based
only on what the targets do. Steven's suggestion to turn this into an
honest linear search is probably what I'd do; ultimately, a dict that
can't hash its keys properly is going to devolve to that anyway.

You could craft a mapping-like type that uses subscripts in this way.
I'm not sure whether it'd help, but there's no particular reason for
__getitem__ to not do a full linear search:

class Lookup:
    def __getitem__(self, item):
        for matcher, value in self.stuff:
            keys = iter(item)
            for key in matcher:
                if key is ZERO_OR_MORE: return value # Matched!
                try: val = next(keys)
                except StopIteration: break # Too short, doesn't match
                if key != val and key is not ANY_ONE: break # Mismatch
            else:
                return value # Matched!
        raise KeyError(item)

Then in your code, it would look like any other mapping type, but it'd
still be the exact same linear search that Steven talked about.

ChrisA