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