# Commits

committed 33f8db6

updated for sage-5.9.beta2

• Participants
• Parent commits 1c09529
• Branches default

# File series

-trac_14359_doctest_unicode_warning.patch  #+todo
+trac_14375_ansi_escapes_indication.patch
 trac_14187_lazy_import_test.patch
 trac_14014_libgap_cyclotomic_matrix.patch
 trac_14014_deletions.patch

# File toric_chow_group.patch

+# User Volker Braun <vbraun@stp.dias.ie>
+
+diff -r ed0826ec137c sage/schemes/generic/toric_chow_group.py
+--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
++++ b/sage/schemes/generic/toric_chow_group.py	Tue Jun 22 16:31:12 2010 +0200
+@@ -0,0 +1,200 @@
++r"""
++The Chow group of a toric variety.
++"""
++
++#*****************************************************************************
++#       Copyright (C) 2010 Volker Braun  <vbraun.name@gmail.com>
++#
++#  Distributed under the terms of the GNU General Public License (GPL)
++#
++#                  http://www.gnu.org/licenses/
++#*****************************************************************************
++
++
++from sage.structure.sage_object import SageObject
++from sage.geometry.cone import is_Cone
++from sage.geometry.fan import is_Fan
++
++
++class ChowCycle(SageObject):
++   r"""
++   An element in the Chow group of a toric variety.
++
++   NOTES:
++
++   * For smooth toric varieties, A_k(X)  = H^{2k}(X,\mathbb{Z})
++
++   * For simplicial toric varieties, A_k(X)\otimes \mathbb{Q}  = H^{2k}(X,\mathbb{Q})
++
++   .. WARNING::
++
++       You should never manually create ChowCycle objects. See
++       Cone.A() for how to construct the Chow (homology) cycle
++       corresponding to a cone of a fan of a toric variety.
++   """
++
++   _desc = "An element of the Chow group"
++
++   def __init__(self, initializing_data=None, ring=ZZ):
++      r"""
++      Construct the Chow group element corresponding to the orbit
++      closure V(\sigma), where \sigma is a cone of the fan of a
++      toric variety.
++
++      INPUT:
++
++      * Either a cone of a fan, see :class:sage.geometry.cone.Cone_of_fan
++
++      * or a list/vector/tuple of ring elements defining the Chow cycle.
++
++      * or None for the neutral element in the Chow group.
++
++      EXAMPLES::
++
++      fan = toric_varieties.dP6().fan()
++      cone = fan.generating_cone(0)
++      cone.A()
++      """
++      self._ring = ring
++
++      if initializing_data==None:
++         self._v = self._zero()
++         return
++
++      elif is_Cone(initializing_data):
++         cone = initializing_data
++         fan = cone.ambient()
++         assert is_Fan(fan), 'The given cone must be a cone in a fan!'
++         cone_dim, k = X.cone_to_fan_idx(cone.index())
++         self._v = self._zero()
++         self._v[X.dimension()-cone_dim][k] = 1
++
++
++      try:
++         self._v = [ vector(self._ring, c) for c in chow_repr ]
++
++      except TypeError:
++         # assume that chow_repr is a Cone object
++
++
++
++   def _zero(self):
++      """
++      Returns the data structure representing the neutral element in
++      the Chow group
++      """
++      d = self._variety.dimension()
++      return [ vector(self._ring, [0]*self._variety.n_fan(d-i))
++               for i in range(0,d+1) ]
++
++
++   def _repr_(self):
++      """
++      The string representation of the Chow cycle
++      """
++      return str(self._v)
++
++
++   # def __mul__(self, other):
++   #    """
++   #    Multiplication in the Chow group.
++   #    """
++   #    if isinstance(other,Divisor):
++   #       return self.intersect_with_divisor(other)
++
++   #    constant = other
++   #    v = [ constant*self._v[i] for i in range(0,len(self._v)) ]
++
++   #    ring = v[0].base_ring()
++   #    return ChowCycle(self._variety, v, ring=ring)
++
++
++   # def __rmul__(self, constant):
++   #    """
++   #    Multiplication in the Chow group.
++   #    """
++   #    return self.__mul__(constant)
++
++
++   def __neg__(self):
++      return ChowCycle(self._variety, [-v for v in self._v], ring=self._ring)
++
++
++   def __add__(self, other):
++      """
++      Addition in the Chow ring.
++      """
++      if other==0:
++         return self.__radd__(other)
++
++      v = [ self._v[i]+other._v[i] for i in range(0,len(self._v)) ]
++
++      ring = v[0].base_ring()
++      return ChowCycle(self._variety, v, ring=ring)
++
++
++   def __radd__(self, x):
++      assert x==0
++      v = [ vector(self._ring, self._v[i]) for i in range(0,len(self._v)) ]
++      return ChowCycle(self._variety, v, ring=self._ring)
++
++
++   def __iadd__(self, other):
++      """
++      In-place addition in the Chow ring.
++      """
++      if other==0:
++         return self
++
++      for i in range(0,len(self._v)):
++         self._v[i] += other._v[i]
++
++      self._ring = self._v[0].base_ring()
++      return self
++
++
++   # def intersect_with_divisor(self, divisor):
++   #    """
++   #    Intersects the Chow homology class with a Cartier divisor.
++
++   #    EXAMPLES::
++
++   #        sage: dP6=toric_variety("dP6")
++   #        sage: p = dP6.find_cone([2])
++   #        sage: D = p.divisor()
++   #        sage: D_chow = p.A()
++   #        sage: D_chow.intersect_with_divisor(D)
++   #        [(0, -1, 0, 0, 0, 0), (0, 0, 0, 0, 0, 0), (0)]
++   #        sage: dP6.degree(_)
++   #        -1
++   #        sage: rel = dP6.rational_equivalence_relations()['Chow_group_relations']
++   #        sage: list( r.intersect_with_divisor(D) for r in rel )
++   #        [[(0, 0, 0, 0, 0, 0), (0, 0, 0, 0, 0, 0), (0)], [(0, 0, 0, 0, 0, 0), (0, 0, 0, 0, 0, 0), (0)], [(0, 0, 0, 0, 0, 0), (0, 0, 0, 0, 0, 0), (0)], [(0, 0, 0, 0, 0, 0), (0, 0, 0, 0, 0, 0), (0)], [(0, 0, 0, 0, 0, 0), (0, 0, 0, 0, 0, 0), (0)], [(0, 0, 0, 0, 0, 0), (0, 0, 0, 0, 0, 0), (0)], [(0, 0, 0, 0, 0, 0), (0, 0, 0, 0, 0, 0), (0)], [(1, -1, 0, 0, 0, 0), (0, 0, 0, 0, 0, 0), (0)]]
++   #    """
++   #    intersection = ChowCycle(self._variety, ring=self._ring)
++   #    X = self._variety
++   #    for d in range(1,X.dimension()):
++   #       for k in range(0,X.n_fan(d)):
++   #          coeff = self._v[X.dimension()-d][k]
++   #          if coeff==0:
++   #             continue
++   #          sigma_idx = X.fan_to_cone_idx(d,k)
++   #          sigma = X.cone(sigma_idx)
++   #          D = divisor.move_away_from(sigma)
++   #          for gamma in sigma.bounds():
++   #             n = gamma.N_quotient(sigma).row(0)
++   #             perp = sigma.M_quotient(gamma).row(0)
++   #             I_gamma = gamma._points_idx - sigma._points_idx
++   #             i = iter(I_gamma).next()
++   #             v_i = vector(X.point(i))
++   #             a_i = D(i)
++   #             s_i = (v_i*perp)/(n*perp)
++   #             b_gamma = self._ring( a_i/s_i )
++   #             try:
++   #                b_gamma = self._ring(b_gamma)
++   #             except TypeError:
++   #                pass # intersection will be coerced
++   #             # print sigma._points_idx, "\t", i, D, a_i, s_i, b_gamma, gamma.A()
++   #             intersection += (coeff*b_gamma)*gamma.A()
++   #    return intersection
++

# File trac_14014_iterator.patch

 # HG changeset patch
-# Parent 12669e705c97bb02e5813691a1db8a6ab06044c9
+# Parent 74a822bf61aff6dca6884cf51852c8264af160bc

-diff --git a/sage/groups/matrix_gps/finitely_generated.py b/sage/groups/matrix_gps/finitely_generated.py
---- a/sage/groups/matrix_gps/finitely_generated.py
-+++ b/sage/groups/matrix_gps/finitely_generated.py
-@@ -266,7 +266,8 @@
-             )
+Implement the matrix group iterator via the GAP permutation group
+iterator, and make it consistent with the list() method.
+
+diff --git a/doc/en/thematic_tutorials/lie/weyl_groups.rst b/doc/en/thematic_tutorials/lie/weyl_groups.rst
+--- a/doc/en/thematic_tutorials/lie/weyl_groups.rst
++++ b/doc/en/thematic_tutorials/lie/weyl_groups.rst
+@@ -212,7 +212,7 @@
+     sage: def bi(u,v) : return [t for t in W if u.bruhat_le(t) and t.bruhat_le(v)]
+     ...
+     sage: bi(s1,s1*s2*s1)
+-    [s1, s1*s2, s1*s2*s1, s2*s1]
++    [s1*s2*s1, s1*s2, s2*s1, s1]
+
+ This would not be a good definition since it would fail if W is
+ affine and be inefficient of W is large. Sage has a Bruhat interval
+diff --git a/doc/en/thematic_tutorials/tutorial-comprehensions.rst b/doc/en/thematic_tutorials/tutorial-comprehensions.rst
+--- a/doc/en/thematic_tutorials/tutorial-comprehensions.rst
++++ b/doc/en/thematic_tutorials/tutorial-comprehensions.rst
+@@ -335,9 +335,6 @@
+     [0 1]
+     [1 1]
+     <BLANKLINE>
+-    [1 1]
+-    [0 1]
+-    <BLANKLINE>
+     [1 0]
+     [0 1]
+     <BLANKLINE>
+@@ -345,6 +342,9 @@
+     [1 1]
+     <BLANKLINE>
+     [1 1]
++    [0 1]
++    <BLANKLINE>
++    [1 1]
+     [1 0]
+     <BLANKLINE>
+
+diff --git a/sage/algebras/group_algebra_new.py b/sage/algebras/group_algebra_new.py
+--- a/sage/algebras/group_algebra_new.py
++++ b/sage/algebras/group_algebra_new.py
+@@ -592,8 +592,8 @@
+             sage: GroupAlgebra(DihedralGroup(6), QQ).random_element()
+             -1/95*(2,6)(3,5) - 1/2*(1,3)(4,6)
+             sage: GroupAlgebra(SU(2, 13), QQ).random_element(1)
+-            1/2*[       6  5*a + 4]
+-            [6*a + 10       12]
++            1/2*[      12 12*a + 7]
++            [   a + 6        7]
          """
-         self._gens_matrix = generator_matrices
--        MatrixGroup_generic.__init__(self, degree, base_ring)
-+        from sage.categories.enumerated_sets import EnumeratedSets
-+        MatrixGroup_generic.__init__(self, degree, base_ring, category=EnumeratedSets())
+         a = self(0)
+         for i in range(n):
+diff --git a/sage/algebras/iwahori_hecke_algebra.py b/sage/algebras/iwahori_hecke_algebra.py
+--- a/sage/algebras/iwahori_hecke_algebra.py
++++ b/sage/algebras/iwahori_hecke_algebra.py
+@@ -49,7 +49,7 @@
+         sage: w0
+         s1*s2*s3*s1*s2*s1
+         sage: H.an_element()
+-        s1*s2*s3 + 3*s1*s2 + 2*s1 + 1
++        s1*s2*s3*s1*s2*s1 + 2*s1*s2*s3*s1*s2 + 3*s1*s2*s3*s2*s1 + s1*s2*s3
+
+     Iwahori Hecke algebras have proved to be fundamental. See for example:
+
+@@ -204,8 +204,7 @@
+             sage: R.<q>=QQ[]
+             sage: H = IwahoriHeckeAlgebraT("A2",q)
+             sage: [H(x) for x in H.coxeter_group()]   # indirect doctest
+-            [1, T1, T1*T2, T1*T2*T1, T2, T2*T1]
+-
++            [T1*T2*T1, T1*T2, T2*T1, T1, T2, 1]
+         """
+         assert w in self.basis().keys()
+         return self.monomial(w)
+diff --git a/sage/categories/groups.py b/sage/categories/groups.py
+--- a/sage/categories/groups.py
++++ b/sage/categories/groups.py
+@@ -207,12 +207,12 @@
+                 sage: M.cayley_table()
+                 *  a b c d e f
+                  +------------
+-                a| d c b a f e
+-                b| e f a b c d
+-                c| f e d c b a
+-                d| a b c d e f
+-                e| b a f e d c
+-                f| c d e f a b
++                a| c e a f b d
++                b| d f b e a c
++                c| a b c d e f
++                d| b a d c f e
++                e| f d e b c a
++                f| e c f a d b
+
+             ::
+
+diff --git a/sage/combinat/root_system/root_system.py b/sage/combinat/root_system/root_system.py
+--- a/sage/combinat/root_system/root_system.py
++++ b/sage/combinat/root_system/root_system.py
+@@ -228,13 +228,13 @@
+         sage: W = L.weyl_group()
+         sage: S3 = [ w.action(id) for w in W.classical() ]
+         sage: [L.classical()(x) for x in S3]
+-        [(1, 2, 3), (2, 1, 3), (3, 1, 2), (3, 2, 1), (1, 3, 2), (2, 3, 1)]
++        [(3, 2, 1), (3, 1, 2), (2, 3, 1), (2, 1, 3), (1, 3, 2), (1, 2, 3)]
+
+     And the action of s_0 on these yields::
+
+         sage: s = W.simple_reflections()
+         sage: [L.classical()(s[0].action(x)) for x in S3]
+-        [(0, 2, 4), (0, 1, 5), (-1, 1, 6), (-2, 2, 6), (-1, 3, 4), (-2, 3, 5)]
++        [(-2, 2, 6), (-1, 1, 6), (-2, 3, 5), (0, 1, 5), (-1, 3, 4), (0, 2, 4)]
+
+     .. RUBRIC:: Dual root systems
+
+diff --git a/sage/combinat/root_system/weyl_group.py b/sage/combinat/root_system/weyl_group.py
+--- a/sage/combinat/root_system/weyl_group.py
++++ b/sage/combinat/root_system/weyl_group.py
+@@ -301,7 +301,7 @@
+         except StandardError:
+             raise NotImplementedError, "reflections are only implemented for finite Weyl groups"
+
+-    def __repr__(self):
++    def _repr_(self):
+         """
+         EXAMPLES::
+
+@@ -315,53 +315,6 @@
+                                                                                                       base_ring=False,
+                                                                                                       type=False))
+
+-
+-    def list(self):
+-        """
+-        Returns a list of the elements of self.
+-
+-        EXAMPLES::
+-
+-            sage: G = WeylGroup(['A',1])
+-            sage: G.list()
+-            [
+-            [1 0]  [0 1]
+-            [0 1], [1 0]
+-            ]
+-
+-            sage: G = WeylGroup(['A',3,1])
+-            sage: G.list()
+-            Traceback (most recent call last):
+-              ...
+-            NotImplementedError: infinite list
+-
+-        This overrides the implementation of MatrixGroup_gap.
+-        Those seem typical timings (without the overriding):
+-
+-        #   sage: W = WeylGroup(["C",4])
+-
+-        #   sage: %time  len(W.list())
+-            CPU times: user 7.63 s, sys: 0.60 s, total: 8.22 s
+-            Wall time: 8.63 s
+-
+-        #    sage: %time  len([ x for x in W])
+-            CPU times: user 3.23 s, sys: 0.09 s, total: 3.32 s
+-            Wall time: 3.34 s
+-
+-        #    sage: %time  len(list(W))
+-            CPU times: user 3.26 s, sys: 0.02 s, total: 3.28 s
+-            Wall time: 3.29 s
+-
+-        Note: listing the matrices in GAP is much faster than the
+-        timings above suggest; the slowness apparently comes from the
+-        interface with GAP, and are therefore highly subject to
+-        improvement.
+-        """
+-        if hasattr(self, "_list_from_iterator"):
+-            return self._list_from_iterator()
+-        else:
+-            raise NotImplementedError, "infinite list"
+-
+     def character_table(self):
+         """
+         Returns the character table as a matrix
+@@ -680,7 +633,7 @@
+     """
+     Class for a Weyl Group elements
+     """
+-    def __init__(self, g, parent):
++    def __init__(self, g, parent, check=False):
+         """
+         EXAMPLES::

-     def __cmp__(self, other):
+@@ -688,7 +641,7 @@
+             sage: s1 = G.simple_reflection(1)
+             sage: TestSuite(s1).run()
          """
+-        MatrixGroupElement_gap.__init__(self, g, parent, check=False)
++        MatrixGroupElement_gap.__init__(self, g, parent, check=check)
+         self.__matrix = self.matrix()
+         self._parent = parent
+
+diff --git a/sage/combinat/tiling.py b/sage/combinat/tiling.py
+--- a/sage/combinat/tiling.py
++++ b/sage/combinat/tiling.py
+@@ -257,31 +257,31 @@
+         sage: from sage.combinat.tiling import orthogonal_transformation
+         sage: orthogonal_transformation(2)
+         [
+-        [1 0]  [ 0 -1]  [ 0  1]  [-1  0]
+-        [0 1], [ 1  0], [-1  0], [ 0 -1]
++        [-1  0]  [ 0 -1]  [ 0  1]  [1 0]
++        [ 0 -1], [ 1  0], [-1  0], [0 1]
+         ]
+         sage: orthogonal_transformation(2, orientation_preserving=False)
+         [
+-        [1 0]  [0 1]  [ 0 -1]  [-1  0]  [ 1  0]  [ 0  1]  [ 0 -1]  [-1  0]
+-        [0 1], [1 0], [ 1  0], [ 0  1], [ 0 -1], [-1  0], [-1  0], [ 0 -1]
++        [-1  0]  [-1  0]  [ 0 -1]  [ 0 -1]  [ 0  1]  [0 1]  [ 1  0]  [1 0]
++        [ 0 -1], [ 0  1], [-1  0], [ 1  0], [-1  0], [1 0], [ 0 -1], [0 1]
+         ]
+         sage: orthogonal_transformation(3)
+         [
+-        [1 0 0]  [0 0 1]  [ 0  0 -1]  [-1  0  0]  [ 0 -1  0]  [0 1 0]
+-        [0 1 0]  [1 0 0]  [ 0  1  0]  [ 0  0  1]  [ 1  0  0]  [0 0 1]
+-        [0 0 1], [0 1 0], [ 1  0  0], [ 0  1  0], [ 0  0  1], [1 0 0],
++        [-1  0  0]  [-1  0  0]  [-1  0  0]  [-1  0  0]  [ 0 -1  0]  [ 0 -1  0]
++        [ 0 -1  0]  [ 0  0 -1]  [ 0  0  1]  [ 0  1  0]  [-1  0  0]  [ 0  0 -1]
++        [ 0  0  1], [ 0 -1  0], [ 0  1  0], [ 0  0 -1], [ 0  0 -1], [ 1  0  0],
+         <BLANKLINE>
+-        [ 1  0  0]  [ 0  0  1]  [ 0  0 -1]  [-1  0  0]  [ 0 -1  0]  [ 0  1  0]
+-        [ 0  0 -1]  [ 0 -1  0]  [-1  0  0]  [ 0 -1  0]  [ 0  0 -1]  [-1  0  0]
+-        [ 0  1  0], [ 1  0  0], [ 0  1  0], [ 0  0  1], [ 1  0  0], [ 0  0  1],
++        [ 0 -1  0]  [ 0 -1  0]  [ 0  0 -1]  [ 0  0 -1]  [ 0  0 -1]  [ 0  0 -1]
++        [ 0  0  1]  [ 1  0  0]  [-1  0  0]  [ 0 -1  0]  [ 0  1  0]  [ 1  0  0]
++        [-1  0  0], [ 0  0  1], [ 0  1  0], [-1  0  0], [ 1  0  0], [ 0 -1  0],
+         <BLANKLINE>
+-        [ 0  1  0]  [ 0  0  1]  [ 0  0 -1]  [ 0 -1  0]  [-1  0  0]  [ 1  0  0]
+-        [ 1  0  0]  [ 0  1  0]  [ 1  0  0]  [ 0  0  1]  [ 0  1  0]  [ 0  0  1]
+-        [ 0  0 -1], [-1  0  0], [ 0 -1  0], [-1  0  0], [ 0  0 -1], [ 0 -1  0],
++        [ 0  0  1]  [ 0  0  1]  [ 0  0  1]  [0 0 1]  [ 0  1  0]  [ 0  1  0]
++        [-1  0  0]  [ 0 -1  0]  [ 0  1  0]  [1 0 0]  [-1  0  0]  [ 0  0 -1]
++        [ 0 -1  0], [ 1  0  0], [-1  0  0], [0 1 0], [ 0  0  1], [-1  0  0],
+         <BLANKLINE>
+-        [ 0  1  0]  [ 0  0  1]  [ 0  0 -1]  [ 0 -1  0]  [-1  0  0]  [ 1  0  0]
+-        [ 0  0 -1]  [-1  0  0]  [ 0 -1  0]  [-1  0  0]  [ 0  0 -1]  [ 0 -1  0]
+-        [-1  0  0], [ 0 -1  0], [-1  0  0], [ 0  0 -1], [ 0 -1  0], [ 0  0 -1]
++        [0 1 0]  [ 0  1  0]  [ 1  0  0]  [ 1  0  0]  [ 1  0  0]  [1 0 0]
++        [0 0 1]  [ 1  0  0]  [ 0 -1  0]  [ 0  0 -1]  [ 0  0  1]  [0 1 0]
++        [1 0 0], [ 0  0 -1], [ 0  0 -1], [ 0  1  0], [ 0 -1  0], [0 0 1]
+         ]
+
+     TESTS::
+@@ -1361,25 +1361,25 @@
+             sage: y = Polyomino([(0,0),(1,0),(2,0),(3,0),(2,1)], color='yellow')
+             sage: T = TilingSolver([y], box=(5,10), reusable=True, reflection=True)
+             sage: for a in T.dlx_common_prefix_solutions(): a
+-            [18, 119, 68, 33, 48, 23, 8, 73, 58, 43]
+-            [18, 119, 68, 33, 48]
+-            [18, 119, 68, 33, 48, 133, 8, 73, 168, 43]
+-            [18, 119]
+-            [18, 119, 178, 143, 48, 23, 8, 73, 58, 43]
+-            [18, 119, 178, 143, 48]
+-            [18, 119, 178, 143, 48, 133, 8, 73, 168, 43]
+-            [18, 119, 178]
+-            [18, 119, 178, 164, 152, 73, 8, 133, 159, 147]
++            [46, 83, 149, 26, 179, 44, 81, 162, 132, 101]
++            [46, 83, 149, 26, 179]
++            [46, 83, 149, 26, 179, 154, 81, 162, 132, 175]
++            [46, 83, 149]
++            [46, 83, 149, 97, 21, 162, 81, 44, 30, 106]
++            [46]
++            [46, 157, 149, 136, 179, 44, 81, 162, 132, 101]
++            [46, 157, 149, 136, 179]
++            [46, 157, 149, 136, 179, 154, 81, 162, 132, 175]
+             []
+-            [74, 19, 177, 33, 49, 134, 109, 72, 58, 42]
+-            [74, 19, 177]
+-            [74, 19, 177, 54, 151, 72, 109, 134, 160, 37]
+-            [74, 19, 177, 54, 151]
+-            [74, 19, 177, 54, 151, 182, 109, 134, 160, 147]
+-            [74]
+-            [74, 129, 177, 164, 151, 72, 109, 134, 160, 37]
+-            [74, 129, 177, 164, 151]
+-            [74, 129, 177, 164, 151, 182, 109, 134, 160, 147]
++            [82, 119, 40, 97, 20, 87, 8, 45, 30, 107]
++            [82, 119, 40, 97, 20]
++            [82, 119, 40, 97, 20, 161, 8, 45, 140, 107]
++            [82, 119]
++            [82, 119, 150, 136, 180, 45, 8, 161, 131, 175]
++            [82, 119, 150]
++            [82, 119, 150, 171, 20, 87, 8, 45, 30, 107]
++            [82, 119, 150, 171, 20]
++            [82, 119, 150, 171, 20, 161, 8, 45, 140, 107]
+         """
+         it = self.dlx_solutions()
+         B = it.next()
+@@ -1426,16 +1426,16 @@
+             sage: y = Polyomino([(0,0),(1,0),(2,0),(3,0),(2,1)], color='yellow')
+             sage: T = TilingSolver([y], box=(5,10), reusable=True, reflection=True)
+             sage: for a in T.dlx_solutions(): a
+-            [18, 119, 68, 33, 48, 23, 8, 73, 58, 43]
+-            [18, 119, 68, 33, 48, 133, 8, 73, 168, 43]
+-            [18, 119, 178, 143, 48, 23, 8, 73, 58, 43]
+-            [18, 119, 178, 143, 48, 133, 8, 73, 168, 43]
+-            [18, 119, 178, 164, 152, 73, 8, 133, 159, 147]
+-            [74, 19, 177, 33, 49, 134, 109, 72, 58, 42]
+-            [74, 19, 177, 54, 151, 72, 109, 134, 160, 37]
+-            [74, 19, 177, 54, 151, 182, 109, 134, 160, 147]
+-            [74, 129, 177, 164, 151, 72, 109, 134, 160, 37]
+-            [74, 129, 177, 164, 151, 182, 109, 134, 160, 147]
++            [46, 83, 149, 26, 179, 44, 81, 162, 132, 101]
++            [46, 83, 149, 26, 179, 154, 81, 162, 132, 175]
++            [46, 83, 149, 97, 21, 162, 81, 44, 30, 106]
++            [46, 157, 149, 136, 179, 44, 81, 162, 132, 101]
++            [46, 157, 149, 136, 179, 154, 81, 162, 132, 175]
++            [82, 119, 40, 97, 20, 87, 8, 45, 30, 107]
++            [82, 119, 40, 97, 20, 161, 8, 45, 140, 107]
++            [82, 119, 150, 136, 180, 45, 8, 161, 131, 175]
++            [82, 119, 150, 171, 20, 87, 8, 45, 30, 107]
++            [82, 119, 150, 171, 20, 161, 8, 45, 140, 107]
+             sage: len(list(T.dlx_incremental_solutions()))
+             123
+         """
+diff --git a/sage/combinat/tutorial.py b/sage/combinat/tutorial.py
+--- a/sage/combinat/tutorial.py
++++ b/sage/combinat/tutorial.py
+@@ -1194,9 +1194,6 @@
+         [0 1]
+         [1 1]
+         <BLANKLINE>
+-        [1 1]
+-        [0 1]
+-        <BLANKLINE>
+         [1 0]
+         [0 1]
+         <BLANKLINE>
+@@ -1204,7 +1201,11 @@
+         [1 1]
+         <BLANKLINE>
+         [1 1]
++        [0 1]
++        <BLANKLINE>
++        [1 1]
+         [1 0]
++        <BLANKLINE>
+
+     ::
+
+diff --git a/sage/groups/libgap_mixin.py b/sage/groups/libgap_mixin.py
+--- a/sage/groups/libgap_mixin.py
++++ b/sage/groups/libgap_mixin.py
+@@ -443,6 +443,27 @@
+         """
+         return self(self.gap().Random())
+
++    def __iter__(self):
++        """
++        Iterate over the elements of the group.
++
++        EXAMPLES::
++
++            sage: F = GF(3)
++            sage: gens = [matrix(F,2, [1,0, -1,1]), matrix(F, 2, [1,1,0,1])]
++            sage: G = MatrixGroup(gens)
++            sage: iter(G).next()
++            [0 1]
++            [2 0]
++        """
++        if hasattr(self.list, 'get_cache') and self.list.get_cache() is not None:
++            for g in self.list():
++                yield g
++            return
++        iterator = self.gap().Iterator()
++        while not iterator.IsDoneIterator().sage():
++            yield self(iterator.NextIterator(), check=False)
++
+     @cached_method
+     def list(self):
+         """
+@@ -510,10 +531,10 @@
+             sage: GL(2,ZZ).list()
+             Traceback (most recent call last):
+             ...
+-            ValueError: group must be finite
++            NotImplementedError: group must be finite
+         """
+         if not self.is_finite():
+-            raise ValueError('group must be finite')
++            raise NotImplementedError('group must be finite')
+         elements = self.gap().Elements()
+         return tuple(self(x, check=False) for x in elements)
+
+diff --git a/sage/groups/matrix_gps/matrix_group.py b/sage/groups/matrix_gps/matrix_group.py
+--- a/sage/groups/matrix_gps/matrix_group.py
++++ b/sage/groups/matrix_gps/matrix_group.py
+@@ -598,5 +598,133 @@
+         return FinitelyGeneratedMatrixGroup_gap(self.degree(), self.base_ring(),
+                                                 libgap_subgroup, ambient=self)
+
++    def __iter__(self):
++        """
++        Iterate over the elements of the group.
+
++        This method overrides the matrix group enumerator in GAP which
++        is very slow, see http://tracker.gap-system.org/issues/369.
+
++        EXAMPLES::
++
++            sage: i = iter(GL(6,5))
++            sage: [ i.next() for j in range(8) ]
++            [
++            [1 0 0 0 0 0]  [4 0 0 0 0 1]  [0 4 0 0 0 0]  [0 4 0 0 0 0]
++            [0 1 0 0 0 0]  [4 0 0 0 0 0]  [0 0 4 0 0 0]  [0 0 4 0 0 0]
++            [0 0 1 0 0 0]  [0 4 0 0 0 0]  [0 0 0 4 0 0]  [0 0 0 4 0 0]
++            [0 0 0 1 0 0]  [0 0 4 0 0 0]  [0 0 0 0 4 0]  [0 0 0 0 4 0]
++            [0 0 0 0 1 0]  [0 0 0 4 0 0]  [0 0 0 0 0 4]  [0 0 0 0 0 4]
++            [0 0 0 0 0 1], [0 0 0 0 4 0], [1 4 0 0 0 0], [2 4 0 0 0 0],
++            <BLANKLINE>
++            [3 0 0 0 0 1]  [4 0 0 1 3 3]  [0 0 0 2 0 0]  [1 0 0 0 4 4]
++            [3 0 0 0 0 0]  [4 0 0 0 3 3]  [0 0 0 0 4 0]  [1 0 0 0 0 4]
++            [0 4 0 0 0 0]  [3 0 0 0 0 1]  [2 2 0 0 0 2]  [1 0 0 0 0 0]
++            [0 0 4 0 0 0]  [3 0 0 0 0 0]  [1 4 0 0 0 0]  [0 1 0 0 0 0]
++            [0 0 0 4 0 0]  [0 4 0 0 0 0]  [0 2 4 0 0 0]  [0 0 1 0 0 0]
++            [4 0 0 0 2 3], [2 0 3 4 4 4], [0 0 1 4 0 0], [0 0 0 1 0 0]
++            ]
++
++        This is the direct computation in GAP, which will just run
++        (almost) forever. If you find that this works then the
++        MatrixGroup_gap.__iter__ and MatrixGroup_gap.list
++        methods can be removed::
++
++            sage: G = GL(6,5).gap()
++            sage: G.Enumerator()   # not tested
++            sage: G.Iterator()     # not tested
++        """
++        if not self.is_finite():
++            # use implementation from category framework
++            for g in super(Group, self).__iter__():
++                yield g
++            return
++        # Use the standard GAP iterator for small groups
++        if self.cardinality() < 1000:
++            for g in super(MatrixGroup_gap, self).__iter__():
++                yield g
++            return
++        # Override for large but finite groups
++        iso = self.gap().IsomorphismPermGroup()
++        P = iso.Image()
++        iterator = P.Iterator()
++        while not iterator.IsDoneIterator().sage():
++            p = iterator.NextIterator()
++            g = iso.PreImageElm(p)
++            yield self(g, check=False)
++
++    @cached_method
++    def list(self):
++        """
++        List all elements of this group.
++
++        This method overrides the matrix group enumerator in GAP which
++        is very slow, see http://tracker.gap-system.org/issues/369.
++
++        OUTPUT:
++
++        A tuple containing all group elements in a random but fixed
++        order.
++
++        EXAMPLES::
++
++            sage: F = GF(3)
++            sage: gens = [matrix(F,2, [1,0, -1,1]), matrix(F, 2, [1,1,0,1])]
++            sage: G = MatrixGroup(gens)
++            sage: G.cardinality()
++            24
++            sage: v = G.list()
++            sage: len(v)
++            24
++            sage: v[:5]
++            (
++            [0 1]  [0 1]  [0 1]  [0 2]  [0 2]
++            [2 0], [2 1], [2 2], [1 0], [1 1]
++            )
++            sage: all(g in G for g in G.list())
++            True
++
++        An example over a ring (see trac 5241)::
++
++            sage: M1 = matrix(ZZ,2,[[-1,0],[0,1]])
++            sage: M2 = matrix(ZZ,2,[[1,0],[0,-1]])
++            sage: M3 = matrix(ZZ,2,[[-1,0],[0,-1]])
++            sage: MG = MatrixGroup([M1, M2, M3])
++            sage: MG.list()
++            (
++            [-1  0]  [-1  0]  [ 1  0]  [1 0]
++            [ 0 -1], [ 0  1], [ 0 -1], [0 1]
++            )
++            sage: MG.list()[1]
++            [-1  0]
++            [ 0  1]
++            sage: MG.list()[1].parent()
++            Matrix group over Integer Ring with 3 generators (
++            [-1  0]  [ 1  0]  [-1  0]
++            [ 0  1], [ 0 -1], [ 0 -1]
++            )
++
++        An example over a field (see trac 10515)::
++
++            sage: gens = [matrix(QQ,2,[1,0,0,1])]
++            sage: MatrixGroup(gens).list()
++            (
++            [1 0]
++            [0 1]
++            )
++
++        Another example over a ring (see trac 9437)::
++
++            sage: len(SL(2, Zmod(4)).list())
++            48
++
++        An error is raised if the group is not finite::
++
++            sage: GL(2,ZZ).list()
++            Traceback (most recent call last):
++            ...
++            NotImplementedError: group must be finite
++        """
++        if not self.is_finite():
++            raise NotImplementedError('group must be finite')
++        return tuple(iter(self))

# File trac_14359_doctest_unicode_warning.patch

-# HG changeset patch
-# User Volker Braun <vbraun@stp.dias.ie>
-# Date 1364315051 -3600
-# Node ID a3bfa50af009bf1a32d0341a58ab3c63bfb6312b
-# Parent a7443d728d6909f70ff856d3780a44e6283f9958
-Fix spurious unicode warning during doctests
-
-diff --git a/doc/en/developer/conventions.rst b/doc/en/developer/conventions.rst
---- a/doc/en/developer/conventions.rst
-+++ b/doc/en/developer/conventions.rst
-@@ -420,7 +420,7 @@
-           Improve further function have_fresh_beers using algorithm
-           buy_a_better_fridge::
-
--              sage: have_fresh_beers('Bière de l'Yvette') # todo: not implemented
-+              sage: have_fresh_beers('Bière de l\'Yvette') # todo: not implemented
-               Enjoy !
-
- - A REFERENCES block to list books or papers (optional). This block serves
-diff --git a/sage/doctest/parsing.py b/sage/doctest/parsing.py
---- a/sage/doctest/parsing.py
-+++ b/sage/doctest/parsing.py
-@@ -1,3 +1,4 @@
-+## -*- encoding: utf-8 -*-
- """
- This module contains functions and classes that parse docstrings.
-
-@@ -21,8 +22,7 @@
- import re, sys
- import doctest
- import collections
--from sage.misc.preparser import preparse
--from Cython.Build.Dependencies import strip_string_literals
-+from sage.misc.preparser import preparse, strip_string_literals
-
- float_regex = re.compile('([+-]?((\d*\.?\d+)|(\d+\.?))([eE][+-]?\d+)?)')
- optional_regex = re.compile(r'(long time|not implemented|not tested|known bug)|([^ a-z]\s*optional\s*[:-]*((\s|\w)*))')
-@@ -71,12 +71,18 @@
-         set([])
-         sage: parse_optional_tags("    sage: print '  # long time'  # not tested")
-         set(['not tested'])
-+
-+    UTF-8 works::
-+
-+         sage: parse_optional_tags("'ěščřžýáíéďĎ'")
-+         set([])
-     """
--    safe, literals = strip_string_literals(string)
-+    safe, literals, state = strip_string_literals(string)
-     first_line = safe.split('\n', 1)[0]
-     if '#' not in first_line:
-         return set()
-     comment = first_line[first_line.find('#')+1:]
-+    comment = comment[comment.index('(')+1 : comment.rindex(')')]
-     # strip_string_literals replaces comments
-     comment = "#" + (literals[comment]).lower()
-
-@@ -120,11 +126,12 @@
-         sage: marked.abs_tol
-         0.01
-     """
--    safe, literals = strip_string_literals(source)
-+    safe, literals, state = strip_string_literals(source)
-     first_line = safe.split('\n', 1)[0]
-     if '#' not in first_line:
-         return want
-     comment = first_line[first_line.find('#')+1:]
-+    comment = comment[comment.index('(')+1 : comment.rindex(')')]
-     # strip_string_literals replaces comments
-     comment = literals[comment]
-     if random_marker.search(comment):
-diff --git a/sage/doctest/sources.py b/sage/doctest/sources.py
---- a/sage/doctest/sources.py
-+++ b/sage/doctest/sources.py
-@@ -677,7 +677,6 @@
-             There are 1 tests in sage/ext/c_lib.pyx that are not being run
-             There are 9 tests in sage/graphs/graph_plot.py that are not being run
-             There are 2 tests in sage/server/notebook/worksheet.py that are not being run
--            doctest:229: UnicodeWarning: Unicode equal comparison failed to convert both arguments to Unicode - interpreting them as being unequal
-             sage: os.chdir(cwd)
-         """
-         expected = []
-diff --git a/sage/misc/messaging.py b/sage/misc/messaging.py
---- a/sage/misc/messaging.py
-+++ b/sage/misc/messaging.py
-@@ -62,7 +62,7 @@
-     To set default values populate pushover_defaults::
-
-         sage: sage.misc.messaging.pushover_defaults["user"] = "USER_TOKEN"
--        sage: sage.misc.messaging.pushover("Hi, how are you?"") # not tested
-+        sage: sage.misc.messaging.pushover("Hi, how are you?") # not tested
-
-     .. note::
-

# File trac_14375_ansi_escapes_indication.patch

+# HG changeset patch
+# User Volker Braun <vbraun@stp.dias.ie>
+# Date 1364338386 -3600
+# Node ID 408b9532187cb64af222f3be6299bed2d28b4687
+# Parent 809286ab516ede21c45f34f3696da756329a2c77
+Mention in got<->want diff that there are ansi escape sequences
+
+diff --git a/sage/doctest/parsing.py b/sage/doctest/parsing.py
+--- a/sage/doctest/parsing.py
++++ b/sage/doctest/parsing.py
+@@ -32,6 +32,7 @@
+ tolerance_pattern = re.compile(r'\b((?:abs(?:olute)?)|(?:rel(?:ative)?))? *?tol(?:erance)?\b( +[0-9.e+-]+)?')
+ backslash_replacer = re.compile(r"""(\s*)sage:(.*)\\\ *
+ \ *(((\.){4}:)|((\.){3}))?\ *""")
++ansi_escape_sequence = re.compile(r'(\x1b[@-Z\\-~]|\x1b\[.*?[@-~]|\x9b.*?[@-~])')
+
+ def parse_optional_tags(string):
+     """
+@@ -572,6 +573,36 @@
+         sage: OC.check_output(ex.want, 'x + 0.8935153492877', optflag)
+         False
+     """
++    def human_readable_escape_sequences(self, string):
++        """
++        Make ANSI escape sequences human readable.
++
++        EXAMPLES::
++
++            sage: print 'This ist \x1b[1mbold\x1b[0m text'
++            This ist <CSI-1m>bold<CSI-0m> text
++
++        TESTS::
++
++            sage: from sage.doctest.parsing import SageOutputChecker
++            sage: OC = SageOutputChecker()
++            sage: teststr = '-'.join([
++            ...       'bold\x1b[1m',
++            ...       'newlinemode\x9b20h',
++            ...       'red\x1b[31m',
++            ...       'oscmd\x1ba'])
++            sage: OC.human_readable_escape_sequences(teststr)
++            'bold<CSI-1m>-newlinemode<CSI-20h>-red<CSI-31m>-oscmd<ESC-a>'
++        """
++        def human_readable(match):
++            ansi_escape = match.group(1)
++            assert len(ansi_escape) >= 2
++            if len(ansi_escape) == 2:
++                return '<ESC-'+ansi_escape[1]+'>'
++            else:
++                return '<CSI-'+ansi_escape.lstrip('\x1b[\x9b')+'>'
++        return ansi_escape_sequence.subn(human_readable, string)[0]
++
+     def check_output(self, want, got, optionflags):
+         """
+         Checks to see if the output matches the desired output.
+@@ -667,6 +698,7 @@
+             sage: print "1.000009"   # abs tol 1e-5
+             1.0
+         """
++        got = self.human_readable_escape_sequences(got)
+         if isinstance(want, MarkedOutput):
+             if want.random:
+                 return True
+@@ -810,6 +842,7 @@
+             Tolerance exceeded: infinity > 1e-01
+
+         """
++        got = self.human_readable_escape_sequences(got)
+         want = example.want
+         diff = doctest.OutputChecker.output_difference(self, example, got, optionflags)
+         if isinstance(want, MarkedOutput) and (want.tol or want.abs_tol or want.rel_tol):

+# HG changeset patch
+# User Andrey Novoseltsev <novoselt@gmail.com>
+# Date 1274173825 21600
+# Node ID 3bc5e812f2d41ac2a1282e42721c8e7b23439532
+# Parent  2bccc589431942796d82cbd410692f8db3d47370
+Trac 8986: Add support for convex rational polyhedral cones.
+
+diff -r 2bccc5894319 -r 3bc5e812f2d4 doc/en/reference/geometry.rst
+--- a/doc/en/reference/geometry.rst	Thu May 27 17:23:03 2010 -0600
++++ b/doc/en/reference/geometry.rst	Tue May 18 03:10:25 2010 -0600
+@@ -1,14 +1,15 @@
+ Combinatorial Geometry
+ ======================
+
+-Sage includes support for computing with lattice and reflexive
+-polytopes and Groebner fans.  Polytopes with rational or numerical
+-coordinates are supported by the Polyhedron class.
++Sage includes classes for convex rational polyhedral cones, Groebner fans,
++lattice and reflexive polytopes (with integral coordinates), and generic
++polytopes and polyhedra (with rational or numerical coordinates).
+
+ .. toctree::
+    :maxdepth: 2
+
++   sage/geometry/cone
++   sage/rings/polynomial/groebner_fan
+    sage/geometry/lattice_polytope
+-   sage/rings/polynomial/groebner_fan
+    sage/geometry/polyhedra
+    sage/geometry/toric_lattice
+diff -r 2bccc5894319 -r 3bc5e812f2d4 sage/geometry/all.py
+--- a/sage/geometry/all.py	Thu May 27 17:23:03 2010 -0600
++++ b/sage/geometry/all.py	Tue May 18 03:10:25 2010 -0600
+@@ -1,3 +1,5 @@
++from cone import Cone
++
+ from polytope import polymake
+
+ from polyhedra import Polyhedron, polytopes
+diff -r 2bccc5894319 -r 3bc5e812f2d4 sage/geometry/cone.py
+--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
++++ b/sage/geometry/cone.py	Tue May 18 03:10:25 2010 -0600
+@@ -0,0 +1,1922 @@
++r"""
++Convex rational polyhedral cones
++
++This module was designed as a part of framework for toric varieties
++(:mod:~sage.schemes.generic.toric_variety,
++:mod:~sage.schemes.generic.fano_toric_variety). While the emphasis is on
++strictly convex cones, non-strictly convex cones are supported as well. Work
++with distinct lattices (in the sense of discrete subgroups spanning vector
++spaces) is supported. The default lattice is :class:ToricLattice
++<sage.geometry.toric_lattice.ToricLatticeFactory> N of the appropriate
++dimension. The only case when you must specify lattice explicitly is creation
++of a 0-dimensional cone, where dimension of the ambient space cannot be
++guessed.
++
++In addition to cones (:class:ConvexRationalPolyhedralCone), this module
++provides the base class for cones and fans (:class:IntegralRayCollection)
++and the function for computing Hasse diagrams of finite atomic and coatomic
++lattices (in the sense of partially ordered sets where any two elements have
++meet and joint) (:func:hasse_diagram_from_incidences).
++
++AUTHORS:
++
++- Andrey Novoseltsev (2010-05-13): initial version.
++
++EXAMPLES:
++
++Use :func:Cone to construct cones::
++
++    sage: octant = Cone([(1,0,0), (0,1,0), (0,0,1)])
++    sage: halfspace = Cone([(1,0,0), (0,1,0), (-1,-1,0), (0,0,1)])
++    sage: positive_xy = Cone([(1,0,0), (0,1,0)])
++    sage: four_rays = Cone([(1,1,1), (1,-1,1), (-1,-1,1), (-1,1,1)])
++
++For all of the cones above we have provided primitive generating rays, but in
++fact this is not necessary - a cone can be constructed from any collection of
++rays (from the same space, of course). If there are non-primitive (or even
++non-integral) rays, they will be replaced with primitive ones. If there are
++extra rays, they will be discarded. Of course, this means that :func:Cone
++has to do some work before actually constructing the cone and sometimes it is
++not desirable, if you know for sure that your input is already "good". In this
++case you can use options check=False to force :func:Cone to use
++exactly the directions that you have specified and normalize=False to
++force it to use exactly the rays that you have specified. However, it is
++better not to use these possibilities without necessity, since cones are
++assumed to be represented by a minimal set of primitive generating rays.
++See :func:Cone for further documentation on construction.
++
++Once you have a cone, you can perfrom numerous operations on it. The most
++important ones are, probably, ray accessing methods::
++
++    sage: halfspace.rays()
++    (N(0, 0, 1), N(1, 0, 0), N(-1, 0, 0), N(0, 1, 0), N(0, -1, 0))
++    sage: halfspace.ray(2)
++    N(-1, 0, 0)
++    sage: halfspace.ray_matrix()
++    [ 0  1 -1  0  0]
++    [ 0  0  0  1 -1]
++    [ 1  0  0  0  0]
++    sage: halfspace.ray_set()
++    frozenset([N(1, 0, 0), N(-1, 0, 0), N(0, 1, 0), N(0, 0, 1), N(0, -1, 0)])
++
++If you want to do something with each ray of a cone, you can write ::
++
++    sage: for ray in positive_xy: print ray
++    N(1, 0, 0)
++    N(0, 1, 0)
++
++You can also get an iterator over only some selected rays::
++
++    sage: for ray in halfspace.ray_iterator([1,2,1]): print ray
++    N(1, 0, 0)
++    N(-1, 0, 0)
++    N(1, 0, 0)
++
++There are two dimensions associated to each cone - the dimension of the
++subspace spanned by the cone and the dimension of the ambient space where it
++lives::
++
++    sage: positive_xy.dim()
++    2
++    sage: positive_xy.ambient_dim()
++    3
++
++You also may be interested in this dimension::
++
++    sage: dim(positive_xy.linear_subspace())
++    0
++    sage: dim(halfspace.linear_subspace())
++    2
++
++Or, perhaps, all you care about is whether it is zero or not::
++
++    sage: positive_xy.is_strictly_convex()
++    True
++    sage: halfspace.is_strictly_convex()
++    False
++
++You can also perform these checks::
++
++    sage: positive_xy.is_simplicial()
++    True
++    sage: four_rays.is_simplicial()
++    False
++    sage: positive_xy.is_smooth()
++    True
++
++You can work with subcones that form faces of other cones::
++
++    sage: face = four_rays.faces(dim=2)[0]
++    sage: face
++    2-dimensional face of 3-dimensional cone
++    sage: face.rays()
++    (N(1, 1, 1), N(1, -1, 1))
++    sage: face.cone_rays()
++    (0, 1)
++    sage: four_rays.rays(face.cone_rays())
++    (N(1, 1, 1), N(1, -1, 1))
++
++If you need to know inclusion relations between faces, use ::
++
++    sage: L = four_rays.face_lattice()
++    sage: map(len, L.level_sets())
++    [1, 4, 4, 1]
++    sage: face = L.level_sets()[2][0]
++    sage: face.element.rays()
++    (N(1, 1, 1), N(1, -1, 1))
++    sage: L.hasse_diagram().neighbors_in(face)
++    [1-dimensional face of 3-dimensional cone,
++     1-dimensional face of 3-dimensional cone]
++
++When all the functionality provided by cones is not enough, you may want to
++check if you can do necessary things using lattice polytopes and polyhedra
++corresponding to cones::
++
++    sage: four_rays.lattice_polytope()
++    A lattice polytope: 3-dimensional, 5 vertices.
++    sage: four_rays.polyhedron()
++    A 3-dimensional polyhedron in QQ^3 defined as
++    the convex hull of 1 vertex and 4 rays.
++
++And of course you are always welcome to suggest new features that should be
++added to cones!
++"""
++
++#*****************************************************************************
++#       Copyright (C) 2010 Andrey Novoseltsev <novoselt@gmail.com>
++#       Copyright (C) 2010 William Stein <wstein@gmail.com>
++#
++#  Distributed under the terms of the GNU General Public License (GPL)
++#
++#                  http://www.gnu.org/licenses/
++#*****************************************************************************
++
++
++import collections
++import copy
++import warnings
++
++from sage.combinat.posets.posets import FinitePoset
++from sage.geometry.lattice_polytope import LatticePolytope
++from sage.geometry.polyhedra import Polyhedron
++from sage.geometry.toric_lattice import ToricLattice, is_ToricLattice
++from sage.graphs.all import DiGraph
++from sage.matrix.all import matrix, identity_matrix
++from sage.misc.all import flatten
++from sage.modules.all import span, vector
++from sage.rings.all import QQ, RR, ZZ, gcd
++from sage.structure.all import SageObject
++from sage.structure.coerce import parent
++
++
++def is_Cone(x):
++    r"""
++    Check if x is a cone.
++
++    INPUT:
++
++    - x -- anything.
++
++    OUTPUT:
++
++    - True if x is a cone and False otherwise.
++
++    EXAMPLES::
++
++        sage: from sage.geometry.cone import is_Cone
++        sage: is_Cone(1)
++        False
++        sage: quadrant = Cone([(1,0), (0,1)])
++        sage: quadrant
++        2-dimensional cone
++        sage: is_Cone(quadrant)
++        True
++    """
++    return isinstance(x, ConvexRationalPolyhedralCone)
++
++
++def Cone(data, lattice=None, check=True, normalize=True):
++    r"""
++    Construct a (not necessarily strictly) convex rational polyhedral cone.
++
++    INPUT:
++
++    - data -- one of the following:
++        * :class:~sage.geometry.polyhedra.Polyhedron object representing
++          a valid cone;
++        * list of rays. Each ray should be given as a list or a vector
++          convertible to the rational extension of the given lattice;
++
++    - lattice -- :class:ToricLattice
++      <sage.geometry.toric_lattice.ToricLatticeFactory>, \ZZ^n, or any
++      other object that behaves like these. If not specified, an attempt will
++      be made to determine an appropriate toric lattice automatically;
++
++    - check -- by default the input data will be checked for correctness
++      (e.g. that all rays have the same number of components) and generating
++      rays will be constructed from data. If you know that the input is
++      a minimal set of generators of a valid cone, you may significantly
++      (up to 100 times on simple input) decrease construction time using
++      check=False option;
++
++    - normalize -- you can further speed up construction using
++      normalize=False option. In this case data must be a list of
++      immutable primitive rays in lattice. In general, you should not use
++      this option, it is designed for code optimization and does not give as
++      drastic improvement in speed as the previous one.
++
++    OUTPUT:
++
++    - convex rational polyhedral cone determined by data.
++
++    EXAMPLES:
++
++    Let's define a cone corresponding to the first quadrant of the plane
++    (note, you can even mix objects of different types to represent rays, as
++    long as you let this function to perform all the checks and necessary
++    conversions!)::
++
++        sage: quadrant = Cone([(1,0), [0,1]])
++        sage: quadrant
++        2-dimensional cone
++        sage: quadrant.rays()
++        (N(1, 0), N(0, 1))
++
++    You may prefer to use :meth:~IntegralRayCollection.ray_matrix when you
++    want to take a look at rays, they will be given as columns::
++
++        sage: quadrant.ray_matrix()
++        [1 0]
++        [0 1]
++
++    If you give more rays than necessary, the extra ones will be discarded::
++
++        sage: Cone([(1,0), (0,1), (1,1), (0,1)]).rays()
++        (N(1, 0), N(0, 1))
++
++    However, this work is not done with check=False option, so use it
++    carefully! ::
++
++        sage: Cone([(1,0), (0,1), (1,1), (0,1)], check=False).rays()
++        (N(1, 0), N(0, 1), N(1, 1), N(0, 1))
++
++    Even worse things can happen with normalize=False option::
++
++        sage: Cone([(1,0), (0,1)], check=False, normalize=False)
++        Traceback (most recent call last):
++        ...
++        AttributeError: 'tuple' object has no attribute 'parent'
++
++    You can construct different "not" cones: not full-dimensional, not
++    strictly convex, not containing any rays::
++
++        sage: one_dimensional_cone = Cone([(1,0)])
++        sage: one_dimensional_cone.dim()
++        1
++        sage: half_plane = Cone([(1,0), (0,1), (-1,0)])
++        sage: half_plane.rays()
++        (N(0, 1), N(1, 0), N(-1, 0))
++        sage: half_plane.is_strictly_convex()
++        False
++        sage: origin = Cone([(0,0)])
++        sage: origin.rays()
++        ()
++        sage: origin.dim()
++        0
++        sage: origin.ambient_dim()
++        2
++
++    You may construct the cone above without giving any rays, but in this case
++    you must provide lattice explicitly::
++
++        sage: origin = Cone([])
++        Traceback (most recent call last):
++        ...
++        ValueError: lattice must be given explicitly if there are no rays!
++        sage: origin = Cone([], lattice=ToricLattice(2))
++        sage: origin.dim()
++        0
++        sage: origin.ambient_dim()
++        2
++        sage: origin.lattice()
++        2-dimensional lattice N
++
++    Of course, you can also provide lattice in other cases::
++
++        sage: L = ToricLattice(3, "L")
++        sage: c1 = Cone([(1,0,0),(1,1,1)], lattice=L)
++        sage: c1.rays()
++        (L(1, 0, 0), L(1, 1, 1))
++
++    Or you can construct cones from rays of a particular lattice::
++
++        sage: ray1 = L(1,0,0)
++        sage: ray2 = L(1,1,1)
++        sage: c2 = Cone([ray1, ray2])
++        sage: c2.rays()
++        (L(1, 0, 0), L(1, 1, 1))
++        sage: c1 == c2
++        True
++
++    When the cone in question is not strictly convex, the standard form for
++    the "generating rays" of the linear subspace is "basis vectors and their
++    negatives", as in the following example::
++
++        sage: plane = Cone([(1,0), (0,1), (-1,-1)])
++        sage: plane.ray_matrix()
++        [ 1 -1  0  0]
++        [ 0  0  1 -1]
++    """
++    # Cone from Polyhedron
++    if isinstance(data, Polyhedron):
++        polyhedron = data
++        if lattice is None:
++            lattice = ToricLattice(polyhedron.ambient_dim())
++        if polyhedron.n_vertices() > 1:
++            raise ValueError("%s is not a cone!" % polyhedron)
++        apex = polyhedron.vertices()[0]
++        if apex.count(0) != len(apex):
++            raise ValueError("the apex of %s is not at the origin!"
++                             % polyhedron)
++        rays = normalize_rays(polyhedron.rays(), lattice)
++        strict_rays = tuple(rays)
++        lines = tuple(normalize_rays(polyhedron.lines(), lattice))
++        for line in lines:
++            rays.append(line)
++            rays.append(-line)
++            rays[-1].set_immutable()
++        cone = ConvexRationalPolyhedralCone(rays, lattice)
++        # Save constructed stuff for later use
++        cone._polyhedron = polyhedron
++        cone._strict_rays = strict_rays
++        cone._lines = lines
++        return cone
++    # Cone from rays
++    rays = data
++    if check or normalize:
++        # In principle, if check is True, this normalization is redundant,
++        # since we will need to renormalize the output from Polyhedra, but
++        # doing it now gives more consistent error messages (and it seems to
++        # be fast anyway, compared to Polyhedron creation).
++        rays = normalize_rays(rays, lattice)
++    if lattice is None:
++        if rays:
++            lattice = rays[0].parent()
++        else:
++            raise ValueError(
++                "lattice must be given explicitly if there are no rays!")
++    if check and rays:
++        # Any set of rays forms a cone, but we want to keep only generators
++        return Cone(Polyhedron(rays=rays), lattice)
++    return ConvexRationalPolyhedralCone(rays, lattice)
++
++
++def normalize_rays(rays, lattice):
++    r"""
++    Normalize a list of rational rays, i.e. make them integral.
++
++    INPUT:
++
++    - rays -- list of rays which can be converted to the rational
++      extension of lattice;
++
++    - lattice -- :class:ToricLattice
++      <sage.geometry.toric_lattice.ToricLatticeFactory>, \ZZ^n, or any
++      other object that behaves like these. If None, an attempt will
++      be made to determine an appropriate toric lattice automatically.
++
++    OUTPUT:
++
++    - list of immutable primitive vectors of the lattice in the same
++      directions as original rays.
++
++    EXAMPLES::
++
++        sage: from sage.geometry.cone import normalize_rays
++        sage: normalize_rays([(0, 1), (0, 2), (3, 2), (5/7, 10/3)], None)
++        [N(0, 1), N(0, 1), N(3, 2), N(3, 14)]
++        sage: L = ToricLattice(2, "L")
++        sage: normalize_rays([(0, 1), (0, 2), (3, 2), (5/7, 10/3)], L.dual())
++        [L*(0, 1), L*(0, 1), L*(3, 2), L*(3, 14)]
++        sage: ray_in_L = L(0,1)
++        sage: normalize_rays([ray_in_L, (0, 2), (3, 2), (5/7, 10/3)], None)
++        [L(0, 1), L(0, 1), L(3, 2), L(3, 14)]
++        sage: normalize_rays([(0, 1), (0, 2), (3, 2), (5/7, 10/3)], ZZ^2)
++        [(0, 1), (0, 1), (3, 2), (3, 14)]
++        sage: normalize_rays([(0, 1), (0, 2), (3, 2), (5/7, 10/3)], ZZ^3)
++        Traceback (most recent call last):
++        ...
++        TypeError: cannot convert (0, 1) to
++        Vector space of dimension 3 over Rational Field!
++        sage: normalize_rays([], ZZ^3)
++        []
++    """
++    if rays is None:
++        rays = []
++    try:
++        rays = list(rays)
++    except TypeError:
++        raise TypeError(
++                    "rays must be given as a list or a compatible structure!"
++                    "\nGot: %s" % rays)
++    if rays:
++        if lattice is None:
++            ray_parent = parent(rays[0])
++            lattice = (ray_parent if is_ToricLattice(ray_parent)
++                                  else ToricLattice(len(rays[0])))
++        V = lattice.base_extend(QQ)
++        for n, ray in enumerate(rays):
++            try:
++                ray = V(ray)
++            except TypeError:
++                raise TypeError("cannot convert %s to %s!" % (ray, V))
++            if ray.is_zero():
++                ray = lattice(0)
++            else:
++                ray = ray.denominator() * ray
++                ray = lattice(ray / gcd(lattice(ray)))
++            ray.set_immutable()
++            rays[n] = ray
++    return rays
++
++
++class IntegralRayCollection(SageObject,
++                            collections.Container,
++                            collections.Hashable,
++                            collections.Iterable):
++    r"""
++    Create a collection of integral rays.
++
++    This is a base class for rational polyhedral cones and fans.
++
++    Ray collections are immutable, but they cache most of the returned values.
++
++    INPUT:
++
++    - rays -- list of immutable vectors in lattice;
++
++    - lattice -- :class:ToricLattice
++      <sage.geometry.toric_lattice.ToricLatticeFactory>, \ZZ^n, or any
++      other object that behaves like these. If None, it will be determined
++      as :func:parent of the first ray. Of course, this cannot be done if
++      there are no rays, so in this case you must give an appropriate
++      lattice directly.
++
++    OUTPUT:
++
++    - collection of given integral rays.
++
++    .. WARNING::
++
++        No correctness check or normalization is performed on the input data.
++        This class is designed for internal operations and you probably should
++        not use it directly.
++
++    TESTS::
++
++        sage: v = vector([0,1])
++        sage: v.set_immutable()
++        sage: c = sage.geometry.cone.IntegralRayCollection([v], None)
++        sage: c.rays()
++        ((0, 1),)
++        sage: TestSuite(c).run()
++    """
++
++    def __init__(self, rays, lattice):
++        r"""
++        See :class:IntegralRayCollection for documentation.
++
++        TESTS::
++
++            sage: v = vector([0,1])
++            sage: v.set_immutable()
++            sage: sage.geometry.cone.IntegralRayCollection([v], None).rays()
++            ((0, 1),)
++        """
++        self._rays = tuple(rays)
++        self._lattice = self._rays[0].parent() if lattice is None else lattice
++
++    def __cmp__(self, right):
++        r"""
++        Compare self and right.
++
++        INPUT:
++
++        - right -- anything.
++
++        OUTPUT:
++
++        - 0 if right is of the same type as self and their rays are
++          the same and listed in the same order. 1 or -1 otherwise.
++
++        TESTS::
++
++            sage: c1 = Cone([(1,0), (0,1)])
++            sage: c2 = Cone([(0,1), (1,0)])
++            sage: c3 = Cone([(0,1), (1,0)])
++            sage: cmp(c1, c2)
++            1
++            sage: cmp(c2, c1)
++            -1
++            sage: cmp(c2, c3)
++            0
++            sage: c2 is c3
++            False
++            sage: cmp(c1, 1)
++            -1
++        """
++        c = cmp(type(self), type(right))
++        if c:
++            return c
++        return cmp((self.lattice(), self.rays()),
++                   (right.lattice(), right.rays()))
++
++    def __hash__(self):
++        r"""
++        Return the hash of self computed from rays.
++
++        OUTPUT:
++
++        - integer.
++
++        TESTS::
++
++            sage: c = Cone([(1,0), (0,1)])
++            sage: hash(c)  # 64-bit
++            4372618627376133801
++        """
++        if "_hash" not in self.__dict__:
++            self._hash = hash(self._rays)
++        return self._hash
++
++    def __iter__(self):
++        r"""
++        Return an iterator over rays of self.
++
++        OUTPUT:
++
++        -  iterator.
++
++        TESTS::
++
++            sage: c = Cone([(1,0), (0,1)])
++            sage: for ray in c: print ray
++            N(1, 0)
++            N(0, 1)
++        """
++        return self.ray_iterator()
++
++    def ambient_dim(self):
++        r"""
++        Return the dimension of the ambient lattice of self.
++
++        OUTPUT:
++
++        - integer.
++
++        EXAMPLES::
++
++            sage: c = Cone([(1,0)])
++            sage: c.ambient_dim()
++            2
++            sage: c.dim()
++            1
++        """
++        return self.lattice().dimension()
++
++    def dim(self):
++        r"""
++        Return the dimension of the subspace spanned by rays of self.
++
++        OUTPUT:
++
++        - integer.
++
++        EXAMPLES::
++
++            sage: c = Cone([(1,0)])
++            sage: c.ambient_dim()
++            2
++            sage: c.dim()
++            1
++        """
++        if "_dim" not in self.__dict__:
++            self._dim = self.ray_matrix().rank()
++        return self._dim
++
++    def lattice(self):
++        r"""
++        Return the ambient lattice of self.
++
++        OUTPUT:
++
++        - lattice.
++
++        EXAMPLES::
++
++            sage: c = Cone([(1,0)])
++            sage: c.lattice()
++            2-dimensional lattice N
++            sage: Cone([], ZZ^3).lattice()
++            Ambient free module of rank 3
++            over the principal ideal domain Integer Ring
++        """
++        return self._lattice
++
++    def nrays(self):
++        r"""
++        Return the number of rays of self.
++
++        OUTPUT:
++
++        - integer.
++
++        EXAMPLES::
++
++            sage: c = Cone([(1,0), (0,1)])
++            sage: c.nrays()
++            2
++        """
++        return len(self._rays)
++
++    def ray(self, n):
++        r"""
++        Return the n-th ray of self.
++
++        INPUT:
++
++        - n -- integer, an index of a ray of self. Enumeration of rays
++          starts with zero.
++
++        OUTPUT:
++
++        - ray, an element of the lattice of self.
++
++        EXAMPLES::
++
++            sage: c = Cone([(1,0), (0,1)])
++            sage: c.ray(0)
++            N(1, 0)
++        """
++        return self._rays[n]
++
++    def ray_iterator(self, ray_list=None):
++        r"""
++        Return an iterator over (some of) the rays of self.
++
++        INPUT:
++
++        - ray_list -- list of integers, the indices of the requested rays.
++          If not specified, an iterator over all rays of self will be
++          returned.
++
++        OUTPUT:
++
++        - iterator.
++
++        EXAMPLES::
++
++            sage: c = Cone([(1,0), (0,1), (-1, 0)])
++            sage: for ray in c.ray_iterator(): print ray
++            N(0, 1)
++            N(1, 0)
++            N(-1, 0)
++            sage: for ray in c.ray_iterator([2,1]): print ray
++            N(-1, 0)
++            N(1, 0)
++        """
++        if ray_list is None:
++            for ray in self._rays:
++                yield ray
++        else:
++            rays = self._rays
++            for n in ray_list:
++                yield rays[n]
++
++    def ray_matrix(self):
++        r"""
++        Return a matrix whose columns are rays of self.
++
++        It can be convenient for linear algebra operations on rays, as well as
++        for easy-to-read output.
++
++        OUTPUT:
++
++        - matrix.
++
++        EXAMPLES::
++
++            sage: c = Cone([(1,0), (0,1), (-1, 0)])
++            sage: c.ray_matrix()
++            [ 0  1 -1]
++            [ 1  0  0]
++        """
++        if "_ray_matrix" not in self.__dict__:
++            self._ray_matrix = matrix(self.nrays(), self.ambient_dim(),
++                                      self._rays).transpose()
++            self._ray_matrix.set_immutable()
++        return self._ray_matrix
++
++    def ray_set(self):
++        r"""
++        Return rays of self as a :class:frozenset.
++
++        Use :meth:rays if you want to get rays in the fixed order.
++
++        OUTPUT:
++
++        - :class:frozenset of rays.
++
++        EXAMPLES::
++
++            sage: c = Cone([(1,0), (0,1), (-1, 0)])
++            sage: c.ray_set()
++            frozenset([N(0, 1), N(1, 0), N(-1, 0)])
++        """
++        if "_ray_set" not in self.__dict__:
++            self._ray_set = frozenset(self._rays)
++        return self._ray_set
++
++    def rays(self, ray_list=None):
++        r"""
++        Return rays of self as a :class:tuple.
++
++        INPUT:
++
++        - ray_list -- list of integers, the indices of the requested rays.
++          If not specified, all rays of self will be returned. You may
++          want to use :meth:ray_set if you do not care about the order of
++          rays. See also :meth:ray_iterator.
++
++        OUTPUT:
++
++        - :class:tuple of rays.
++
++        EXAMPLES::
++
++            sage: c = Cone([(1,0), (0,1), (-1, 0)])
++            sage: c.rays()
++            (N(0, 1), N(1, 0), N(-1, 0))
++            sage: c.rays([0, 2])
++            (N(0, 1), N(-1, 0))
++        """
++        if ray_list is None:
++            return self._rays
++        else:
++            return tuple(self.ray_iterator(ray_list))
++
++
++class ConvexRationalPolyhedralCone(IntegralRayCollection):
++    r"""
++    Create a convex rational polyhedral cone.
++
++    .. WARNING::
++
++        This class does not perform any checks of correctness of input nor
++        does it convert input into the standard representation. Use
++        :func:Cone to construct cones.
++
++    Cones are immutable, but they cache most of the returned values.
++
++    INPUT:
++
++    - same as for :class:IntegralRayCollection.
++
++    OUTPUT:
++
++    - convex rational polyhedral cone.
++
++    TESTS::
++
++        sage: v = vector([0,1])
++        sage: v.set_immutable()
++        sage: c = sage.geometry.cone.ConvexRationalPolyhedralCone([v], None)
++        sage: c.rays()
++        ((0, 1),)
++        sage: TestSuite(c).run()
++
++        sage: c = Cone([(0,1)])
++        sage: TestSuite(c).run()
++    """
++
++    # No __init__ method, just use the base class.
++
++    def __contains__(self, point):
++        r"""
++        Check if point is contained in self.
++
++        See :meth:_contains (which is called by this function) for
++        documentation.
++
++        TESTS::
++
++            sage: c = Cone([(1,0), (0,1)])
++            sage: (1,1) in c
++            True
++            sage: [1,1] in c
++            True
++            sage: (-1,0) in c
++            False
++        """
++        return self._contains(point)
++
++    def __getstate__(self):
++        r"""
++        Return the dictionary that should be pickled.
++
++        OUTPUT:
++
++        - :class:dict.
++
++        TESTS::
++
++            sage: loads(dumps(Cone([(1,0)])))
++            1-dimensional cone
++        """
++        state = copy.copy(self.__dict__)
++        state.pop("_polyhedron", None) # Polyhedron is not picklable.
++        state.pop("_lattice_polytope", None) # Just to save time and space.
++        return state
++
++    def _contains(self, point):
++        r"""
++        Check if point is contained in self.
++
++        This function is called by :meth:__contains__ and :meth:contains
++        to ensure the same call depth for warning messages.
++
++        INPUT:
++
++        - point -- anything. An attempt will be made to convert it into a
++          single element of the ambient space of self. If it fails,
++          False will be returned.
++
++        OUTPUT:
++
++        - True if point is contained in self, False otherwise.
++
++        TESTS::
++
++            sage: c = Cone([(1,0), (0,1)])
++            sage: c._contains((1,1))
++            True
++        """
++        if is_ToricLattice(parent(point)):
++            # Special treatment for elements of OTHER toric lattices
++            if point not in self.lattice():
++                # This is due to the discussion in Trac #8986
++                warnings.warn("you have checked if a cone contains a point "
++                              "from another lattice, this is always False!",
++                              stacklevel=3)
++                return False
++        else:
++            try: # to cook up a point being exact ...
++                point = self.lattice().base_extend(QQ)(point)
++            except TypeError:
++                try: # ... or at least numeric
++                    point = self.lattice().base_extend(RR)(point)
++                except TypeError:
++                    # Give up, input is really strange
++                    return False
++        return all(n * point >= 0 for n in self.facet_normals())
++
++    def _latex_(self):
++        r"""
++        Return a LaTeX representation of self.
++
++        OUTPUT:
++
++        - string.
++
++        TESTS::
++
++            sage: quadrant = Cone([(1,0), (0,1)])
++            sage: quadrant._latex_()
++            '\\sigma^{2}'
++        """
++        return r"\sigma^{%d}" % self.dim()
++
++    def _repr_(self):
++        r"""
++        Return a string representation of self.
++
++        OUTPUT:
++
++        - string.
++
++        TESTS::
++
++            sage: quadrant = Cone([(1,0), (0,1)])
++            sage: quadrant._repr_()
++            '2-dimensional cone'
++            sage: quadrant
++            2-dimensional cone
++        """
++        return "%d-dimensional cone" % self.dim()
++
++    def contains(self, *args):
++        r"""
++        Check if a given point is contained in self.
++
++        INPUT:
++
++        - anything. An attempt will be made to convert all arguments into a
++          single element of the ambient space of self. If it fails,
++          False will be returned.
++
++        OUTPUT:
++
++        - True if the given point is contained in self, False
++          otherwise.
++
++        EXAMPLES::
++
++            sage: c = Cone([(1,0), (0,1)])
++            sage: c.contains(c.lattice()(1,0))
++            True
++            sage: c.contains((1,0))
++            True
++            sage: c.contains((1,1))
++            True
++            sage: c.contains(1,1)
++            True
++            sage: c.contains((-1,0))
++            False
++            sage: c.contains(c.lattice().dual()(1,0)) #random output (warning)
++            False
++            sage: c.contains(c.lattice().dual()(1,0))
++            False
++            sage: c.contains(1)
++            False
++            sage: c.contains(1/2, sqrt(3))
++            True
++            sage: c.contains(-1/2, sqrt(3))
++            False