# Copyright 2007 Google, Inc. All Rights Reserved.
# Licensed to PSF under a Contributor Agreement.

"""Abstract Base Classes (ABCs) for collections, according to PEP 3119.

DON'T USE THIS MODULE DIRECTLY! The classes here should be imported
via collections; they are defined here only to alleviate certain
bootstrapping issues. Unit tests are in test_collections.
"""

from abc import ABCMeta, abstractmethod
import sys

__all__ = ["Hashable", "Iterable", "Iterator",
"Sized", "Container", "Callable",
"Set", "MutableSet",
"Mapping", "MutableMapping",
"MappingView", "KeysView", "ItemsView", "ValuesView",
"Sequence", "MutableSequence",
]

### ONE-TRICK PONIES ###

def _hasattr(C, attr):
try:
return any(attr in B.__dict__ for B in C.__mro__)
except AttributeError:
# Old-style class
return hasattr(C, attr)


class Hashable:
__metaclass__ = ABCMeta

@abstractmethod
def __hash__(self):
return 0

@classmethod
def __subclasshook__(cls, C):
if cls is Hashable:
try:
for B in C.__mro__:
if "__hash__" in B.__dict__:
if B.__dict__["__hash__"]:
return True
break
except AttributeError:
# Old-style class
if getattr(C, "__hash__", None):
return True
return NotImplemented


class Iterable:
__metaclass__ = ABCMeta

@abstractmethod
def __iter__(self):
while False:
yield None

@classmethod
def __subclasshook__(cls, C):
if cls is Iterable:
if _hasattr(C, "__iter__"):
return True
return NotImplemented

Iterable.register(str)


class Iterator(Iterable):

@abstractmethod
def next(self):
'Return the next item from the iterator. When exhausted, raise StopIteration'
raise StopIteration

def __iter__(self):
return self

@classmethod
def __subclasshook__(cls, C):
if cls is Iterator:
if _hasattr(C, "next") and _hasattr(C, "__iter__"):
return True
return NotImplemented


class Sized:
__metaclass__ = ABCMeta

@abstractmethod
def __len__(self):
return 0

@classmethod
def __subclasshook__(cls, C):
if cls is Sized:
if _hasattr(C, "__len__"):
return True
return NotImplemented


class Container:
__metaclass__ = ABCMeta

@abstractmethod
def __contains__(self, x):
return False

@classmethod
def __subclasshook__(cls, C):
if cls is Container:
if _hasattr(C, "__contains__"):
return True
return NotImplemented


class Callable:
__metaclass__ = ABCMeta

@abstractmethod
def __call__(self, *args, **kwds):
return False

@classmethod
def __subclasshook__(cls, C):
if cls is Callable:
if _hasattr(C, "__call__"):
return True
return NotImplemented


### SETS ###


class Set(Sized, Iterable, Container):
"""A set is a finite, iterable container.

This class provides concrete generic implementations of all
methods except for __contains__, __iter__ and __len__.

To override the comparisons (presumably for speed, as the
semantics are fixed), all you have to do is redefine __le__ and
then the other operations will automatically follow suit.
"""

def __le__(self, other):
if not isinstance(other, Set):
return NotImplemented
if len(self) > len(other):
return False
for elem in self:
if elem not in other:
return False
return True

def __lt__(self, other):
if not isinstance(other, Set):
return NotImplemented
return len(self) < len(other) and self.__le__(other)

def __gt__(self, other):
if not isinstance(other, Set):
return NotImplemented
return other < self

def __ge__(self, other):
if not isinstance(other, Set):
return NotImplemented
return other <= self

def __eq__(self, other):
if not isinstance(other, Set):
return NotImplemented
return len(self) == len(other) and self.__le__(other)

def __ne__(self, other):
return not (self == other)

@classmethod
def _from_iterable(cls, it):
'''Construct an instance of the class from any iterable input.

Must override this method if the class constructor signature
does not accept an iterable for an input.
'''
return cls(it)

def __and__(self, other):
if not isinstance(other, Iterable):
return NotImplemented
return self._from_iterable(value for value in other if value in self)

def isdisjoint(self, other):
'Return True if two sets have a null intersection.'
for value in other:
if value in self:
return False
return True

def __or__(self, other):
if not isinstance(other, Iterable):
return NotImplemented
chain = (e for s in (self, other) for e in s)
return self._from_iterable(chain)

def __sub__(self, other):
if not isinstance(other, Set):
if not isinstance(other, Iterable):
return NotImplemented
other = self._from_iterable(other)
return self._from_iterable(value for value in self
if value not in other)

def __xor__(self, other):
if not isinstance(other, Set):
if not isinstance(other, Iterable):
return NotImplemented
other = self._from_iterable(other)
return (self - other) | (other - self)

# Sets are not hashable by default, but subclasses can change this
__hash__ = None

def _hash(self):
"""Compute the hash value of a set.

Note that we don't define __hash__: not all sets are hashable.
But if you define a hashable set type, its __hash__ should
call this function.

This must be compatible __eq__.

All sets ought to compare equal if they contain the same
elements, regardless of how they are implemented, and
regardless of the order of the elements; so there's not much
freedom for __eq__ or __hash__. We match the algorithm used
by the built-in frozenset type.
"""
MAX = sys.maxint
MASK = 2 * MAX + 1
n = len(self)
h = 1927868237 * (n + 1)
h &= MASK
for x in self:
hx = hash(x)
h ^= (hx ^ (hx << 16) ^ 89869747) * 3644798167
h &= MASK
h = h * 69069 + 907133923
h &= MASK
if h > MAX:
h -= MASK + 1
if h == -1:
h = 590923713
return h

Set.register(frozenset)


class MutableSet(Set):
"""A mutable set is a finite, iterable container.

This class provides concrete generic implementations of all
methods except for __contains__, __iter__, __len__,
add(), and discard().

To override the comparisons (presumably for speed, as the
semantics are fixed), all you have to do is redefine __le__ and
then the other operations will automatically follow suit.
"""

@abstractmethod
def add(self, value):
"""Add an element."""
raise NotImplementedError

@abstractmethod
def discard(self, value):
"""Remove an element. Do not raise an exception if absent."""
raise NotImplementedError

def remove(self, value):
"""Remove an element. If not a member, raise a KeyError."""
if value not in self:
raise KeyError(value)
self.discard(value)

def pop(self):
"""Return the popped value. Raise KeyError if empty."""
it = iter(self)
try:
value = next(it)
except StopIteration:
raise KeyError
self.discard(value)
return value

def clear(self):
"""This is slow (creates N new iterators!) but effective."""
try:
while True:
self.pop()
except KeyError:
pass

def __ior__(self, it):
for value in it:
self.add(value)
return self

def __iand__(self, it):
for value in (self - it):
self.discard(value)
return self

def __ixor__(self, it):
if it is self:
self.clear()
else:
if not isinstance(it, Set):
it = self._from_iterable(it)
for value in it:
if value in self:
self.discard(value)
else:
self.add(value)
return self

def __isub__(self, it):
if it is self:
self.clear()
else:
for value in it:
self.discard(value)
return self

MutableSet.register(set)


### MAPPINGS ###


class Mapping(Sized, Iterable, Container):

"""A Mapping is a generic container for associating key/value
pairs.

This class provides concrete generic implementations of all
methods except for __getitem__, __iter__, and __len__.

"""

@abstractmethod
def __getitem__(self, key):
raise KeyError

def get(self, key, default=None):
'D.get(k[,d]) -> D[k] if k in D, else d. d defaults to None.'
try:
return self[key]
except KeyError:
return default

def __contains__(self, key):
try:
self[key]
except KeyError:
return False
else:
return True

def iterkeys(self):
'D.iterkeys() -> an iterator over the keys of D'
return iter(self)

def itervalues(self):
'D.itervalues() -> an iterator over the values of D'
for key in self:
yield self[key]

def iteritems(self):
'D.iteritems() -> an iterator over the (key, value) items of D'
for key in self:
yield (key, self[key])

def keys(self):
"D.keys() -> list of D's keys"
return list(self)

def items(self):
"D.items() -> list of D's (key, value) pairs, as 2-tuples"
return [(key, self[key]) for key in self]

def values(self):
"D.values() -> list of D's values"
return [self[key] for key in self]

# Mappings are not hashable by default, but subclasses can change this
__hash__ = None

def __eq__(self, other):
if not isinstance(other, Mapping):
return NotImplemented
return dict(self.items()) == dict(other.items())

def __ne__(self, other):
return not (self == other)

class MappingView(Sized):

def __init__(self, mapping):
self._mapping = mapping

def __len__(self):
return len(self._mapping)

def __repr__(self):
return '{0.__class__.__name__}({0._mapping!r})'.format(self)


class KeysView(MappingView, Set):

@classmethod
def _from_iterable(self, it):
return set(it)

def __contains__(self, key):
return key in self._mapping

def __iter__(self):
for key in self._mapping:
yield key


class ItemsView(MappingView, Set):

@classmethod
def _from_iterable(self, it):
return set(it)

def __contains__(self, item):
key, value = item
try:
v = self._mapping[key]
except KeyError:
return False
else:
return v == value

def __iter__(self):
for key in self._mapping:
yield (key, self._mapping[key])


class ValuesView(MappingView):

def __contains__(self, value):
for key in self._mapping:
if value == self._mapping[key]:
return True
return False

def __iter__(self):
for key in self._mapping:
yield self._mapping[key]


class MutableMapping(Mapping):

"""A MutableMapping is a generic container for associating
key/value pairs.

This class provides concrete generic implementations of all
methods except for __getitem__, __setitem__, __delitem__,
__iter__, and __len__.

"""

@abstractmethod
def __setitem__(self, key, value):
raise KeyError

@abstractmethod
def __delitem__(self, key):
raise KeyError

__marker = object()

def pop(self, key, default=__marker):
'''D.pop(k[,d]) -> v, remove specified key and return the corresponding value.
If key is not found, d is returned if given, otherwise KeyError is raised.
'''
try:
value = self[key]
except KeyError:
if default is self.__marker:
raise
return default
else:
del self[key]
return value

def popitem(self):
'''D.popitem() -> (k, v), remove and return some (key, value) pair
as a 2-tuple; but raise KeyError if D is empty.
'''
try:
key = next(iter(self))
except StopIteration:
raise KeyError
value = self[key]
del self[key]
return key, value

def clear(self):
'D.clear() -> None. Remove all items from D.'
try:
while True:
self.popitem()
except KeyError:
pass

def update(*args, **kwds):
''' D.update([E, ]**F) -> None. Update D from mapping/iterable E and F.
If E present and has a .keys() method, does: for k in E: D[k] = E[k]
If E present and lacks .keys() method, does: for (k, v) in E: D[k] = v
In either case, this is followed by: for k, v in F.items(): D[k] = v
'''
if len(args) > 2:
raise TypeError("update() takes at most 2 positional "
"arguments ({} given)".format(len(args)))
elif not args:
raise TypeError("update() takes at least 1 argument (0 given)")
self = args[0]
other = args[1] if len(args) >= 2 else ()

if isinstance(other, Mapping):
for key in other:
self[key] = other[key]
elif hasattr(other, "keys"):
for key in other.keys():
self[key] = other[key]
else:
for key, value in other:
self[key] = value
for key, value in kwds.items():
self[key] = value

def setdefault(self, key, default=None):
'D.setdefault(k[,d]) -> D.get(k,d), also set D[k]=d if k not in D'
try:
return self[key]
except KeyError:
self[key] = default
return default

MutableMapping.register(dict)


### SEQUENCES ###


class Sequence(Sized, Iterable, Container):
"""All the operations on a read-only sequence.

Concrete subclasses must override __new__ or __init__,
__getitem__, and __len__.
"""

@abstractmethod
def __getitem__(self, index):
raise IndexError

def __iter__(self):
i = 0
try:
while True:
v = self[i]
yield v
i += 1
except IndexError:
return

def __contains__(self, value):
for v in self:
if v == value:
return True
return False

def __reversed__(self):
for i in reversed(range(len(self))):
yield self[i]

def index(self, value):
'''S.index(value) -> integer -- return first index of value.
Raises ValueError if the value is not present.
'''
for i, v in enumerate(self):
if v == value:
return i
raise ValueError

def count(self, value):
'S.count(value) -> integer -- return number of occurrences of value'
return sum(1 for v in self if v == value)

Sequence.register(tuple)
Sequence.register(basestring)
Sequence.register(buffer)
Sequence.register(xrange)


class MutableSequence(Sequence):

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

Concrete subclasses must provide __new__ or __init__,
__getitem__, __setitem__, __delitem__, __len__, and insert().

"""

@abstractmethod
def __setitem__(self, index, value):
raise IndexError

@abstractmethod
def __delitem__(self, index):
raise IndexError

@abstractmethod
def insert(self, index, value):
'S.insert(index, object) -- insert object before index'
raise IndexError

def append(self, value):
'S.append(object) -- append object to the end of the sequence'
self.insert(len(self), value)

def reverse(self):
'S.reverse() -- reverse *IN PLACE*'
n = len(self)
for i in range(n//2):
self[i], self[n-i-1] = self[n-i-1], self[i]

def extend(self, values):
'S.extend(iterable) -- extend sequence by appending elements from the iterable'
for v in values:
self.append(v)

def pop(self, index=-1):
'''S.pop([index]) -> item -- remove and return item at index (default last).
Raise IndexError if list is empty or index is out of range.
'''
v = self[index]
del self[index]
return v

def remove(self, value):
'''S.remove(value) -- remove first occurrence of value.
Raise ValueError if the value is not present.
'''
del self[self.index(value)]

def __iadd__(self, values):
self.extend(values)
return self

MutableSequence.register(list)