source: python/trunk/Lib/_abcoll.py@ 394

Last change on this file since 394 was 391, checked in by dmik, 11 years ago

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