class opdict(dict):
    """
    Minimal order preserving dictionary.  Uses a list of keys in addition
    to an internal dictionary to keep track of the order in which entries are
    added to the dictionary.  Calls to keys(), values(), items(), iterkeys(),
    itervalues() and iteritems() and popitem() will return data in the order
    that it was added to the dictionary.

    This class is intended as a drop in replacement for the builtin dict type
    and replicates all its methods.  While the internal representation would
    enable the addition of mutable sequence methods such as slices these have
    not (yet) been implemented.

    The motivation for creating this class was to stop the standard library
    ConfigParser module randomising the order of sections and options when
    saving modified configs back to a file.

    Anthony Horton
    horton@ast.cam.ac.uk
    20050216
    """

    def __init__(self, arg={}, **kwargs):

        # Dictionarys can be initialised with a mapping, an iterator object,
        # a sequence or (since Python 2.3) keyword arguments.  Most of these
        # methods of initialising don't provide or allow for any preferred
        # ordering, but if given a sequence type (or corresponding iterator)
        # we should retain the ordering.

        if kwargs and not arg:
            # Keyword initialisation
            dict.__init__(self, kwargs)
            self.__keylist = dict.keys(self)
        else:
            # Have a positional argument which is either a mapping, a sequence,
            # some other sort of iterable container, or an iterator.

            if hasattr(arg, 'keys'):
                # Argument is almost certainly some sort of mapping.
                dict.__init__(self, arg)
                # Store the keys
                self.__keylist = arg.keys()

            else:
                self.__keylist = []
                dict.__init__({})
                # Argument is either a sequence, some other sort of iterable
                # container, or an iterator.  For all of these should iterate
                # through in order, added them to the dictionary and keylist.
                for item in arg:
                    self.__setitem__(*item)

            # May also have some keyword arguments.
            if kwargs:
                self.update(kwargs)
                self.__keylist.extend(kwargs.keys())

    def __delitem__(self, key):
        dict.__delitem__(self, key)
        self.__keylist.remove(key)

    def __setitem__(self, key, value):
        has_key = self.has_key(key)
        dict.__setitem__(self, key, value)
        if not has_key:
            self.__keylist.append(key)

    def __iter__(self):
        return self.iterkeys()

    def __str__(self):
        return '{' + ', '.join(\
            [': '.join((repr(key), repr(self[key]))) for key in self.keys()]\
            ) + '}'
    
    def __repr__(self):
        return self.__str__()

    def keys(self):
        return self.__keylist[:]

    def values(self):
        return [self[key] for key in self.keys()]

    def items(self):
        return [(key, self[key]) for key in self.keys()]

    def iterkeys(self):
        return iter(self.keys())

    def itervalues(self):
        return iter(self.values())

    def iteritems(self):
        return iter(self.items())

    def update(self, opd):
        for key in opd:
            self[key] = opd[key]

    def pop(self, key, default=None):
        if self.has_key(key):
            value = self[key]
            del self[key]
            return value
        else:
            if default:
                return default
            else:
                raise KeyError(key)

    def popitem(self):
        if not self.__keylist:
            raise KeyError
        key = self.__keylist[-1]
        item = (key, self[key])
        del self[key]
        return item

    def copy(self):
        return opdict(self.items())

    def clear(self):
        dict.clear(self)
        self.__keylist = []

    def fromkeys(keys, value=None):
        opd = opdict()
        for key in keys:
            opd[key] = value
        return opd

    def setdefault(self, key, default=None):
        try:
            return self[key]
        except KeyError:
            self[key] = default
            return default