2
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$
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:])
\$\endgroup\$
  • \$\begingroup\$ "Do you really need to store all the data twice?" - it makes things much easier and there won't be tons of entries so I'd say it's worth the additional memory used. Of course it's not necessary when switching to a single dict instead of the nested ones. Thanks for the detailed answer! \$\endgroup\$ – ThiefMaster Jul 26 '12 at 8:59
  • \$\begingroup\$ github.com/ThiefMaster/Flask-IRC/blob/… is the new version - much more readable :) \$\endgroup\$ – ThiefMaster Jul 26 '12 at 10:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.