Python User Controlable Ordered Dictionary: one can actually control the item order.

arbitrarily_ordered_dict

"""Class that represents an ordered dict over which
the user can actually control the item order, and
replace keys already in the dicionary in their
original insertion place.

It also does that in O[1]

If used intenselly, where memory leak of
items deleted might be a problem, the
".compact" method should be called from
time to time to reindex the dictionary


"""


from collections.abc import MutableMapping

_deleted = object()

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)
            position = len(self.order) - 1
            self.data[key] = (position, value)
        else:
            self.data[key] = (self.data[key][0], value)
    def __getitem__(self, key):
        return self.data[key][1]
    def __delitem__(self, key):
        position = self.data[key][0]
        del self.data[key]
        self.order[position] = _deleted
    def __len__(self):
        return len(self.data)
    def __iter__(self):
        for value in self.order:
            if value is not _deleted:
                yield value
        
    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] = position, value
        
    def compact(self):
        """Removes deleted item information from order metadata"""
        offset = 0
        keys = iter(self)
        new_index = 0
        new_indexes = []
        for index in self.order:
            if index is _deleted:
                offset += 1
                continue
            new_indexes.append(new_index)
            key = next(keys)
            if offset:
                self.data[key] = new_index, self.data[key][1]
            new_index += 1
        self.order = new_indexes

    def __repr__(self):
        return f"{self.__class__.__name__}({{{', '.join('{}:{}'.format(key, self[key]) for key in self)}}})"