# Mapping, with sequence as key, wildcard and subsequence matching

Marko Rauhamaa marko at pacujo.net
Thu Jul 16 08:53:44 CEST 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

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
```