1 # Copyright 2007 Google, Inc. All Rights Reserved.
2 # Licensed to PSF under a Contributor Agreement.
4 """Abstract Base Classes (ABCs) for collections, according to PEP 3119.
6 DON'T USE THIS MODULE DIRECTLY! The classes here should be imported
7 via collections; they are defined here only to alleviate certain
8 bootstrapping issues. Unit tests are in test_collections.
11 from abc
import ABCMeta
, abstractmethod
14 __all__
= ["Hashable", "Iterable", "Iterator",
15 "Sized", "Container", "Callable",
17 "Mapping", "MutableMapping",
18 "MappingView", "KeysView", "ItemsView", "ValuesView",
19 "Sequence", "MutableSequence",
22 ### ONE-TRICK PONIES ###
25 __metaclass__
= ABCMeta
32 def __subclasshook__(cls
, C
):
35 if "__hash__" in B
.__dict
__:
36 if B
.__dict
__["__hash__"]:
43 __metaclass__
= ABCMeta
51 def __subclasshook__(cls
, C
):
53 if any("__iter__" in B
.__dict
__ for B
in C
.__mro
__):
57 Iterable
.register(str)
60 class Iterator(Iterable
):
70 def __subclasshook__(cls
, C
):
72 if any("next" in B
.__dict
__ for B
in C
.__mro
__):
78 __metaclass__
= ABCMeta
85 def __subclasshook__(cls
, C
):
87 if any("__len__" in B
.__dict
__ for B
in C
.__mro
__):
93 __metaclass__
= ABCMeta
96 def __contains__(self
, x
):
100 def __subclasshook__(cls
, C
):
102 if any("__contains__" in B
.__dict
__ for B
in C
.__mro
__):
104 return NotImplemented
108 __metaclass__
= ABCMeta
111 def __call__(self
, *args
, **kwds
):
115 def __subclasshook__(cls
, C
):
117 if any("__call__" in B
.__dict
__ for B
in C
.__mro
__):
119 return NotImplemented
125 class Set(Sized
, Iterable
, Container
):
126 """A set is a finite, iterable container.
128 This class provides concrete generic implementations of all
129 methods except for __contains__, __iter__ and __len__.
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.
136 def __le__(self
, other
):
137 if not isinstance(other
, Set
):
138 return NotImplemented
139 if len(self
) > len(other
):
142 if elem
not in other
:
146 def __lt__(self
, other
):
147 if not isinstance(other
, Set
):
148 return NotImplemented
149 return len(self
) < len(other
) and self
.__le
__(other
)
151 def __gt__(self
, other
):
152 if not isinstance(other
, Set
):
153 return NotImplemented
156 def __ge__(self
, other
):
157 if not isinstance(other
, Set
):
158 return NotImplemented
161 def __eq__(self
, other
):
162 if not isinstance(other
, Set
):
163 return NotImplemented
164 return len(self
) == len(other
) and self
.__le
__(other
)
166 def __ne__(self
, other
):
167 return not (self
== other
)
170 def _from_iterable(cls
, it
):
171 '''Construct an instance of the class from any iterable input.
173 Must override this method if the class constructor signature
174 does not accept an iterable for an input.
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
)
183 def isdisjoint(self
, other
):
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
)
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
)
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
)
210 # Sets are not hashable by default, but subclasses can change this
214 """Compute the hash value of a set.
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
220 This must be compatible __eq__.
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.
231 h
= 1927868237 * (n
+ 1)
235 h ^
= (hx ^
(hx
<< 16) ^
89869747) * 3644798167
237 h
= h
* 69069 + 907133923
245 Set
.register(frozenset)
248 class MutableSet(Set
):
251 def add(self
, value
):
252 """Add an element."""
253 raise NotImplementedError
256 def discard(self
, value
):
257 """Remove an element. Do not raise an exception if absent."""
258 raise NotImplementedError
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
)
267 """Return the popped value. Raise KeyError if empty."""
271 except StopIteration:
277 """This is slow (creates N new iterators!) but effective."""
284 def __ior__(self
, it
):
289 def __iand__(self
, c
):
295 def __ixor__(self
, it
):
296 if not isinstance(it
, Set
):
297 it
= self
._from
_iterable
(it
)
305 def __isub__(self
, it
):
310 MutableSet
.register(set)
316 class Mapping(Sized
, Iterable
, Container
):
319 def __getitem__(self
, key
):
322 def get(self
, key
, default
=None):
328 def __contains__(self
, key
):
339 def itervalues(self
):
345 yield (key
, self
[key
])
351 return [(key
, self
[key
]) for key
in self
]
354 return [self
[key
] for key
in self
]
356 # Mappings are not hashable by default, but subclasses can change this
359 def __eq__(self
, other
):
360 return isinstance(other
, Mapping
) and \
361 dict(self
.items()) == dict(other
.items())
363 def __ne__(self
, other
):
364 return not (self
== other
)
366 class MappingView(Sized
):
368 def __init__(self
, mapping
):
369 self
._mapping
= mapping
372 return len(self
._mapping
)
375 return '{0.__class__.__name__}({0._mapping!r})'.format(self
)
378 class KeysView(MappingView
, Set
):
380 def __contains__(self
, key
):
381 return key
in self
._mapping
384 for key
in self
._mapping
:
388 class ItemsView(MappingView
, Set
):
390 def __contains__(self
, item
):
393 v
= self
._mapping
[key
]
400 for key
in self
._mapping
:
401 yield (key
, self
._mapping
[key
])
404 class ValuesView(MappingView
):
406 def __contains__(self
, value
):
407 for key
in self
._mapping
:
408 if value
== self
._mapping
[key
]:
413 for key
in self
._mapping
:
414 yield self
._mapping
[key
]
417 class MutableMapping(Mapping
):
420 def __setitem__(self
, key
, value
):
424 def __delitem__(self
, key
):
429 def pop(self
, key
, default
=__marker
):
433 if default
is self
.__marker
:
442 key
= next(iter(self
))
443 except StopIteration:
456 def update(self
, other
=(), **kwds
):
457 if isinstance(other
, Mapping
):
459 self
[key
] = other
[key
]
460 elif hasattr(other
, "keys"):
461 for key
in other
.keys():
462 self
[key
] = other
[key
]
464 for key
, value
in other
:
466 for key
, value
in kwds
.items():
469 def setdefault(self
, key
, default
=None):
476 MutableMapping
.register(dict)
482 class Sequence(Sized
, Iterable
, Container
):
483 """All the operations on a read-only sequence.
485 Concrete subclasses must override __new__ or __init__,
486 __getitem__, and __len__.
490 def __getitem__(self
, index
):
503 def __contains__(self
, value
):
509 def __reversed__(self
):
510 for i
in reversed(range(len(self
))):
513 def index(self
, value
):
514 for i
, v
in enumerate(self
):
519 def count(self
, value
):
520 return sum(1 for v
in self
if v
== value
)
522 Sequence
.register(tuple)
523 Sequence
.register(basestring
)
524 Sequence
.register(buffer)
525 Sequence
.register(xrange)
528 class MutableSequence(Sequence
):
531 def __setitem__(self
, index
, value
):
535 def __delitem__(self
, index
):
539 def insert(self
, index
, value
):
542 def append(self
, value
):
543 self
.insert(len(self
), value
)
547 for i
in range(n
//2):
548 self
[i
], self
[n
-i
-1] = self
[n
-i
-1], self
[i
]
550 def extend(self
, values
):
554 def pop(self
, index
=-1):
559 def remove(self
, value
):
560 del self
[self
.index(value
)]
562 def __iadd__(self
, values
):
565 MutableSequence
.register(list)