source: titan/mediathek/localhoster/lib/python2.7/_abcoll.py @ 40114

Last change on this file since 40114 was 40094, checked in by obi, 5 years ago

tithek add yoztube-dl support

File size: 18.2 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), redefine __le__ and __ge__,
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 len(self) > len(other) and self.__ge__(other)
169
170    def __ge__(self, other):
171        if not isinstance(other, Set):
172            return NotImplemented
173        if len(self) < len(other):
174            return False
175        for elem in other:
176            if elem not in self:
177                return False
178        return True
179
180    def __eq__(self, other):
181        if not isinstance(other, Set):
182            return NotImplemented
183        return len(self) == len(other) and self.__le__(other)
184
185    def __ne__(self, other):
186        return not (self == other)
187
188    @classmethod
189    def _from_iterable(cls, it):
190        '''Construct an instance of the class from any iterable input.
191
192        Must override this method if the class constructor signature
193        does not accept an iterable for an input.
194        '''
195        return cls(it)
196
197    def __and__(self, other):
198        if not isinstance(other, Iterable):
199            return NotImplemented
200        return self._from_iterable(value for value in other if value in self)
201
202    __rand__ = __and__
203
204    def isdisjoint(self, other):
205        'Return True if two sets have a null intersection.'
206        for value in other:
207            if value in self:
208                return False
209        return True
210
211    def __or__(self, other):
212        if not isinstance(other, Iterable):
213            return NotImplemented
214        chain = (e for s in (self, other) for e in s)
215        return self._from_iterable(chain)
216
217    __ror__ = __or__
218
219    def __sub__(self, other):
220        if not isinstance(other, Set):
221            if not isinstance(other, Iterable):
222                return NotImplemented
223            other = self._from_iterable(other)
224        return self._from_iterable(value for value in self
225                                   if value not in other)
226
227    def __rsub__(self, other):
228        if not isinstance(other, Set):
229            if not isinstance(other, Iterable):
230                return NotImplemented
231            other = self._from_iterable(other)
232        return self._from_iterable(value for value in other
233                                   if value not in self)
234
235    def __xor__(self, other):
236        if not isinstance(other, Set):
237            if not isinstance(other, Iterable):
238                return NotImplemented
239            other = self._from_iterable(other)
240        return (self - other) | (other - self)
241
242    __rxor__ = __xor__
243
244    # Sets are not hashable by default, but subclasses can change this
245    __hash__ = None
246
247    def _hash(self):
248        """Compute the hash value of a set.
249
250        Note that we don't define __hash__: not all sets are hashable.
251        But if you define a hashable set type, its __hash__ should
252        call this function.
253
254        This must be compatible __eq__.
255
256        All sets ought to compare equal if they contain the same
257        elements, regardless of how they are implemented, and
258        regardless of the order of the elements; so there's not much
259        freedom for __eq__ or __hash__.  We match the algorithm used
260        by the built-in frozenset type.
261        """
262        MAX = sys.maxint
263        MASK = 2 * MAX + 1
264        n = len(self)
265        h = 1927868237 * (n + 1)
266        h &= MASK
267        for x in self:
268            hx = hash(x)
269            h ^= (hx ^ (hx << 16) ^ 89869747)  * 3644798167
270            h &= MASK
271        h = h * 69069 + 907133923
272        h &= MASK
273        if h > MAX:
274            h -= MASK + 1
275        if h == -1:
276            h = 590923713
277        return h
278
279Set.register(frozenset)
280
281
282class MutableSet(Set):
283    """A mutable set is a finite, iterable container.
284
285    This class provides concrete generic implementations of all
286    methods except for __contains__, __iter__, __len__,
287    add(), and discard().
288
289    To override the comparisons (presumably for speed, as the
290    semantics are fixed), all you have to do is redefine __le__ and
291    then the other operations will automatically follow suit.
292    """
293
294    @abstractmethod
295    def add(self, value):
296        """Add an element."""
297        raise NotImplementedError
298
299    @abstractmethod
300    def discard(self, value):
301        """Remove an element.  Do not raise an exception if absent."""
302        raise NotImplementedError
303
304    def remove(self, value):
305        """Remove an element. If not a member, raise a KeyError."""
306        if value not in self:
307            raise KeyError(value)
308        self.discard(value)
309
310    def pop(self):
311        """Return the popped value.  Raise KeyError if empty."""
312        it = iter(self)
313        try:
314            value = next(it)
315        except StopIteration:
316            raise KeyError
317        self.discard(value)
318        return value
319
320    def clear(self):
321        """This is slow (creates N new iterators!) but effective."""
322        try:
323            while True:
324                self.pop()
325        except KeyError:
326            pass
327
328    def __ior__(self, it):
329        for value in it:
330            self.add(value)
331        return self
332
333    def __iand__(self, it):
334        for value in (self - it):
335            self.discard(value)
336        return self
337
338    def __ixor__(self, it):
339        if it is self:
340            self.clear()
341        else:
342            if not isinstance(it, Set):
343                it = self._from_iterable(it)
344            for value in it:
345                if value in self:
346                    self.discard(value)
347                else:
348                    self.add(value)
349        return self
350
351    def __isub__(self, it):
352        if it is self:
353            self.clear()
354        else:
355            for value in it:
356                self.discard(value)
357        return self
358
359MutableSet.register(set)
360
361
362### MAPPINGS ###
363
364
365class Mapping(Sized, Iterable, Container):
366
367    """A Mapping is a generic container for associating key/value
368    pairs.
369
370    This class provides concrete generic implementations of all
371    methods except for __getitem__, __iter__, and __len__.
372
373    """
374
375    @abstractmethod
376    def __getitem__(self, key):
377        raise KeyError
378
379    def get(self, key, default=None):
380        'D.get(k[,d]) -> D[k] if k in D, else d.  d defaults to None.'
381        try:
382            return self[key]
383        except KeyError:
384            return default
385
386    def __contains__(self, key):
387        try:
388            self[key]
389        except KeyError:
390            return False
391        else:
392            return True
393
394    def iterkeys(self):
395        'D.iterkeys() -> an iterator over the keys of D'
396        return iter(self)
397
398    def itervalues(self):
399        'D.itervalues() -> an iterator over the values of D'
400        for key in self:
401            yield self[key]
402
403    def iteritems(self):
404        'D.iteritems() -> an iterator over the (key, value) items of D'
405        for key in self:
406            yield (key, self[key])
407
408    def keys(self):
409        "D.keys() -> list of D's keys"
410        return list(self)
411
412    def items(self):
413        "D.items() -> list of D's (key, value) pairs, as 2-tuples"
414        return [(key, self[key]) for key in self]
415
416    def values(self):
417        "D.values() -> list of D's values"
418        return [self[key] for key in self]
419
420    # Mappings are not hashable by default, but subclasses can change this
421    __hash__ = None
422
423    def __eq__(self, other):
424        if not isinstance(other, Mapping):
425            return NotImplemented
426        return dict(self.items()) == dict(other.items())
427
428    def __ne__(self, other):
429        return not (self == other)
430
431class MappingView(Sized):
432
433    def __init__(self, mapping):
434        self._mapping = mapping
435
436    def __len__(self):
437        return len(self._mapping)
438
439    def __repr__(self):
440        return '{0.__class__.__name__}({0._mapping!r})'.format(self)
441
442
443class KeysView(MappingView, Set):
444
445    @classmethod
446    def _from_iterable(self, it):
447        return set(it)
448
449    def __contains__(self, key):
450        return key in self._mapping
451
452    def __iter__(self):
453        for key in self._mapping:
454            yield key
455
456KeysView.register(type({}.viewkeys()))
457
458class ItemsView(MappingView, Set):
459
460    @classmethod
461    def _from_iterable(self, it):
462        return set(it)
463
464    def __contains__(self, item):
465        key, value = item
466        try:
467            v = self._mapping[key]
468        except KeyError:
469            return False
470        else:
471            return v == value
472
473    def __iter__(self):
474        for key in self._mapping:
475            yield (key, self._mapping[key])
476
477ItemsView.register(type({}.viewitems()))
478
479class ValuesView(MappingView):
480
481    def __contains__(self, value):
482        for key in self._mapping:
483            if value == self._mapping[key]:
484                return True
485        return False
486
487    def __iter__(self):
488        for key in self._mapping:
489            yield self._mapping[key]
490
491ValuesView.register(type({}.viewvalues()))
492
493class MutableMapping(Mapping):
494
495    """A MutableMapping is a generic container for associating
496    key/value pairs.
497
498    This class provides concrete generic implementations of all
499    methods except for __getitem__, __setitem__, __delitem__,
500    __iter__, and __len__.
501
502    """
503
504    @abstractmethod
505    def __setitem__(self, key, value):
506        raise KeyError
507
508    @abstractmethod
509    def __delitem__(self, key):
510        raise KeyError
511
512    __marker = object()
513
514    def pop(self, key, default=__marker):
515        '''D.pop(k[,d]) -> v, remove specified key and return the corresponding value.
516          If key is not found, d is returned if given, otherwise KeyError is raised.
517        '''
518        try:
519            value = self[key]
520        except KeyError:
521            if default is self.__marker:
522                raise
523            return default
524        else:
525            del self[key]
526            return value
527
528    def popitem(self):
529        '''D.popitem() -> (k, v), remove and return some (key, value) pair
530           as a 2-tuple; but raise KeyError if D is empty.
531        '''
532        try:
533            key = next(iter(self))
534        except StopIteration:
535            raise KeyError
536        value = self[key]
537        del self[key]
538        return key, value
539
540    def clear(self):
541        'D.clear() -> None.  Remove all items from D.'
542        try:
543            while True:
544                self.popitem()
545        except KeyError:
546            pass
547
548    def update(*args, **kwds):
549        ''' D.update([E, ]**F) -> None.  Update D from mapping/iterable E and F.
550            If E present and has a .keys() method, does:     for k in E: D[k] = E[k]
551            If E present and lacks .keys() method, does:     for (k, v) in E: D[k] = v
552            In either case, this is followed by: for k, v in F.items(): D[k] = v
553        '''
554        if not args:
555            raise TypeError("descriptor 'update' of 'MutableMapping' object "
556                            "needs an argument")
557        self = args[0]
558        args = args[1:]
559        if len(args) > 1:
560            raise TypeError('update expected at most 1 arguments, got %d' %
561                            len(args))
562        if args:
563            other = args[0]
564            if isinstance(other, Mapping):
565                for key in other:
566                    self[key] = other[key]
567            elif hasattr(other, "keys"):
568                for key in other.keys():
569                    self[key] = other[key]
570            else:
571                for key, value in other:
572                    self[key] = value
573        for key, value in kwds.items():
574            self[key] = value
575
576    def setdefault(self, key, default=None):
577        'D.setdefault(k[,d]) -> D.get(k,d), also set D[k]=d if k not in D'
578        try:
579            return self[key]
580        except KeyError:
581            self[key] = default
582        return default
583
584MutableMapping.register(dict)
585
586
587### SEQUENCES ###
588
589
590class Sequence(Sized, Iterable, Container):
591    """All the operations on a read-only sequence.
592
593    Concrete subclasses must override __new__ or __init__,
594    __getitem__, and __len__.
595    """
596
597    @abstractmethod
598    def __getitem__(self, index):
599        raise IndexError
600
601    def __iter__(self):
602        i = 0
603        try:
604            while True:
605                v = self[i]
606                yield v
607                i += 1
608        except IndexError:
609            return
610
611    def __contains__(self, value):
612        for v in self:
613            if v == value:
614                return True
615        return False
616
617    def __reversed__(self):
618        for i in reversed(range(len(self))):
619            yield self[i]
620
621    def index(self, value):
622        '''S.index(value) -> integer -- return first index of value.
623           Raises ValueError if the value is not present.
624        '''
625        for i, v in enumerate(self):
626            if v == value:
627                return i
628        raise ValueError
629
630    def count(self, value):
631        'S.count(value) -> integer -- return number of occurrences of value'
632        return sum(1 for v in self if v == value)
633
634Sequence.register(tuple)
635Sequence.register(basestring)
636Sequence.register(buffer)
637Sequence.register(xrange)
638
639
640class MutableSequence(Sequence):
641
642    """All the operations on a read-only sequence.
643
644    Concrete subclasses must provide __new__ or __init__,
645    __getitem__, __setitem__, __delitem__, __len__, and insert().
646
647    """
648
649    @abstractmethod
650    def __setitem__(self, index, value):
651        raise IndexError
652
653    @abstractmethod
654    def __delitem__(self, index):
655        raise IndexError
656
657    @abstractmethod
658    def insert(self, index, value):
659        'S.insert(index, object) -- insert object before index'
660        raise IndexError
661
662    def append(self, value):
663        'S.append(object) -- append object to the end of the sequence'
664        self.insert(len(self), value)
665
666    def reverse(self):
667        'S.reverse() -- reverse *IN PLACE*'
668        n = len(self)
669        for i in range(n//2):
670            self[i], self[n-i-1] = self[n-i-1], self[i]
671
672    def extend(self, values):
673        'S.extend(iterable) -- extend sequence by appending elements from the iterable'
674        for v in values:
675            self.append(v)
676
677    def pop(self, index=-1):
678        '''S.pop([index]) -> item -- remove and return item at index (default last).
679           Raise IndexError if list is empty or index is out of range.
680        '''
681        v = self[index]
682        del self[index]
683        return v
684
685    def remove(self, value):
686        '''S.remove(value) -- remove first occurrence of value.
687           Raise ValueError if the value is not present.
688        '''
689        del self[self.index(value)]
690
691    def __iadd__(self, values):
692        self.extend(values)
693        return self
694
695MutableSequence.register(list)
Note: See TracBrowser for help on using the repository browser.