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

Last change on this file since 389 was 2, checked in by Yuri Dario, 15 years ago

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