--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/web/lib/django/utils/datastructures.py Wed Jan 20 00:34:04 2010 +0100
@@ -0,0 +1,441 @@
+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 items(self):
+ item_list = []
+ for dict_ in self.dicts:
+ item_list.extend(dict_.items())
+ return item_list
+
+ 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):
+ from copy import deepcopy
+ return self.__class__([(key, deepcopy(value, memo))
+ for key, value in self.iteritems()])
+
+ def __setitem__(self, key, value):
+ super(SortedDict, self).__setitem__(key, value)
+ if key not in self.keyOrder:
+ self.keyOrder.append(key)
+
+ def __delitem__(self, key):
+ super(SortedDict, self).__delitem__(key)
+ self.keyOrder.remove(key)
+
+ def __iter__(self):
+ for k in self.keyOrder:
+ yield k
+
+ 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, super(SortedDict, self).__getitem__(key)
+
+ def keys(self):
+ return self.keyOrder[:]
+
+ def iterkeys(self):
+ return iter(self.keyOrder)
+
+ def values(self):
+ return map(super(SortedDict, self).__getitem__, self.keyOrder)
+
+ def itervalues(self):
+ for key in self.keyOrder:
+ yield super(SortedDict, self).__getitem__(key)
+
+ def update(self, dict_):
+ for k, v in dict_.items():
+ self.__setitem__(k, v)
+
+ def setdefault(self, key, default):
+ if key not in self.keyOrder:
+ 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 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
+