]>
Commit | Line | Data |
---|---|---|
4710c53d | 1 | # Copyright 2007 Google, Inc. All Rights Reserved.\r |
2 | # Licensed to PSF under a Contributor Agreement.\r | |
3 | \r | |
4 | """Abstract Base Classes (ABCs) for collections, according to PEP 3119.\r | |
5 | \r | |
6 | DON'T USE THIS MODULE DIRECTLY! The classes here should be imported\r | |
7 | via collections; they are defined here only to alleviate certain\r | |
8 | bootstrapping issues. Unit tests are in test_collections.\r | |
9 | """\r | |
10 | \r | |
11 | from abc import ABCMeta, abstractmethod\r | |
12 | import sys\r | |
13 | \r | |
14 | __all__ = ["Hashable", "Iterable", "Iterator",\r | |
15 | "Sized", "Container", "Callable",\r | |
16 | "Set", "MutableSet",\r | |
17 | "Mapping", "MutableMapping",\r | |
18 | "MappingView", "KeysView", "ItemsView", "ValuesView",\r | |
19 | "Sequence", "MutableSequence",\r | |
20 | ]\r | |
21 | \r | |
22 | ### ONE-TRICK PONIES ###\r | |
23 | \r | |
24 | def _hasattr(C, attr):\r | |
25 | try:\r | |
26 | return any(attr in B.__dict__ for B in C.__mro__)\r | |
27 | except AttributeError:\r | |
28 | # Old-style class\r | |
29 | return hasattr(C, attr)\r | |
30 | \r | |
31 | \r | |
32 | class Hashable:\r | |
33 | __metaclass__ = ABCMeta\r | |
34 | \r | |
35 | @abstractmethod\r | |
36 | def __hash__(self):\r | |
37 | return 0\r | |
38 | \r | |
39 | @classmethod\r | |
40 | def __subclasshook__(cls, C):\r | |
41 | if cls is Hashable:\r | |
42 | try:\r | |
43 | for B in C.__mro__:\r | |
44 | if "__hash__" in B.__dict__:\r | |
45 | if B.__dict__["__hash__"]:\r | |
46 | return True\r | |
47 | break\r | |
48 | except AttributeError:\r | |
49 | # Old-style class\r | |
50 | if getattr(C, "__hash__", None):\r | |
51 | return True\r | |
52 | return NotImplemented\r | |
53 | \r | |
54 | \r | |
55 | class Iterable:\r | |
56 | __metaclass__ = ABCMeta\r | |
57 | \r | |
58 | @abstractmethod\r | |
59 | def __iter__(self):\r | |
60 | while False:\r | |
61 | yield None\r | |
62 | \r | |
63 | @classmethod\r | |
64 | def __subclasshook__(cls, C):\r | |
65 | if cls is Iterable:\r | |
66 | if _hasattr(C, "__iter__"):\r | |
67 | return True\r | |
68 | return NotImplemented\r | |
69 | \r | |
70 | Iterable.register(str)\r | |
71 | \r | |
72 | \r | |
73 | class Iterator(Iterable):\r | |
74 | \r | |
75 | @abstractmethod\r | |
76 | def next(self):\r | |
77 | raise StopIteration\r | |
78 | \r | |
79 | def __iter__(self):\r | |
80 | return self\r | |
81 | \r | |
82 | @classmethod\r | |
83 | def __subclasshook__(cls, C):\r | |
84 | if cls is Iterator:\r | |
85 | if _hasattr(C, "next") and _hasattr(C, "__iter__"):\r | |
86 | return True\r | |
87 | return NotImplemented\r | |
88 | \r | |
89 | \r | |
90 | class Sized:\r | |
91 | __metaclass__ = ABCMeta\r | |
92 | \r | |
93 | @abstractmethod\r | |
94 | def __len__(self):\r | |
95 | return 0\r | |
96 | \r | |
97 | @classmethod\r | |
98 | def __subclasshook__(cls, C):\r | |
99 | if cls is Sized:\r | |
100 | if _hasattr(C, "__len__"):\r | |
101 | return True\r | |
102 | return NotImplemented\r | |
103 | \r | |
104 | \r | |
105 | class Container:\r | |
106 | __metaclass__ = ABCMeta\r | |
107 | \r | |
108 | @abstractmethod\r | |
109 | def __contains__(self, x):\r | |
110 | return False\r | |
111 | \r | |
112 | @classmethod\r | |
113 | def __subclasshook__(cls, C):\r | |
114 | if cls is Container:\r | |
115 | if _hasattr(C, "__contains__"):\r | |
116 | return True\r | |
117 | return NotImplemented\r | |
118 | \r | |
119 | \r | |
120 | class Callable:\r | |
121 | __metaclass__ = ABCMeta\r | |
122 | \r | |
123 | @abstractmethod\r | |
124 | def __call__(self, *args, **kwds):\r | |
125 | return False\r | |
126 | \r | |
127 | @classmethod\r | |
128 | def __subclasshook__(cls, C):\r | |
129 | if cls is Callable:\r | |
130 | if _hasattr(C, "__call__"):\r | |
131 | return True\r | |
132 | return NotImplemented\r | |
133 | \r | |
134 | \r | |
135 | ### SETS ###\r | |
136 | \r | |
137 | \r | |
138 | class Set(Sized, Iterable, Container):\r | |
139 | """A set is a finite, iterable container.\r | |
140 | \r | |
141 | This class provides concrete generic implementations of all\r | |
142 | methods except for __contains__, __iter__ and __len__.\r | |
143 | \r | |
144 | To override the comparisons (presumably for speed, as the\r | |
145 | semantics are fixed), all you have to do is redefine __le__ and\r | |
146 | then the other operations will automatically follow suit.\r | |
147 | """\r | |
148 | \r | |
149 | def __le__(self, other):\r | |
150 | if not isinstance(other, Set):\r | |
151 | return NotImplemented\r | |
152 | if len(self) > len(other):\r | |
153 | return False\r | |
154 | for elem in self:\r | |
155 | if elem not in other:\r | |
156 | return False\r | |
157 | return True\r | |
158 | \r | |
159 | def __lt__(self, other):\r | |
160 | if not isinstance(other, Set):\r | |
161 | return NotImplemented\r | |
162 | return len(self) < len(other) and self.__le__(other)\r | |
163 | \r | |
164 | def __gt__(self, other):\r | |
165 | if not isinstance(other, Set):\r | |
166 | return NotImplemented\r | |
167 | return other < self\r | |
168 | \r | |
169 | def __ge__(self, other):\r | |
170 | if not isinstance(other, Set):\r | |
171 | return NotImplemented\r | |
172 | return other <= self\r | |
173 | \r | |
174 | def __eq__(self, other):\r | |
175 | if not isinstance(other, Set):\r | |
176 | return NotImplemented\r | |
177 | return len(self) == len(other) and self.__le__(other)\r | |
178 | \r | |
179 | def __ne__(self, other):\r | |
180 | return not (self == other)\r | |
181 | \r | |
182 | @classmethod\r | |
183 | def _from_iterable(cls, it):\r | |
184 | '''Construct an instance of the class from any iterable input.\r | |
185 | \r | |
186 | Must override this method if the class constructor signature\r | |
187 | does not accept an iterable for an input.\r | |
188 | '''\r | |
189 | return cls(it)\r | |
190 | \r | |
191 | def __and__(self, other):\r | |
192 | if not isinstance(other, Iterable):\r | |
193 | return NotImplemented\r | |
194 | return self._from_iterable(value for value in other if value in self)\r | |
195 | \r | |
196 | def isdisjoint(self, other):\r | |
197 | for value in other:\r | |
198 | if value in self:\r | |
199 | return False\r | |
200 | return True\r | |
201 | \r | |
202 | def __or__(self, other):\r | |
203 | if not isinstance(other, Iterable):\r | |
204 | return NotImplemented\r | |
205 | chain = (e for s in (self, other) for e in s)\r | |
206 | return self._from_iterable(chain)\r | |
207 | \r | |
208 | def __sub__(self, other):\r | |
209 | if not isinstance(other, Set):\r | |
210 | if not isinstance(other, Iterable):\r | |
211 | return NotImplemented\r | |
212 | other = self._from_iterable(other)\r | |
213 | return self._from_iterable(value for value in self\r | |
214 | if value not in other)\r | |
215 | \r | |
216 | def __xor__(self, other):\r | |
217 | if not isinstance(other, Set):\r | |
218 | if not isinstance(other, Iterable):\r | |
219 | return NotImplemented\r | |
220 | other = self._from_iterable(other)\r | |
221 | return (self - other) | (other - self)\r | |
222 | \r | |
223 | # Sets are not hashable by default, but subclasses can change this\r | |
224 | __hash__ = None\r | |
225 | \r | |
226 | def _hash(self):\r | |
227 | """Compute the hash value of a set.\r | |
228 | \r | |
229 | Note that we don't define __hash__: not all sets are hashable.\r | |
230 | But if you define a hashable set type, its __hash__ should\r | |
231 | call this function.\r | |
232 | \r | |
233 | This must be compatible __eq__.\r | |
234 | \r | |
235 | All sets ought to compare equal if they contain the same\r | |
236 | elements, regardless of how they are implemented, and\r | |
237 | regardless of the order of the elements; so there's not much\r | |
238 | freedom for __eq__ or __hash__. We match the algorithm used\r | |
239 | by the built-in frozenset type.\r | |
240 | """\r | |
241 | MAX = sys.maxint\r | |
242 | MASK = 2 * MAX + 1\r | |
243 | n = len(self)\r | |
244 | h = 1927868237 * (n + 1)\r | |
245 | h &= MASK\r | |
246 | for x in self:\r | |
247 | hx = hash(x)\r | |
248 | h ^= (hx ^ (hx << 16) ^ 89869747) * 3644798167\r | |
249 | h &= MASK\r | |
250 | h = h * 69069 + 907133923\r | |
251 | h &= MASK\r | |
252 | if h > MAX:\r | |
253 | h -= MASK + 1\r | |
254 | if h == -1:\r | |
255 | h = 590923713\r | |
256 | return h\r | |
257 | \r | |
258 | Set.register(frozenset)\r | |
259 | \r | |
260 | \r | |
261 | class MutableSet(Set):\r | |
262 | \r | |
263 | @abstractmethod\r | |
264 | def add(self, value):\r | |
265 | """Add an element."""\r | |
266 | raise NotImplementedError\r | |
267 | \r | |
268 | @abstractmethod\r | |
269 | def discard(self, value):\r | |
270 | """Remove an element. Do not raise an exception if absent."""\r | |
271 | raise NotImplementedError\r | |
272 | \r | |
273 | def remove(self, value):\r | |
274 | """Remove an element. If not a member, raise a KeyError."""\r | |
275 | if value not in self:\r | |
276 | raise KeyError(value)\r | |
277 | self.discard(value)\r | |
278 | \r | |
279 | def pop(self):\r | |
280 | """Return the popped value. Raise KeyError if empty."""\r | |
281 | it = iter(self)\r | |
282 | try:\r | |
283 | value = next(it)\r | |
284 | except StopIteration:\r | |
285 | raise KeyError\r | |
286 | self.discard(value)\r | |
287 | return value\r | |
288 | \r | |
289 | def clear(self):\r | |
290 | """This is slow (creates N new iterators!) but effective."""\r | |
291 | try:\r | |
292 | while True:\r | |
293 | self.pop()\r | |
294 | except KeyError:\r | |
295 | pass\r | |
296 | \r | |
297 | def __ior__(self, it):\r | |
298 | for value in it:\r | |
299 | self.add(value)\r | |
300 | return self\r | |
301 | \r | |
302 | def __iand__(self, it):\r | |
303 | for value in (self - it):\r | |
304 | self.discard(value)\r | |
305 | return self\r | |
306 | \r | |
307 | def __ixor__(self, it):\r | |
308 | if it is self:\r | |
309 | self.clear()\r | |
310 | else:\r | |
311 | if not isinstance(it, Set):\r | |
312 | it = self._from_iterable(it)\r | |
313 | for value in it:\r | |
314 | if value in self:\r | |
315 | self.discard(value)\r | |
316 | else:\r | |
317 | self.add(value)\r | |
318 | return self\r | |
319 | \r | |
320 | def __isub__(self, it):\r | |
321 | if it is self:\r | |
322 | self.clear()\r | |
323 | else:\r | |
324 | for value in it:\r | |
325 | self.discard(value)\r | |
326 | return self\r | |
327 | \r | |
328 | MutableSet.register(set)\r | |
329 | \r | |
330 | \r | |
331 | ### MAPPINGS ###\r | |
332 | \r | |
333 | \r | |
334 | class Mapping(Sized, Iterable, Container):\r | |
335 | \r | |
336 | @abstractmethod\r | |
337 | def __getitem__(self, key):\r | |
338 | raise KeyError\r | |
339 | \r | |
340 | def get(self, key, default=None):\r | |
341 | try:\r | |
342 | return self[key]\r | |
343 | except KeyError:\r | |
344 | return default\r | |
345 | \r | |
346 | def __contains__(self, key):\r | |
347 | try:\r | |
348 | self[key]\r | |
349 | except KeyError:\r | |
350 | return False\r | |
351 | else:\r | |
352 | return True\r | |
353 | \r | |
354 | def iterkeys(self):\r | |
355 | return iter(self)\r | |
356 | \r | |
357 | def itervalues(self):\r | |
358 | for key in self:\r | |
359 | yield self[key]\r | |
360 | \r | |
361 | def iteritems(self):\r | |
362 | for key in self:\r | |
363 | yield (key, self[key])\r | |
364 | \r | |
365 | def keys(self):\r | |
366 | return list(self)\r | |
367 | \r | |
368 | def items(self):\r | |
369 | return [(key, self[key]) for key in self]\r | |
370 | \r | |
371 | def values(self):\r | |
372 | return [self[key] for key in self]\r | |
373 | \r | |
374 | # Mappings are not hashable by default, but subclasses can change this\r | |
375 | __hash__ = None\r | |
376 | \r | |
377 | def __eq__(self, other):\r | |
378 | if not isinstance(other, Mapping):\r | |
379 | return NotImplemented\r | |
380 | return dict(self.items()) == dict(other.items())\r | |
381 | \r | |
382 | def __ne__(self, other):\r | |
383 | return not (self == other)\r | |
384 | \r | |
385 | class MappingView(Sized):\r | |
386 | \r | |
387 | def __init__(self, mapping):\r | |
388 | self._mapping = mapping\r | |
389 | \r | |
390 | def __len__(self):\r | |
391 | return len(self._mapping)\r | |
392 | \r | |
393 | def __repr__(self):\r | |
394 | return '{0.__class__.__name__}({0._mapping!r})'.format(self)\r | |
395 | \r | |
396 | \r | |
397 | class KeysView(MappingView, Set):\r | |
398 | \r | |
399 | @classmethod\r | |
400 | def _from_iterable(self, it):\r | |
401 | return set(it)\r | |
402 | \r | |
403 | def __contains__(self, key):\r | |
404 | return key in self._mapping\r | |
405 | \r | |
406 | def __iter__(self):\r | |
407 | for key in self._mapping:\r | |
408 | yield key\r | |
409 | \r | |
410 | \r | |
411 | class ItemsView(MappingView, Set):\r | |
412 | \r | |
413 | @classmethod\r | |
414 | def _from_iterable(self, it):\r | |
415 | return set(it)\r | |
416 | \r | |
417 | def __contains__(self, item):\r | |
418 | key, value = item\r | |
419 | try:\r | |
420 | v = self._mapping[key]\r | |
421 | except KeyError:\r | |
422 | return False\r | |
423 | else:\r | |
424 | return v == value\r | |
425 | \r | |
426 | def __iter__(self):\r | |
427 | for key in self._mapping:\r | |
428 | yield (key, self._mapping[key])\r | |
429 | \r | |
430 | \r | |
431 | class ValuesView(MappingView):\r | |
432 | \r | |
433 | def __contains__(self, value):\r | |
434 | for key in self._mapping:\r | |
435 | if value == self._mapping[key]:\r | |
436 | return True\r | |
437 | return False\r | |
438 | \r | |
439 | def __iter__(self):\r | |
440 | for key in self._mapping:\r | |
441 | yield self._mapping[key]\r | |
442 | \r | |
443 | \r | |
444 | class MutableMapping(Mapping):\r | |
445 | \r | |
446 | @abstractmethod\r | |
447 | def __setitem__(self, key, value):\r | |
448 | raise KeyError\r | |
449 | \r | |
450 | @abstractmethod\r | |
451 | def __delitem__(self, key):\r | |
452 | raise KeyError\r | |
453 | \r | |
454 | __marker = object()\r | |
455 | \r | |
456 | def pop(self, key, default=__marker):\r | |
457 | try:\r | |
458 | value = self[key]\r | |
459 | except KeyError:\r | |
460 | if default is self.__marker:\r | |
461 | raise\r | |
462 | return default\r | |
463 | else:\r | |
464 | del self[key]\r | |
465 | return value\r | |
466 | \r | |
467 | def popitem(self):\r | |
468 | try:\r | |
469 | key = next(iter(self))\r | |
470 | except StopIteration:\r | |
471 | raise KeyError\r | |
472 | value = self[key]\r | |
473 | del self[key]\r | |
474 | return key, value\r | |
475 | \r | |
476 | def clear(self):\r | |
477 | try:\r | |
478 | while True:\r | |
479 | self.popitem()\r | |
480 | except KeyError:\r | |
481 | pass\r | |
482 | \r | |
483 | def update(*args, **kwds):\r | |
484 | if len(args) > 2:\r | |
485 | raise TypeError("update() takes at most 2 positional "\r | |
486 | "arguments ({} given)".format(len(args)))\r | |
487 | elif not args:\r | |
488 | raise TypeError("update() takes at least 1 argument (0 given)")\r | |
489 | self = args[0]\r | |
490 | other = args[1] if len(args) >= 2 else ()\r | |
491 | \r | |
492 | if isinstance(other, Mapping):\r | |
493 | for key in other:\r | |
494 | self[key] = other[key]\r | |
495 | elif hasattr(other, "keys"):\r | |
496 | for key in other.keys():\r | |
497 | self[key] = other[key]\r | |
498 | else:\r | |
499 | for key, value in other:\r | |
500 | self[key] = value\r | |
501 | for key, value in kwds.items():\r | |
502 | self[key] = value\r | |
503 | \r | |
504 | def setdefault(self, key, default=None):\r | |
505 | try:\r | |
506 | return self[key]\r | |
507 | except KeyError:\r | |
508 | self[key] = default\r | |
509 | return default\r | |
510 | \r | |
511 | MutableMapping.register(dict)\r | |
512 | \r | |
513 | \r | |
514 | ### SEQUENCES ###\r | |
515 | \r | |
516 | \r | |
517 | class Sequence(Sized, Iterable, Container):\r | |
518 | """All the operations on a read-only sequence.\r | |
519 | \r | |
520 | Concrete subclasses must override __new__ or __init__,\r | |
521 | __getitem__, and __len__.\r | |
522 | """\r | |
523 | \r | |
524 | @abstractmethod\r | |
525 | def __getitem__(self, index):\r | |
526 | raise IndexError\r | |
527 | \r | |
528 | def __iter__(self):\r | |
529 | i = 0\r | |
530 | try:\r | |
531 | while True:\r | |
532 | v = self[i]\r | |
533 | yield v\r | |
534 | i += 1\r | |
535 | except IndexError:\r | |
536 | return\r | |
537 | \r | |
538 | def __contains__(self, value):\r | |
539 | for v in self:\r | |
540 | if v == value:\r | |
541 | return True\r | |
542 | return False\r | |
543 | \r | |
544 | def __reversed__(self):\r | |
545 | for i in reversed(range(len(self))):\r | |
546 | yield self[i]\r | |
547 | \r | |
548 | def index(self, value):\r | |
549 | for i, v in enumerate(self):\r | |
550 | if v == value:\r | |
551 | return i\r | |
552 | raise ValueError\r | |
553 | \r | |
554 | def count(self, value):\r | |
555 | return sum(1 for v in self if v == value)\r | |
556 | \r | |
557 | Sequence.register(tuple)\r | |
558 | Sequence.register(basestring)\r | |
559 | Sequence.register(buffer)\r | |
560 | Sequence.register(xrange)\r | |
561 | \r | |
562 | \r | |
563 | class MutableSequence(Sequence):\r | |
564 | \r | |
565 | @abstractmethod\r | |
566 | def __setitem__(self, index, value):\r | |
567 | raise IndexError\r | |
568 | \r | |
569 | @abstractmethod\r | |
570 | def __delitem__(self, index):\r | |
571 | raise IndexError\r | |
572 | \r | |
573 | @abstractmethod\r | |
574 | def insert(self, index, value):\r | |
575 | raise IndexError\r | |
576 | \r | |
577 | def append(self, value):\r | |
578 | self.insert(len(self), value)\r | |
579 | \r | |
580 | def reverse(self):\r | |
581 | n = len(self)\r | |
582 | for i in range(n//2):\r | |
583 | self[i], self[n-i-1] = self[n-i-1], self[i]\r | |
584 | \r | |
585 | def extend(self, values):\r | |
586 | for v in values:\r | |
587 | self.append(v)\r | |
588 | \r | |
589 | def pop(self, index=-1):\r | |
590 | v = self[index]\r | |
591 | del self[index]\r | |
592 | return v\r | |
593 | \r | |
594 | def remove(self, value):\r | |
595 | del self[self.index(value)]\r | |
596 | \r | |
597 | def __iadd__(self, values):\r | |
598 | self.extend(values)\r | |
599 | return self\r | |
600 | \r | |
601 | MutableSequence.register(list)\r |