class MergeDict(object):

    """

    A simple class for creating new "virtual" dictionaries that actually look

    up values in more than one dictionary, passed in the constructor.

    If a key appears in more than one of the given dictionaries, only the

    first occurrence will be used.

    """

    def __init__(self, *dicts):

        self.dicts = dicts

    def __getitem__(self, key):

        for dict_ in self.dicts:

            try:

                return dict_[key]

            except KeyError:

                pass

        raise KeyError

    def __copy__(self):

        return self.__class__(*self.dicts)

    def get(self, key, default=None):

        try:

            return self[key]

        except KeyError:

            return default

    def getlist(self, key):

        for dict_ in self.dicts:

            if key in dict_.keys():

                return dict_.getlist(key)

        return []

        for dict_ in self.dicts:

    def has_key(self, key):

        for dict_ in self.dicts:

            if key in dict_:

                return True

        return False

    __contains__ = has_key

    def copy(self):

        """Returns a copy of this object."""

        return self.__copy__()

class SortedDict(dict):

    """

    A dictionary that keeps its keys in the order in which they're inserted.

    """

    def __new__(cls, *args, **kwargs):

        instance = super(SortedDict, cls).__new__(cls, *args, **kwargs)

        instance.keyOrder = []

        return instance

    def __init__(self, data=None):

        if data is None:

            data = {}

        super(SortedDict, self).__init__(data)

        if isinstance(data, dict):

            self.keyOrder = data.keys()

        else:

            self.keyOrder = []

            for key, value in data:

                if key not in self.keyOrder:

                    self.keyOrder.append(key)

    def __deepcopy__(self, memo):

        return self.__class__([(key, deepcopy(value, memo))

                               for key, value in self.iteritems()])

    def __setitem__(self, key, value):

        super(SortedDict, self).__setitem__(key, value)

    def __delitem__(self, key):

        super(SortedDict, self).__delitem__(key)

        self.keyOrder.remove(key)

    def __iter__(self):

    def pop(self, k, *args):

        result = super(SortedDict, self).pop(k, *args)

        try:

            self.keyOrder.remove(k)

        except ValueError:

            # Key wasn't in the dictionary in the first place. No problem.

            pass

        return result

    def popitem(self):

        result = super(SortedDict, self).popitem()

        self.keyOrder.remove(result[0])

        return result

    def items(self):

        return zip(self.keyOrder, self.values())

    def iteritems(self):

        for key in self.keyOrder:

    def keys(self):

        return self.keyOrder[:]

    def iterkeys(self):

        return iter(self.keyOrder)

    def values(self):

    def itervalues(self):

        for key in self.keyOrder:

    def update(self, dict_):

    def setdefault(self, key, default):

            self.keyOrder.append(key)

        return super(SortedDict, self).setdefault(key, default)

    def value_for_index(self, index):

        """Returns the value of the item at the given zero-based index."""

        return self[self.keyOrder[index]]

    def insert(self, index, key, value):

        """Inserts the key, value pair before the item with the given index."""

        if key in self.keyOrder:

            n = self.keyOrder.index(key)

            del self.keyOrder[n]

            if n < index:

                index -= 1

        self.keyOrder.insert(index, key)

        super(SortedDict, self).__setitem__(key, value)

    def copy(self):

        """Returns a copy of this object."""

        # This way of initializing the copy means it works for subclasses, too.

        obj = self.__class__(self)

        obj.keyOrder = self.keyOrder[:]

        return obj

    def __repr__(self):

        """

        Replaces the normal dict.__repr__ with a version that returns the keys

        in their sorted order.

        """

        return '{%s}' % ', '.join(['%r: %r' % (k, v) for k, v in self.items()])

    def clear(self):

        super(SortedDict, self).clear()

        self.keyOrder = []

class MultiValueDictKeyError(KeyError):

    pass

class MultiValueDict(dict):

    """

    A subclass of dictionary customized to handle multiple values for the

    same key.

    >>> d = MultiValueDict({'name': ['Adrian', 'Simon'], 'position': ['Developer']})

    >>> d['name']

    'Simon'

    >>> d.getlist('name')

    ['Adrian', 'Simon']

    >>> d.get('lastname', 'nonexistent')

    'nonexistent'

    >>> d.setlist('lastname', ['Holovaty', 'Willison'])

    This class exists to solve the irritating problem raised by cgi.parse_qs,

    which returns a list for every key, even though most Web forms submit

    single name-value pairs.

    """

    def __init__(self, key_to_list_mapping=()):

        super(MultiValueDict, self).__init__(key_to_list_mapping)

    def __repr__(self):

        return "<%s: %s>" % (self.__class__.__name__,

                             super(MultiValueDict, self).__repr__())

    def __getitem__(self, key):

        """

        Returns the last data value for this key, or [] if it's an empty list;

        raises KeyError if not found.

        """

        try:

            list_ = super(MultiValueDict, self).__getitem__(key)

        except KeyError:

        try:

            return list_[-1]

        except IndexError:

            return []

    def __setitem__(self, key, value):

        super(MultiValueDict, self).__setitem__(key, [value])

    def __copy__(self):

        return self.__class__(super(MultiValueDict, self).items())

    def __deepcopy__(self, memo=None):

        if memo is None:

            memo = {}

        result = self.__class__()

        memo[id(self)] = result

        for key, value in dict.items(self):

            dict.__setitem__(result, copy.deepcopy(key, memo),

                             copy.deepcopy(value, memo))

        return result

    def __getstate__(self):

        obj_dict = self.__dict__.copy()

        obj_dict['_data'] = dict([(k, self.getlist(k)) for k in self])

        return obj_dict

    def __setstate__(self, obj_dict):

        data = obj_dict.pop('_data', {})

        for k, v in data.items():

            self.setlist(k, v)

        self.__dict__.update(obj_dict)

    def get(self, key, default=None):

        """

        Returns the last data value for the passed key. If key doesn't exist

        or value is an empty list, then default is returned.

        """

        try:

            val = self[key]

        except KeyError:

            return default

        if val == []:

            return default

        return val

    def getlist(self, key):

        """

        Returns the list of values for the passed key. If key doesn't exist,

        then an empty list is returned.

        """

        try:

            return super(MultiValueDict, self).__getitem__(key)

        except KeyError:

            return []

    def setlist(self, key, list_):

        super(MultiValueDict, self).__setitem__(key, list_)

    def setdefault(self, key, default=None):

        if key not in self:

            self[key] = default

        return self[key]

    def setlistdefault(self, key, default_list=()):

        if key not in self:

            self.setlist(key, default_list)

        return self.getlist(key)

    def appendlist(self, key, value):

        """Appends an item to the internal list associated with key."""

        self.setlistdefault(key, [])

        super(MultiValueDict, self).__setitem__(key, self.getlist(key) + [value])

    def items(self):

        """

        Returns a list of (key, value) pairs, where value is the last item in

        the list associated with the key.

        """

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

    def iteritems(self):

        """

        Yields (key, value) pairs, where value is the last item in the list

        associated with the key.

        """

        for key in self.keys():

            yield (key, self[key])

    def lists(self):

        """Returns a list of (key, list) pairs."""

        return super(MultiValueDict, self).items()

    def iterlists(self):

        """Yields (key, list) pairs."""

        return super(MultiValueDict, self).iteritems()

    def values(self):

        """Returns a list of the last value on every key list."""

        return [self[key] for key in self.keys()]

    def itervalues(self):

        """Yield the last value on every key list."""

        for key in self.iterkeys():

            yield self[key]

    def copy(self):

        """Returns a copy of this object."""

        return self.__deepcopy__()

    def update(self, *args, **kwargs):

        """

        update() extends rather than replaces existing key lists.

        Also accepts keyword args.

        """

        if len(args) > 1:

        if args:

            other_dict = args[0]

            if isinstance(other_dict, MultiValueDict):

                for key, value_list in other_dict.lists():

                    self.setlistdefault(key, []).extend(value_list)

            else:

                try:

                    for key, value in other_dict.items():

                        self.setlistdefault(key, []).append(value)

                except TypeError:

        for key, value in kwargs.iteritems():

            self.setlistdefault(key, []).append(value)

class DotExpandedDict(dict):

    """

    A special dictionary constructor that takes a dictionary in which the keys

    may contain dots to specify inner dictionaries. It's confusing, but this

    example should make sense.

    >>> d = DotExpandedDict({'person.1.firstname': ['Simon'], \

            'person.1.lastname': ['Willison'], \

            'person.2.firstname': ['Adrian'], \

            'person.2.lastname': ['Holovaty']})

    >>> d

    {'person': {'1': {'lastname': ['Willison'], 'firstname': ['Simon']}, '2': {'lastname': ['Holovaty'], 'firstname': ['Adrian']}}}

    >>> d['person']

    {'1': {'lastname': ['Willison'], 'firstname': ['Simon']}, '2': {'lastname': ['Holovaty'], 'firstname': ['Adrian']}}

    >>> d['person']['1']

    {'lastname': ['Willison'], 'firstname': ['Simon']}

    # Gotcha: Results are unpredictable if the dots are "uneven":

    >>> DotExpandedDict({'c.1': 2, 'c.2': 3, 'c': 1})

    {'c': 1}

    """

    def __init__(self, key_to_list_mapping):

        for k, v in key_to_list_mapping.items():

            current = self

            bits = k.split('.')

            for bit in bits[:-1]:

                current = current.setdefault(bit, {})

            # Now assign value to current position

            try:

                current[bits[-1]] = v

            except TypeError: # Special-case if current isn't a dict.

                current = {bits[-1]: v}

class ImmutableList(tuple):

    """

    A tuple-like object that raises useful errors when it is asked to mutate.

    Example::

        >>> a = ImmutableList(range(5), warning="You cannot mutate this.")