blinkster: comparison web/lib/django/utils/datastructures.py

equal deleted inserted replaced

-:8d941af65caf
+:77b6da96e6f1
+from types import GeneratorType
+from django.utils.copycompat import deepcopy
+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 []
+def iteritems(self):
+seen = set()
+for dict_ in self.dicts:
+for item in dict_.iteritems():
+k, v = item
+if k in seen:
+continue
+seen.add(k)
+yield item
+def iterkeys(self):
+for k, v in self.iteritems():
+yield k
+def itervalues(self):
+for k, v in self.iteritems():
+yield v
+def items(self):
+return list(self.iteritems())
+def keys(self):
+return list(self.iterkeys())
+def values(self):
+return list(self.itervalues())
+def has_key(self, key):
+for dict_ in self.dicts:
+if key in dict_:
+return True
+return False
+__contains__ = has_key
+__iter__ = iterkeys
+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 = {}
+elif isinstance(data, GeneratorType):
+# Unfortunately we need to be able to read a generator twice.  Once
+# to get the data into self with our super().__init__ call and a
+# second time to setup keyOrder correctly
+data = list(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):
+if key not in self:
+self.keyOrder.append(key)
+super(SortedDict, self).__setitem__(key, value)
+def __delitem__(self, key):
+super(SortedDict, self).__delitem__(key)
+self.keyOrder.remove(key)
+def __iter__(self):
+return iter(self.keyOrder)
+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:
+yield key, self[key]
+def keys(self):
+return self.keyOrder[:]
+def iterkeys(self):
+return iter(self.keyOrder)
+def values(self):
+return map(self.__getitem__, self.keyOrder)
+def itervalues(self):
+for key in self.keyOrder:
+yield self[key]
+def update(self, dict_):
+for k, v in dict_.iteritems():
+self[k] = v
+def setdefault(self, key, default):
+if key not in self:
+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:
+raise MultiValueDictKeyError("Key %r not found in %r" % (key, self))
+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):
+import django.utils.copycompat as copy
+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:
+raise TypeError("update expected at most 1 arguments, got %d" % len(args))
+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:
+raise ValueError("MultiValueDict.update() takes either a MultiValueDict or dictionary")
+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.")
+>>> a[3] = '4'
+Traceback (most recent call last):
+...
+AttributeError: You cannot mutate this.
+"""
+def __new__(cls, *args, **kwargs):
+if 'warning' in kwargs:
+warning = kwargs['warning']
+del kwargs['warning']
+else:
+warning = 'ImmutableList object is immutable.'
+self = tuple.__new__(cls, *args, **kwargs)
+self.warning = warning
+return self
+def complain(self, *wargs, **kwargs):
+if isinstance(self.warning, Exception):
+raise self.warning
+else:
+raise AttributeError(self.warning)
+# All list mutation functions complain.
+__delitem__  = complain
+__delslice__ = complain
+__iadd__     = complain
+__imul__     = complain
+__setitem__  = complain
+__setslice__ = complain
+append       = complain
+extend       = complain
+insert       = complain
+pop          = complain
+remove       = complain
+sort         = complain
+reverse      = complain
+class DictWrapper(dict):
+"""
+Wraps accesses to a dictionary so that certain values (those starting with
+the specified prefix) are passed through a function before being returned.
+The prefix is removed before looking up the real value.
+Used by the SQL construction code to ensure that values are correctly
+quoted before being used.
+"""
+def __init__(self, data, func, prefix):
+super(DictWrapper, self).__init__(data)
+self.func = func
+self.prefix = prefix
+def __getitem__(self, key):
+"""
+Retrieves the real value after stripping the prefix string (if
+present). If the prefix is present, pass the value through self.func
+before returning, otherwise return the raw value.
+"""
+if key.startswith(self.prefix):
+use_func = True
+key = key[len(self.prefix):]
+else:
+use_func = False
+value = super(DictWrapper, self).__getitem__(key)
+if use_func:
+return self.func(value)
+return value