Is it possible to swap two keys of an ordered dictionary?

Question

Note: I am using python 3.8.2, so dictionaries are considered ordered

I was creating a binary tree, and I used dictionaries to model the tree. For example: {1:[2, 3], 2:[4, 5], 3:[], 4:[], 5:[]}

In the example, the tree above would look like this:

I was trying to simulate the ‘rising’ of some nodes, and keep the order of the dict as well. I know that using myDict[key1], myDict[key2] = myDict[key2], myDict[key1] won’t work, as the places of the values change, not the keys.

I was also thinking of using .popitem() to remove the last value until I’m either at key1 or key2, and the keep going until I get to the other key, but this seems kinda hard. Is there any other way to do this?

user_14324945 · Answer

Since you only want to swap two keys, we could start off with the following code:

>>> changedDict = {}
>>> for key, value in myDict.items():
...     if key not in (key1, key2):
...         changedDict[key] = value

And continue as follows:

...     elif key == key1:
...         changedDict[key] = myDict[key2]
...     else:
...         changedDict[key] = myDict[key1]

user_108205 · Answer

Dictionaries, although they now keep the insertion order, are not arbitrarily orderable otherwise. If you want really to use the dict order information to build your tree, I think the only reliable way would be to build a fresh dictionary, copying the contents of the original one, for each of these swap operations.

A more reasonable approach, if you want an arbitrarily ordered dictionary would be to inherit from collections.abc.MutableMappingand kep track of your data inside that object, using a dictionary and some other data structure, such as a list.

It may sound complicated, but it may be simpler than you think:

from collections.abc import MutableMapping

class SuperOrdered(MutableMapping):
    def __init__(self):
        self.data = {}
        self.order = []
    def __setitem__(self, key, value):
        if key not in self.data:
            self.order.append(key)
        self.data[key] = value
    def __getitem__(self, key):
        return self.data[key]
    def __delitem__(self, key):
        del self.data[key]
        self.order.remove(key)
    def __len__(self):
        return len(self.data)
    def __iter__(self):
        yield from iter(self.order)
    def replace_key(self, oldkey, newkey, value):
        if newkey in self.data:
            del self[newkey]
        position = self.order.index(oldkey)
        self.order[position] = newkey
        self.data[newkey] = value
    def __repr__(self):
        return f"{self.__class__.__name__}({{{', '.join(repr(key) + ':' + repr(self.data[key]) for key in self)}}})"

And voilá - the mapping + the "replace_key" method should be enough for you to build your tree as you are thinking about it.

This is the class above in the interactive prompt:

In [18]: aa = SuperOrdered()                                                                                             

In [19]: aa["a"] = 1;aa["b"] = 2;aa["c"] = 3                                                                             

In [20]: aa                                                                                                              
Out[20]: SuperOrdered({'a':1, 'b':2, 'c':3})

In [21]: aa.replace_key("a", "d", 4)                                                                                     

In [22]: aa                                                                                                              
Out[22]: SuperOrdered({'d':4, 'b':2, 'c':3})

Apart from this answer, and out of topic: if you want to check a tree implementation that I hope is "production ready", I've published one as part of my extradict package (pip installable).

update: One might also inherit from collections.OrderedDict and add a replace_key method there. That code would have to deal with OrderedDict internals, but it would not be hard.

External links: Github modification

Is it possible to swap two keys of an ordered dictionary?

2 Answers