reverse dict lookup & Relation class

[Steven D'Aprano]

On Wed, 14 Jan 2009 16:30:36 -0800, Aaron Brady wrote:

> Hi, this is a continuation of something that comes up now and again
> about reverse lookups on dictionaries, as well as a follow-up to my
> pursuit of a Relation class from earlier.

[...]

> What's the best way to construct this class?  Or, do you have an
> argument that it could not be simpler than using a relational db?
> Brainstorming, not flamestorming.

Here's a lightweight solution that uses lazy calculation of the reverse 
dict. It makes a number of assumptions:

- both keys and values will be hashable and unique;
- the dict won't be so large that calculating the reverse dictionary will 
be time consuming;
- modifications to instance.reverse are undefined.


Usage:


>>> d = ReverseDict(x=2, y=3, z=4)
>>> d['x']
2
>>> d.reverse[2]
'x'
>>> d['a'] = 0
>>> d.reverse[0]
'a'





def make_dirty(func):
    from functools import wraps
    @wraps(func)
    def f(self, *args, **kwargs):
        self._dirty = True
        return func(self, *args, **kwargs)
    return f


# only tested a little bit
class ReverseDict(dict):
    def __init__(self, *args, **kwargs):
        super(ReverseDict, self).__init__(*args, **kwargs)
        self._dirty = True
    @make_dirty
    def clear():
        super(ReverseDict, self).clear()
    @make_dirty
    def __setitem__(self, key, value):
        super(ReverseDict, self).__setitem__(key, value)
    @make_dirty
    def __delitem__(self, key):
        super(ReverseDict, self).__delitem__()
    @make_dirty
    def pop(self, key, *arg):
        return super(ReverseDict, self).pop(key, *arg)
    @make_dirty
    def popitem(self):
        return super(ReverseDict, self).popitem()
    @make_dirty
    def setdefault(self, key, value=None):
        return super(ReverseDict, self).setdefault(key, value)
    @make_dirty
    def update(self, other):
        return super(ReverseDict, self).update(other)
    @property
    def reverse(self):
        if self._dirty:
            # Modify this to support repeated and non-hashable values.
            self._reverse = dict((value, key) for 
            (key, value) in self.iteritems())
            self._dirty = False
        return self._reverse




An even more lightweight solution is to give up O(1) for the reverse 
lookup:


# untested
class ReversableDict(dict):
    def lookupvalue(self, value):
        for k,v in self.iteritems():
            if v == value: return k
        raise ValueError('value not found')
    def lookupallvalues(self, value):
        results = []
        for k,v in self.iteritems():
            if v == value: results.append(k)
        return results




-- 
Steven