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 __init__(self, data=None):
  58         if data is None:
  59             data = {}
  60         super(SortedDict, self).__init__(data)
  61         if isinstance(data, dict):
  62             self.keyOrder = data.keys()
  63         else:
  64             self.keyOrder = []
  65             for key, value in data:
  66                 if key not in self.keyOrder:
  67                     self.keyOrder.append(key)
  68
  69     def __deepcopy__(self, memo):
  70         from copy import deepcopy
  71         return self.__class__([(key, deepcopy(value, memo))
  72                                for key, value in self.iteritems()])
  73
  74     def __setitem__(self, key, value):
  75         super(SortedDict, self).__setitem__(key, value)
  76         if key not in self.keyOrder:
  77             self.keyOrder.append(key)
  78
  79     def __delitem__(self, key):
  80         super(SortedDict, self).__delitem__(key)
  81         self.keyOrder.remove(key)
  82
  83     def __iter__(self):
  84         for k in self.keyOrder:
  85             yield k
  86
  87     def pop(self, k, *args):
  88         result = super(SortedDict, self).pop(k, *args)
  89         try:
  90             self.keyOrder.remove(k)
  91         except ValueError:
  92             # Key wasn't in the dictionary in the first place. No problem.
  93             pass
  94         return result
  95
  96     def popitem(self):
  97         result = super(SortedDict, self).popitem()
  98         self.keyOrder.remove(result[0])
  99         return result
 100
 101     def items(self):
 102         return zip(self.keyOrder, self.values())
 103
 104     def iteritems(self):
 105         for key in self.keyOrder:
 106             yield key, super(SortedDict, self).__getitem__(key)
 107
 108     def keys(self):
 109         return self.keyOrder[:]
 110
 111     def iterkeys(self):
 112         return iter(self.keyOrder)
 113
 114     def values(self):
 115         return [super(SortedDict, self).__getitem__(k) for k in self.keyOrder]
 116
 117     def itervalues(self):
 118         for key in self.keyOrder:
 119             yield super(SortedDict, self).__getitem__(key)
 120
 121     def update(self, dict_):
 122         for k, v in dict_.items():
 123             self.__setitem__(k, v)
 124
 125     def setdefault(self, key, default):
 126         if key not in self.keyOrder:
 127             self.keyOrder.append(key)
 128         return super(SortedDict, self).setdefault(key, default)
 129
 130     def value_for_index(self, index):
 131         """Returns the value of the item at the given zero-based index."""
 132         return self[self.keyOrder[index]]
 133
 134     def insert(self, index, key, value):
 135         """Inserts the key, value pair before the item with the given index."""
 136         if key in self.keyOrder:
 137             n = self.keyOrder.index(key)
 138             del self.keyOrder[n]
 139             if n < index:
 140                 index -= 1
 141         self.keyOrder.insert(index, key)
 142         super(SortedDict, self).__setitem__(key, value)
 143
 144     def copy(self):
 145         """Returns a copy of this object."""
 146         # This way of initializing the copy means it works for subclasses, too.
 147         obj = self.__class__(self)
 148         obj.keyOrder = self.keyOrder[:]
 149         return obj
 150
 151     def __repr__(self):
 152         """
 153         Replaces the normal dict.__repr__ with a version that returns the keys
 154         in their sorted order.
 155         """
 156         return '{%s}' % ', '.join(['%r: %r' % (k, v) for k, v in self.items()])
 157
 158     def clear(self):
 159         super(SortedDict, self).clear()
 160         self.keyOrder = []
 161
 162 class MultiValueDictKeyError(KeyError):
 163     pass
 164
 165 class MultiValueDict(dict):
 166     """
 167     A subclass of dictionary customized to handle multiple values for the
 168     same key.
 169
 170     >>> d = MultiValueDict({'name': ['Adrian', 'Simon'], 'position': ['Developer']})
 171     >>> d['name']
 172     'Simon'
 173     >>> d.getlist('name')
 174     ['Adrian', 'Simon']
 175     >>> d.get('lastname', 'nonexistent')
 176     'nonexistent'
 177     >>> d.setlist('lastname', ['Holovaty', 'Willison'])
 178
 179     This class exists to solve the irritating problem raised by cgi.parse_qs,
 180     which returns a list for every key, even though most Web forms submit
 181     single name-value pairs.
 182     """
 183     def __init__(self, key_to_list_mapping=()):
 184         super(MultiValueDict, self).__init__(key_to_list_mapping)
 185
 186     def __repr__(self):
 187         return "<%s: %s>" % (self.__class__.__name__,
 188                              super(MultiValueDict, self).__repr__())
 189
 190     def __getitem__(self, key):
 191         """
 192         Returns the last data value for this key, or [] if it's an empty list;
 193         raises KeyError if not found.
 194         """
 195         try:
 196             list_ = super(MultiValueDict, self).__getitem__(key)
 197         except KeyError:
 198             raise MultiValueDictKeyError, "Key %r not found in %r" % (key, self)
 199         try:
 200             return list_[-1]
 201         except IndexError:
 202             return []
 203
 204     def __setitem__(self, key, value):
 205         super(MultiValueDict, self).__setitem__(key, [value])
 206
 207     def __copy__(self):
 208         return self.__class__(super(MultiValueDict, self).items())
 209
 210     def __deepcopy__(self, memo=None):
 211         import copy
 212         if memo is None:
 213             memo = {}
 214         result = self.__class__()
 215         memo[id(self)] = result
 216         for key, value in dict.items(self):
 217             dict.__setitem__(result, copy.deepcopy(key, memo),
 218                              copy.deepcopy(value, memo))
 219         return result
 220
 221     def get(self, key, default=None):
 222         """
 223         Returns the last data value for the passed key. If key doesn't exist
 224         or value is an empty list, then default is returned.
 225         """
 226         try:
 227             val = self[key]
 228         except KeyError:
 229             return default
 230         if val == []:
 231             return default
 232         return val
 233
 234     def getlist(self, key):
 235         """
 236         Returns the list of values for the passed key. If key doesn't exist,
 237         then an empty list is returned.
 238         """
 239         try:
 240             return super(MultiValueDict, self).__getitem__(key)
 241         except KeyError:
 242             return []
 243
 244     def setlist(self, key, list_):
 245         super(MultiValueDict, self).__setitem__(key, list_)
 246
 247     def setdefault(self, key, default=None):
 248         if key not in self:
 249             self[key] = default
 250         return self[key]
 251
 252     def setlistdefault(self, key, default_list=()):
 253         if key not in self:
 254             self.setlist(key, default_list)
 255         return self.getlist(key)
 256
 257     def appendlist(self, key, value):
 258         """Appends an item to the internal list associated with key."""
 259         self.setlistdefault(key, [])
 260         super(MultiValueDict, self).__setitem__(key, self.getlist(key) + [value])
 261
 262     def items(self):
 263         """
 264         Returns a list of (key, value) pairs, where value is the last item in
 265         the list associated with the key.
 266         """
 267         return [(key, self[key]) for key in self.keys()]
 268
 269     def lists(self):
 270         """Returns a list of (key, list) pairs."""
 271         return super(MultiValueDict, self).items()
 272
 273     def values(self):
 274         """Returns a list of the last value on every key list."""
 275         return [self[key] for key in self.keys()]
 276
 277     def copy(self):
 278         """Returns a copy of this object."""
 279         return self.__deepcopy__()
 280
 281     def update(self, *args, **kwargs):
 282         """
 283         update() extends rather than replaces existing key lists.
 284         Also accepts keyword args.
 285         """
 286         if len(args) > 1:
 287             raise TypeError, "update expected at most 1 arguments, got %d" % len(args)
 288         if args:
 289             other_dict = args[0]
 290             if isinstance(other_dict, MultiValueDict):
 291                 for key, value_list in other_dict.lists():
 292                     self.setlistdefault(key, []).extend(value_list)
 293             else:
 294                 try:
 295                     for key, value in other_dict.items():
 296                         self.setlistdefault(key, []).append(value)
 297                 except TypeError:
 298                     raise ValueError, "MultiValueDict.update() takes either a MultiValueDict or dictionary"
 299         for key, value in kwargs.iteritems():
 300             self.setlistdefault(key, []).append(value)
 301
 302 class DotExpandedDict(dict):
 303     """
 304     A special dictionary constructor that takes a dictionary in which the keys
 305     may contain dots to specify inner dictionaries. It's confusing, but this
 306     example should make sense.
 307
 308     >>> d = DotExpandedDict({'person.1.firstname': ['Simon'], \
 309             'person.1.lastname': ['Willison'], \
 310             'person.2.firstname': ['Adrian'], \
 311             'person.2.lastname': ['Holovaty']})
 312     >>> d
 313     {'person': {'1': {'lastname': ['Willison'], 'firstname': ['Simon']}, '2': {'lastname': ['Holovaty'], 'firstname': ['Adrian']}}}
 314     >>> d['person']
 315     {'1': {'lastname': ['Willison'], 'firstname': ['Simon']}, '2': {'lastname': ['Holovaty'], 'firstname': ['Adrian']}}
 316     >>> d['person']['1']
 317     {'lastname': ['Willison'], 'firstname': ['Simon']}
 318
 319     # Gotcha: Results are unpredictable if the dots are "uneven":
 320     >>> DotExpandedDict({'c.1': 2, 'c.2': 3, 'c': 1})
 321     {'c': 1}
 322     """
 323     def __init__(self, key_to_list_mapping):
 324         for k, v in key_to_list_mapping.items():
 325             current = self
 326             bits = k.split('.')
 327             for bit in bits[:-1]:
 328                 current = current.setdefault(bit, {})
 329             # Now assign value to current position
 330             try:
 331                 current[bits[-1]] = v
 332             except TypeError: # Special-case if current isn't a dict.
 333                 current = {bits[-1]: v}
 334
 335 class FileDict(dict):
 336     """
 337     A dictionary used to hold uploaded file contents. The only special feature
 338     here is that repr() of this object won't dump the entire contents of the
 339     file to the output. A handy safeguard for a large file upload.
 340     """
 341     def __repr__(self):
 342         if 'content' in self:
 343             d = dict(self, content='<omitted>')
 344             return dict.__repr__(d)
 345         return dict.__repr__(self)