This is a class that acts like a dictionary, except that it maintains insert order. This can be useful when you wish to associate two objects in a key-value manner and would like to use a dictionary interface to access the elements, but you need to remember what order the elements were added
Python, 40 lines
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 | class OrderedDictionary:
def __init__(self):
self._keys=[]
self._values=[]
def __len__ (self):
return len (sef.keys)
def __getitem__ (self, key):
if self.has_key (key):
return self._values[self._keys.index(key)]
else:
return None
def __setitem__ (self, key, value):
if self.has_key (key):
self._values [self._keys.index(key)] = value
else:
self._keys.append(key)
self._values.append(value)
def __delitem__(self, key):
val = self[key]
self._keys.remove(key)
self._values.remove (val)
def has_key (self, aKey):
return aKey in self._keys
def keys (self):
return self._keys
def values (self):
return self._values
def items (self):
return map (None, self._keys, self._values)
|
not entirely unlike a dict. This is a nice class that people will find useful, but it needs some work.
I see a potential ERROR in __delitem__. The list.remove() command removes the first matching item in the list. So if two items have the same value, trouble will ensue if you try to remove the second of these two items. The key of the second item will be removed and the value of the first item will be removed. This will distort the key,value alignment of the dict for all items between the first and second item mentioned.
SOLUTION: find the index of the key you are deleting, delete the key, and then delete the value at the same index.
Also, a WARNING:
__getitem__ returns "None" when a key is not present. This is instead of raising a KeyError like a regular dict.
Using index() may be time-expensive. Using index() to locate a value in the _values list may be time-expensive if there are a large number of items. It may be better for the class to use its own dictionary to store the items (albeit at the cost of space), with the _keys list keeping track of the order.
Correction. Of course I meant the _keys list rather than the _values list!
Typos. def __len__ (self): return len(self._keys)