symbian-qemu-0.9.1-12/python-2.6.1/Lib/_abcoll.py
changeset 1 2fb8b9db1c86
equal deleted inserted replaced
0:ffa851df0825 1:2fb8b9db1c86
       
     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)