ActiveState Code

Recipe 438823: Ordered Dictionary

Yet another ordered dict.

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
class odict(dict):

    def __init__(self, d={}):
        self._keys = d.keys()
        dict.__init__(self, d)

    def __delitem__(self, key):
        dict.__delitem__(self, key)
        self._keys.remove(key)

    def __setitem__(self, key, item):
        dict.__setitem__(self, key, item)
        # a peculiar sharp edge from copy.deepcopy
        # we'll have our set item called without __init__
        if not hasattr(self, '_keys'):
            self._keys = [key,]
        if key not in self._keys:
            self._keys.append(key)

    def clear(self):
        dict.clear(self)
        self._keys = []

    def items(self):
        items = []
        for i in self._keys:
            items.append(i, self[i])
        return items

    def keys(self):
        return self._keys

    def popitem(self):
        if len(self._keys) == 0:
            raise KeyError('dictionary is empty')
        else:
            key = self._keys[-1]
            val = self[key]
            del self[key]
            return key, val

    def setdefault(self, key, failobj = None):
        dict.setdefault(self, key, failobj)
        if key not in self._keys:
            self._keys.append(key)

    def update(self, d):
        for key in d.keys():
            if not self.has_key(key):
                self._keys.append(key)
        dict.update(self, d)

    def values(self):
        v = []
        for i in self._keys:
            v.append(self[i])
        return v

    def move(self, key, index):

        """ Move the specified to key to *before* the specified index. """

        try:
            cur = self._keys.index(key)
        except ValueError:
            raise KeyError(key)
        self._keys.insert(index, key)
        # this may have shifted the position of cur, if it is after index
        if cur >= index: cur = cur + 1
        del self._keys[cur]

    def index(self, key):
        if not self.has_key(key):
            raise KeyError(key)
        return self._keys.index(key)

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

Discussion

This one is a bit neater than the other ordered dict in here, using generators in places where it can, and plays nicely with deepcopy.

Comments

  1. 1. At 8:33 a.m. on 20 feb 2007, x x said:

    not compatible with pprint.

    Traceback (most recent call last):
  File "verbs.py", line 71, in ?
    pprint.pprint(result)
  File "/usr/lib/python2.4/pprint.py", line 55, in pprint
    printer.pprint(object)
  File "/usr/lib/python2.4/pprint.py", line 106, in pprint
    self._stream.write(self.pformat(object) + "\n")
  File "/usr/lib/python2.4/pprint.py", line 110, in pformat
    self._format(object, sio, 0, 0, {}, 0)
  File "/usr/lib/python2.4/pprint.py", line 144, in _format
    items.sort()
AttributeError: 'generator' object has no attribute 'sort'



Any solution?
  2. 2. At 2:59 a.m. on 7 jun 2007, Anand Chitipothu said:

    Problems. There are some problems with this implementation.

    values() and items() must return a list.

    since iterkeys() and __iter__() methods are not implemented, for k in d: returns keys in the any order.

  3. 3. At 4:25 a.m. on 23 dec 2007, Doug Winter (the author) said:

    Thanks guys. Thanks for the feedback, I've updated the recipe which should sort those problems I hope.

  4. 4. At 10:34 a.m. on 27 dec 2007, Yongsub Chung said:

    items(), append function. maybe you wanted to write:

    items.append((i, self[i]))

    rather than

    items.append(i, self[i])

    passing 2 parameters fails to match function signature.

Sign in to comment