Longest-match lookup via nested dicts

Question

I have the following datastructure to perform a longest-match lookup via nested dicts. For example. cs['a b c d'] with a and a b c being in the structure will return a b c and the remainder d.

I wonder if there's a better way to implement the _lookup method and possible the __setitem__ method. I'm also not completely sure if the way __getitem__ works (returning a tuple with the data in the structure and the remainder of the input) isn't a bit confusing when used with the [] operator.

class CommandStorage(object):
    """Stores multi-part commands.

    Performs fast lookups returning the command and any arguments which were
    not part of the command.
    """

    def __init__(self, commands={}):
        self._root = {}
        self._commands = {}
        for cmd, func in commands:
            self[cmd] = func

    def _lookup(self, line):
        parts = line.split(' ')
        found = None
        found_container = None
        container = self._root
        command_parts = 0
        for i, part in enumerate(parts):
            if part not in container:
                return found_container, found, parts[command_parts:]
            container = container[part]
            if None in container:
                found_container = container
                found = container[None]
                command_parts = i + 1
        return found_container, found, parts[command_parts:]

    def __setitem__(self, cmd, func):
        container = self._root
        parts = cmd.split(' ')
        for part in parts:
            container = container.setdefault(part, {})
        if None in container:
            raise ValueError('Command %s already exists' % cmd)
        container[None] = func
        self._commands[cmd] = func

    def __getitem__(self, line):
        return self._lookup(line)[1:]

    def __contains__(self, item):
        cmd, args = self[item]
        return cmd is not None and not args

    def __delitem__(self, cmd):
        if cmd not in self:
            raise KeyError(cmd)
        container = self._lookup(cmd)[0]
        del container[None]
        del self._commands[cmd]

    def __iter__(self):
        return iter(self._commands)

    def __len__(self):
        return len(self._commands)

    def __nonzero__(self):
        return bool(self._commands)

    def iterkeys(self):
        return self._commands.iterkeys()

    def iteritems(self):
        return self._commands.iteritems()

    def itervalues(self):
        return self._commands.itervalues()

    def __repr__(self):
        return '<CommandStorage(%r)>' % self._commands.keys()

The full code (with a doctest) is in this gist as the doctest is not really relevant for the question

Answer 1

class CommandStorage(object):
    """Stores multi-part commands.

    Performs fast lookups returning the command and any arguments which were
    not part of the command.
    """

    def __init__(self, commands={}):
        self._root = {}
        self._commands = {}

Do you really need to store all the data twice?

        for cmd, func in commands:

That should be commands.items(), guess you've never used the parameter

            self[cmd] = func

    def _lookup(self, line):
        parts = line.split(' ')
        found = None
        found_container = None
        container = self._root
        command_parts = 0
        for i, part in enumerate(parts):
            if part not in container:
                return found_container, found, parts[command_parts:]
            container = container[part]

The recommended way to structure something like this to catch the KeyError, so:

try:
    container = container[part]
except KeyError:
    return found_container, found, parts[command_parts:]
else:
    proceed

As it stands, your code looks up the container[part] twice.

            if None in container:

Using None to store the actual value is counter-intuitive. That's not what None usually means.

                found_container = container
                found = container[None]
                command_parts = i + 1

Having these three pieces of data feels ugly.

        return found_container, found, parts[command_parts:]

I think the problem is your data structure. Your collection of dicts of dicts of dicts is tricky to navigate.

    def __setitem__(self, cmd, func):
        container = self._root
        parts = cmd.split(' ')
        for part in parts:

I'd combine these last two lines

            container = container.setdefault(part, {})
        if None in container:
            raise ValueError('Command %s already exists' % cmd)
        container[None] = func
        self._commands[cmd] = func

    def __getitem__(self, line):
        return self._lookup(line)[1:]

I think this is a bad idea. This function doesn't act like [] typically acts in python. So just make this a regular method

    def __contains__(self, item):
    def __delitem__(self, cmd):
    def __iter__(self):
    def __len__(self):
    def __nonzero__(self):
    def iterkeys(self):
    def iteritems(self):
    def itervalues(self):

You've implemented all these functions to make it act like a dictionary. But its not a dictionary. Unless the object is designed to provide the features of a dictionary, don't attempt to provide the dictionary interface.

    def __repr__(self):
        return '<CommandStorage(%r)>' % self._commands.keys()

Here's how I'd approach it. Don't use nested dicts, just store everything in one dict. __setitem__ becomes trivial:

def __setitem__(self, cmd, func):
    parts = tuple(cmd.split(' '))
    if parts in self._commands:
        raise ValueError('Command %s already exists' % cmd)
    else:
        self._commands[parts] = func

Then, _lookup becomes:

def _lookup(self, line):
    parts = tuple(line.split(' '))
    # start with longest match, work backwards
    # first match found will be longest match
    for index in xrange(len(parts), -1, -1):
        try:
            function = self._commands[parts[:index]]
        except KeyError:
            pass # no match found, try next one
        else:
            break # match, stop search
    else:
        function = None # if all else fails, report None as function

    return function, list(parts[index:])