ActiveState Code

Recipe 496761: A more clean implementation for Ordered Dictionary

An Ordered Dict records the order in which items are added. This implementation uses much less code than the others by extending not well-known class DictMixin.

Python 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
from UserDict import DictMixin


class odict(DictMixin):
    
    def __init__(self):
        self._keys = []
        self._data = {}
        
        
    def __setitem__(self, key, value):
        if key not in self._data:
            self._keys.append(key)
        self._data[key] = value
        
        
    def __getitem__(self, key):
        return self._data[key]
    
    
    def __delitem__(self, key):
        del self._data[key]
        self._keys.remove(key)
        
        
    def keys(self):
        return list(self._keys)
    
    
    def copy(self):
        copyDict = odict()
        copyDict._data = self._data.copy()
        copyDict._keys = self._keys[:]
        return copyDict

Comments

  1. 1. At 1:52 p.m. on 5 aug 2006, Brodie Rao said:

    Some Suggestions. Adding the following to odict should allow its constructor to act like the dict() factory function, will preserve element order when converting from ordered sequences, and should repr() in order.

    def __init__(self, data=None, **kwdata):
    self._keys = []
    self._data = {}
    if data is not None:
        if hasattr(data, 'items'):
            items = data.items()
        else:
            items = list(data)
        for i in xrange(len(items)):
            length = len(items[i])
            if length != 2:
                raise ValueError('dictionary update sequence element '
                    '#%d has length %d; 2 is required' % (i, length))
            self._keys.append(items[i][0])
            self._data[items[i][0]] = items[i][1]
    if kwdata:
        self._merge_keys(kwdata.iterkeys())
        self.update(kwdata)


def __repr__(self):
    result = []
    for key in self._keys:
        result.append('%s: %s' % (repr(key), repr(self._data[key])))
    return ''.join(['{', ', '.join(result), '}'])


def _merge_keys(self, keys):
    self._keys.extend(keys)
    newkeys = {}
    self._keys = [newkeys.setdefault(x, x) for x in self._keys
        if x not in newkeys]


def update(self, data):
    if data is not None:
        if hasattr(data, 'iterkeys'):
            self._merge_keys(data.iterkeys())
        else:
            self._merge_keys(data.keys())
        self._data.update(data)

    And some tests:

    >>> odict({'one': 2, 'two': 3})
{'two': 3, 'one': 2}
>>> odict({'one': 2, 'two': 3}.items())
{'two': 3, 'one': 2}
>>> odict({'one': 2, 'two': 3}.iteritems())
{'two': 3, 'one': 2}
>>> odict(zip(('one', 'two'), (2, 3)))
{'one': 2, 'two': 3}
>>> odict([['two', 3], ['one', 2]])
{'two': 3, 'one': 2}
>>> odict(one=2, two=3)
{'two': 3, 'one': 2}
>>> odict([(['one', 'two'][i-2], i) for i in (2, 3)])
{'one': 2, 'two': 3}
>>> odict({'one': 1}, one=2)
{'one': 2}
>>> dict({'one': 1}, one=2)
{'one': 2}

    And I suppose you could add this so you aren't copying self._keys when calling __iter__:

    def __iter__(self):
    for key in self._keys:
        yield key

    Also, you probably should have named this "OrderedDict", to go along with the Python naming conventions.

  2. 2. At 7:09 p.m. on 5 aug 2006, Brodie Rao said:

    __repr__ Fix. Whoops, messed up __repr__ there. It should probably be something like this:

    def __repr__(self):
    result = []
    for key in self._keys:
        result.append('(%s, %s)' % (repr(key), repr(self._data[key])))
    return ''.join(['OrderedDict', '([', ', '.join(result), '])'])
  3. 3. At 7:39 p.m. on 5 aug 2006, Brodie Rao said:

    Slicing. Also, if you wanted to add slicing support, this should work:

    def __getitem__(self, key):
    if isinstance(key, slice):
        result = [(k, self._data[k]) for k in self._keys[key]]
        return OrderedDict(result)
    return self._data[key]
  4. 4. At 2:51 a.m. on 7 jun 2007, Anand Chitipothu said:

    odict not a dictionary. odict is a not really a dictionary. it can not be used as replacement of a dictionary.

    for example the following code fails.

    >>> from odict import odict
>>> def f(a, b): return a+b
...
>>> d = odict()
>>> d['a'] = 1
>>> d['b'] = 2
>>>
>>> d
{'a': 1, 'b': 2}
>>>
>>> f(**d)
Traceback (most recent call last):
  File "", line 1, in ?
TypeError: f() argument after ** must be a dictionary
  5. 5. At 5:03 p.m. on 12 sep 2007, James Stroud said:

    odict not a dictionary. This is a bug in the standard library, as UserDict is not a dictionary either:

    py> def doit(**args):
...   print args
...
py> from UserDict import UserDict
py> doit(**UserDict())
------------------------------------------------------------
Traceback (most recent call last):
  File "", line 1, in  : doit() argument after ** must be a dictionary

    In fact, I would classify this as a bug related to type checking and thus is a bug in the interpreter itself.

Sign in to comment