PEP 372: OrderedDict()
diff --git a/Lib/collections.py b/Lib/collections.py
index f8392b6..b65e12f 100644
--- a/Lib/collections.py
+++ b/Lib/collections.py
@@ -1,5 +1,5 @@
__all__ = ['deque', 'defaultdict', 'namedtuple', 'UserDict', 'UserList',
- 'UserString', 'Counter']
+ 'UserString', 'Counter', 'OrderedDict']
# For bootstrapping reasons, the collection ABCs are defined in _abcoll.py.
# They should however be considered an integral part of collections.py.
from _abcoll import *
@@ -11,7 +11,81 @@
from keyword import iskeyword as _iskeyword
import sys as _sys
import heapq as _heapq
-from itertools import repeat as _repeat, chain as _chain, starmap as _starmap
+from itertools import repeat as _repeat, chain as _chain, starmap as _starmap, \
+ zip_longest as _zip_longest
+
+################################################################################
+### OrderedDict
+################################################################################
+
+class OrderedDict(dict, MutableMapping):
+
+ def __init__(self, *args, **kwds):
+ if len(args) > 1:
+ raise TypeError('expected at most 1 arguments, got %d' % len(args))
+ if not hasattr(self, '_keys'):
+ self._keys = []
+ self.update(*args, **kwds)
+
+ def clear(self):
+ del self._keys[:]
+ dict.clear(self)
+
+ def __setitem__(self, key, value):
+ if key not in self:
+ self._keys.append(key)
+ dict.__setitem__(self, key, value)
+
+ def __delitem__(self, key):
+ dict.__delitem__(self, key)
+ self._keys.remove(key)
+
+ def __iter__(self):
+ return iter(self._keys)
+
+ def __reversed__(self):
+ return reversed(self._keys)
+
+ def popitem(self):
+ if not self:
+ raise KeyError('dictionary is empty')
+ key = self._keys.pop()
+ value = dict.pop(self, key)
+ return key, value
+
+ def __reduce__(self):
+ items = [[k, self[k]] for k in self]
+ inst_dict = vars(self).copy()
+ inst_dict.pop('_keys', None)
+ return (self.__class__, (items,), inst_dict)
+
+ setdefault = MutableMapping.setdefault
+ update = MutableMapping.update
+ pop = MutableMapping.pop
+ keys = MutableMapping.keys
+ values = MutableMapping.values
+ items = MutableMapping.items
+
+ def __repr__(self):
+ if not self:
+ return '%s()' % (self.__class__.__name__,)
+ return '%s(%r)' % (self.__class__.__name__, list(self.items()))
+
+ def copy(self):
+ return self.__class__(self)
+
+ @classmethod
+ def fromkeys(cls, iterable, value=None):
+ d = cls()
+ for key in iterable:
+ d[key] = value
+ return d
+
+ def __eq__(self, other):
+ if isinstance(other, OrderedDict):
+ return all(p==q for p, q in _zip_longest(self.items(), other.items()))
+ return dict.__eq__(self, other)
+
################################################################################