diff options
Diffstat (limited to 'parts/django/django/utils/datastructures.py')
| -rw-r--r-- | parts/django/django/utils/datastructures.py | 473 |
1 files changed, 473 insertions, 0 deletions
diff --git a/parts/django/django/utils/datastructures.py b/parts/django/django/utils/datastructures.py new file mode 100644 index 0000000..d73963f --- /dev/null +++ b/parts/django/django/utils/datastructures.py @@ -0,0 +1,473 @@ +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 = [] + seen = set() + for key, value in data: + if key not in seen: + self.keyOrder.append(key) + seen.add(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 + |