new_contents: # Copyright (c) 2009 Raymond Hettinger
  #
  # Permission is hereby granted, free of charge, to any person
  # obtaining a copy of this software and associated documentation files
  # (the "Software"), to deal in the Software without restriction,
  # including without limitation the rights to use, copy, modify, merge,
  # publish, distribute, sublicense, and/or sell copies of the Software,
  # and to permit persons to whom the Software is furnished to do so,
  # subject to the following conditions:
  #
  #     The above copyright notice and this permission notice shall be
  #     included in all copies or substantial portions of the Software.
  #
  #     THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  #     EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
  #     OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  #     NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
  #     HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
  #     WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  #     FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
  #     OTHER DEALINGS IN THE SOFTWARE.
  
  from UserDict import DictMixin
  
  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):
              if len(self) != len(other):
                  return False
              for p, q in  zip(self.items(), other.items()):
                  if p != q:
                      return False
              return True
          return dict.__eq__(self, other)
  
      def __ne__(self, other):
          return not self == other
  
subject: Add ordereddict for python 2.6 compatibility.