Mapping, with sequence as key, wildcard and subsequence matching
Marko Rauhamaa
marko at pacujo.net
Thu Jul 16 02:53:44 EDT 2015
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
More information about the Python-list
mailing list