family.py

"""
Families

A Family is an associative container which models a family
`(f_i)_{i \in I}`. Then, ``f[i]`` returns the element of the family indexed by
``i``. Whenever available, set and combinatorial class operations (counting,
iteration, listing) on the family are induced from those of the index
set. Families should be created through the :func:`Family` function.

AUTHORS:

- Nicolas Thiery (2008-02): initial release

- Florent Hivert (2008-04): various fixes, cleanups and improvements.

TESTS:

Check for workaround :trac:`12482` (shall be run in a fresh session)::

    sage: P = Partitions(3)
    sage: Family(P, lambda x: x).category() # used to return ``enumerated sets``
    Category of finite enumerated sets
    sage: Family(P, lambda x: x).category()
    Category of finite enumerated sets
"""
#*****************************************************************************
#       Copyright (C) 2008 Nicolas Thiery <nthiery at users.sf.net>,
#                          Mike Hansen <[email protected]>,
#                          Florent Hivert <[email protected]>
#
#  Distributed under the terms of the GNU General Public License (GPL)
#                  http://www.gnu.org/licenses/
#*****************************************************************************
from sage.misc.cachefunc import cached_method
from sage.structure.parent import Parent
from sage.categories.enumerated_sets import EnumeratedSets
from sage.categories.finite_enumerated_sets import FiniteEnumeratedSets
from sage.categories.infinite_enumerated_sets import InfiniteEnumeratedSets
from sage.sets.finite_enumerated_set import FiniteEnumeratedSet
from sage.misc.lazy_import import lazy_import
from sage.rings.integer import Integer
from sage.misc.misc import AttrCallObject

def Family(indices, function=None, hidden_keys=[], hidden_function=None, lazy=False, name=None):
    r"""
    A Family is an associative container which models a family
    `(f_i)_{i \in I}`. Then, ``f[i]`` returns the element of the family
    indexed by `i`. Whenever available, set and combinatorial class
    operations (counting, iteration, listing) on the family are induced
    from those of the index set.

    There are several available implementations (classes) for different
    usages; Family serves as a factory, and will create instances of
    the appropriate classes depending on its arguments.

    INPUT:

    - ``indices`` -- the indices for the family
    - ``function`` -- (optional) the function `f` applied to all visible
      indices; the default is the identity function
    - ``hidden_keys`` -- (optional) a list of hidden indices that can be
      accessed through ``my_family[i]``
    - ``hidden_function`` -- (optional) a function for the hidden indices
    - ``lazy`` -- boolean (default: ``False``); whether the family is lazily
      created or not; if the indices are infinite, then this is automatically
      made ``True``
    - ``name`` -- (optional) the name of the function; only used when the
      family is lazily created via a function

    EXAMPLES:

    In its simplest form, a list `l = [l_0, l_1, \ldots, l_{\ell}]` or a
    tuple by itself is considered as the family `(l_i)_{i \in I}` where
    `I` is the set `\{0, \ldots, \ell\}` where `\ell` is ``len(l) - 1``.
    So ``Family(l)`` returns the corresponding family::

        sage: f = Family([1,2,3])
        sage: f
        Family (1, 2, 3)
        sage: f = Family((1,2,3))
        sage: f
        Family (1, 2, 3)

    Instead of a list you can as well pass any iterable object::

        sage: f = Family(2*i+1 for i in [1,2,3]);
        sage: f
        Family (3, 5, 7)

    A family can also be constructed from a dictionary ``t``. The resulting
    family is very close to ``t``, except that the elements of the family
    are the values of ``t``. Here, we define the family
    `(f_i)_{i \in \{3,4,7\}}` with `f_3 = a`, `f_4 = b`, and `f_7 = d`::

        sage: f = Family({3: 'a', 4: 'b', 7: 'd'})
        sage: f
        Finite family {3: 'a', 4: 'b', 7: 'd'}
        sage: f[7]
        'd'
        sage: len(f)
        3
        sage: list(f)
        ['a', 'b', 'd']
        sage: [ x for x in f ]
        ['a', 'b', 'd']
        sage: f.keys()
        [3, 4, 7]
        sage: 'b' in f
        True
        sage: 'e' in f
        False

    A family can also be constructed by its index set `I` and
    a function `f`, as in `(f(i))_{i \in I}`::

        sage: f = Family([3,4,7], lambda i: 2*i)
        sage: f
        Finite family {3: 6, 4: 8, 7: 14}
        sage: f.keys()
        [3, 4, 7]
        sage: f[7]
        14
        sage: list(f)
        [6, 8, 14]
        sage: [x for x in f]
        [6, 8, 14]
        sage: len(f)
        3

    By default, all images are computed right away, and stored in an internal
    dictionary::

        sage: f = Family((3,4,7), lambda i: 2*i)
        sage: f
        Finite family {3: 6, 4: 8, 7: 14}

    Note that this requires all the elements of the list to be
    hashable. One can ask instead for the images `f(i)` to be computed
    lazily, when needed::

        sage: f = Family([3,4,7], lambda i: 2*i, lazy=True)
        sage: f
        Lazy family (<lambda>(i))_{i in [3, 4, 7]}
        sage: f[7]
        14
        sage: list(f)
        [6, 8, 14]
        sage: [x for x in f]
        [6, 8, 14]

    This allows in particular for modeling infinite families::

        sage: f = Family(ZZ, lambda i: 2*i, lazy=True)
        sage: f
        Lazy family (<lambda>(i))_{i in Integer Ring}
        sage: f.keys()
        Integer Ring
        sage: f[1]
        2
        sage: f[-5]
        -10
        sage: i = iter(f)
        sage: i.next(), i.next(), i.next(), i.next(), i.next()
        (0, 2, -2, 4, -4)

    Note that the ``lazy`` keyword parameter is only needed to force
    laziness. Usually it is automatically set to a correct default value (ie:
    ``False`` for finite data structures and ``True`` for enumerated sets::

        sage: f == Family(ZZ, lambda i: 2*i)
        True

    Beware that for those kind of families len(f) is not supposed to
    work. As a replacement, use the .cardinality() method::

       sage: f = Family(Permutations(3), attrcall("to_lehmer_code"))
       sage: list(f)
       [[0, 0, 0], [0, 1, 0], [1, 0, 0], [1, 1, 0], [2, 0, 0], [2, 1, 0]]
       sage: f.cardinality()
       6

    Caveat: Only certain families with lazy behavior can be pickled. In
    particular, only functions that work with Sage's pickle_function
    and unpickle_function (in sage.misc.fpickle) will correctly
    unpickle. The following two work::

       sage: f = Family(Permutations(3), lambda p: p.to_lehmer_code()); f
       Lazy family (<lambda>(i))_{i in Standard permutations of 3}
       sage: f == loads(dumps(f))
       True

       sage: f = Family(Permutations(3), attrcall("to_lehmer_code")); f
       Lazy family (i.to_lehmer_code())_{i in Standard permutations of 3}
       sage: f == loads(dumps(f))
       True

    But this one does not::

       sage: def plus_n(n): return lambda x: x+n
       sage: f = Family([1,2,3], plus_n(3), lazy=True); f
       Lazy family (<lambda>(i))_{i in [1, 2, 3]}
       sage: f == loads(dumps(f))
       Traceback (most recent call last):
       ...
       ValueError: Cannot pickle code objects from closures

    Finally, it can occasionally be useful to add some hidden elements
    in a family, which are accessible as ``f[i]``, but do not appear in the
    keys or the container operations::

        sage: f = Family([3,4,7], lambda i: 2*i, hidden_keys=[2])
        sage: f
        Finite family {3: 6, 4: 8, 7: 14}
        sage: f.keys()
        [3, 4, 7]
        sage: f.hidden_keys()
        [2]
        sage: f[7]
        14
        sage: f[2]
        4
        sage: list(f)
        [6, 8, 14]
        sage: [x for x in f]
        [6, 8, 14]
        sage: len(f)
        3

    The following example illustrates when the function is actually
    called::

        sage: def compute_value(i):
        ...       print('computing 2*'+str(i))
        ...       return 2*i
        sage: f = Family([3,4,7], compute_value, hidden_keys=[2])
        computing 2*3
        computing 2*4
        computing 2*7
        sage: f
        Finite family {3: 6, 4: 8, 7: 14}
        sage: f.keys()
        [3, 4, 7]
        sage: f.hidden_keys()
        [2]
        sage: f[7]
        14
        sage: f[2]
        computing 2*2
        4
        sage: f[2]
        4
        sage: list(f)
        [6, 8, 14]
        sage: [x for x in f]
        [6, 8, 14]
        sage: len(f)
        3

    Here is a close variant where the function for the hidden keys is
    different from that for the other keys::

        sage: f = Family([3,4,7], lambda i: 2*i, hidden_keys=[2], hidden_function = lambda i: 3*i)
        sage: f
        Finite family {3: 6, 4: 8, 7: 14}
        sage: f.keys()
        [3, 4, 7]
        sage: f.hidden_keys()
        [2]
        sage: f[7]
        14
        sage: f[2]
        6
        sage: list(f)
        [6, 8, 14]
        sage: [x for x in f]
        [6, 8, 14]
        sage: len(f)
        3

    Family accept finite and infinite EnumeratedSets as input::

        sage: f = Family(FiniteEnumeratedSet([1,2,3]))
        sage: f
        Family (1, 2, 3)
        sage: from sage.categories.examples.infinite_enumerated_sets import NonNegativeIntegers
        sage: f = Family(NonNegativeIntegers())
        sage: f
        Family (An example of an infinite enumerated set: the non negative integers)

    ::

        sage: f = Family(FiniteEnumeratedSet([3,4,7]), lambda i: 2*i)
        sage: f
        Finite family {3: 6, 4: 8, 7: 14}
        sage: f.keys()
        {3, 4, 7}
        sage: f[7]
        14
        sage: list(f)
        [6, 8, 14]
        sage: [x for x in f]
        [6, 8, 14]
        sage: len(f)
        3

    TESTS::

        sage: f = Family({1:'a', 2:'b', 3:'c'})
        sage: f
        Finite family {1: 'a', 2: 'b', 3: 'c'}
        sage: f[2]
        'b'
        sage: loads(dumps(f)) == f
        True

    ::

        sage: f = Family({1:'a', 2:'b', 3:'c'}, lazy=True)
        Traceback (most recent call last):
        ValueError: lazy keyword only makes sense together with function keyword !

    ::

        sage: f = Family(range(1,27), lambda i: chr(i+96))
        sage: f
            Finite family {1: 'a', 2: 'b', 3: 'c', 4: 'd', 5: 'e', 6: 'f', 7: 'g', 8: 'h', 9: 'i', 10: 'j', 11: 'k', 12: 'l', 13: 'm', 14: 'n', 15: 'o', 16: 'p', 17: 'q', 18: 'r', 19: 's', 20: 't', 21: 'u', 22: 'v', 23: 'w', 24: 'x', 25: 'y', 26: 'z'}
        sage: f[2]
        'b'

    The factory ``Family`` is supposed to be idempotent. We test this feature here::

        sage: from sage.sets.family import FiniteFamily, LazyFamily, TrivialFamily
        sage: f = FiniteFamily({3: 'a', 4: 'b', 7: 'd'})
        sage: g = Family(f)
        sage: f == g
        True

        sage: f = Family([3,4,7], lambda i: 2*i, hidden_keys=[2])
        sage: g = Family(f)
        sage: f == g
        True

        sage: f = LazyFamily([3,4,7], lambda i: 2*i)
        sage: g = Family(f)
        sage: f == g
        True

        sage: f = TrivialFamily([3,4,7])
        sage: g = Family(f)
        sage: f == g
        True

    The family should keep the order of the keys::

        sage: f = Family(["c", "a", "b"], lambda x: x+x)
        sage: list(f)
        ['cc', 'aa', 'bb']

    TESTS:

    Only the hidden function is applied to the hidden keys::

        sage: f = lambda x : 2*x
        sage: h_f = lambda x:x%2
        sage: F = Family([1,2,3,4],function = f, hidden_keys=[5],hidden_function=h_f)
        sage: F[5]
        1
    """
    assert(type(hidden_keys) == list)
    assert(isinstance(lazy, bool))

    if hidden_keys == []:
        if hidden_function is not None:
            raise ValueError("hidden_function keyword only makes sense "
                             "together with hidden_keys keyword !")
        if function is None:
            if lazy:
                raise ValueError("lazy keyword only makes sense together with function keyword !")
            if isinstance(indices, dict):
                return FiniteFamily(indices)
            if isinstance(indices, (list, tuple) ):
                return TrivialFamily(indices)
            if isinstance(indices, (FiniteFamily, LazyFamily, TrivialFamily) ):
                return indices
            from sage.combinat.combinat import CombinatorialClass # workaround #12482
            if (indices in EnumeratedSets()
                or isinstance(indices, CombinatorialClass)):
                return EnumeratedFamily(indices)
            if hasattr(indices, "__iter__"):
                return TrivialFamily(indices)

            raise NotImplementedError
        if (isinstance(indices, (list, tuple, FiniteEnumeratedSet) )
               and not lazy):
            return FiniteFamily(dict([(i, function(i)) for i in indices]),
                                keys = indices)

        return LazyFamily(indices, function, name)
    if lazy:
        raise ValueError("lazy keyword is incompatible with hidden keys !")
    if hidden_function is None:
        hidden_function = function
    return FiniteFamilyWithHiddenKeys(dict([(i, function(i)) for i in indices]),
                                      hidden_keys, hidden_function)

class AbstractFamily(Parent):
    """
    The abstract class for family

    Any family belongs to a class which inherits from :class:`AbstractFamily`.
    """
    def hidden_keys(self):
        """
        Returns the hidden keys of the family, if any.

        EXAMPLES::

            sage: f = Family({3: 'a', 4: 'b', 7: 'd'})
            sage: f.hidden_keys()
            []
        """
        return []

    def zip(self, f, other, name=None):
        """
        Given two families with same index set `I` (and same hidden
        keys if relevant), returns the family
        `( f(self[i], other[i]) )_{i \in I}`

        .. TODO:: generalize to any number of families and merge with map?

        EXAMPLES::

            sage: f = Family({3: 'a', 4: 'b', 7: 'd'})
            sage: g = Family({3: '1', 4: '2', 7: '3'})
            sage: h = f.zip(lambda x,y: x+y, g)
            sage: list(h)
            ['a1', 'b2', 'd3']
        """
        assert(self.keys() == other.keys())
        assert(self.hidden_keys() == other.hidden_keys())
        return Family(self.keys(), lambda i: f(self[i],other[i]), hidden_keys=self.hidden_keys(), name=name)

    def map(self, f, name=None):
        """
        Returns the family `( f(\mathtt{self}[i]) )_{i \in I}`, where
        `I` is the index set of self.

        .. TODO:: good name?

        EXAMPLES::

            sage: f = Family({3: 'a', 4: 'b', 7: 'd'})
            sage: g = f.map(lambda x: x+'1')
            sage: list(g)
            ['a1', 'b1', 'd1']
        """
        return Family(self.keys(), lambda i: f(self[i]), hidden_keys=self.hidden_keys(), name=name)

    # temporary; tested by TestSuite.
    _an_element_ = EnumeratedSets.ParentMethods._an_element_

    @cached_method
    def inverse_family(self):
        """
        Returns the inverse family, with keys and values
        exchanged. This presumes that there are no duplicate values in
        ``self``.

        This default implementation is not lazy and therefore will
        only work with not too big finite families. It is also cached
        for the same reason::

            sage: Family({3: 'a', 4: 'b', 7: 'd'}).inverse_family()
            Finite family {'a': 3, 'b': 4, 'd': 7}

            sage: Family((3,4,7)).inverse_family()
            Finite family {3: 0, 4: 1, 7: 2}

        """
        return Family( dict( (self[k], k) for k in self.keys()) )

class FiniteFamily(AbstractFamily):
    r"""
    A :class:`FiniteFamily` is an associative container which models a finite
    family `(f_i)_{i \in I}`. Its elements `f_i` are therefore its
    values. Instances should be created via the :func:`Family` factory. See its
    documentation for examples and tests.

    EXAMPLES:

    We define the family `(f_i)_{i \in \{3,4,7\}}` with `f_3=a`,
    `f_4=b`, and `f_7=d`::

        sage: from sage.sets.family import FiniteFamily
        sage: f = FiniteFamily({3: 'a', 4: 'b', 7: 'd'})

    Individual elements are accessible as in a usual dictionary::

        sage: f[7]
        'd'

    And the other usual dictionary operations are also available::

        sage: len(f)
        3
        sage: f.keys()
        [3, 4, 7]

    However f behaves as a container for the `f_i`'s::

        sage: list(f)
        ['a', 'b', 'd']
        sage: [ x for x in f ]
        ['a', 'b', 'd']

    The order of the elements can be specified using the ``keys`` optional argument::

        sage: f = FiniteFamily({"a": "aa", "b": "bb", "c" : "cc" }, keys = ["c", "a", "b"])
        sage: list(f)
        ['cc', 'aa', 'bb']

    """

    def __init__(self, dictionary, keys = None):
        """
        TESTS::

            sage: from sage.sets.family import FiniteFamily
            sage: f = FiniteFamily({3: 'a', 4: 'b', 7: 'd'})
            sage: TestSuite(f).run()

        Check for bug #5538::

            sage: d = {1:"a", 3:"b", 4:"c"}
            sage: f = Family(d)
            sage: d[2] = 'DD'
            sage: f
            Finite family {1: 'a', 3: 'b', 4: 'c'}
            """
        # TODO: use keys to specify the order of the elements
        Parent.__init__(self, category = FiniteEnumeratedSets())
        self._dictionary = dict(dictionary)
        self._keys = keys
        if keys is None:
            # Note: this overrides the two methods keys and values!
            self.keys   = dictionary.keys
            self.values = dictionary.values

    def keys(self):
        """
        Returns the index set of this family

        EXAMPLES::

            sage: f = Family(["c", "a", "b"], lambda x: x+x)
            sage: f.keys()
            ['c', 'a', 'b']
        """
        return self._keys

    def values(self):
        """
        Returns the elements of this family

        EXAMPLES::

            sage: f = Family(["c", "a", "b"], lambda x: x+x)
            sage: f.values()
            ['cc', 'aa', 'bb']
        """
        return [ self._dictionary[key] for key in self._keys ]

    def has_key(self, k):
        """
        Returns whether ``k`` is a key of ``self``

        EXAMPLES::

            sage: Family({"a":1, "b":2, "c":3}).has_key("a")
            True
            sage: Family({"a":1, "b":2, "c":3}).has_key("d")
            False
        """
        return self._dictionary.has_key(k)

    def __eq__(self, other):
        """
        EXAMPLES::

            sage: f = Family({1:'a', 2:'b', 3:'c'})
            sage: g = Family({1:'a', 2:'b', 3:'c'})
            sage: f == g
            True

        TESTS::

            sage: from sage.sets.family import FiniteFamily

            sage: f1 = FiniteFamily({1:'a', 2:'b', 3:'c'}, keys = [1,2,3])
            sage: g1 = FiniteFamily({1:'a', 2:'b', 3:'c'}, keys = [1,2,3])
            sage: h1 = FiniteFamily({1:'a', 2:'b', 3:'c'}, keys = [2,1,3])

            sage: f1 == g1
            True
            sage: f1 == h1
            False
            sage: f1 == f
            False
        """
        return (isinstance(other, self.__class__) and
                self._keys       == other._keys and
                self._dictionary == other._dictionary)

    def _repr_(self):
        """
        EXAMPLES::

            sage: from sage.sets.family import FiniteFamily
            sage: FiniteFamily({3: 'a'}) # indirect doctest
            Finite family {3: 'a'}
        """
        return "Finite family %s"%self._dictionary

    def __contains__(self, x):
        """
        EXAMPLES::

            sage: from sage.sets.family import FiniteFamily
            sage: f = FiniteFamily({3: 'a'})
            sage: 'a' in f
            True
            sage: 'b' in f
            False
        """
        return x in self.values()

    def __len__(self):
        """
        Returns the number of elements in self.

        EXAMPLES::

            sage: from sage.sets.family import FiniteFamily
            sage: f = FiniteFamily({3: 'a', 4: 'b', 7: 'd'})
            sage: len(f)
            3
        """
        return len(self._dictionary)

    def cardinality(self):
        """
        Returns the number of elements in self.

        EXAMPLES::

            sage: from sage.sets.family import FiniteFamily
            sage: f = FiniteFamily({3: 'a', 4: 'b', 7: 'd'})
            sage: f.cardinality()
            3
        """
        return Integer(len(self._dictionary))

    def __iter__(self):
        """
        EXAMPLES::

            sage: from sage.sets.family import FiniteFamily
            sage: f = FiniteFamily({3: 'a'})
            sage: i = iter(f)
            sage: i.next()
            'a'
        """
        return iter(self.values())

    def __getitem__(self, i):
        """
        Note that we can't just do self.__getitem__ =
        dictionary.__getitem__ in the __init__ method since Python
        queries the object's type/class for the special methods rather than
        querying the object itself.

        EXAMPLES::

            sage: from sage.sets.family import FiniteFamily
            sage: f = FiniteFamily({3: 'a', 4: 'b', 7: 'd'})
            sage: f[3]
            'a'
        """
        return self._dictionary.__getitem__(i)

    # For the pickle and copy modules
    def __getstate__(self):
        """
        TESTS::

            sage: from sage.sets.family import FiniteFamily
            sage: f = FiniteFamily({3: 'a'})
            sage: f.__getstate__()
            {'keys': None, 'dictionary': {3: 'a'}}
        """
        return {'dictionary': self._dictionary, 'keys': self._keys}

    def __setstate__(self, state):
        """
        TESTS::

            sage: from sage.sets.family import FiniteFamily
            sage: f = FiniteFamily({3: 'a'})
            sage: f.__setstate__({'dictionary': {4:'b'}})
            sage: f
            Finite family {4: 'b'}
        """
        self.__init__(state['dictionary'], keys = state.get("keys"))

class FiniteFamilyWithHiddenKeys(FiniteFamily):
    r"""
    A close variant of :class:`FiniteFamily` where the family contains some
    hidden keys whose corresponding values are computed lazily (and
    remembered). Instances should be created via the :func:`Family` factory.
    See its documentation for examples and tests.

    Caveat: Only instances of this class whose functions are compatible
    with :mod:`sage.misc.fpickle` can be pickled.
    """
    def __init__(self, dictionary, hidden_keys, hidden_function):
        """
        EXAMPLES::

            sage: f = Family([3,4,7], lambda i: 2*i, hidden_keys=[2])
            sage: TestSuite(f).run()
        """
        FiniteFamily.__init__(self, dictionary)
        self._hidden_keys = hidden_keys
        self.hidden_function = hidden_function
        self.hidden_dictionary = {}

        # would be better to define as usual method
        # any better to unset the def of __getitem__ by FiniteFamily?
        #self.__getitem__ = lambda i: dictionary[i] if dictionary.has_key(i) else hidden_dictionary[i]

    def __getitem__(self, i):
        """
        EXAMPLES::

            sage: f = Family([3,4,7], lambda i: 2*i, hidden_keys=[2])
            sage: f[3]
            6
            sage: f[2]
            4
            sage: f[5]
            Traceback (most recent call last):
            ...
            KeyError
        """
        if i in self._dictionary:
            return self._dictionary[i]

        if i not in self.hidden_dictionary:
            if i not in self._hidden_keys:
                raise KeyError
            self.hidden_dictionary[i] = self.hidden_function(i)

        return self.hidden_dictionary[i]

    def hidden_keys(self):
        """
        Returns self's hidden keys.

        EXAMPLES::

            sage: f = Family([3,4,7], lambda i: 2*i, hidden_keys=[2])
            sage: f.hidden_keys()
            [2]
        """
        return self._hidden_keys

    def __getstate__(self):
        """
        TESTS::

            sage: f = Family([3,4,7], lambda i: 2*i, hidden_keys=[2])
            sage: d = f.__getstate__()
            sage: d['hidden_keys']
            [2]
        """
        from sage.misc.fpickle import pickle_function
        f = pickle_function(self.hidden_function)
        return {'dictionary': self._dictionary,
                'hidden_keys': self._hidden_keys,
                'hidden_dictionary': self.hidden_dictionary,
                'hidden_function': f}

    def __setstate__(self, d):
        """
        TESTS::

            sage: f = Family([3,4,7], lambda i: 2*i, hidden_keys=[2])
            sage: d = f.__getstate__()
            sage: f = Family([4,5,6], lambda i: 2*i, hidden_keys=[2])
            sage: f.__setstate__(d)
            sage: f.keys()
            [3, 4, 7]
            sage: f[3]
            6
        """
        hidden_function = d['hidden_function']
        if isinstance(hidden_function, str):
        # Let's assume that hidden_function is an unpickled function.
            from sage.misc.fpickle import unpickle_function
            hidden_function = unpickle_function(hidden_function)
        self.__init__(d['dictionary'], d['hidden_keys'], hidden_function)
        self.hidden_dictionary = d['hidden_dictionary']


class LazyFamily(AbstractFamily):
    r"""
    A LazyFamily(I, f) is an associative container which models the
    (possibly infinite) family `(f(i))_{i \in I}`.

    Instances should be created via the :func:`Family` factory. See its
    documentation for examples and tests.
    """
    def __init__(self, set, function, name=None):
        """
        TESTS::

            sage: from sage.sets.family import LazyFamily
            sage: f = LazyFamily([3,4,7], lambda i: 2*i); f
            Lazy family (<lambda>(i))_{i in [3, 4, 7]}
            sage: TestSuite(f).run()   # __contains__ is not implemented
            Failure ...
            The following tests failed: _test_an_element, _test_enumerated_set_contains, _test_some_elements

        Check for bug #5538::

            sage: l = [3,4,7]
            sage: f = LazyFamily(l, lambda i: 2*i);
            sage: l[1] = 18
            sage: f
            Lazy family (<lambda>(i))_{i in [3, 4, 7]}
        """
        from sage.combinat.combinat import CombinatorialClass # workaround #12482

        if set in FiniteEnumeratedSets():
            category = FiniteEnumeratedSets()
        elif set in InfiniteEnumeratedSets():
            category = InfiniteEnumeratedSets()
        elif isinstance(set, (list, tuple, CombinatorialClass)):
            category = FiniteEnumeratedSets()
        else:
            category = EnumeratedSets()

        Parent.__init__(self, category = category)
        from copy import copy
        self.set = copy(set)
        self.function = function
        self.function_name = name

    def __eq__(self, other):
        """
        WARNING: Since there is no way to compare function, we only compare
        their name.

        TESTS::

            sage: from sage.sets.family import LazyFamily
            sage: fun = lambda i: 2*i
            sage: f = LazyFamily([3,4,7], fun)
            sage: g = LazyFamily([3,4,7], fun)
            sage: f == g
            True
        """
        from sage.misc.fpickle import pickle_function
        if not isinstance(other, self.__class__):
            return False
        if not self.set == other.set:
            return False
        return self.__repr__() == other.__repr__()

    def _repr_(self):
        """
        EXAMPLES::

            sage: from sage.sets.family import LazyFamily
            sage: def fun(i): 2*i
            sage: f = LazyFamily([3,4,7], fun); f
            Lazy family (fun(i))_{i in [3, 4, 7]}

            sage: f = Family(Permutations(3), attrcall("to_lehmer_code"), lazy=True); f
            Lazy family (i.to_lehmer_code())_{i in Standard permutations of 3}

            sage: f = LazyFamily([3,4,7], lambda i: 2*i); f
            Lazy family (<lambda>(i))_{i in [3, 4, 7]}

            sage: f = LazyFamily([3,4,7], lambda i: 2*i, name='foo'); f
            Lazy family (foo(i))_{i in [3, 4, 7]}

        TESTS:

            Check that a using a class as the function is correctly handled::

                sage: Family(NonNegativeIntegers(), PerfectMatchings)
                Lazy family (<class 'sage.combinat.perfect_matching.PerfectMatchings'>(i))_{i in Non negative integers}
        """
        if self.function_name is not None:
            name = self.function_name + "(i)"
        elif isinstance(self.function, type(lambda x:1)):
            name = self.function.__name__
            name = name+"(i)"
        else:
            name = repr(self.function)
            if isinstance(self.function, AttrCallObject):
                name = "i"+name[1:]
            else:
                name = name+"(i)"
        return "Lazy family ({})_{{i in {}}}".format(name, self.set)

    def keys(self):
        """
        Returns self's keys.

        EXAMPLES::

            sage: from sage.sets.family import LazyFamily
            sage: f = LazyFamily([3,4,7], lambda i: 2*i)
            sage: f.keys()
            [3, 4, 7]
        """
        return self.set

    def cardinality(self):
        """
        Return the number of elements in self.

        EXAMPLES::

            sage: from sage.sets.family import LazyFamily
            sage: f = LazyFamily([3,4,7], lambda i: 2*i)
            sage: f.cardinality()
            3
            sage: from sage.categories.examples.infinite_enumerated_sets import NonNegativeIntegers
            sage: l = LazyFamily(NonNegativeIntegers(), lambda i: 2*i)
            sage: l.cardinality()
            +Infinity

        TESTS:

        Check that :trac:`15195` is fixed::

            sage: C = CartesianProduct(PositiveIntegers(), [1,2,3])
            sage: C.cardinality()
            +Infinity
            sage: F = Family(C, lambda x: x)
            sage: F.cardinality()
            +Infinity
            """
        try:
            return Integer(len(self.set))
        except (AttributeError, NotImplementedError, TypeError):
            return self.set.cardinality()

    def __iter__(self):
        """
        EXAMPLES::

            sage: from sage.sets.family import LazyFamily
            sage: f = LazyFamily([3,4,7], lambda i: 2*i)
            sage: [i for i in f]
            [6, 8, 14]
        """
        for i in self.set:
            yield self[i]

    def __getitem__(self, i):
        """
        EXAMPLES::

            sage: from sage.sets.family import LazyFamily
            sage: f = LazyFamily([3,4,7], lambda i: 2*i)
            sage: f[3]
            6

        TESTS::

            sage: f[5]
            10
        """
        return self.function(i)

    def __getstate__(self):
        """
        EXAMPLES::

            sage: from sage.sets.family import LazyFamily
            sage: f = LazyFamily([3,4,7], lambda i: 2*i)
            sage: d = f.__getstate__()
            sage: d['set']
            [3, 4, 7]

            sage: f = LazyFamily(Permutations(3), lambda p: p.to_lehmer_code())
            sage: f == loads(dumps(f))
            True

            sage: f = LazyFamily(Permutations(3), attrcall("to_lehmer_code"))
            sage: f == loads(dumps(f))
            True
        """
        f = self.function
        # This should be done once for all by registering
        # sage.misc.fpickle.pickle_function to copy_reg
        if type(f) is type(Family): # TODO: where is the python `function` type?
            from sage.misc.fpickle import pickle_function
            f = pickle_function(f)

        return {'set': self.set,
                'function': f}

    def __setstate__(self, d):
        """
        EXAMPLES::

            sage: from sage.sets.family import LazyFamily
            sage: f = LazyFamily([3,4,7], lambda i: 2*i)
            sage: d = f.__getstate__()
            sage: f = LazyFamily([4,5,6], lambda i: 2*i)
            sage: f.__setstate__(d)
            sage: f.keys()
            [3, 4, 7]
            sage: f[3]
            6
        """
        function = d['function']
        if isinstance(function, str):
        # Let's assume that function is an unpickled function.
            from sage.misc.fpickle import unpickle_function
            function = unpickle_function(function)

        self.__init__(d['set'], function)


class TrivialFamily(AbstractFamily):
    r"""
    :class:`TrivialFamily` turns a list/tuple `c` into a family indexed by the
    set `\{0, \dots, |c|-1\}`.

    Instances should be created via the :func:`Family` factory. See its
    documentation for examples and tests.
    """
    def __init__(self, enumeration):
        """
        EXAMPLES::

            sage: from sage.sets.family import TrivialFamily
            sage: f = TrivialFamily((3,4,7)); f
            Family (3, 4, 7)
            sage: f = TrivialFamily([3,4,7]); f
            Family (3, 4, 7)
            sage: TestSuite(f).run()
        """
        Parent.__init__(self, category = FiniteEnumeratedSets())
        self._enumeration = tuple(enumeration)

    def __eq__(self, other):
        """
        TESTS::

        sage: f = Family((3,4,7))
        sage: g = Family([3,4,7])
        sage: f == g
        True
        """
        return (isinstance(other, self.__class__) and
                self._enumeration == other._enumeration)

    def _repr_(self):
        """
        EXAMPLES::

            sage: from sage.sets.family import TrivialFamily
            sage: f = TrivialFamily([3,4,7]); f # indirect doctest
            Family (3, 4, 7)
        """
        return "Family %s"%((self._enumeration),)

    def keys(self):
        """
        Returns self's keys.

        EXAMPLES::

            sage: from sage.sets.family import TrivialFamily
            sage: f = TrivialFamily([3,4,7])
            sage: f.keys()
            [0, 1, 2]
        """
        return range(len(self._enumeration))

    def cardinality(self):
        """
        Return the number of elements in self.

        EXAMPLES::

            sage: from sage.sets.family import TrivialFamily
            sage: f = TrivialFamily([3,4,7])
            sage: f.cardinality()
            3
        """
        return Integer(len(self._enumeration))

    def __iter__(self):
        """
        EXAMPLES::

            sage: from sage.sets.family import TrivialFamily
            sage: f = TrivialFamily([3,4,7])
            sage: [i for i in f]
            [3, 4, 7]
        """
        return iter(self._enumeration)

    def __contains__(self, x):
        """
        EXAMPLES::

            sage: from sage.sets.family import TrivialFamily
            sage: f = TrivialFamily([3,4,7])
            sage: 3 in f
            True
            sage: 5 in f
            False
        """
        return x in self._enumeration

    def __getitem__(self, i):
        """
        EXAMPLES::

            sage: from sage.sets.family import TrivialFamily
            sage: f = TrivialFamily([3,4,7])
            sage: f[1]
            4
        """
        return self._enumeration[i]

    def __getstate__(self):
        """
        TESTS::

            sage: from sage.sets.family import TrivialFamily
            sage: f = TrivialFamily([3,4,7])
            sage: f.__getstate__()
            {'_enumeration': (3, 4, 7)}
        """
        return {'_enumeration': self._enumeration}

    def __setstate__(self, state):
        """
        TESTS::

            sage: from sage.sets.family import TrivialFamily
            sage: f = TrivialFamily([3,4,7])
            sage: f.__setstate__({'_enumeration': (2, 4, 8)})
            sage: f
            Family (2, 4, 8)
        """
        self.__init__(state['_enumeration'])



from sage.categories.examples.infinite_enumerated_sets import NonNegativeIntegers
from sage.rings.infinity import Infinity

class EnumeratedFamily(LazyFamily):
    r"""
    :class:`EnumeratedFamily` turns an enumerated set ``c`` into a family
    indexed by the set `\{0,\dots, |c|-1\}`.

    Instances should be created via the :func:`Family` factory. See its
    documentation for examples and tests.
    """
    def __init__(self, enumset):
        """
        EXAMPLES::

            sage: from sage.sets.family import EnumeratedFamily
            sage: f = EnumeratedFamily(Permutations(3))
            sage: TestSuite(f).run()

            sage: from sage.categories.examples.infinite_enumerated_sets import NonNegativeIntegers
            sage: f = Family(NonNegativeIntegers())
            sage: TestSuite(f).run()
        """
        if enumset.cardinality() == Infinity:
            baseset=NonNegativeIntegers()
        else:
            baseset=xrange(enumset.cardinality())
        LazyFamily.__init__(self, baseset, enumset.unrank)
        self.enumset = enumset

    def __eq__(self, other):
        """
        EXAMPLES::

            sage: f = Family(Permutations(3))
            sage: g = Family(Permutations(3))
            sage: f == g
            True
        """
        return (isinstance(other, self.__class__) and
                self.enumset == other.enumset)

    def __repr__(self):
        """
        EXAMPLES::

            sage: f = Family(Permutations(3)); f # indirect doctest
            Family (Standard permutations of 3)

            sage: from sage.categories.examples.infinite_enumerated_sets import NonNegativeIntegers
            sage: f = Family(NonNegativeIntegers()); f
            Family (An example of an infinite enumerated set: the non negative integers)
        """
#        return "Family ((%s)[i])_(i=1...%s)"%(self.enumset, self.enumset.cardinality())
        if isinstance(self.enumset, FiniteEnumeratedSet):
            return "Family %s"%(self.enumset._elements,)
        return "Family (%s)"%(self.enumset)

    def __contains__(self, x):
        """
        EXAMPLES::

            sage: f = Family(Permutations(3))
            sage: f.keys()
            Standard permutations of 3
            sage: [2,1,3] in f
            True
        """
        return x in self.enumset


    def keys(self):
        """
        Returns self's keys.

        EXAMPLES::

            sage: from sage.sets.family import EnumeratedFamily
            sage: f = EnumeratedFamily(Permutations(3))
            sage: f.keys()
            Standard permutations of 3

            sage: from sage.categories.examples.infinite_enumerated_sets import NonNegativeIntegers
            sage: f = Family(NonNegativeIntegers())
            sage: f.keys()
            An example of an infinite enumerated set: the non negative integers
        """
        return self.enumset

    def cardinality(self):
        """
        Return the number of elements in self.

        EXAMPLES::

            sage: from sage.sets.family import EnumeratedFamily
            sage: f = EnumeratedFamily(Permutations(3))
            sage: f.cardinality()
            6

            sage: from sage.categories.examples.infinite_enumerated_sets import NonNegativeIntegers
            sage: f = Family(NonNegativeIntegers())
            sage: f.cardinality()
            +Infinity
        """
        return self.enumset.cardinality()

    def __iter__(self):
        """
        EXAMPLES::

            sage: from sage.sets.family import EnumeratedFamily
            sage: f = EnumeratedFamily(Permutations(3))
            sage: [i for i in f]
            [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
        """
        for i in self.enumset:
            yield i

    def __getitem__(self, i):
        """
        EXAMPLES::

            sage: from sage.sets.family import EnumeratedFamily
            sage: f = EnumeratedFamily(Permutations(3));
            sage: f[1]
            [1, 3, 2]
        """
        return self.enumset.unrank(i)

    def __getstate__(self):
        """
        EXAMPLES::

            sage: from sage.sets.family import EnumeratedFamily
            sage: f = EnumeratedFamily(Permutations(3));
            sage: f.__getstate__()
            {'enumset': Standard permutations of 3}
            sage: loads(dumps(f)) == f
            True
        """
        return {'enumset': self.enumset}

    def __setstate__(self, state):
        """
        EXAMPLES::

            sage: from sage.sets.family import EnumeratedFamily
            sage: f = EnumeratedFamily(Permutations(0));
            sage: f.__setstate__({'enumset': Permutations(3)})
            sage: f
            Family (Standard permutations of 3)
        """
        self.__init__(state['enumset'])