Two way/reverse map

Question

I'm doing this switchboard thing in python where I need to keep track of who's talking to whom, so if Alice --> Bob, then that implies that Bob --> Alice.

Yes, I could populate two hash maps, but I'm wondering if anyone has an idea to do it with one.

Or suggest another data structure.

There are no multiple conversations. Let's say this is for a customer service call center, so when Alice dials into the switchboard, she's only going to talk to Bob. His replies also go only to her.

Answer 1

Two hash maps is actually probably the fastest-performing solution assuming you can spare the memory. I would wrap those in a single class - the burden on the programmer is in ensuring that two the hash maps sync up correctly.

Answer 2

I know it's an older question, but I wanted to mention another great solution to this problem, namely the python package bidict. It's extremely straight forward to use:

from bidict import bidict
map = bidict(Bob = "Alice")
print(map["Bob"])
print(map.inv["Alice"])

Answer 3

Another possible solution is to implement a subclass of dict, that holds the original dictionary and keeps track of a reversed version of it. Keeping two seperate dicts can be useful if keys and values are overlapping.

class TwoWayDict(dict):
    def __init__(self, my_dict):
        dict.__init__(self, my_dict)
        self.rev_dict = {v : k for k,v in my_dict.iteritems()}

    def __setitem__(self, key, value):
        dict.__setitem__(self, key, value)
        self.rev_dict.__setitem__(value, key)

    def pop(self, key):
        self.rev_dict.pop(self[key])
        dict.pop(self, key)

    # The above is just an idea other methods
    # should also be overridden. 

Example:

>>> d = {'a' : 1, 'b' : 2} # suppose we need to use d and its reversed version
>>> twd = TwoWayDict(d)    # create a two-way dict
>>> twd
{'a': 1, 'b': 2}
>>> twd.rev_dict
{1: 'a', 2: 'b'}
>>> twd['a']
1
>>> twd.rev_dict[2]
'b'
>>> twd['c'] = 3    # we add to twd and reversed version also changes
>>> twd
{'a': 1, 'c': 3, 'b': 2}
>>> twd.rev_dict
{1: 'a', 2: 'b', 3: 'c'}
>>> twd.pop('a')   # we pop elements from twd and reversed  version changes
>>> twd
{'c': 3, 'b': 2}
>>> twd.rev_dict
{2: 'b', 3: 'c'}

Answer 4

Here's one more two-way dictionary implementation by extending pythons dict class in case you didn't like any of those other ones:

class DoubleD(dict):
    """ Access and delete dictionary elements by key or value. """ 

    def __getitem__(self, key):
        if key not in self:
            inv_dict = {v:k for k,v in self.items()}
            return inv_dict[key]
        return dict.__getitem__(self, key)

    def __delitem__(self, key):
        if key not in self:
            inv_dict = {v:k for k,v in self.items()}
            dict.__delitem__(self, inv_dict[key])
        else:
            dict.__delitem__(self, key)

Use it as a normal python dictionary except in construction:

dd = DoubleD()
dd['foo'] = 'bar'

Answer 5

I would just populate a second hash, with

reverse_map = dict((reversed(item) for item in forward_map.items()))

Answer 6

There's the collections-extended library on pypi: https://pypi.python.org/pypi/collections-extended/0.6.0

Using the bijection class is as easy as:

RESPONSE_TYPES = bijection({
    0x03 : 'module_info',
    0x09 : 'network_status_response',
    0x10 : 'trust_center_device_update'
})
>>> RESPONSE_TYPES[0x03]
'module_info'
>>> RESPONSE_TYPES.inverse['network_status_response']
0x09