Commits

Volker Braun committed d1d9469

working on piecewise functions

Comments (0)

Files changed (11)

+trac_14523_improve_attach.patch
+trac_14523_readline.patch
+trac_13125_real_set.patch
+trac_13125_misc.patch
+trac_9556-dynamic_class_everywhere.patch
+trac_14780-embed_tuples_in_SR.patch
+trac_9556-dynamic_class_everywhere.part2.patch
+trac_14800_subs.patch
+trac_14801_piecewiese.patch
+trac_14353_fan_morphism_factoring.patch
+trac_14353_auxiliary_methods.patch
+trac_14353_toric_morphism_factoring.patch
+trac_14353_toric_morphism_composition.patch
+trac_14537_identity_morphism.patch
 trac_14469_repr_graphics.patch
 trac_13084_ppl_lattice_polygon.patch
 trac_13084_toric_weierstrass.patch
 trac_13084_weierstrass_cleanup-fc.patch
 trac_13084_misc.patch
 trac_13458_toric_Weierstrass_covering.patch
-trac_14523_improve_attach.patch
-trac_14523_readline.patch
 trac_14682_doctest_fixes.patch
 trac_12559_tour_chinese.patch
 trac_14703_infinite_fp_group_check.patch
 trac_12892_orbit_closure_morphism.patch
 trac_12892_toric_morphism_fibers.patch
 trac_12892_toric_morphism_divisors.patch
-trac_14353_fan_morphism_factoring.patch   
-trac_14353_auxiliary_methods.patch        
-trac_14353_toric_morphism_factoring.patch 
 trac_12900_Demazure_roots.patch
 trac_xxxx_fiber_divisor_graph.patch
 trac_14357_lazy_everywhere.patch

trac_13125_misc.patch

+# HG changeset patch
+# Parent 5ff9faece6300cb5e5080570e869e623fed21b6f
+
+Further improvements to RealSet
+
+diff --git a/sage/sets/real_set.py b/sage/sets/real_set.py
+--- a/sage/sets/real_set.py
++++ b/sage/sets/real_set.py
+@@ -51,6 +51,7 @@
+ 
+ from sage.structure.parent import Parent
+ from sage.structure.unique_representation import UniqueRepresentation
++from sage.rings.all import ZZ
+ from sage.rings.real_lazy import LazyFieldElement, RLF
+ from sage.rings.infinity import infinity, minus_infinity
+ 
+@@ -110,7 +111,7 @@
+             sage: I.is_empty()
+             False
+         """
+-        return (self._lower == self._upper) and not (self._lower_closed or self._upper_closed)
++        return (self._lower == self._upper) and not (self._lower_closed and self._upper_closed)
+ 
+     def is_point(self):
+         """
+@@ -512,7 +513,39 @@
+             lower = upper = RLF(0)
+             lower_closed = upper_closed = False
+         return RealInterval(lower, lower_closed, upper, upper_closed)
++
++    def contains(self, x):
++        """
++        Return whether `x` is contained in the interval
++
++        INPUT:
++
++        - ``x`` -- a real number.
++
++        OUTPUT:
++
++        Boolean.
++
++        EXAMPLES::
+         
++            sage: i = RealSet.open_closed(0,2)[0]; i
++            (0, 2]
++            sage: i.contains(0)
++            False
++            sage: i.contains(1)
++            True
++            sage: i.contains(2)
++            True
++        """
++        cmp_lower = cmp(self._lower, x)
++        cmp_upper = cmp(x, self._upper)
++        if cmp_lower == cmp_upper == -1:
++            return True
++        if cmp_lower == 0:
++            return self._lower_closed
++        if cmp_upper == 0:
++            return self._upper_closed
++        return False
+ 
+ 
+ class RealSet(UniqueRepresentation, Parent):
+@@ -588,6 +621,31 @@
+         """
+         self._intervals = intervals
+     
++    def __cmp__(self, other):
++        """
++        Intervals are sorted by lower bound, then upper bound
++
++        OUTPUT:
++
++        `-1`, `0`, or `+1` depending on how the intervals compare.
++        
++        EXAMPLES::
++
++             sage: I1 = RealSet.open_closed(1, 3);  I1
++             (1, 3]
++             sage: I2 = RealSet.open_closed(0, 5);  I2
++             (0, 5]
++             sage: cmp(I1, I2)
++             1
++             sage: sorted([I1, I2])
++             [(0, 5], (1, 3]]
++             sage: I1 == I1
++             True
++        """
++        # note that the interval representation is normalized into a
++        # unique form
++        return cmp(self._intervals, other._intervals)
++
+     def __iter__(self):
+         """
+         Iterate over the component intervals is ascending order
+@@ -625,6 +683,19 @@
+ 
+     __len__ = n_components
+ 
++    def is_empty(self):
++        """
++        Return whether the set is empty
++        
++        EXAMPLES::
++
++            sage: RealSet(0, 1).is_empty()
++            False
++            sage: RealSet(0, 0).is_empty()
++            True
++        """
++        return len(self._intervals) == 0
++
+     def get_interval(self, i):
+         """
+         Return the ``i``-th connected component.
+@@ -994,6 +1065,19 @@
+             (1, 2)
+             sage: s1 & s2    # syntactic sugar
+             (1, 2)
++
++            sage: s1 = RealSet((0, 1), (2, 3));  s1
++            (0, 1) + (2, 3)
++            sage: s2 = RealSet([0, 1], [2, 3]);  s2
++            [0, 1] + [2, 3]
++            sage: s3 = RealSet([1, 2]);  s3
++            [1, 2]
++            sage: s1.intersection(s2)
++            (0, 1) + (2, 3)
++            sage: s1.intersection(s3)
++            {}
++            sage: s2.intersection(s3)
++            {1} + {2}
+         """
+         # TODO: this can be done in linear time since the intervals are already sorted
+         intervals = []
+@@ -1128,3 +1212,114 @@
+         return self.intersection(other.complement())
+ 
+     __sub__ = difference
++
++    def contains(self, x):
++        """
++        Return whether `x` is contained in the set
++
++        INPUT:
++
++        - ``x`` -- a real number.
++
++        OUTPUT:
++
++        Boolean.
++
++        EXAMPLES::
++        
++            sage: s = RealSet(0,2) + RealSet.unbounded_above_closed(10);  s
++            (0, 2) + [10, +Infinity)
++            sage: s.contains(1)
++            True
++            sage: s.contains(0)
++            False
++            sage: 10 in s    # syntactic sugar
++            True
++        """
++        x = RLF(x)
++        for interval in self._intervals:
++            if interval.contains(x):
++                return True
++        return False
++    
++    __contains__ = contains
++    
++    def an_element(self):
++        """
++        Return a point of the set
++
++        OUTPUT:
++
++        A real number. ``ValueError` if the set is empty.
++
++        EXAMPLES:
++
++            sage: RealSet.open_closed(0, 1).an_element()
++            1
++            sage: RealSet(0, 1).an_element()
++            1/2
++        """
++        if len(self._intervals) == 0:
++            raise ValueError('set is empty')
++        i = self._intervals[0]
++        if i.lower_closed():
++            return i.lower()
++        if i.upper_closed():
++            return i.upper()
++        return (i.lower() + i.upper())/ZZ(2)
++
++    def is_disjoint_from(self, other):
++        """
++        Test whether the two sets are disjoint
++
++        OUTPUT:
++
++        Boolean.
++
++        EXAMPLES::
++
++            sage: s1 = RealSet((0, 1), (2, 3));  s1
++            (0, 1) + (2, 3)
++            sage: s2 = RealSet([1, 2]);  s2
++            [1, 2]
++            sage: s1.is_disjoint_from(s2)
++            True
++        """
++        return self.intersection(other).is_empty()
++
++    @staticmethod
++    def are_pairwise_disjoint(*real_set_collection):
++        """
++        Test whether sets are pairwise disjoint
++       
++        INPUT:
++
++        - ``*real_set_collection`` -- a list/tuple/iterable of real
++          sets.
++ 
++        OUTPUT:
++        
++        Boolean.
++        
++        EXAMPLES::
++        
++            sage: s1 = RealSet((0, 1), (2, 3))
++            sage: s2 = RealSet((1, 2))
++            sage: s3 = RealSet.point(3)
++            sage: RealSet.are_pairwise_disjoint(s1, s2, s3)
++            True
++            sage: RealSet.are_pairwise_disjoint(s1, s2, s3, [10,10])
++            True
++            sage: RealSet.are_pairwise_disjoint(s1, s2, s3, [-1, 1/2])
++            False
++        """
++        sets = map(RealSet, real_set_collection)
++        for i in range(len(sets)):
++            for j in range(i):
++                si = sets[i]
++                sj = sets[j]
++                if not si.is_disjoint_from(sj):
++                    return False
++        return True
++
++                

trac_13125_real_set.patch

+# HG changeset patch
+# Parent 48994bb317c2b344703015a95077e33416210699
+
+Implement RealSet - finite unions of open/closed/semi-closed subsets of the real line.
+
+diff --git a/sage/rings/real_lazy.pyx b/sage/rings/real_lazy.pyx
+--- a/sage/rings/real_lazy.pyx
++++ b/sage/rings/real_lazy.pyx
+@@ -279,7 +279,7 @@
+         else:
+             raise ValueError, "RLF has only one generator."
+ 
+-    def __repr__(self):
++    def _repr_(self):
+         """
+         Return a string representation of ``self``.
+ 
+@@ -451,7 +451,7 @@
+         """
+         return "\\Bold{C}"
+ 
+-    def __repr__(self):
++    def _repr_(self):
+         """
+         Return a string representation of ``self``.
+ 
+diff --git a/sage/sets/all.py b/sage/sets/all.py
+--- a/sage/sets/all.py
++++ b/sage/sets/all.py
+@@ -1,3 +1,7 @@
++from sage.misc.lazy_import import lazy_import
++
++lazy_import('sage.sets.real_set', 'RealSet')
++
+ from set import Set, is_Set, EnumeratedSet
+ from integer_range import IntegerRange
+ from non_negative_integers import NonNegativeIntegers
+diff --git a/sage/sets/real_set.py b/sage/sets/real_set.py
+new file mode 100644
+--- /dev/null
++++ b/sage/sets/real_set.py
+@@ -0,0 +1,1130 @@
++# -*- coding: utf-8 -*-
++"""
++Subsets of the Real Line
++
++This module contains subsets of the real line that can be constructed
++as the union of a finite set of open and closed intervals.
++
++EXAMPLES::
++
++    sage: RealSet(0,1)
++    (0, 1)
++    sage: RealSet((0,1), [2,3])
++    (0, 1) + [2, 3]
++    sage: RealSet(-oo, oo)
++    (-Infinity, +Infinity)
++
++Brackets must be balanced in Python, so the naive notation for
++half-open intervals does not work::
++
++    sage: RealSet([0,1))
++    Traceback (most recent call last):
++    ...
++    SyntaxError: invalid syntax
++    
++Instead, you can use the following construction functions::
++
++    sage: RealSet.open_closed(0,1)
++    (0, 1]
++    sage: RealSet.closed_open(0,1)
++    [0, 1)
++    sage: RealSet.point(1/2)
++    {1/2}
++    sage: RealSet.unbounded_below_open(0)
++    (-Infinity, 0)
++    sage: RealSet.unbounded_below_closed(0)
++    (-Infinity, 0]
++    sage: RealSet.unbounded_above_open(1)
++    (1, +Infinity)
++    sage: RealSet.unbounded_above_closed(1)
++    [1, +Infinity)
++"""
++
++########################################################################
++#       Copyright (C) 2013 Volker Braun <vbraun.name@gmail.com>
++#
++#  Distributed under the terms of the GNU General Public License (GPL)
++#   as published by the Free Software Foundation; either version 2 of
++#   the License, or (at your option) any later version.
++#                   http://www.gnu.org/licenses/
++########################################################################
++
++from sage.structure.parent import Parent
++from sage.structure.unique_representation import UniqueRepresentation
++from sage.rings.real_lazy import LazyFieldElement, RLF
++from sage.rings.infinity import infinity, minus_infinity
++
++
++class RealInterval(UniqueRepresentation, Parent):
++
++    def __init__(self, lower, lower_closed, upper, upper_closed, check=True):
++        """
++        A real interval
++
++        You are not supposed to create :class:`RealInterval` objects
++        yourself. Always use :class:`RealSet` instead.
++
++        EXAMPLES::
++
++            sage: RealSet([0, oo])
++            Traceback (most recent call last):
++            ...
++            ValueError: interval cannot be closed at +oo
++        """
++        self._lower = lower
++        self._upper = upper
++        self._lower_closed = lower_closed
++        self._upper_closed = upper_closed
++        if check:
++            if not isinstance(lower, LazyFieldElement):
++                raise ValueError('lower bound must be in RLF')
++            if not isinstance(upper, LazyFieldElement):
++                raise ValueError('upper bound must be in RLF')
++            if not isinstance(lower_closed, bool):
++                raise ValueError('lower_closed must be boolean')
++            if not isinstance(upper_closed, bool):
++                raise ValueError('upper_closed must be boolean')
++            if lower == infinity or upper == minus_infinity:
++                raise ValueError('only lower/upper bound can be minus/plus infinity')
++            if lower > upper:
++                raise ValueError('lower/upper bounds are not sorted')
++            if (lower_closed and lower == minus_infinity):
++                raise ValueError('interval cannot be closed at -oo')
++            if (upper_closed and upper == infinity):
++                raise ValueError('interval cannot be closed at +oo')
++            
++    def is_empty(self):
++        """
++        Return whether the interval is empty
++        
++        The normalized form of :class:`RealSet` has all intervals
++        non-empty, so this method usually returns ``False``.
++
++        OUTPUT:
++
++        Boolean.
++
++        EXAMPLES::
++
++            sage: I = RealSet(0, 1)[0]
++            sage: I.is_empty()
++            False
++        """
++        return (self._lower == self._upper) and not (self._lower_closed or self._upper_closed)
++
++    def is_point(self):
++        """
++        Return whether the interval consists of a single point
++
++        OUTPUT:
++        
++        Boolean.
++
++        EXAMPLES::
++
++            sage: I = RealSet(0, 1)[0]
++            sage: I.is_point()
++            False
++        """
++        return (self._lower == self._upper) and self._lower_closed and self._upper_closed
++
++    def lower(self):
++        """
++        Return the lower bound
++        
++        OUTPUT:
++
++        The lower bound as it was originally specified.
++        
++        EXAMPLES::
++
++            sage: I = RealSet(0, 1)[0]
++            sage: I.lower()
++            0
++            sage: I.upper()
++            1
++        """
++        return self._lower._value
++
++    def upper(self):
++        """
++        Return the upper bound
++
++        OUTPUT:
++
++        The upper bound as it was originally specified.
++        
++        EXAMPLES::
++
++            sage: I = RealSet(0, 1)[0]
++            sage: I.lower()
++            0
++            sage: I.upper()
++            1
++        """
++        return self._upper._value
++                
++    def lower_closed(self):
++        """
++        Return whether the interval is open at the lower bound
++        
++        OUTPUT:
++
++        Boolean.
++        
++        EXAMPLES::
++
++            sage: I = RealSet.open_closed(0, 1)[0];  I
++            (0, 1]
++            sage: I.lower_closed()
++            False
++            sage: I.lower_open()
++            True
++            sage: I.upper_closed()
++            True
++            sage: I.upper_open()
++            False
++        """
++        return self._lower_closed
++
++    def upper_closed(self):
++        """
++        Return whether the interval is closed at the lower bound
++
++        OUTPUT:
++
++        Boolean.
++        
++        EXAMPLES::
++
++            sage: I = RealSet.open_closed(0, 1)[0];  I
++            (0, 1]
++            sage: I.lower_closed()
++            False
++            sage: I.lower_open()
++            True
++            sage: I.upper_closed()
++            True
++            sage: I.upper_open()
++            False
++        """
++        return self._upper_closed
++                
++    def lower_open(self):
++        """
++        Return whether the interval is closed at the upper bound
++
++        OUTPUT:
++
++        Boolean.
++        
++        EXAMPLES::
++
++            sage: I = RealSet.open_closed(0, 1)[0];  I
++            (0, 1]
++            sage: I.lower_closed()
++            False
++            sage: I.lower_open()
++            True
++            sage: I.upper_closed()
++            True
++            sage: I.upper_open()
++            False
++        """
++        return not self._lower_closed
++
++    def upper_open(self):
++        """
++        Return whether the interval is closed at the upper bound
++
++        OUTPUT:
++
++        Boolean.
++        
++        EXAMPLES::
++
++            sage: I = RealSet.open_closed(0, 1)[0];  I
++            (0, 1]
++            sage: I.lower_closed()
++            False
++            sage: I.lower_open()
++            True
++            sage: I.upper_closed()
++            True
++            sage: I.upper_open()
++            False
++        """
++        return not self._upper_closed
++                
++    def __cmp__(self, other):
++        """
++        Intervals are sorted by lower bound, then upper bound
++
++        OUTPUT:
++
++        `-1`, `0`, or `+1` depending on how the intervals compare.
++        
++        EXAMPLES::
++
++             sage: I1 = RealSet.open_closed(1, 3)[0];  I1
++             (1, 3]
++             sage: I2 = RealSet.open_closed(0, 5)[0];  I2
++             (0, 5]
++             sage: cmp(I1, I2)
++             1
++             sage: sorted([I1, I2])
++             [(0, 5], (1, 3]]
++        """
++        return cmp([self._lower, self._lower_closed, self._upper, self._upper_closed],
++                   [other._lower, other._lower_closed, other._upper, other._upper_closed])
++        
++    element_class = LazyFieldElement
++
++    def _repr_(self):
++        """
++        Return a string representation
++
++        OUTPUT:
++
++        String.
++        
++        EXAMPLES::
++
++            sage: RealSet.open_closed(0, 1)
++            (0, 1]
++            sage: RealSet.point(0)
++            {0}
++        """
++        if self.is_point():
++            return '{' + str(self._lower._value) + '}'
++        s =  '[' if self._lower_closed else '('
++        s += str(self._lower._value)
++        s += ', '
++        s += str(self._upper._value)
++        s +=  ']' if self._upper_closed else ')'
++        return s
++
++    def closure(self):
++        """
++        Return the closure
++
++        OUTPUT:
++
++        The closure as a new :class:`RealInterval`
++
++        EXAMPLES:
++        
++            sage: RealSet.open(0,1)[0].closure()
++            [0, 1]
++            sage: RealSet.open(-oo,1)[0].closure()
++            (-Infinity, 1]
++            sage: RealSet.open(0, oo)[0].closure()
++            [0, +Infinity)
++        """
++        lower_closed = (self._lower != minus_infinity)
++        upper_closed = (self._upper != infinity)
++        return RealInterval(self._lower, lower_closed, self._upper, upper_closed)
++        
++    def interior(self):
++        """
++        Return the interior
++
++        OUTPUT:
++
++        The interior as a new :class:`RealInterval`
++
++        EXAMPLES:
++        
++            sage: RealSet.closed(0, 1)[0].interior()
++            (0, 1)
++            sage: RealSet.open_closed(-oo, 1)[0].interior()
++            (-Infinity, 1)
++            sage: RealSet.closed_open(0, oo)[0].interior()
++            (0, +Infinity)
++        """
++        return RealInterval(self._lower, False, self._upper, False)
++        
++    def is_connected(self, other):
++        """
++        Test whether two intervals are connected
++        
++        OUTPUT:
++
++        Boolean. Whether the set-theoretic union of the two intervals
++        has a single connected component.
++
++        EXAMPLES::
++        
++            sage: I1 = RealSet.open(0, 1)[0];  I1
++            (0, 1)
++            sage: I2 = RealSet.closed(1, 2)[0];  I2
++            [1, 2]
++            sage: I1.is_connected(I2)
++            True
++            sage: I1.is_connected(I2.interior())
++            False
++            sage: I1.closure().is_connected(I2.interior())
++            True
++            sage: I2.is_connected(I1)
++            True
++            sage: I2.interior().is_connected(I1)
++            False
++            sage: I2.closure().is_connected(I1.interior())
++            True
++            sage: I3 = RealSet.closed(1/2, 3/2)[0]; I3
++            [1/2, 3/2]
++            sage: I1.is_connected(I3)
++            True
++            sage: I3.is_connected(I1)
++            True
++        """
++        cmp_lu = cmp(self._lower, other._upper)
++        cmp_ul = cmp(self._upper, other._lower)
++        # self is seperated and below other
++        if cmp_ul == -1:
++            return False
++        # self is adjacent and below other 
++        if cmp_ul == 0:
++            return self._upper_closed or other._lower_closed
++        # self is seperated and above other
++        if cmp_lu == +1:
++            return False
++        # self is adjacent and above other 
++        if cmp_lu == 0:
++            return self._lower_closed or other._upper_closed
++        # They are not separated
++        return True
++        
++    def convex_hull(self, other):
++        """
++        Return the convex hull of the two intervals
++
++        OUTPUT:
++
++        The convex hull as a new :class:`RealInterval`.
++
++        EXAMPLES::
++
++            sage: I1 = RealSet.open(0, 1)[0];  I1
++            (0, 1)
++            sage: I2 = RealSet.closed(1, 2)[0];  I2
++            [1, 2]
++            sage: I1.convex_hull(I2)
++            (0, 2]
++            sage: I2.convex_hull(I1)
++            (0, 2]
++            sage: I1.convex_hull(I2.interior())
++            (0, 2)
++            sage: I1.closure().convex_hull(I2.interior())
++            [0, 2)
++            sage: I1.closure().convex_hull(I2)
++            [0, 2]
++            sage: I3 = RealSet.closed(1/2, 3/2)[0]; I3
++            [1/2, 3/2]
++            sage: I1.convex_hull(I3)
++            (0, 3/2]
++        """
++        cmp_ll = cmp(self._lower, other._lower)
++        cmp_uu = cmp(self._upper, other._upper)
++        lower = upper = None
++        lower_closed = upper_closed = None
++        if cmp_ll == -1:
++            lower = self._lower
++            lower_closed = self._lower_closed
++        elif cmp_ll == +1:
++            lower = other._lower
++            lower_closed = other._lower_closed
++        else:
++            assert(cmp_ll == 0)
++            lower = self._lower
++            lower_closed = self._lower_closed or other._lower_closed
++        if cmp_uu == +1:
++            upper = self._upper
++            upper_closed = self._upper_closed
++        elif cmp_uu == -1:
++            upper = other._upper
++            upper_closed = other._upper_closed
++        else:
++            assert(cmp_uu == 0)
++            upper = self._upper
++            upper_closed = self._upper_closed or other._upper_closed
++        return RealInterval(lower, lower_closed, upper, upper_closed)
++
++    def intersection(self, other):
++        """
++        Return the intersection of the two intervals
++        
++        INPUT:
++        
++        - ``other`` -- a :class:`RealInterval`
++
++        OUTPUT:
++
++        The intersection as a new :class:`RealInterval`
++
++        EXAMPLES::
++
++            sage: I1 = RealSet.open(0, 2)[0];  I1
++            (0, 2)
++            sage: I2 = RealSet.closed(1, 3)[0];  I2
++            [1, 3]
++            sage: I1.intersection(I2)
++            [1, 2)
++            sage: I2.intersection(I1)
++            [1, 2)
++            sage: I1.closure().intersection(I2.interior())
++            (1, 2]
++            sage: I2.interior().intersection(I1.closure())
++            (1, 2]
++
++            sage: I3 = RealSet.closed(10, 11)[0];  I3
++            [10, 11]
++            sage: I1.intersection(I3)
++            (0, 0)
++            sage: I3.intersection(I1)
++            (0, 0)
++        """
++        cmp_ll = cmp(self._lower, other._lower)
++        cmp_uu = cmp(self._upper, other._upper)
++        lower = upper = None
++        lower_closed = upper_closed = None
++        if cmp_ll == -1:
++            lower = other._lower
++            lower_closed = other._lower_closed
++        elif cmp_ll == +1:
++            lower = self._lower
++            lower_closed = self._lower_closed
++        else:
++            assert(cmp_ll == 0)
++            lower = self._lower
++            lower_closed = self._lower_closed and other._lower_closed
++        if cmp_uu == +1:
++            upper = other._upper
++            upper_closed = other._upper_closed
++        elif cmp_uu == -1:
++            upper = self._upper
++            upper_closed = self._upper_closed
++        else:
++            assert(cmp_uu == 0)
++            upper = self._upper
++            upper_closed = self._upper_closed and other._upper_closed
++        if lower > upper:
++            lower = upper = RLF(0)
++            lower_closed = upper_closed = False
++        return RealInterval(lower, lower_closed, upper, upper_closed)
++        
++
++
++class RealSet(UniqueRepresentation, Parent):
++
++    @staticmethod
++    def __classcall__(cls, *args):
++        """
++        Normalize the input.
++
++        INPUT:
++        
++        See :class:`RealSet`.
++          
++        OUTPUT:
++
++        A :class:`RealSet`.
++
++        EXAMPLES::
++
++            sage: RealSet(RealSet.open_closed(0,1), RealSet.closed_open(2,3))
++            (0, 1] + [2, 3)
++        """
++        intervals = []
++        if len(args) == 2:
++            # allow RealSet(0,1) interval constructor
++            try:
++                lower, upper = args
++                lower.n()
++                upper.n()
++                args = (RealSet._prep(lower, upper), )
++            except (AttributeError, ValueError, TypeError):
++                pass
++        for arg in args:
++            if isinstance(arg, tuple):
++                lower, upper = RealSet._prep(*arg)
++                intervals.append(RealInterval(lower, False, upper, False))
++            elif isinstance(arg, list):
++                lower, upper = RealSet._prep(*arg)
++                intervals.append(RealInterval(lower, True, upper, True))
++            elif isinstance(arg, RealInterval):
++                intervals.append(arg)
++            elif isinstance(arg, RealSet):
++                intervals.extend(arg._intervals)
++            else:
++                raise ValueError(str(arg) + ' does not determine real interval')
++        intervals = RealSet.normalize(intervals)
++        return UniqueRepresentation.__classcall__(cls, intervals)
++                
++    def __init__(self, intervals):
++        """
++        A subset of the real line
++
++        INPUT:
++
++        Arguments defining a real set. Possibilities are either two
++        real numbers to construct an open set or a list/tuple/iterable
++        of intervals. The individual intervals can be specified by
++        either a :class:`RealInterval`, a tuple of two real numbers
++        (constructing an open interval), or a list of two number
++        (constructing a closed interval).
++
++        EXAMPLES::
++
++            sage: RealSet(0,1)    # open set from two numbers
++            (0, 1)
++            sage: i = RealSet(0,1)[0]
++            sage: RealSet(i)      # interval
++            (0, 1)
++            sage: RealSet(i, (3,4))    # tuple of two numbers = open set
++            (0, 1) + (3, 4)
++            sage: RealSet(i, [3,4])    # list of two numbers = closed set
++            (0, 1) + [3, 4]
++        """
++        self._intervals = intervals
++    
++    def __iter__(self):
++        """
++        Iterate over the component intervals is ascending order
++        
++        OUTPUT:
++
++        An iterator over the intervals.
++
++        EXAMPLES::
++
++            sage: s = RealSet(RealSet.open_closed(0,1), RealSet.closed_open(2,3))
++            sage: i = iter(s)
++            sage: i.next()
++            (0, 1]
++            sage: i.next()
++            [2, 3)
++        """
++        return iter(self._intervals)
++
++    def n_components(self):
++        """
++        Return the number of connected components
++
++        See also :meth:`get_interval`
++
++        EXAMPLES::
++
++            sage: s = RealSet(RealSet.open_closed(0,1), RealSet.closed_open(2,3))
++            sage: s.n_components()
++            2
++            sage: len(s)   # shorthand
++            2
++        """
++        return len(self._intervals)
++
++    __len__ = n_components
++
++    def get_interval(self, i):
++        """
++        Return the ``i``-th connected component.
++
++        Note that the intervals representing the real set are always
++        normalized, see :meth:`normalize`.
++
++        INPUT:
++        
++        - ``i`` -- integer.
++
++        OUTPUT:
++
++        The $i$-th connected component as a :class:`RealInterval`.
++
++        EXAMPLES::
++        
++            sage: s = RealSet(RealSet.open_closed(0,1), RealSet.closed_open(2,3))
++            sage: s.get_interval(0)
++            (0, 1]
++            sage: s[0]    # shorthand
++            (0, 1]
++            sage: s.get_interval(1)
++            [2, 3)
++            sage: s[0] == s.get_interval(0)
++            True
++        """
++        return self._intervals[i]
++
++    __getitem__ = get_interval
++
++    @staticmethod
++    def normalize(intervals):
++        """
++        Bring a collection of intervals into canonical form
++
++        INPUT:
++
++        - ``intervals`` -- a list/tuple/iterable of intervals.
++
++        OUTPUT:
++        
++        A tuple of intervals such that
++
++        * they are sorted in ascending order (by lower bound)
++        
++        * there is a gap between each interval
++        
++        * all intervals are non-empty
++
++        EXAMPLES::
++
++            sage: i1 = RealSet((0, 1))[0]
++            sage: i2 = RealSet([1, 2])[0]
++            sage: i3 = RealSet((2, 3))[0]
++            sage: RealSet.normalize([i1, i2, i3])
++            ((0, 3),)
++
++            sage: RealSet((0, 1), [1, 2], (2, 3))
++            (0, 3)
++            sage: RealSet((0, 1), (1, 2), (2, 3))
++            (0, 1) + (1, 2) + (2, 3)
++            sage: RealSet([0, 1], [2, 3])
++            [0, 1] + [2, 3]
++            sage: RealSet((0, 2), (1, 3))
++            (0, 3)
++            sage: RealSet(0,0)
++            {}
++        """
++        # sort by lower bound
++        intervals = sorted(intervals)
++        if len(intervals) == 0:
++            return tuple()
++        merged = []
++        curr = intervals.pop(0)
++        while len(intervals) != 0:
++            next = intervals.pop(0)
++            cmp_ul = cmp(curr._upper, next._lower)
++            if cmp_ul == +1 or (
++                cmp_ul == 0 and (curr._upper_closed or next._lower_closed)):
++                curr = curr.convex_hull(next)
++            else:
++                if not curr.is_empty():
++                    merged.append(curr)
++                curr = next
++        if not curr.is_empty():
++            merged.append(curr)
++        return tuple(merged)
++
++    def _repr_(self):
++        """
++        Return a string representation
++        
++        OUTPUT:
++
++        A string representation.
++
++        EXAMPLES::
++
++            sage: RealSet(0, 1)._repr_()
++            '(0, 1)'
++        """
++        if self.n_components() == 0:
++            return '{}'
++        else:
++            # Switch to u'\u222A' (cup sign) with Python 3
++            return ' + '.join(map(repr, self._intervals))
++
++    @staticmethod
++    def _prep(lower, upper):
++        """
++        Helper to prepare the lower and upper bound
++
++        EXAMPLES::
++
++            sage: RealSet._prep(1, 0)
++            (0, 1)
++        """
++        lower = RLF(lower)
++        upper = RLF(upper)
++        if upper < lower:
++            return upper, lower
++        else:
++            return lower, upper
++
++    @staticmethod
++    def open(lower, upper):
++        """
++        Construct an open interval
++
++        INPUT:
++
++        - ``lower``, ``upper`` -- two real numbers or infinity. They
++          will be sorted if necessary.
++
++        OUTPUT:
++
++        A new :class:`RealSet`.
++
++        EXAMPLES::
++
++            sage: RealSet.open(1, 0)
++            (0, 1)
++        """
++        lower, upper = RealSet._prep(lower, upper)
++        return RealSet(RealInterval(lower, False, upper, False))
++
++    @staticmethod
++    def closed(lower, upper):
++        """
++        Construct a closed interval
++
++        INPUT:
++
++        - ``lower``, ``upper`` -- two real numbers or infinity. They
++          will be sorted if necessary.
++
++        OUTPUT:
++
++        A new :class:`RealSet`.
++
++        EXAMPLES::
++
++            sage: RealSet.closed(1, 0)
++            [0, 1]
++        """
++        lower, upper = RealSet._prep(lower, upper)
++        return RealSet(RealInterval(lower, True, upper, True))
++
++    @staticmethod
++    def point(p):
++        """
++        Construct an interval containing a single point
++
++        INPUT:
++
++        - ``p``, ``upper`` -- a real number.
++
++        OUTPUT:
++
++        A new :class:`RealSet`.
++
++        EXAMPLES::
++
++            sage: RealSet.open(1, 0)
++            (0, 1)
++        """
++        p = RLF(p)
++        return RealSet(RealInterval(p, True, p, True))
++    
++    @staticmethod
++    def open_closed(lower, upper):
++        """
++        Construct a half-open interval
++
++        INPUT:
++
++        - ``lower``, ``upper`` -- two real numbers or infinity. They
++          will be sorted if necessary.
++
++        OUTPUT:
++
++        A new :class:`RealSet` that is open at the lower bound and
++        closed at the upper bound.
++
++        EXAMPLES::
++
++            sage: RealSet.open_closed(1, 0)
++            (0, 1]
++        """
++        lower, upper = RealSet._prep(lower, upper)
++        return RealSet(RealInterval(lower, False, upper, True))
++
++    @staticmethod
++    def closed_open(lower, upper):
++        """
++        Construct an half-open interval
++
++        INPUT:
++
++        - ``lower``, ``upper`` -- two real numbers or infinity. They
++          will be sorted if necessary.
++
++        OUTPUT:
++
++        A new :class:`RealSet` that is closed at the lower bound and
++        open an the upper bound.
++
++        EXAMPLES::
++
++            sage: RealSet.closed_open(1, 0)
++            [0, 1)
++        """
++        lower, upper = RealSet._prep(lower, upper)
++        return RealSet(RealInterval(lower, True, upper, False))
++
++    @staticmethod
++    def unbounded_below_closed(bound):
++        """
++        Construct a semi-infinite interval
++
++        INPUT:
++
++        - ``bound`` -- a real number.
++
++        OUTPUT:
++
++        A new :class:`RealSet` from minus infinity to the bound (including).
++
++        EXAMPLES::
++
++            sage: RealSet.unbounded_below_closed(1)
++            (-Infinity, 1]
++        """
++        return RealSet(RealInterval(RLF(minus_infinity), False, RLF(bound), True))
++
++    @staticmethod
++    def unbounded_below_open(bound):
++        """
++        Construct a semi-infinite interval
++
++        INPUT:
++
++        - ``bound`` -- a real number.
++
++        OUTPUT:
++
++        A new :class:`RealSet` from minus infinity to the bound (excluding).
++
++        EXAMPLES::
++
++            sage: RealSet.unbounded_below_open(1)
++            (-Infinity, 1)
++        """
++        return RealSet(RealInterval(RLF(minus_infinity), False, RLF(bound), False))
++
++    @staticmethod
++    def unbounded_above_closed(bound):
++        """
++        Construct a semi-infinite interval
++
++        INPUT:
++
++        - ``bound`` -- a real number.
++
++        OUTPUT:
++
++        A new :class:`RealSet` from the bound (including) to plus
++        infinity.
++
++        EXAMPLES::
++
++            sage: RealSet.unbounded_above_closed(1)
++            [1, +Infinity)
++        """
++        return RealSet(RealInterval(RLF(bound), True, RLF(infinity), False))
++
++    @staticmethod
++    def unbounded_above_open(bound):
++        """
++        Construct a semi-infinite interval
++
++        INPUT:
++
++        - ``bound`` -- a real number.
++
++        OUTPUT:
++
++        A new :class:`RealSet` from the bound (excluding) to plus
++        infinity.
++
++        EXAMPLES::
++
++            sage: RealSet.unbounded_above_open(1)
++            (1, +Infinity)
++        """
++        return RealSet(RealInterval(RLF(bound), False, RLF(infinity), False))
++
++    def union(self, other):
++        """
++        Return the union of the two sets
++
++        INPUT:
++        
++        - ``other`` -- a :class:`RealSet`.
++
++        OUTPUT:
++        
++        The set-theoretic union as a new :class:`RealSet`.
++
++        EXAMPLES::
++
++            sage: s1 = RealSet(0,2)
++            sage: s2 = RealSet(1,3)
++            sage: s1.union(s2)
++            (0, 3)
++            sage: s1 | s2    # syntactic sugar
++            (0, 3)
++            sage: s1 + s2    # syntactic sugar
++            (0, 3)
++        """
++        intervals = self._intervals + other._intervals
++        return RealSet(*intervals)
++    
++    __or__ = union
++    __add__ = union
++
++    def intersection(self, other):
++        """
++        Return the intersection of the two sets
++
++        INPUT:
++        
++        - ``other`` -- a :class:`RealSet`.
++
++        OUTPUT:
++        
++        The set-theoretic intersection as a new :class:`RealSet`.
++
++        EXAMPLES::
++
++            sage: s1 = RealSet(0,2) + RealSet.unbounded_above_closed(10);  s1
++            (0, 2) + [10, +Infinity)
++            sage: s2 = RealSet(1,3) + RealSet.unbounded_below_closed(-10);  s2
++            (-Infinity, -10] + (1, 3)
++            sage: s1.intersection(s2)
++            (1, 2)
++            sage: s1 & s2    # syntactic sugar
++            (1, 2)
++        """
++        # TODO: this can be done in linear time since the intervals are already sorted
++        intervals = []
++        for i1 in self._intervals:
++            for i2 in other._intervals:
++                intervals.append(i1.intersection(i2))
++        return RealSet(*intervals)
++
++    __and__ = intersection
++
++    def inf(self):
++        """
++        Return the infimum
++
++        OUTPUT:
++
++        A real number or infinity.
++
++        EXAMPLES::
++
++            sage: s1 = RealSet(0,2) + RealSet.unbounded_above_closed(10);  s1
++            (0, 2) + [10, +Infinity)
++            sage: s1.inf()
++            0
++
++            sage: s2 = RealSet(1,3) + RealSet.unbounded_below_closed(-10);  s2
++            (-Infinity, -10] + (1, 3)
++            sage: s2.inf()
++            -Infinity
++        """
++        if self.n_components() == 0:
++            return infinity
++        return self._intervals[0].lower()
++
++    def sup(self):
++        """
++        Return the supremum
++
++        OUTPUT:
++
++        A real number or infinity.
++
++        EXAMPLES::
++
++            sage: s1 = RealSet(0,2) + RealSet.unbounded_above_closed(10);  s1
++            (0, 2) + [10, +Infinity)
++            sage: s1.sup()
++            +Infinity
++
++            sage: s2 = RealSet(1,3) + RealSet.unbounded_below_closed(-10);  s2
++            (-Infinity, -10] + (1, 3)
++            sage: s2.sup()
++            3
++        """
++        if self.n_components() == 0:
++            return minus_infinity
++        return self._intervals[-1].upper()
++
++    def complement(self):
++        """
++        Return the complement
++
++        OUTPUT:
++
++        The set-theoretic complement as a new :class:`RealSet`.
++        
++        EXAMPLES::
++
++            sage: RealSet(0,1).complement()
++            (-Infinity, 0] + [1, +Infinity)
++       
++            sage: s1 = RealSet(0,2) + RealSet.unbounded_above_closed(10);  s1
++            (0, 2) + [10, +Infinity)
++            sage: s1.complement()
++            (-Infinity, 0] + [2, 10)
++
++            sage: s2 = RealSet(1,3) + RealSet.unbounded_below_closed(-10);  s2
++            (-Infinity, -10] + (1, 3)
++            sage: s2.complement()
++            (-10, 1] + [3, +Infinity)
++        """
++        n = self.n_components()
++        if n == 0:
++            return RealSet(minus_infinity, infinity)
++        intervals = []
++        if self.inf() != minus_infinity:
++            first = self._intervals[0]
++            intervals.append(RealInterval(RLF(minus_infinity), False, 
++                                          first._lower, first.lower_open()))
++        if self.sup() != infinity:
++            last = self._intervals[-1]
++            intervals.append(RealInterval(last._upper, last.upper_open(), 
++                                          RLF(infinity), False))
++        for i in range(1,n):
++            prev = self._intervals[i-1]
++            next = self._intervals[i]
++            i = RealInterval(prev._upper, prev.upper_open(),
++                             next._lower, next.lower_open())
++            intervals.append(i)
++        return RealSet(*intervals)
++                             
++    def difference(self, other):
++        """
++        Return ``self`` with ``other`` subtracted
++
++        INPUT:
++        
++        - ``other`` -- a :class:`RealSet`.
++
++        OUTPUT:
++        
++        The set-theoretic difference of ``self`` with ``other``
++        removed as a new :class:`RealSet`.
++
++        OUTPUT:
++
++        A new :class:`RealSet`
++
++            sage: s1 = RealSet(0,2) + RealSet.unbounded_above_closed(10);  s1
++            (0, 2) + [10, +Infinity)
++            sage: s2 = RealSet(1,3) + RealSet.unbounded_below_closed(-10);  s2
++            (-Infinity, -10] + (1, 3)
++            sage: s1.difference(s2)
++            (0, 1] + [10, +Infinity)
++            sage: s1 - s2    # syntactic sugar
++            (0, 1] + [10, +Infinity)
++            sage: s2.difference(s1)
++            (-Infinity, -10] + [2, 3)
++            sage: s2 - s1    # syntactic sugar
++            (-Infinity, -10] + [2, 3)
++        """
++        return self.intersection(other.complement())
++
++    __sub__ = difference

trac_14353_toric_morphism_composition.patch

+# HG changeset patch
+# Parent a779af3c322a2c453844fe56c683aa140803173a
+
+Use the morphism framework for composition of toric morphisms
+
+diff --git a/sage/schemes/toric/morphism.py b/sage/schemes/toric/morphism.py
+--- a/sage/schemes/toric/morphism.py
++++ b/sage/schemes/toric/morphism.py
+@@ -161,6 +161,12 @@
+ #                  http://www.gnu.org/licenses/
+ #*****************************************************************************
+ 
++# For now, the scheme morphism base class cannot derive from Morphism
++# since this would clash with elliptic curves. So we derive only on
++# the toric varieties level from Morphism. See
++# https://groups.google.com/d/msg/sage-devel/qF4yU6Vdmao/wQlNrneSmWAJ
++from sage.categories.morphism import Morphism
++
+ from sage.structure.sequence  import Sequence
+ from sage.rings.all import ZZ
+ 
+@@ -174,7 +180,7 @@
+ 
+ ############################################################################
+ # A points on a toric variety determined by homogeneous coordinates.
+-class SchemeMorphism_point_toric_field(SchemeMorphism_point):
++class SchemeMorphism_point_toric_field(SchemeMorphism_point, Morphism):
+     """
+     A point of a toric variety determined by homogeneous coordinates
+     in a field.
+@@ -245,7 +251,7 @@
+ 
+ ############################################################################
+ # A morphism of toric varieties determined by homogeneous polynomials.
+-class SchemeMorphism_polynomial_toric_variety(SchemeMorphism_polynomial):
++class SchemeMorphism_polynomial_toric_variety(SchemeMorphism_polynomial, Morphism):
+     """
+     A morphism determined by homogeneous polynomials.
+ 
+@@ -341,7 +347,7 @@
+         
+ ############################################################################
+ # A morphism of toric varieties determined by a fan morphism
+-class SchemeMorphism_fan_toric_variety(SchemeMorphism):
++class SchemeMorphism_fan_toric_variety(SchemeMorphism, Morphism):
+     """
+     Construct a morphism determined by a fan morphism
+ 
+@@ -462,7 +468,7 @@
+         else:
+             return cmp(type(self), type(right))
+ 
+-    def __imul__(self, right):
++    def _composition_(self, right, homset):
+         """
+         Return the composition of ``self`` and ``right``.
+         
+@@ -480,25 +486,19 @@
+             sage: P3 = toric_varieties.P(3)
+             sage: m = matrix([(2,0,0), (1,1,0)])
+             sage: phi = A2.hom(m, P3)
+-            sage: phi
++            sage: phi1, phi2, phi3 = phi.factor()
++            sage: phi1 * phi2
+             Scheme morphism:
+               From: 2-d affine toric variety
+               To:   3-d CPR-Fano toric variety covered by 4 affine patches
+-              Defn: Defined by sending Rational polyhedral fan in 2-d lattice N to
+-                    Rational polyhedral fan in 3-d lattice N.
+-            sage: prod(phi.factor()) # indirect test
+-            Scheme morphism:
+-              From: 2-d affine toric variety
+-              To:   3-d CPR-Fano toric variety covered by 4 affine patches
+-              Defn: Defined by sending Rational polyhedral fan in 2-d lattice N to
+-                    Rational polyhedral fan in 3-d lattice N.
++              Defn: Defined by sending Rational polyhedral fan in Sublattice 
++                    <N(1, 0, 0), N(0, 1, 0)> to Rational polyhedral fan in 3-d lattice N.
++            sage: phi1 * phi2 * phi3 == phi
++            True
+         """
+-        if not isinstance(right, SchemeMorphism_fan_toric_variety):
+-            raise NotImplementedError("only composing toric morphisms based on "
+-                                "fan morphisms is implemented at the moment")
+         f = self.fan_morphism() * right.fan_morphism()
+-        return right.domain().hom(f, self.codomain())
+-
++        return homset(f, self.codomain())
++        
+     def _repr_defn(self):
+         """
+         Return a string representation of the definition of ``self``.

trac_14353_toric_morphism_factoring.patch

 # HG changeset patch
-# Parent e3e148cfc191b19a56a7cec9903f3470023c85c1
+# User Andrey Novoseltsev <novoselt@gmail.com>
+# Date 1365570115 21600
+# Node ID ecd0aa73d06679eea552be0127d6abd9789e4d96
+# Parent  a535f3797e001d13b7fda0f90f49056680dbc2d3
 Factor method for toric morphisms defined by fan morphisms.
 
 diff --git a/sage/schemes/toric/morphism.py b/sage/schemes/toric/morphism.py
 --- a/sage/schemes/toric/morphism.py
 +++ b/sage/schemes/toric/morphism.py
-@@ -427,6 +427,43 @@
+@@ -427,6 +427,78 @@
              raise ValueError('The fan morphism codomain must be the fan of the codomain.')
          self._fan_morphism = fan_morphism
  
++    def __cmp__(self, right):
++        r"""
++        Compare ``self`` and ``right``.
++
++        INPUT:
++
++        - ``right`` -- anything.
++
++        OUTPUT:
++
++        - 0 if ``right`` is also a toric morphism between the same domain and
++          codomain, given by an equal fan morphism. 1 or -1 otherwise.
++
++        TESTS::
++
++            sage: A2 = toric_varieties.A2()
++            sage: P3 = toric_varieties.P(3)
++            sage: m = matrix([(2,0,0), (1,1,0)])
++            sage: phi = A2.hom(m, P3)
++            sage: cmp(phi, phi)
++            0
++            sage: cmp(phi, prod(phi.factor()))
++            0
++            sage: cmp(phi, phi.factor()[0])
++            -1
++            sage: cmp(phi, 1) * cmp(1, phi)
++            -1
++        """
++        if isinstance(right, SchemeMorphism_fan_toric_variety):
++            return cmp(
++                [self.domain(), self.codomain(), self.fan_morphism()],
++                [right.domain(), right.codomain(), right.fan_morphism()])
++        else:
++            return cmp(type(self), type(right))
++
 +    def __imul__(self, right):
 +        """
 +        Return the composition of ``self`` and ``right``.
      def _repr_defn(self):
          """
          Return a string representation of the definition of ``self``.
-@@ -450,6 +487,98 @@
+@@ -450,6 +522,98 @@
          s += '.'
          return s
  
      def fan_morphism(self):
          """
          Return the defining fan morphism.
-@@ -515,6 +644,29 @@
+@@ -515,6 +679,29 @@
                  polys[i] *= x**d
          return SchemeMorphism_polynomial_toric_variety(self.parent(), polys)
  

trac_14537_identity_morphism.patch

+# HG changeset patch
+# Date 1367842270 -7200
+# User Thomas Feulner <thomas.feulner@uni-bayreuth.de>
+# Parent 1077314f416653b28e199c382667a1f11e444bdd
+#14537: Composition with the identity morphism
+
+diff --git a/sage/categories/morphism.pyx b/sage/categories/morphism.pyx
+--- a/sage/categories/morphism.pyx
++++ b/sage/categories/morphism.pyx
+@@ -215,10 +215,10 @@
+             return self._codomain._element_constructor(x, *args, **kwds)
+ 
+     def __mul__(left, right):
+-        if not isinstance(right, Morphism):
+-            raise TypeError, "right (=%s) must be a morphism to multiply it by %s"%(right, left)
+-        if not isinstance(left, Morphism):
+-            raise TypeError, "left (=%s) must be a morphism to multiply it by %s"%(left, right)
++        if not isinstance(right, Map):
++            raise TypeError, "right (=%s) must be a map to multiply it by %s"%(right, left)
++        if not isinstance(left, Map):
++            raise TypeError, "left (=%s) must be a map to multiply it by %s"%(left, right)
+         if right.codomain() != left.domain():
+             raise TypeError, "self (=%s) domain must equal right (=%s) codomain"%(left, right)
+         if isinstance(left, IdentityMorphism):

trac_14780-embed_tuples_in_SR.patch

+# HG changeset patch
+# User Burcin Erocal <burcin@erocal.org>
+# Date 1371783600 -7200
+#      Fri Jun 21 05:00:00 2013 +0200
+# Node ID 9a78ccc0eaa81503a375495d4c8038e1c441fc04
+# Parent  891f9c82cd8e5b927fb062f2d0c6e7834587d2d0
+Allow embedding tuples in SR.
+
+diff --git a/sage/libs/ginac.pxd b/sage/libs/ginac.pxd
+--- a/sage/libs/ginac.pxd
++++ b/sage/libs/ginac.pxd
+@@ -20,6 +20,7 @@
+     
+     # forward declaration of GEx
+     ctypedef struct GEx "ex"
++    ctypedef struct GExprSeq "exprseq"
+ 
+     ctypedef struct GBasic "basic":
+         unsigned int gethash()
+@@ -198,6 +199,8 @@
+     GEx* GEx_construct_long "Construct_p<ex, long>" (void *mem, long n) except +
+     GEx* GEx_construct_double "Construct_p<ex, double>" \
+             (void *mem, double d) except +
++    GEx* GEx_construct_exprseq "Construct_p<ex, exprseq>" \
++            (void *mem, GExprSeq s)
+ 
+     GEx* GEx_construct_pyobject "ASSIGN_WRAP" (GEx mem, object n)        
+ 
+@@ -224,6 +227,15 @@
+         int size()
+         GEx at(int i)
+ 
++    ctypedef struct GExprSeq "exprseq":
++        pass
++
++    GExprSeq* GExprSeq_construct_exvector "Construct_p<exprseq, exvector>" \
++            (void *mem, GExVector m) except +
++    bint is_a_exprseq "is_a<exprseq>" (GEx e)
++    bint is_exactly_a_exprseq "is_exactly_a<exprseq>" (GEx e)
++
++
+     ctypedef struct GExSetIter "std::set<ex, ex_is_less>::const_iterator":
+         void inc "operator++" ()
+         GEx obj "operator*" ()
+diff --git a/sage/symbolic/pynac.pyx b/sage/symbolic/pynac.pyx
+--- a/sage/symbolic/pynac.pyx
++++ b/sage/symbolic/pynac.pyx
+@@ -62,6 +62,44 @@
+     nex._parent = ring.SR
+     return nex
+ 
++cdef public object exprseq_to_PyTuple(GEx seq):
++    """
++    Convert an exprseq to a Python tuple.
++
++    Used while converting arguments of symbolic functions to Python objects.
++
++    EXAMPLES::
++
++        sage: from sage.symbolic.function import BuiltinFunction
++        sage: class TFunc(BuiltinFunction):
++        ....:     def __init__(self):
++        ....:         BuiltinFunction.__init__(self, 'tfunc', nargs=0)
++        ....:
++        ....:     def _eval_(self, *args):
++        ....:         print "len(args): %s, types: %s"%(len(args), str(map(type, args)))
++        ....:         for i, a in enumerate(args):
++        ....:             if isinstance(a, tuple):
++        ....:                 print "argument %s is a tuple, with types %s"%(str(i), str(map(type, a)))
++        ....:
++        sage: tfunc = TFunc()
++        sage: u = SR._force_pyobject((1, x+1, 2))
++        sage: tfunc(u, x, SR._force_pyobject((3.0, 2^x)))
++        len(args): 3, types: [<type 'tuple'>, <type 'sage.symbolic.expression.Expression'>, <type 'tuple'>]
++        argument 0 is a tuple, with types [<type 'sage.rings.integer.Integer'>, <type 'sage.symbolic.expression.Expression'>, <type 'sage.rings.integer.Integer'>]
++        argument 2 is a tuple, with types [<type 'sage.rings.real_mpfr.RealLiteral'>, <type 'sage.symbolic.expression.Expression'>]
++        tfunc((1, x + 1, 2), x, (3.00000000000000, 2^x))
++    """
++    from sage.symbolic.ring import SR
++    res = []
++    for i in range(seq.nops()):
++        if is_a_numeric(seq.op(i)):
++            res.append(py_object_from_numeric(seq.op(i)))
++        elif is_exactly_a_exprseq(seq.op(i)):
++            res.append(exprseq_to_PyTuple(seq.op(i)))
++        else:
++            res.append(new_Expression_from_GEx(SR, seq.op(i)))
++    return tuple(res)
++
+ cdef public object exvector_to_PyTuple(GExVector seq):
+     """
+     Converts arguments list given to a function to a PyTuple. 
+@@ -71,12 +109,39 @@
+ 
+     We convert Python objects wrapped in symbolic expressions back to regular
+     Python objects.
++
++    EXAMPLES::
++
++        sage: from sage.symbolic.function import BuiltinFunction
++        sage: class TFunc(BuiltinFunction):
++        ....:     def __init__(self):
++        ....:         BuiltinFunction.__init__(self, 'tfunc', nargs=0)
++        ....:
++        ....:     def _eval_(self, *args):
++        ....:         print "len(args): %s, types: %s"%(len(args), str(map(type, args)))
++        sage: tfunc = TFunc()
++        sage: u = SR._force_pyobject((1, x+1, 2))
++        sage: tfunc(u, x, 3.0, 5.0r, 1r)
++        len(args): 5, types: [<type 'tuple'>, <type 'sage.symbolic.expression.Expression'>, <type 'sage.rings.real_mpfr.RealLiteral'>, <type 'float'>, <type 'int'>]
++        tfunc((1, x + 1, 2), x, 3.00000000000000, 5.0, 1)
++
++    TESTS:
++
++    Check if symbolic functions in the arguments are preserved::
++
++        sage: tfunc(sin(x), tfunc(1, x^2))
++        len(args): 2, types: [<type 'sage.rings.integer.Integer'>, <type 'sage.symbolic.expression.Expression'>]
++        len(args): 2, types: [<type 'sage.symbolic.expression.Expression'>, <type 'sage.symbolic.expression.Expression'>]
++        tfunc(sin(x), tfunc(1, x^2))
++
+     """
+     from sage.symbolic.ring import SR
+     res = []
+     for i in range(seq.size()):
+         if is_a_numeric(seq.at(i)):
+             res.append(py_object_from_numeric(seq.at(i)))
++        elif is_exactly_a_exprseq(seq.at(i)):
++            res.append(exprseq_to_PyTuple(seq.at(i)))
+         else:
+             res.append(new_Expression_from_GEx(SR, seq.at(i)))
+     return tuple(res)
+diff --git a/sage/symbolic/ring.pyx b/sage/symbolic/ring.pyx
+--- a/sage/symbolic/ring.pyx
++++ b/sage/symbolic/ring.pyx
+@@ -285,20 +285,65 @@
+ 
+         return new_Expression_from_GEx(self, exp)
+ 
+-    def _force_pyobject(self, x):
++    def _force_pyobject(self, x, bint force=False):
+         """
+         Wrap the given Python object in a symbolic expression even if it
+         cannot be coerced to the Symbolic Ring.
+ 
+         EXAMPLES::
+ 
+-            sage: t = SR._force_pyobject([3,4,5]); t
+-            [3, 4, 5]
++            sage: t = SR._force_pyobject(QQ); t
++            Rational Field
+             sage: type(t)
+             <type 'sage.symbolic.expression.Expression'>
++
++        Testing tuples::
++
++            sage: t = SR._force_pyobject((1, 2, x, x+1, x+2)); t
++            (1, 2, x, x + 1, x + 2)
++            sage: t.subs(x = 2*x^2)
++            (1, 2, 2*x^2, 2*x^2 + 1, 2*x^2 + 2)
++            sage: t.op[0]
++            1
++            sage: t.op[2]
++            x
++
++        It also works if the argument is a ``list``::
++
++            sage: t = SR._force_pyobject([1, 2, x, x+1, x+2]); t
++            (1, 2, x, x + 1, x + 2)
++            sage: t.subs(x = 2*x^2)
++            (1, 2, 2*x^2, 2*x^2 + 1, 2*x^2 + 2)
++            sage: SR._force_pyobject((QQ, RR, CC))
++            (Rational Field, Real Field with 53 bits of precision, Complex Field with 53 bits of precision)
++            sage: t = SR._force_pyobject((QQ, (x, x + 1, x + 2), CC)); t
++            (Rational Field, (x, x + 1, x + 2), Complex Field with 53 bits of precision)
++            sage: t.subs(x=x^2)
++            (Rational Field, (x^2, x^2 + 1, x^2 + 2), Complex Field with 53 bits of precision)
+         """
+         cdef GEx exp
+-        GEx_construct_pyobject(exp, x)
++        cdef GExprSeq ex_seq
++        cdef GExVector ex_v
++        if not force:
++            # first check if we can do it the nice way
++            if isinstance(x, Expression):
++                return x
++            try:
++                return self._coerce_(x)
++            except TypeError:
++                pass
++
++            # tuples can be packed into exprseq
++            if isinstance(x, (tuple, list)):
++                for e in x:
++                    ex_v.push_back((<Expression>SR._force_pyobject(e))._gobj)
++
++                GExprSeq_construct_exvector(&ex_seq, ex_v)
++
++                GEx_construct_exprseq(&exp, ex_seq)
++            else:
++                GEx_construct_pyobject(exp, x)
++
+         return new_Expression_from_GEx(self, exp)
+ 
+     def wild(self, unsigned int n=0):

trac_14800_subs.patch

+# HG changeset patch
+# Parent f2bdb68b144f510a415b9bb498a3c40ad9214941
+
+Optional Pynac -> Python callback for subs()
+
+diff --git a/module_list.py b/module_list.py
+--- a/module_list.py
++++ b/module_list.py
+@@ -1952,6 +1952,12 @@
+               depends = ginac_depends + numpy_depends,
+               libraries = ["pynac", "gmp"]),
+ 
++    Extension('sage.symbolic.substitution_map',
++              sources = ['sage/symbolic/substitution_map.pyx'],
++              language = 'c++',
++              depends = ginac_depends,
++              libraries = ["pynac", "gmp"]),
++    
+     ################################
+     ## 
+     ## sage.tests
+diff --git a/sage/libs/ginac.pxd b/sage/libs/ginac.pxd
+--- a/sage/libs/ginac.pxd
++++ b/sage/libs/ginac.pxd
+@@ -78,7 +78,7 @@
+         bint find(GEx pattern, GExList s) except +
+         bint has(GEx pattern)         except +
+         GEx subs(GEx expr)            except +
+-        GEx subs_map "subs" (GExMap map) except +
++        GEx subs_map "subs" (GExMap map, unsigned options) except +
+         GEx coeff(GEx expr, int n)    except +
+         GEx lcoeff(GEx expr)          except +
+         GEx tcoeff(GEx expr)          except +
+@@ -193,6 +193,8 @@
+     GEx* GEx_construct_symbol "Construct_p<ex, symbol>" \
+             (void *mem, GSymbol m) except +
+     GEx* GEx_construct_ex "Construct_p<ex, ex>" (void *mem, GEx m) except +
++    void GExMap_destruct "Destruct<exmap>"(GExMap *mem) except +
++    GExMap* GEx_construct_exmap "Construct_p<exmap, exmap>" (void *mem, GExMap m) except +
+     GEx* GEx_construct_long "Construct_p<ex, long>" (void *mem, long n) except +
+     GEx* GEx_construct_double "Construct_p<ex, double>" \
+             (void *mem, double d) except +
+@@ -350,6 +352,7 @@
+         unsigned get_nparams()
+         void set_python_func()
+         GFunctionOpt eval_func(object f)
++        GFunctionOpt subs_func(object f)
+         GFunctionOpt evalf_func(object f)
+         GFunctionOpt conjugate_func(object f)
+         GFunctionOpt real_part_func(object f)
+@@ -510,6 +513,7 @@
+         GEx pyExpression_to_ex(object res) except *
+         object ex_to_pyExpression(GEx juice)
+         int py_get_ginac_serial()
++        object subs_args_to_PyTuple(GExMap map, unsigned options, GExVector seq)
+ 
+         object py_get_sfunction_from_serial(unsigned s) except +
+         unsigned py_get_serial_from_sfunction(object f) except +
+@@ -519,7 +523,6 @@
+         stdstring* py_print_function(unsigned id, object args) except +
+         stdstring* py_latex_function(unsigned id, object args) except +
+ 
+-
+         GConstant py_get_constant(const_char_ptr name) except +
+ 
+         stdstring* (*py_print_fderivative)(unsigned id, object params, object args) except +
+diff --git a/sage/symbolic/expression.pyx b/sage/symbolic/expression.pyx
+--- a/sage/symbolic/expression.pyx
++++ b/sage/symbolic/expression.pyx
+@@ -4016,7 +4016,7 @@
+             smap.insert(make_pair((<Expression>self.coerce_in(k))._gobj,
+                                   (<Expression>self.coerce_in(v))._gobj))
+ 
+-        return new_Expression_from_GEx(self._parent, self._gobj.subs_map(smap))
++        return new_Expression_from_GEx(self._parent, self._gobj.subs_map(smap, 0))
+ 
+     subs = substitute
+     
+diff --git a/sage/symbolic/function.pyx b/sage/symbolic/function.pyx
+--- a/sage/symbolic/function.pyx
++++ b/sage/symbolic/function.pyx
+@@ -150,6 +150,9 @@
+         if not self._evalf_params_first:
+             opt.do_not_evalf_params()
+ 
++        if hasattr(self, '_subs_'):
++            opt.subs_func(self)
++
+         if hasattr(self, '_evalf_'):
+             opt.evalf_func(self)
+ 
+diff --git a/sage/symbolic/pynac.pyx b/sage/symbolic/pynac.pyx
+--- a/sage/symbolic/pynac.pyx
++++ b/sage/symbolic/pynac.pyx
+@@ -34,6 +34,7 @@
+ from sage.rings.all import CC
+ 
+ from sage.symbolic.expression cimport Expression, new_Expression_from_GEx
++from sage.symbolic.substitution_map cimport SubstitutionMap, new_SubstitutionMap_from_GExMap
+ from sage.symbolic.function import get_sfunction_from_serial
+ from sage.symbolic.function cimport Function, parent_c
+ from sage.symbolic.constants_c cimport PynacConstant
+@@ -158,6 +159,32 @@
+     """
+     return py_get_ginac_serial()
+ 
++cdef public object subs_args_to_PyTuple(const GExMap& map, unsigned options, const GExVector& seq):
++    """
++    Convert arguments from ``GiNaC::subs()`` to a PyTuple. 
++    
++    EXAMPLES::
++
++        sage: from sage.symbolic.function import BuiltinFunction
++        sage: class TFunc(BuiltinFunction):
++        ....:     def __init__(self):
++        ....:         BuiltinFunction.__init__(self, 'tfunc', nargs=0)
++        ....:
++        ....:     def _subs_(self, *args):
++        ....:         print "len(args): %s, types: %s"%(len(args), str(map(type, args)))
++        ....:         return args[-1]
++        sage: tfunc = TFunc()
++        sage: tfunc(x).subs(x=1)
++        len(args): 3, types: [<type 'sage.symbolic.substitution_map.SubstitutionMap'>, 
++        <type 'long'>, <type 'sage.symbolic.expression.Expression'>]
++        x
++    """
++    from sage.symbolic.ring import SR
++    res = []
++    res.append(new_SubstitutionMap_from_GExMap(map))
++    res.append(options)
++    return tuple(res) + exvector_to_PyTuple(seq)
++
+ #################################################################
+ # Printing helpers
+ #################################################################
+@@ -2134,6 +2161,7 @@
+     py_funcs.exvector_to_PyTuple = &exvector_to_PyTuple
+     py_funcs.pyExpression_to_ex = &pyExpression_to_ex
+     py_funcs.ex_to_pyExpression = &ex_to_pyExpression
++    py_funcs.subs_args_to_PyTuple = &subs_args_to_PyTuple
+     py_funcs.py_print_function = &py_print_function
+     py_funcs.py_latex_function = &py_latex_function
+     py_funcs.py_get_ginac_serial = &py_get_ginac_serial
+diff --git a/sage/symbolic/substitution_map.pxd b/sage/symbolic/substitution_map.pxd
+new file mode 100644
+--- /dev/null
++++ b/sage/symbolic/substitution_map.pxd
+@@ -0,0 +1,11 @@
++from sage.libs.ginac cimport *
++
++from sage.symbolic.expression cimport Expression
++from sage.structure.sage_object cimport SageObject
++
++cdef class SubstitutionMap(SageObject):
++    cdef GExMap _gmapobj
++    cpdef Expression apply_to(self, Expression expr, unsigned options)
++    
++cdef SubstitutionMap new_SubstitutionMap_from_GExMap(const GExMap& smap)
++
+diff --git a/sage/symbolic/substitution_map.pyx b/sage/symbolic/substitution_map.pyx
+new file mode 100644
+--- /dev/null
++++ b/sage/symbolic/substitution_map.pyx
+@@ -0,0 +1,112 @@
++"""
++Substitution Maps
++
++This object wraps Pynac ``smap`` objects. These encode substitutions
++of symbolic expressions. The main use of this module is to hook into
++Pynac's ``subs()`` methods and pass a wrapper for the substitution map
++back to Python.
++"""
++
++########################################################################
++#       Copyright (C) 2013 Volker Braun <vbraun.name@gmail.com>
++#
++#  Distributed under the terms of the GNU General Public License (GPL)
++#   as published by the Free Software Foundation; either version 2 of
++#   the License, or (at your option) any later version.
++#                   http://www.gnu.org/licenses/
++########################################################################
++
++include "sage/ext/interrupt.pxi"
++include "sage/ext/stdsage.pxi"
++include "sage/ext/cdefs.pxi"
++include "sage/ext/python.pxi"
++
++from sage.libs.ginac cimport *
++from sage.symbolic.expression cimport *
++
++
++cdef class SubstitutionMap(SageObject):
++
++    cpdef Expression apply_to(self, Expression expr, unsigned options):
++        """
++        Apply the substitution to a symbolic expression
++
++        EXAMPLES::
++        
++            sage: from sage.symbolic.substitution_map import make_map
++            sage: subs = make_map({x:x+1})
++            sage: subs.apply_to(x^2, 0)
++            (x + 1)^2
++        """
++        return new_Expression_from_GEx(expr._parent, 
++                                       expr._gobj.subs_map(self._gmapobj, options))
++
++    def _repr_(self):
++        """
++        Return the string representation
++
++        EXAMPLES::
++        
++            sage: from sage.symbolic.substitution_map import make_map
++            sage: make_map({x:x+1})
++            SubsMap
++        """
++        return 'SubsMap'  # GEx_to_str(&x._gobj)
++    
++    def __dealloc__(self):
++        """
++        Delete memory occupied by this substitution map
++
++        EXAMPLES::
++        
++            sage: from sage.symbolic.substitution_map import make_map
++            sage: make_map({x:x+1})
++            SubsMap
++        """
++        GExMap_destruct(&self._gmapobj)
++
++
++cdef SubstitutionMap new_SubstitutionMap_from_GExMap(const GExMap& smap):
++    """
++    Wrap a Pynac object into a Python object
++
++    INPUT:
++
++    - ``smap`` --  a Pynac ``exmap``.
++
++    OUTPUT:
++
++    A new Python :class:`SubstitutionMap`
++
++    EXAMPLES::
++
++        sage: from sage.symbolic.substitution_map import make_map
++        sage: make_map({x:x+1})
++        SubsMap
++    """
++    cdef SubstitutionMap result
++    result = <SubstitutionMap>PY_NEW(SubstitutionMap)
++    GEx_construct_exmap(&result._gmapobj, smap)
++    return result
++