app/django/utils/datastructures.py

   1 class MergeDict(object):
   2     """
   3     A simple class for creating new "virtual" dictionaries that actually look
   4     up values in more than one dictionary, passed in the constructor.
   5
   6     If a key appears in more than one of the given dictionaries, only the
   7     first occurrence will be used.
   8     """
   9     def __init__(self, *dicts):
  10         self.dicts = dicts
  11
  12     def __getitem__(self, key):
  13         for dict_ in self.dicts:
  14             try:
  15                 return dict_[key]
  16             except KeyError:
  17                 pass
  18         raise KeyError
  19
  20     def __copy__(self):
  21         return self.__class__(*self.dicts)
  22
  23     def get(self, key, default=None):
  24         try:
  25             return self[key]
  26         except KeyError:
  27             return default
  28
  29     def getlist(self, key):
  30         for dict_ in self.dicts:
  31             if key in dict_.keys():
  32                 return dict_.getlist(key)
  33         return []
  34
  35     def items(self):
  36         item_list = []
  37         for dict_ in self.dicts:
  38             item_list.extend(dict_.items())
  39         return item_list
  40
  41     def has_key(self, key):
  42         for dict_ in self.dicts:
  43             if key in dict_:
  44                 return True
  45         return False
  46
  47     __contains__ = has_key
  48
  49     def copy(self):
  50         """Returns a copy of this object."""
  51         return self.__copy__()
  52
  53 class SortedDict(dict):
  54     """
  55     A dictionary that keeps its keys in the order in which they're inserted.
  56     """
  57     def __new__(cls, *args, **kwargs):
  58         instance = super(SortedDict, cls).__new__(cls, *args, **kwargs)
  59         instance.keyOrder = []
  60         return instance
  61
  62     def __init__(self, data=None):
  63         if data is None:
  64             data = {}
  65         super(SortedDict, self).__init__(data)
  66         if isinstance(data, dict):
  67             self.keyOrder = data.keys()
  68         else:
  69             self.keyOrder = []
  70             for key, value in data:
  71                 if key not in self.keyOrder:
  72                     self.keyOrder.append(key)
  73
  74     def __deepcopy__(self, memo):
  75         from copy import deepcopy
  76         return self.__class__([(key, deepcopy(value, memo))
  77                                for key, value in self.iteritems()])
  78
  79     def __setitem__(self, key, value):
  80         super(SortedDict, self).__setitem__(key, value)
  81         if key not in self.keyOrder:
  82             self.keyOrder.append(key)
  83
  84     def __delitem__(self, key):
  85         super(SortedDict, self).__delitem__(key)
  86         self.keyOrder.remove(key)
  87
  88     def __iter__(self):
  89         for k in self.keyOrder:
  90             yield k
  91
  92     def pop(self, k, *args):
  93         result = super(SortedDict, self).pop(k, *args)
  94         try:
  95             self.keyOrder.remove(k)
  96         except ValueError:
  97             # Key wasn't in the dictionary in the first place. No problem.
  98             pass
  99         return result
 100
 101     def popitem(self):
 102         result = super(SortedDict, self).popitem()
 103         self.keyOrder.remove(result[0])
 104         return result
 105
 106     def items(self):
 107         return zip(self.keyOrder, self.values())
 108
 109     def iteritems(self):
 110         for key in self.keyOrder:
 111             yield key, super(SortedDict, self).__getitem__(key)
 112
 113     def keys(self):
 114         return self.keyOrder[:]
 115
 116     def iterkeys(self):
 117         return iter(self.keyOrder)
 118
 119     def values(self):
 120         return [super(SortedDict, self).__getitem__(k) for k in self.keyOrder]
 121
 122     def itervalues(self):
 123         for key in self.keyOrder:
 124             yield super(SortedDict, self).__getitem__(key)
 125
 126     def update(self, dict_):
 127         for k, v in dict_.items():
 128             self.__setitem__(k, v)
 129
 130     def setdefault(self, key, default):
 131         if key not in self.keyOrder:
 132             self.keyOrder.append(key)
 133         return super(SortedDict, self).setdefault(key, default)
 134
 135     def value_for_index(self, index):
 136         """Returns the value of the item at the given zero-based index."""
 137         return self[self.keyOrder[index]]
 138
 139     def insert(self, index, key, value):
 140         """Inserts the key, value pair before the item with the given index."""
 141         if key in self.keyOrder:
 142             n = self.keyOrder.index(key)
 143             del self.keyOrder[n]
 144             if n < index:
 145                 index -= 1
 146         self.keyOrder.insert(index, key)
 147         super(SortedDict, self).__setitem__(key, value)
 148
 149     def copy(self):
 150         """Returns a copy of this object."""
 151         # This way of initializing the copy means it works for subclasses, too.
 152         obj = self.__class__(self)
 153         obj.keyOrder = self.keyOrder[:]
 154         return obj
 155
 156     def __repr__(self):
 157         """
 158         Replaces the normal dict.__repr__ with a version that returns the keys
 159         in their sorted order.
 160         """
 161         return '{%s}' % ', '.join(['%r: %r' % (k, v) for k, v in self.items()])
 162
 163     def clear(self):
 164         super(SortedDict, self).clear()
 165         self.keyOrder = []
 166
 167 class MultiValueDictKeyError(KeyError):
 168     pass
 169
 170 class MultiValueDict(dict):
 171     """
 172     A subclass of dictionary customized to handle multiple values for the
 173     same key.
 174
 175     >>> d = MultiValueDict({'name': ['Adrian', 'Simon'], 'position': ['Developer']})
 176     >>> d['name']
 177     'Simon'
 178     >>> d.getlist('name')
 179     ['Adrian', 'Simon']
 180     >>> d.get('lastname', 'nonexistent')
 181     'nonexistent'
 182     >>> d.setlist('lastname', ['Holovaty', 'Willison'])
 183
 184     This class exists to solve the irritating problem raised by cgi.parse_qs,
 185     which returns a list for every key, even though most Web forms submit
 186     single name-value pairs.
 187     """
 188     def __init__(self, key_to_list_mapping=()):
 189         super(MultiValueDict, self).__init__(key_to_list_mapping)
 190
 191     def __repr__(self):
 192         return "<%s: %s>" % (self.__class__.__name__,
 193                              super(MultiValueDict, self).__repr__())
 194
 195     def __getitem__(self, key):
 196         """
 197         Returns the last data value for this key, or [] if it's an empty list;
 198         raises KeyError if not found.
 199         """
 200         try:
 201             list_ = super(MultiValueDict, self).__getitem__(key)
 202         except KeyError:
 203             raise MultiValueDictKeyError, "Key %r not found in %r" % (key, self)
 204         try:
 205             return list_[-1]
 206         except IndexError:
 207             return []
 208
 209     def __setitem__(self, key, value):
 210         super(MultiValueDict, self).__setitem__(key, [value])
 211
 212     def __copy__(self):
 213         return self.__class__(super(MultiValueDict, self).items())
 214
 215     def __deepcopy__(self, memo=None):
 216         import copy
 217         if memo is None:
 218             memo = {}
 219         result = self.__class__()
 220         memo[id(self)] = result
 221         for key, value in dict.items(self):
 222             dict.__setitem__(result, copy.deepcopy(key, memo),
 223                              copy.deepcopy(value, memo))
 224         return result
 225
 226     def get(self, key, default=None):
 227         """
 228         Returns the last data value for the passed key. If key doesn't exist
 229         or value is an empty list, then default is returned.
 230         """
 231         try:
 232             val = self[key]
 233         except KeyError:
 234             return default
 235         if val == []:
 236             return default
 237         return val
 238
 239     def getlist(self, key):
 240         """
 241         Returns the list of values for the passed key. If key doesn't exist,
 242         then an empty list is returned.
 243         """
 244         try:
 245             return super(MultiValueDict, self).__getitem__(key)
 246         except KeyError:
 247             return []
 248
 249     def setlist(self, key, list_):
 250         super(MultiValueDict, self).__setitem__(key, list_)
 251
 252     def setdefault(self, key, default=None):
 253         if key not in self:
 254             self[key] = default
 255         return self[key]
 256
 257     def setlistdefault(self, key, default_list=()):
 258         if key not in self:
 259             self.setlist(key, default_list)
 260         return self.getlist(key)
 261
 262     def appendlist(self, key, value):
 263         """Appends an item to the internal list associated with key."""
 264         self.setlistdefault(key, [])
 265         super(MultiValueDict, self).__setitem__(key, self.getlist(key) + [value])
 266
 267     def items(self):
 268         """
 269         Returns a list of (key, value) pairs, where value is the last item in
 270         the list associated with the key.
 271         """
 272         return [(key, self[key]) for key in self.keys()]
 273
 274     def iteritems(self):
 275         """
 276         Yields (key, value) pairs, where value is the last item in the list
 277         associated with the key.
 278         """
 279         for key in self.keys():
 280             yield (key, self[key])
 281
 282     def lists(self):
 283         """Returns a list of (key, list) pairs."""
 284         return super(MultiValueDict, self).items()
 285
 286     def values(self):
 287         """Returns a list of the last value on every key list."""
 288         return [self[key] for key in self.keys()]
 289
 290     def copy(self):
 291         """Returns a copy of this object."""
 292         return self.__deepcopy__()
 293
 294     def update(self, *args, **kwargs):
 295         """
 296         update() extends rather than replaces existing key lists.
 297         Also accepts keyword args.
 298         """
 299         if len(args) > 1:
 300             raise TypeError, "update expected at most 1 arguments, got %d" % len(args)
 301         if args:
 302             other_dict = args[0]
 303             if isinstance(other_dict, MultiValueDict):
 304                 for key, value_list in other_dict.lists():
 305                     self.setlistdefault(key, []).extend(value_list)
 306             else:
 307                 try:
 308                     for key, value in other_dict.items():
 309                         self.setlistdefault(key, []).append(value)
 310                 except TypeError:
 311                     raise ValueError, "MultiValueDict.update() takes either a MultiValueDict or dictionary"
 312         for key, value in kwargs.iteritems():
 313             self.setlistdefault(key, []).append(value)
 314
 315 class DotExpandedDict(dict):
 316     """
 317     A special dictionary constructor that takes a dictionary in which the keys
 318     may contain dots to specify inner dictionaries. It's confusing, but this
 319     example should make sense.
 320
 321     >>> d = DotExpandedDict({'person.1.firstname': ['Simon'], \
 322             'person.1.lastname': ['Willison'], \
 323             'person.2.firstname': ['Adrian'], \
 324             'person.2.lastname': ['Holovaty']})
 325     >>> d
 326     {'person': {'1': {'lastname': ['Willison'], 'firstname': ['Simon']}, '2': {'lastname': ['Holovaty'], 'firstname': ['Adrian']}}}
 327     >>> d['person']
 328     {'1': {'lastname': ['Willison'], 'firstname': ['Simon']}, '2': {'lastname': ['Holovaty'], 'firstname': ['Adrian']}}
 329     >>> d['person']['1']
 330     {'lastname': ['Willison'], 'firstname': ['Simon']}
 331
 332     # Gotcha: Results are unpredictable if the dots are "uneven":
 333     >>> DotExpandedDict({'c.1': 2, 'c.2': 3, 'c': 1})
 334     {'c': 1}
 335     """
 336     def __init__(self, key_to_list_mapping):
 337         for k, v in key_to_list_mapping.items():
 338             current = self
 339             bits = k.split('.')
 340             for bit in bits[:-1]:
 341                 current = current.setdefault(bit, {})
 342             # Now assign value to current position
 343             try:
 344                 current[bits[-1]] = v
 345             except TypeError: # Special-case if current isn't a dict.
 346                 current = {bits[-1]: v}
 347
 348 class ImmutableList(tuple):
 349     """
 350     A tuple-like object that raises useful errors when it is asked to mutate.
 351
 352     Example::
 353
 354         >>> a = ImmutableList(range(5), warning="You cannot mutate this.")
 355         >>> a[3] = '4'
 356         Traceback (most recent call last):
 357             ...
 358         AttributeError: You cannot mutate this.
 359     """
 360
 361     def __new__(cls, *args, **kwargs):
 362         if 'warning' in kwargs:
 363             warning = kwargs['warning']
 364             del kwargs['warning']
 365         else:
 366             warning = 'ImmutableList object is immutable.'
 367         self = tuple.__new__(cls, *args, **kwargs)
 368         self.warning = warning
 369         return self
 370
 371     def complain(self, *wargs, **kwargs):
 372         if isinstance(self.warning, Exception):
 373             raise self.warning
 374         else:
 375             raise AttributeError, self.warning
 376
 377     # All list mutation functions complain.
 378     __delitem__  = complain
 379     __delslice__ = complain
 380     __iadd__     = complain
 381     __imul__     = complain
 382     __setitem__  = complain
 383     __setslice__ = complain
 384     append       = complain
 385     extend       = complain
 386     insert       = complain
 387     pop          = complain
 388     remove       = complain
 389     sort         = complain
 390     reverse      = complain
 391
 392 class DictWrapper(dict):
 393     """
 394     Wraps accesses to a dictionary so that certain values (those starting with
 395     the specified prefix) are passed through a function before being returned.
 396     The prefix is removed before looking up the real value.
 397
 398     Used by the SQL construction code to ensure that values are correctly
 399     quoted before being used.
 400     """
 401     def __init__(self, data, func, prefix):
 402         super(DictWrapper, self).__init__(data)
 403         self.func = func
 404         self.prefix = prefix
 405
 406     def __getitem__(self, key):
 407         """
 408         Retrieves the real value after stripping the prefix string (if
 409         present). If the prefix is present, pass the value through self.func
 410         before returning, otherwise return the raw value.
 411         """
 412         if key.startswith(self.prefix):
 413             use_func = True
 414             key = key[len(self.prefix):]
 415         else:
 416             use_func = False
 417         value = super(DictWrapper, self).__getitem__(key)
 418         if use_func:
 419             return self.func(value)
 420         return value
 421