conestack / odict Goto Github PK

Dictionary in which the insertion order of items is preserved (using an internal double linked list). In this implementation replacing an existing item keeps it at its original position.

Internal representation: values of the dict.

[pred_key, val, succ_key]

The sequence of elements uses as a double linked list. The links are dict keys. self.lh and self.lt are the keys of first and last element inserted in the odict.

When this package was created, collections.OrderedDict not existed yet.

Another problem is that dict cannot always be inherited from in conjunction with other base classes. This may result in instance layout conflicts or other errors. So odict is written in a way that let you alter the dictionary base implementation.

Import and create ordered dictionary.

from odict import odict
od = odict()

It is possible to use _odict base class to implement an ordered dict not inheriting from dict type. This is useful i.e. when persisting to ZODB.

Inheriting from dict and Persistent at the same time fails. Also, using a regular list for the internal double linked list representation causes problems, so we define a custom class for it as well.

from persistent.dict import PersistentDict
from persistent.list import PersistentList

class podict(_odict, PersistentDict):

    def _dict_impl(self):
        return PersistentDict

    def _list_factory(self):
        return PersistentList

In Python < 3.7 casting to dict will fail. The reason for this can be found here. The __init__ function of dict checks whether arg is subclass of dict, and ignores overwritten __getitem__ & co if so. This was fixed and later reverted due to behavioural problems with pickle:

>>> dict(odict([(1, 1)]))
{1: [nil, 1, nil]}

Use one of the following ways for type conversion.

>>> dict(odict([(1, 1)]).items())
{1: 1}

>>> odict([(1, 1)]).as_dict()
{1: 1}

In a C reimplementation of this data structure, things could be simplified (and speed up) a lot if given a value you can at the same time find its key. With that, you can use normal C pointers.

• Python 2.7, 3.7+
• Probably works with other/older versions

• bearophile (Original Author)
• Robert Niederreiter (Author)
• Georg Bernhard
• Florian Friesdorf
• Jens Klein

under the Python Software Foundation License.