Welcome, guest | Sign In | My Account | Store | Cart

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, 34 lines
 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

6 comments

Brodie Rao 15 years, 4 months ago  # | flag

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.

Brodie Rao 15 years, 4 months ago  # | flag

__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), '])'])
Brodie Rao 15 years, 4 months ago  # | flag

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]
Anand Chitipothu 14 years, 5 months ago  # | flag

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
James Stroud 14 years, 2 months ago  # | flag

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.

Martin Miller 11 years, 5 months ago  # | flag

Re: odict not a dictionary.
FWIW, the problems previously mentioned with DictMixin and UserDict not being considered dictionaries has apparently been fixed -- at least it appears to be in Python 2.6.2, the version installed on the machine I'm using.

Created by Igor Ghisi on Wed, 31 May 2006 (PSF)
Python recipes (4591)
Igor Ghisi's recipes (1)

Required Modules

Other Information and Tasks