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 

     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.

     9 """

    10 

    11 from abc import ABCMeta, abstractmethod

    12 import 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 

    24 class 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 

    42 class 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 

    57 Iterable.register(str)

    58 

    59 

    60 class 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 

    77 class 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 

    92 class 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 

   107 class 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 

   125 class 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 

   245 Set.register(frozenset)

   246 

   247 

   248 class MutableSet(Set):

   249 

   250     @abstractmethod

   251     def add(self, value):

   252         """Return True if it was added, False if already there."""

   253         raise NotImplementedError

   254 

   255     @abstractmethod

   256     def discard(self, value):

   257         """Return True if it was deleted, False if not there."""

   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 = it.__next__()

   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, c):

   290         for value in self:

   291             if value not in c:

   292                 self.discard(value)

   293         return self

   294 

   295     def __ixor__(self, it):

   296         if not isinstance(it, Set):

   297             it = self._from_iterable(it)

   298         for value in it:

   299             if value in self:

   300                 self.discard(value)

   301             else:

   302                 self.add(value)

   303         return self

   304 

   305     def __isub__(self, it):

   306         for value in it:

   307             self.discard(value)

   308         return self

   309 

   310 MutableSet.register(set)

   311 

   312 

   313 ### MAPPINGS ###

   314 

   315 

   316 class Mapping(Sized, Iterable, Container):

   317 

   318     @abstractmethod

   319     def __getitem__(self, key):

   320         raise KeyError

   321 

   322     def get(self, key, default=None):

   323         try:

   324             return self[key]

   325         except KeyError:

   326             return default

   327 

   328     def __contains__(self, key):

   329         try:

   330             self[key]

   331         except KeyError:

   332             return False

   333         else:

   334             return True

   335 

   336     def iterkeys(self):

   337         return iter(self)

   338 

   339     def itervalues(self):

   340         for key in self:

   341             yield self[key]

   342 

   343     def iteritems(self):

   344         for key in self:

   345             yield (key, self[key])

   346 

   347     def keys(self):

   348         return list(self)

   349 

   350     def items(self):

   351         return [(key, self[key]) for key in self]

   352 

   353     def values(self):

   354         return [self[key] for key in self]

   355 

   356     # Mappings are not hashable by default, but subclasses can change this

   357     __hash__ = None

   358 

   359     def __eq__(self, other):

   360         return isinstance(other, Mapping) and \

   361                dict(self.items()) == dict(other.items())

   362 

   363     def __ne__(self, other):

   364         return not (self == other)

   365 

   366 class MappingView(Sized):

   367 

   368     def __init__(self, mapping):

   369         self._mapping = mapping

   370 

   371     def __len__(self):

   372         return len(self._mapping)

   373 

   374 

   375 class KeysView(MappingView, Set):

   376 

   377     def __contains__(self, key):

   378         return key in self._mapping

   379 

   380     def __iter__(self):

   381         for key in self._mapping:

   382             yield key

   383 

   384 

   385 class ItemsView(MappingView, Set):

   386 

   387     def __contains__(self, item):

   388         key, value = item

   389         try:

   390             v = self._mapping[key]

   391         except KeyError:

   392             return False

   393         else:

   394             return v == value

   395 

   396     def __iter__(self):

   397         for key in self._mapping:

   398             yield (key, self._mapping[key])

   399 

   400 

   401 class ValuesView(MappingView):

   402 

   403     def __contains__(self, value):

   404         for key in self._mapping:

   405             if value == self._mapping[key]:

   406                 return True

   407         return False

   408 

   409     def __iter__(self):

   410         for key in self._mapping:

   411             yield self._mapping[key]

   412 

   413 

   414 class MutableMapping(Mapping):

   415 

   416     @abstractmethod

   417     def __setitem__(self, key, value):

   418         raise KeyError

   419 

   420     @abstractmethod

   421     def __delitem__(self, key):

   422         raise KeyError

   423 

   424     __marker = object()

   425 

   426     def pop(self, key, default=__marker):

   427         try:

   428             value = self[key]

   429         except KeyError:

   430             if default is self.__marker:

   431                 raise

   432             return default

   433         else:

   434             del self[key]

   435             return value

   436 

   437     def popitem(self):

   438         try:

   439             key = next(iter(self))

   440         except StopIteration:

   441             raise KeyError

   442         value = self[key]

   443         del self[key]

   444         return key, value

   445 

   446     def clear(self):

   447         try:

   448             while True:

   449                 self.popitem()

   450         except KeyError:

   451             pass

   452 

   453     def update(self, other=(), **kwds):

   454         if isinstance(other, Mapping):

   455             for key in other:

   456                 self[key] = other[key]

   457         elif hasattr(other, "keys"):

   458             for key in other.keys():

   459                 self[key] = other[key]

   460         else:

   461             for key, value in other:

   462                 self[key] = value

   463         for key, value in kwds.items():

   464             self[key] = value

   465 

   466     def setdefault(self, key, default=None):

   467         try:

   468             return self[key]

   469         except KeyError:

   470             self[key] = default

   471         return default

   472 

   473 MutableMapping.register(dict)

   474 

   475 

   476 ### SEQUENCES ###

   477 

   478 

   479 class Sequence(Sized, Iterable, Container):

   480     """All the operations on a read-only sequence.

   481 

   482     Concrete subclasses must override __new__ or __init__,

   483     __getitem__, and __len__.

   484     """

   485 

   486     @abstractmethod

   487     def __getitem__(self, index):

   488         raise IndexError

   489 

   490     def __iter__(self):

   491         i = 0

   492         try:

   493             while True:

   494                 v = self[i]

   495                 yield v

   496                 i += 1

   497         except IndexError:

   498             return

   499 

   500     def __contains__(self, value):

   501         for v in self:

   502             if v == value:

   503                 return True

   504         return False

   505 

   506     def __reversed__(self):

   507         for i in reversed(range(len(self))):

   508             yield self[i]

   509 

   510     def index(self, value):

   511         for i, v in enumerate(self):

   512             if v == value:

   513                 return i

   514         raise ValueError

   515 

   516     def count(self, value):

   517         return sum(1 for v in self if v == value)

   518 

   519 Sequence.register(tuple)

   520 Sequence.register(basestring)

   521 Sequence.register(buffer)

   522 

   523 

   524 class 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 

   561 MutableSequence.register(list)