Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #93905

Re: Mapping, with sequence as key, wildcard and subsequence matching

Show key headers only | View raw

Ben Finney <ben+python@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

Back to comp.lang.python | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

Mapping, with sequence as key, wildcard and subsequence matching Ben Finney <ben+python@benfinney.id.au> - 2015-07-16 11:51 +1000
  Re: Mapping, with sequence as key, wildcard and subsequence matching Steven D'Aprano <steve@pearwood.info> - 2015-07-16 14:01 +1000
    Re: Mapping, with sequence as key, wildcard and subsequence matching Ben Finney <ben+python@benfinney.id.au> - 2015-07-16 15:53 +1000
    Re: Mapping, with sequence as key, wildcard and subsequence matching Ethan Furman <ethan@stoneleaf.us> - 2015-07-15 23:31 -0700
    Re: Mapping, with sequence as key, wildcard and subsequence matching Ben Finney <ben+python@benfinney.id.au> - 2015-07-16 16:37 +1000
    Re: Mapping, with sequence as key, wildcard and subsequence matching Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-07-16 08:09 +0100
    Re: Mapping, with sequence as key, wildcard and subsequence matching Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-07-16 08:24 +0100
  Re: Mapping, with sequence as key, wildcard and subsequence matching Marko Rauhamaa <marko@pacujo.net> - 2015-07-16 09:53 +0300

csiph-web