[kupfer] datatools: Include OrderedDict

[Ulrik Sverdrup <usverdrup src gnome org>]

commit f8d26aaa822a9bd8aac66e3838927a53618dfdb7
Author: Ulrik Sverdrup <ulrik sverdrup gmail com>
Date:   Sat Apr 2 01:50:41 2011 +0200

    datatools: Include OrderedDict
    
    Including Raymond Hettinger's Ordered dict recipe::
    
        http://code.activestate.com/recipes/576693/
        Created by Raymond Hettinger on Wed, 18 Mar 2009 (MIT)
        Licensed under the MIT License

 kupfer/datatools.py |  115 +++++++++++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 115 insertions(+), 0 deletions(-)
---
diff --git a/kupfer/datatools.py b/kupfer/datatools.py
index c5ae3e8..2de858b 100644
--- a/kupfer/datatools.py
+++ b/kupfer/datatools.py
@@ -1,5 +1,11 @@
 import itertools
 
+try:
+	from collections import OrderedDict
+except ImportError:
+	from UserDict import DictMixin
+	OrderedDict = None
+
 class SavedIterable (object):
 	"""Wrap an iterable and cache it.
 
@@ -93,6 +99,115 @@ def UniqueIterator(seq, key=None):
 				yield obj
 				coll.add(K)
 
+
+if not OrderedDict:
+	"""
+	The following is:
+	http://code.activestate.com/recipes/576693/
+	Created by Raymond Hettinger on Wed, 18 Mar 2009 (MIT) 
+	Licensed under the MIT License
+	"""
+
+	class OrderedDict(dict, DictMixin):
+
+		def __init__(self, *args, **kwds):
+			if len(args) > 1:
+				raise TypeError('expected at most 1 arguments, got %d' % len(args))
+			try:
+				self.__end
+			except AttributeError:
+				self.clear()
+			self.update(*args, **kwds)
+
+		def clear(self):
+			self.__end = end = []
+			end += [None, end, end]         # sentinel node for doubly linked list
+			self.__map = {}                 # key --> [key, prev, next]
+			dict.clear(self)
+
+		def __setitem__(self, key, value):
+			if key not in self:
+				end = self.__end
+				curr = end[1]
+				curr[2] = end[1] = self.__map[key] = [key, curr, end]
+			dict.__setitem__(self, key, value)
+
+		def __delitem__(self, key):
+			dict.__delitem__(self, key)
+			key, prev, next = self.__map.pop(key)
+			prev[2] = next
+			next[1] = prev
+
+		def __iter__(self):
+			end = self.__end
+			curr = end[2]
+			while curr is not end:
+				yield curr[0]
+				curr = curr[2]
+
+		def __reversed__(self):
+			end = self.__end
+			curr = end[1]
+			while curr is not end:
+				yield curr[0]
+				curr = curr[1]
+
+		def popitem(self, last=True):
+			if not self:
+				raise KeyError('dictionary is empty')
+			if last:
+				key = reversed(self).next()
+			else:
+				key = iter(self).next()
+			value = self.pop(key)
+			return key, value
+
+		def __reduce__(self):
+			items = [[k, self[k]] for k in self]
+			tmp = self.__map, self.__end
+			del self.__map, self.__end
+			inst_dict = vars(self).copy()
+			self.__map, self.__end = tmp
+			if inst_dict:
+				return (self.__class__, (items,), inst_dict)
+			return self.__class__, (items,)
+
+		def keys(self):
+			return list(self)
+
+		setdefault = DictMixin.setdefault
+		update = DictMixin.update
+		pop = DictMixin.pop
+		values = DictMixin.values
+		items = DictMixin.items
+		iterkeys = DictMixin.iterkeys
+		itervalues = DictMixin.itervalues
+		iteritems = DictMixin.iteritems
+
+		def __repr__(self):
+			if not self:
+				return '%s()' % (self.__class__.__name__,)
+			return '%s(%r)' % (self.__class__.__name__, 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 len(self)==len(other) and self.items() == other.items()
+			return dict.__eq__(self, other)
+
+		def __ne__(self, other):
+			return not self == other
+
+
 if __name__ == '__main__':
 	import doctest
 	doctest.testmod()