This dictionary class extends UserDict to record the order in which items are added. Calling keys(), values(), items(), etc. will return results in this order. This works similarly to the array type in PHP.
Download
Copy to clipboard1 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 | from UserDict import UserDict
class odict(UserDict):
def __init__(self, dict = None):
self._keys = []
UserDict.__init__(self, dict)
def __delitem__(self, key):
UserDict.__delitem__(self, key)
self._keys.remove(key)
def __setitem__(self, key, item):
UserDict.__setitem__(self, key, item)
if key not in self._keys: self._keys.append(key)
def clear(self):
UserDict.clear(self)
self._keys = []
def copy(self):
dict = UserDict.copy(self)
dict._keys = self._keys[:]
return dict
def items(self):
return zip(self._keys, self.values())
def keys(self):
return self._keys
def popitem(self):
try:
key = self._keys[-1]
except IndexError:
raise KeyError('dictionary is empty')
val = self[key]
del self[key]
return (key, val)
def setdefault(self, key, failobj = None):
UserDict.setdefault(self, key, failobj)
if key not in self._keys: self._keys.append(key)
def update(self, dict):
UserDict.update(self, dict)
for key in dict.keys():
if key not in self._keys: self._keys.append(key)
def values(self):
return map(self.get, self._keys)
|
Often it is useful to use a dictionary to store information where the order of that information matters. In Python, one must usually keep a list of keys and pass the list along with the dictionary to any functions that need to maintain this order. This implementation stores the list of keys internally and overrides the usual accessor methods to keep the list up to date with each operation.
Example:
>>> d = odict()
>>> d['a'] = 1
>>> d['b'] = 2
>>> d['c'] = 3
>>> d.items()
[('a', 1), ('b', 2), ('c', 3)]
popitem() has been fixed in this version to throw the correct exception on an empty dictionary.
Note that all operations on the key list are O(n).
Bug in __init__ regarding _keys. If UserDict.__init__ is actually passed a dictionary from __init__, then it will attempt to call update; but _keys isn't yet defined, and so an error will be raised. Therefore _keys must be defined first:
Bug in __init__ regarding _keys. I made the above change to the source. Thanks for catching this.
Ordered Dictionary at Parnassus. There is a more complete module addressing this topic under http://home.arcor.de/wolfgang.grafen/Python/Modules/Modules.html called seqdict.
seqdict keeps one value for one key
mseqdict keeps multiple values per key and is the closest emulation of areal world dictionary.
(Search Parnassus for seqdict)
Serious bug in copy(). There is a serious problem with copy() The returned object instance is one of UserDict not of odict. I use:
and for update:
keys() should return a copy of self._keys. It would be better to have
to prevent changes to self._keys by callers of the keys() method.
Bug in setdefault. setdefault returns the value (new or existing) for the given key.
here is a correct setdefault:
Extending to Sorted Dictionary. I needed a Sorted Dictionary and this Ordered Dictionary made a great starting point.
I substituted: bisect.insort(self._keys,key) for: self._keys.append(key)
in a few places and I was there.
Thanks for the help
variations in base class. you may want to derive from IterableUserDict to allow for things like [k for k in mydict].
or in python >=2.2: derive directly from dict.
if you cant decide, build a mixin using super() or a wrapper - this gives the ability to order any dict-like object