maggie maggie - 1 month ago 17
Python Question

How to implement insert for OrderedDict in python 3

I want to insert an item into an OrderedDict at a certain position.
Using the gist of this SO answer i have the problem that it doesn't work on python 3.

This is the implementation used

from collections import OrderedDict

class ListDict(OrderedDict):

def __init__(self, *args, **kwargs):
super(ListDict, self).__init__(*args, **kwargs)

def __insertion(self, link_prev, key_value):
key, value = key_value
if link_prev[2] != key:
if key in self:
del self[key]
link_next = link_prev[1]
self._OrderedDict__map[key] = link_prev[1] = link_next[0] = [link_prev, link_next, key]
dict.__setitem__(self, key, value)

def insert_after(self, existing_key, key_value):
self.__insertion(self._OrderedDict__map[existing_key], key_value)

def insert_before(self, existing_key, key_value):
self.__insertion(self._OrderedDict__map[existing_key][0], key_value)


Using it like

ld = ListDict([(1,1), (2,2), (3,3)])
ld.insert_before(2, (1.5, 1.5))


gives

File "...", line 35, in insert_before
self.__insertion(self._OrderedDict__map[existing_key][0], key_value)
AttributeError: 'ListDict' object has no attribute '_OrderedDict__map'


It works with python 2.7. What is the reason that it fails in python 3?
Checking the source code of the OrderedDict implementation shows that
self.__map
is used instead of
self._OrderedDict__map
. Changing the code to the usage of
self.__map
gives

AttributeError: 'ListDict' object has no attribute '_ListDict__map'


How come? And how can i make this work in python 3? OrderedDict uses the internal
__map
attribute to store a doubly linked list. So how can i access this attribute properly?

Answer

I'm not sure you wouldn't be better served just keeping up with a separate list and dict in your code, but here is a stab at a pure Python implementation of such an object. This will be an order of magnitude slower than an actual OrderedDict in Python 3.5, which as I pointed out in my comment has been rewritten in C.

"""
A list/dict hybrid; like OrderedDict with insert_before and insert_after
"""
import collections.abc


class MutableOrderingDict(collections.abc.MutableMapping):
    def __init__(self, iterable_or_mapping=None, **kw):
        # This mimics dict's initialization and accepts the same arguments
        # Of course, you have to pass an ordered iterable or mapping unless you
        # want the order to be arbitrary. Garbage in, garbage out and all :)
        self.__data = {}
        self.__keys = []
        if iterable_or_mapping is not None:
            try:
                iterable = iterable_or_mapping.items()
            except AttributeError:
                iterable = iterable_or_mapping
            for key, value in iterable:
                self.__keys.append(key)
                self.__data[key] = value
        for key, value in kw.items():
            self.__keys.append(key)
            self.__data[key] = value

    def insert_before(self, key, new_key, value):
        try:
            self.__keys.insert(self.__keys.index(key), new_key)
        except ValueError:
            raise KeyError(key) from ValueError
        else:
            self.__data[new_key] = value

    def insert_after(self, key, new_key, value):
        try:
            self.__keys.insert(self.__keys.index(key) + 1, new_key)
        except ValueError:
            raise KeyError(key) from ValueError
        else:
            self.__data[new_key] = value

    def __getitem__(self, key):
        return self.__data[key]

    def __setitem__(self, key, value):
        self.__keys.append(key)
        self.__data[key] = value

    def __delitem__(self, key):
        del self.__data[key]
        self.__keys.remove(key)

    def __iter__(self):
        return iter(self.__keys)

    def __len__(self):
        return len(self.__keys)

    def __contains__(self, key):
        return key in self.__keys

    def __eq__(self, other):
        try:
            return (self.__data == dict(other.items()) and
                    self.__keys == list(other.keys()))
        except AttributeError:
            return False

    def keys(self):
        for key in self.__keys:
            yield key

    def items(self):
        for key in self.__keys:
            yield key, self.__data[key]

    def values(self):
        for key in self.__keys:
            yield self.__data[key]

    def get(self, key, default=None):
        try:
            return self.__data[key]
        except KeyError:
            return default

    def pop(self, key, default=None):
        value = self.get(key, default)
        self.__delitem__(key)
        return value

    def popitem(self):
        try:
            return self.__data.pop(self.__keys.pop())
        except IndexError:
            raise KeyError('%s is empty' % self.__class__.__name__)


    def clear(self):
        self.__keys = []
        self.__data = {}

    def update(self, mapping):
        for key, value in mapping.items():
            self.__keys.append(key)
            self.__data[key] = value

    def setdefault(self, key, default):
        try:
            return self[key]
        except KeyError:
            self[key] = default
            return self[key]

    def __repr__(self):
        return 'MutableOrderingDict(%s)' % ', '.join(('%r: %r' % (k, v)
                                                      for k, v in self.items()))

I ended up implementing the whole collections.abc.MutableMapping contract because none of the methods were very long, but you probably won't use all of them. In particular, __eq__ and popitem are a little arbitrary. I changed your signature on the insert_* methods to a 4-argument one that feels a little more natural to me. Final note: Only tested on Python 3.5. Certainly will not work on Python 2 without some (minor) changes.