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