CODEWITHSUNDEEP
pythondictionary
ted
ted

Reputation: 4975

Data structure to implement a dictionary with multiple indexes?

I am looking for a data structure that holds the same values under two different indexes, where I can access the data by either one.

Example:

x = mysticalDataStructure()
x.add(1,'karl', dog)
x.add(2,'lisa', cat)

$ x[1].age
2
$ x['karl'].age
2
$ x[1].age = 4
$ x['karl'].age
4

Is there anything prerolled, or what is the best approach to roll my own (I need access via an index (number going from 0 to n in increments of 1), and via a string).

collections.ordereddict does not seem to have fast random access via the position, as far as I see I can only walk it with the iterator until I reach element i (I can insert in the right order).

Upvotes: 13

Views: 14679

Answers (3)

Aleksei astynax Pirogov
Aleksei astynax Pirogov

Reputation: 2491

class MultiKeyDict(object):

    def __init__(self, **kwargs):
        self._keys = {}
        self._data = {}
        for k, v in kwargs.iteritems():
            self[k] = v

    def __getitem__(self, key):
        try:
            return self._data[key]
        except KeyError:
            return self._data[self._keys[key]]

    def __setitem__(self, key, val):
        try:
            self._data[self._keys[key]] = val
        except KeyError:
            if isinstance(key, tuple):
               if not key:
                  raise ValueError(u'Empty tuple cannot be used as a key')
               key, other_keys = key[0], key[1:]
            else:
               other_keys = []
            self._data[key] = val
            for k in other_keys:
                self._keys[k] = key

    def add_keys(self, to_key, new_keys):
        if to_key not in self._data:
            to_key = self._keys[to_key]
        for key in new_keys:
            self._keys[key] = to_key


    @classmethod
    def from_dict(cls, dic):
        result = cls()
        for key, val in dic.items():
            result[key] = val
        return result

Usage:

>>> d = MultiKeyDict(a=1, b=2)
>>> d['c', 'd'] = 3 # two keys for one value
>>> print d['c'], d['d']
3 3
>>> d['c'] = 4
>>> print d['d']
4
>>> d.add_keys('d', ('e',))
>>> d['e']
4
>>> d2 = MultiKeyDict.from_dict({ ('a', 'b'): 1 })
>>> d2['a'] = 2
>>> d2['b']
2

Upvotes: 13

Trevor
Trevor

Reputation: 9578

Is there a particular reason you can't just use a dictionary:

x = {}
x[1] = x['karl'] = dog
x[2] = x['lisa'] = cat

Then you can access it by either.

If you really don't want to repeat your self you do this:

class MysticalDataStructure(dict):
    def add(self, key1, key2, value):
        return self[key1] = self[key2] = value

x = MysticalDataStructure()
x.add(1, 'karl', dog)
x.add(2, 'lisa', cat)

Upvotes: 12

Has QUIT--Anony-Mousse
Has QUIT--Anony-Mousse

Reputation: 77454

Just use three maps.

maps = [dict(), dict(), dict()]

def insert(rec):
   maps[0][rec[0]] = rec
   maps[1][rec[1]] = rec
   maps[2][rec[2]] = rec

Changes to key attributes of the rec object will require reinsertion though. Just like any other map, when you change the key of an object.

The maps just map key -> object, after all. They don't actually store copies of the object (it just isn't garbage collected). So a map is an index, nothing more. If you want three indexes, use three maps. Write a couple of glue code functions to manage them.

As mentioned by Trevor, you can also use a shared dictionary:

index = dict()

def insert(rec):
    index[rec[0]] = rec
    index[rec[1]] = rec
    index[rec[2]] = rec

then you can access it by either.

Beware of key collisions though!

Upvotes: 2

Related Questions