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)
672