Mapping, with sequence as key, wildcard and subsequence matching

[Marko Rauhamaa]

Ben Finney <ben+python at benfinney.id.au>:

> What well-defined data type exists with the following properties:
>
> * Mapping, key → value.
>
> * Each key is a sequence (e.g. `tuple`) of items such as text strings.
>
> * Items in a key may be the sentinel `ANY` value, which will match any
>   value at that position.
>
> * A key may specify that it will match *only* sequences of the same
>   length.
>
> * A key may specify that it will match sequences with arbitrarily many
>   additional unspecified items.

What you are describing is a tree; the sequences specify paths:

========================================================================
class Node:
    ANY = object()
    UNDEFINED = object()

    def __init__(self):
        self.value = Node.UNDEFINED
        self.children = {}

    def setvalue(self, keyseq, value, offset=0):
        try:
            next = keyseq[offset]
        except IndexError:
            self.value = value
            return
        if next is Node.ANY:
            raise KeyError()
        try:
            child = self.children[next]
        except KeyError:
            self.children[next] = child = Node()
        child.setvalue(keyseq, value, offset + 1)

    def lookup(self, keyseq, offset=0):
        try:
            next = keyseq[offset]
        except IndexError:
            for value in self.yieldall():
                yield value
            return
        if next is Node.ANY:
            for child in self.children.itervalues():
                for value in child.lookup(keyseq, offset + 1):
                    yield value
            return
        try:
            child = self.children[next]
        except KeyError:
            return
        for value in child.lookup(keyseq, offset + 1):
            yield value

    def yieldall(self):
        if self.value is not Node.UNDEFINED:
            yield self.value
        for child in self.children.itervalues():
            for value in child.yieldall():
                yield value
=====================================================================

Usage:

=====================================================================
tree = Node()
tree.setvalue((1, 2), 3)
print list(tree.lookup((1, 2)))
print list(tree.lookup((Node.ANY, 2)))
=====================================================================

CAVEAT: Code barely tested.


Marko