text: """
  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 <mhansen@gmail.com>,
  #                          Florent Hivert <Florent.Hivert@univ-rouen.fr>
  #
  #  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(isinstance(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
  
      @cached_method
      def __hash__(self):
          """
          Return a hash value for ``self``.
  
          EXAMPLES::
  
              sage: f = Family(["c", "a", "b"], lambda x: x+x)
              sage: hash(f) == hash(f)
              True
              sage: f2 = Family(["a", "c", "b"], lambda x: x+x)
              sage: hash(f) == hash(f2)
              True
              sage: g = Family(["b", "c", "a"], lambda x: x+x+x)
              sage: hash(f) == hash(g)
              False
  
          ::
  
              sage: f = Family({1:[1,2]})
              sage: hash(f) == hash(f)
              True
          """
          try:
              return hash(frozenset(self._dictionary.items()))
          except (TypeError, ValueError):
              return hash(frozenset(list(self.keys()) + map(repr, self.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 k in self._dictionary
  
      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
  
      @cached_method
      def __hash__(self):
          """
          Return a hash value for ``self``.
  
          EXAMPLES::
  
              sage: from sage.sets.family import LazyFamily
              sage: f = LazyFamily([3,4,7], lambda i: 2*i)
              sage: hash(f) == hash(f)
              True
              sage: g = LazyFamily(ZZ, lambda i: 2*i)
              sage: hash(g) == hash(g)
              True
              sage: h = LazyFamily(ZZ, lambda i: 2*i, name='foo')
              sage: hash(h) == hash(h)
              True
  
          ::
  
              sage: class X(object):
              ....:     def __call__(self, x):
              ....:         return x
              ....:     __hash__ = None
              sage: f = Family([1,2,3], X())
              sage: hash(f) == hash(f)
              True
          """
          try:
              return hash(self.keys()) + hash(self.function)
          except (TypeError, ValueError):
              return super(LazyFamily, self).__hash__()
  
      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 isinstance(f, 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 __hash__(self):
          """
          Return a hash value for ``self``.
  
          EXAMPLES::
  
              sage: from sage.sets.family import TrivialFamily
              sage: f = TrivialFamily((3,4,7))
              sage: hash(f) == hash(f)
              True
          """
          return hash(self._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'])
  