sympy/core/basic.py

   1 """Base class for all objects in sympy"""
   2
   3 import sympy.mpmath as mpmath
   4
   5 from assumptions import AssumeMeths, make__get_assumption
   6 from sympify import _sympify, _sympifyit, sympify, SympifyError
   7 from cache import cacheit, Memoizer, MemoizerArg
   8
   9 # from numbers  import Number, Integer, Rational, Real /cyclic/
  10 # from interval import Interval /cyclic/
  11 # from symbol   import Symbol, Wild, Temporary /cyclic/
  12 # from add      import Add  /cyclic/
  13 # from mul      import Mul  /cyclic/
  14 # from power    import Pow  /cyclic/
  15 # from function import Derivative, FunctionClass   /cyclic/
  16 # from relational import Equality, Unequality, Inequality, StrictInequality /cyclic/
  17 # from sympy.functions.elementary.complexes import abs as abs_   /cyclic/
  18 # from sympy.printing import StrPrinter
  19
  20 # used for canonical ordering of symbolic sequences
  21 # via __cmp__ method:
  22 # FIXME this is *so* irrelevant and outdated!
  23 ordering_of_classes = [
  24     # singleton numbers
  25     'Zero', 'One','Half','Infinity','NaN','NegativeOne','NegativeInfinity',
  26     # numbers
  27     'Integer','Rational','Real',
  28     # singleton symbols
  29     'Exp1','Pi','ImaginaryUnit',
  30     # symbols
  31     'Symbol','Wild','Temporary',
  32     # Functions that should come before Pow/Add/Mul
  33     'ApplyConjugate', 'ApplyAbs',
  34     # arithmetic operations
  35     'Pow', 'Mul', 'Add',
  36     # function values
  37     'Apply',
  38     'ApplyExp','ApplyLog',
  39     'ApplySin','ApplyCos','ApplyTan','ApplyCot',
  40     'ApplyASin','ApplyACos','ApplyATan','ApplyACot',
  41     'ApplySinh','ApplyCosh','ApplyTanh','ApplyCoth',
  42     'ApplyASinh','ApplyACosh','ApplyATanh','ApplyACoth',
  43     'ApplyRisingFactorial','ApplyFallingFactorial',
  44     'ApplyFactorial','ApplyBinomial',
  45     'ApplyFloor', 'ApplyCeiling',
  46     'ApplyRe','ApplyIm', 'ApplyArg',
  47     'ApplySqrt','ApplySign',
  48     'ApplyMrvLog',
  49     'ApplyGamma','ApplyLowerGamma','ApplyUpperGamma','ApplyPolyGamma',
  50     'ApplyErf',
  51     'ApplyChebyshev','ApplyChebyshev2',
  52     'Derivative','Integral',
  53     # defined singleton functions
  54     'Abs','Sign','Sqrt',
  55     'Floor', 'Ceiling',
  56     'Re', 'Im', 'Arg',
  57     'Conjugate',
  58     'Exp','Log','MrvLog',
  59     'Sin','Cos','Tan','Cot','ASin','ACos','ATan','ACot',
  60     'Sinh','Cosh','Tanh','Coth','ASinh','ACosh','ATanh','ACoth',
  61     'RisingFactorial','FallingFactorial',
  62     'Factorial','Binomial',
  63     'Gamma','LowerGamma','UpperGamma','PolyGamma',
  64     'Erf',
  65     # special polynomials
  66     'Chebyshev','Chebyshev2',
  67     # undefined functions
  68     'Function','WildFunction',
  69     # anonymous functions
  70     'Lambda',
  71     # operators
  72     'FDerivative','FApply',
  73     # composition of functions
  74     'FPow', 'Composition',
  75     # Landau O symbol
  76     'Order',
  77     # relational operations
  78     'Equality', 'Unequality', 'StrictInequality', 'Inequality',
  79     ]
  80
  81
  82 class BasicType(type):
  83     pass
  84
  85 class BasicMeta(BasicType):
  86
  87     classnamespace = {}
  88     singleton = {}
  89
  90     def __init__(cls,*args,**kws):
  91         n = cls.__name__
  92         c = BasicMeta.classnamespace.get(n)
  93         if c is None:
  94             BasicMeta.classnamespace[n] = cls
  95         else:
  96             print 'Ignoring redefinition of %s: %s defined earlier than %s' % (n, c, cls)
  97         type.__init__(cls, *args, **kws)
  98
  99         # --- assumptions ---
 100
 101         # initialize default_assumptions dictionary
 102         default_assumptions = {}
 103
 104         for k,v in cls.__dict__.iteritems():
 105             if not k.startswith('is_'):
 106                 continue
 107
 108             # this is not an assumption (e.g. is_Integer)
 109             if k[3:] not in AssumeMeths._assume_defined:
 110                 continue
 111
 112             k = k[3:]
 113             if isinstance(v,(bool,int,long,type(None))):
 114                 if v is not None:
 115                     v = bool(v)
 116                 default_assumptions[k] = v
 117                 #print '  %r <-- %s' % (k,v)
 118
 119
 120         # XXX maybe we should try to keep ._default_premises out of class ?
 121         # XXX __slots__ in class ?
 122         cls._default_premises = default_assumptions
 123
 124         for base in cls.__bases__:
 125             try:
 126                 base_premises = base._default_premises
 127             except AttributeError:
 128                 continue    # no ._default_premises is ok
 129
 130             for k,v in base_premises.iteritems():
 131
 132                 # if an assumption is already present in child, we should ignore base
 133                 # e.g. Integer.is_integer=T, but Rational.is_integer=F (for speed)
 134                 if k in default_assumptions:
 135                     continue
 136
 137                 default_assumptions[k] = v
 138
 139
 140
 141         # deduce all consequences from default assumptions -- make it complete
 142         xass = AssumeMeths._assume_rules.deduce_all_facts(default_assumptions)
 143
 144         # and store completed set into cls -- this way we'll avoid rededucing
 145         # extensions of class default assumptions each time on instance
 146         # creation -- we keep it prededuced already.
 147         cls.default_assumptions = xass
 148
 149         #print '\t(%2i)  %s' % (len(default_assumptions), default_assumptions)
 150         #print '\t(%2i)  %s' % (len(xass), xass)
 151
 152
 153
 154         # let's store new derived assumptions back into class.
 155         # this will result in faster access to this attributes.
 156         #
 157         # Timings
 158         # -------
 159         #
 160         # a = Integer(5)
 161         # %timeit a.is_zero     -> 20 us (without this optimization)
 162         # %timeit a.is_zero     ->  2 us (with    this optimization)
 163         #
 164         #
 165         # BTW: it is very important to study the lessons learned here --
 166         #      we could drop Basic.__getattr__ completely (!)
 167         #
 168         # %timeit x.is_Add      -> 2090 ns  (Basic.__getattr__  present)
 169         # %timeit x.is_Add      ->  825 ns  (Basic.__getattr__  absent)
 170         #
 171         # so we may want to override all assumptions is_<xxx> methods and
 172         # remove Basic.__getattr__
 173
 174
 175         # first we need to collect derived premises
 176         derived_premises = {}
 177
 178         for k,v in xass.iteritems():
 179             if k not in default_assumptions:
 180                 derived_premises[k] = v
 181
 182         cls._derived_premises = derived_premises
 183
 184
 185         for k,v in xass.iteritems():
 186             assert v == cls.__dict__.get('is_'+k, v),  (cls,k,v)
 187             # NOTE: this way Integer.is_even = False (inherited from Rational)
 188             # NOTE: the next code blocks add 'protection-properties' to overcome this
 189             setattr(cls, 'is_'+k, v)
 190
 191         # protection e.g. for Initeger.is_even=F <- (Rational.is_integer=F)
 192         for base in cls.__bases__:
 193             try:
 194                 base_derived_premises = base._derived_premises
 195             except AttributeError:
 196                 continue    # no ._derived_premises is ok
 197
 198             for k,v in base_derived_premises.iteritems():
 199                 if not cls.__dict__.has_key('is_'+k):
 200                     #print '%s -- overriding: %s' % (cls.__name__, k)
 201                     is_k = make__get_assumption(cls.__name__, k)
 202                     setattr(cls, 'is_'+k, property(is_k))
 203
 204
 205
 206     def __cmp__(cls, other):
 207         try:
 208             other = sympify(other)
 209         except ValueError:
 210             #if we cannot sympify it, other is definitely not equal to cls
 211             return -1
 212         n1 = cls.__name__
 213         n2 = other.__name__
 214         c = cmp(n1,n2)
 215         if not c: return 0
 216
 217         UNKNOWN = len(ordering_of_classes)+1
 218         try:
 219             i1 = ordering_of_classes.index(n1)
 220         except ValueError:
 221             #print 'Add',n1,'to basic.ordering_of_classes list'
 222             #return c
 223             i1 = UNKNOWN
 224         try:
 225             i2 = ordering_of_classes.index(n2)
 226         except ValueError:
 227             #print 'Add',n2,'to basic.ordering_of_classes list'
 228             #return c
 229             i2 = UNKNOWN
 230         if i1 == UNKNOWN and i2 == UNKNOWN:
 231             return c
 232         return cmp(i1,i2)
 233
 234
 235
 236 class Basic(AssumeMeths):
 237     """
 238     Base class for all objects in sympy.
 239
 240     Conventions:
 241
 242     1)
 243     When you want to access parameters of some instance, always use .args:
 244     Example:
 245
 246     >>> from sympy import symbols, cot
 247     >>> x, y = symbols('xy')
 248
 249     >>> cot(x).args
 250     (x,)
 251
 252     >>> cot(x).args[0]
 253     x
 254
 255     >>> (x*y).args
 256     (x, y)
 257
 258     >>> (x*y).args[1]
 259     y
 260
 261
 262     2) Never use internal methods or variables (the ones prefixed with "_").
 263     Example:
 264
 265     >>> cot(x)._args    #don't use this, use cot(x).args instead
 266     (x,)
 267
 268
 269     """
 270
 271     __metaclass__ = BasicMeta
 272
 273     __slots__ = ['_mhash',              # hash value
 274                  '_args',               # arguments
 275                  '_assume_type_keys',   # assumptions typeinfo keys
 276                 ]
 277
 278     # To be overridden with True in the appropriate subclasses
 279     is_Atom = False
 280     is_Symbol = False
 281     is_Function = False
 282     is_Add = False
 283     is_Mul = False
 284     is_Pow = False
 285     is_Number = False
 286     is_Real = False
 287     is_Rational = False
 288     is_Integer = False
 289     is_NumberSymbol = False
 290     is_Order = False
 291
 292     def __new__(cls, *args, **assumptions):
 293         obj = object.__new__(cls)
 294
 295         # FIXME we are slowed a *lot* by Add/Mul passing is_commutative as the
 296         # only assumption.
 297         #
 298         # .is_commutative is not an assumption -- it's like typeinfo!!!
 299         # we should remove it.
 300
 301         # initially assumptions are shared between instances and class
 302         obj._assumptions  = cls.default_assumptions
 303         obj._a_inprogress = []
 304
 305         # NOTE this could be made lazy -- probably not all instances will need
 306         # fully derived assumptions?
 307         if assumptions:
 308             obj._learn_new_facts(assumptions)
 309             #                      ^
 310             # FIXME this is slow   |    another NOTE: speeding this up is *not*
 311             #        |             |    important. say for %timeit x+y most of
 312             # .------'             |    the time is spent elsewhere
 313             # |                    |
 314             # |  XXX _learn_new_facts  could be asked about what *new* facts have
 315             # v  XXX been learned -- we'll need this to append to _hashable_content
 316             basek = set(cls.default_assumptions.keys())
 317             k2    = set(obj._assumptions.keys())
 318             newk  = k2.difference(basek)
 319
 320             obj._assume_type_keys = frozenset(newk)
 321         else:
 322             obj._assume_type_keys = None
 323
 324         obj._mhash = None # will be set by __hash__ method.
 325         obj._args = args  # all items in args must be Basic objects
 326         return obj
 327
 328
 329     # XXX better name?
 330     @property
 331     def assumptions0(self):
 332         """return object `type` assumptions
 333
 334            For example:
 335
 336              Symbol('x', real=True)
 337              Symbol('x', integer=True)
 338
 339           are different objects, and besides Python type (Symbol), initial
 340           assumptions, are too forming their typeinfo.
 341         """
 342
 343         cls = type(self)
 344         A   = self._assumptions
 345
 346         # assumptions shared:
 347         if A is cls.default_assumptions or (self._assume_type_keys is None):
 348             assumptions0 = {}
 349         else:
 350             assumptions0 = dict( (k, A[k]) for k in self._assume_type_keys )
 351
 352         return assumptions0
 353
 354
 355     def new(self, *args):
 356         """create new 'similar' object
 357
 358            this is conceptually equivalent to:
 359
 360              type(self) (*args)
 361
 362            but takes type assumptions into account.
 363
 364            see: assumptions0
 365         """
 366         obj = type(self) (*args, **self.assumptions0)
 367         return obj
 368
 369
 370     # NOTE NOTE NOTE
 371     # --------------
 372     #
 373     # new-style classes + __getattr__ is *very* slow!
 374
 375     # def __getattr__(self, name):
 376     #     raise 'no way, *all* attribute access will be 2.5x slower'
 377
 378     # here is what we do instead:
 379     for k in AssumeMeths._assume_defined:
 380         exec "is_%s  = property(make__get_assumption('Basic', '%s'))" % (k,k)
 381
 382
 383     # NB: there is no need in protective __setattr__
 384
 385
 386
 387     def __hash__(self):
 388         # hash cannot be cached using cache_it because infinite recurrence
 389         # occurs as hash is needed for setting cache dictionary keys
 390         h = self._mhash
 391         if h is None:
 392             h = (type(self).__name__,) + self._hashable_content()
 393
 394             if self._assume_type_keys is not None:
 395                 a = []
 396                 kv= self._assumptions
 397                 for k in sorted(self._assume_type_keys):
 398                     a.append( (k, kv[k]) )
 399
 400                 h = hash( h + tuple(a) )
 401
 402             else:
 403                 h = hash( h )
 404
 405
 406             self._mhash = h
 407             return h
 408
 409         else:
 410             return h
 411
 412     def _hashable_content(self):
 413         # If class defines additional attributes, like name in Symbol,
 414         # then this method should be updated accordingly to return
 415         # relevant attributes as tuple.
 416         return self._args
 417
 418     def __nonzero__(self):
 419         """Tests if 'self' is an instance of Zero class.
 420
 421            This should be understand as an idiom:
 422
 423                [1] bool(x) <=> bool(x is not S.Zero)
 424
 425                [2] bool(not x) <=> bool(x is S.Zero)
 426
 427            Allowing definition of __nonzero__ method is important in
 428            algorithms where uniform handling of int, long values and
 429            and sympy expressions is required.
 430
 431            >>> from sympy import *
 432            >>> x,y = symbols('xy')
 433
 434            >>> bool(0)
 435            False
 436            >>> bool(1)
 437            True
 438
 439            >>> bool(S.Zero)
 440            False
 441            >>> bool(S.One)
 442            True
 443
 444            >>> bool(x*y)
 445            True
 446            >>> bool(x + y)
 447            True
 448
 449         """
 450         return self is not S.Zero
 451
 452     def compare(self, other):
 453         """
 454         Return -1,0,1 if the object is smaller, equal, or greater than other
 455         (not always in mathematical sense).
 456         If the object is of different type from other then their classes
 457         are ordered according to sorted_classes list.
 458         """
 459         # all redefinitions of __cmp__ method should start with the
 460         # following three lines:
 461         if self is other: return 0
 462         c = cmp(self.__class__, other.__class__)
 463         if c: return c
 464         #
 465         st = self._hashable_content()
 466         ot = other._hashable_content()
 467         c = cmp(len(st),len(ot))
 468         if c: return c
 469         for l,r in zip(st,ot):
 470             if isinstance(l, Basic):
 471                 c = l.compare(r)
 472             else:
 473                 c = cmp(l, r)
 474             if c: return c
 475         return 0
 476
 477     @staticmethod
 478     def _compare_pretty(a, b):
 479         from sympy.series.order import Order
 480         if isinstance(a, Order) and not isinstance(b, Order):
 481             return 1
 482         if not isinstance(a, Order) and isinstance(b, Order):
 483             return -1
 484
 485         # FIXME this produces wrong ordering for 1 and 0
 486         # e.g. the ordering will be 1 0 2 3 4 ...
 487         # because 1 = x^0, but 0 2 3 4 ... = x^1
 488         p1, p2, p3 = Wild("p1"), Wild("p2"), Wild("p3")
 489         r_a = a.match(p1 * p2**p3)
 490         r_b = b.match(p1 * p2**p3)
 491         if r_a is not None and r_b is not None:
 492             c = Basic.compare(r_a[p3], r_b[p3])
 493             if c!=0:
 494                 return c
 495
 496         return Basic.compare(a,b)
 497
 498     @staticmethod
 499     def compare_pretty(a, b):
 500         """
 501         Is a>b in the sense of ordering in printing?
 502
 503         yes ..... return 1
 504         no ...... return -1
 505         equal ... return 0
 506
 507         Strategy:
 508
 509         It uses Basic.compare as a fallback, but improves it in many cases,
 510         like x**3, x**4, O(x**3) etc. In those simple cases, it just parses the
 511         expression and returns the "sane" ordering such as:
 512
 513         1 < x < x**2 < x**3 < O(x**4) etc.
 514
 515         """
 516         try:
 517             a = _sympify(a)
 518         except SympifyError:
 519             pass
 520
 521         try:
 522             b = _sympify(b)
 523         except SympifyError:
 524             pass
 525
 526         # both objects are non-SymPy
 527         if (not isinstance(a, Basic)) and (not isinstance(b, Basic)):
 528             return cmp(a,b)
 529
 530         if not isinstance(a, Basic):
 531             return -1   # other < sympy
 532
 533         if not isinstance(b, Basic):
 534             return +1   # sympy > other
 535
 536         # now both objects are from SymPy, so we can proceed to usual comparison
 537         return Basic._compare_pretty(a, b)
 538
 539
 540     def __eq__(self, other):
 541         """a == b  -> Compare two symbolic trees and see whether they are equal
 542
 543            this is the same as:
 544
 545              a.compare(b) == 0
 546
 547            but faster
 548         """
 549
 550         if type(self) is not type(other):
 551             try:
 552                 other = _sympify(other)
 553             except SympifyError:
 554                 return False    # sympy != other
 555
 556             if type(self) is not type(other):
 557                 return False
 558
 559         # type(self) == type(other)
 560         st = self._hashable_content()
 561         ot = other._hashable_content()
 562
 563         return (st == ot)
 564
 565     def __ne__(self, other):
 566         """a != b  -> Compare two symbolic trees and see whether they are different
 567
 568            this is the same as:
 569
 570              a.compare(b) != 0
 571
 572            but faster
 573         """
 574
 575         if type(self) is not type(other):
 576             try:
 577                 other = _sympify(other)
 578             except SympifyError:
 579                 return True     # sympy != other
 580
 581             if type(self) is not type(other):
 582                 return True
 583
 584         # type(self) == type(other)
 585         st = self._hashable_content()
 586         ot = other._hashable_content()
 587
 588         return (st != ot)
 589
 590     # TODO all comparison methods should return True/False directly (?)
 591     # see #153
 592     #
 593     # OTOH Py3k says
 594     #
 595     #    Comparisons other than == and != between disparate types will raise an
 596     #    exception unless explicitly supported by the type
 597     #
 598     # references:
 599     #
 600     # http://www.python.org/dev/peps/pep-0207/
 601     # http://www.python.org/dev/peps/pep-3100/#id18
 602     # http://mail.python.org/pipermail/python-dev/2004-June/045111.html
 603
 604     @_sympifyit('other', False) # sympy >  other
 605     def __lt__(self, other):
 606         #return sympify(other) > self
 607         return StrictInequality(self, other)
 608
 609     @_sympifyit('other', True)  # sympy >  other
 610     def __gt__(self, other):
 611         return StrictInequality(other, self)
 612         #return sympify(other) < self
 613
 614     @_sympifyit('other', False) # sympy >  other
 615     def __le__(self, other):
 616         return Inequality(self, other)
 617
 618     @_sympifyit('other', True)  # sympy >  other
 619     def __ge__(self, other):
 620         return sympify(other) <= self
 621
 622
 623     # ***************
 624     # * Arithmetics *
 625     # ***************
 626
 627     def __pos__(self):
 628         return self
 629     def __neg__(self):
 630         return Mul(S.NegativeOne, self)
 631     def __abs__(self):
 632         return abs_(self)
 633
 634     @_sympifyit('other', NotImplemented)
 635     def __add__(self, other):
 636         return Add(self, other)
 637     @_sympifyit('other', NotImplemented)
 638     def __radd__(self, other):
 639         return Add(other, self)
 640
 641     @_sympifyit('other', NotImplemented)
 642     def __sub__(self, other):
 643         return Add(self, -other)
 644     @_sympifyit('other', NotImplemented)
 645     def __rsub__(self, other):
 646         return Add(other, -self)
 647
 648     @_sympifyit('other', NotImplemented)
 649     def __mul__(self, other):
 650         return Mul(self, other)
 651     @_sympifyit('other', NotImplemented)
 652     def __rmul__(self, other):
 653         return Mul(other, self)
 654
 655     @_sympifyit('other', NotImplemented)
 656     def __pow__(self, other):
 657         return Pow(self, other)
 658     @_sympifyit('other', NotImplemented)
 659     def __rpow__(self, other):
 660         return Pow(other, self)
 661
 662     @_sympifyit('other', NotImplemented)
 663     def __div__(self, other):
 664         return Mul(self, Pow(other, S.NegativeOne))
 665     @_sympifyit('other', NotImplemented)
 666     def __rdiv__(self, other):
 667         return Mul(other, Pow(self, S.NegativeOne))
 668
 669     __truediv__ = __div__
 670     __rtruediv__ = __rdiv__
 671
 672
 673
 674
 675
 676     def __repr__(self):
 677         return StrPrinter.doprint(self)
 678
 679     def __str__(self):
 680         return StrPrinter.doprint(self)
 681
 682     def atoms(self, *types):
 683         """Returns the atoms that form the current object.
 684
 685            >>> from sympy import *
 686            >>> x,y = symbols('xy')
 687
 688            >>> sorted((x+y**2 + 2*x*y).atoms())
 689            [2, x, y]
 690
 691            You can also filter the results by a given type(s) of object:
 692
 693            >>> sorted((x+y+2+y**2*sin(x)).atoms(Symbol))
 694            [x, y]
 695
 696            >>> sorted((x+y+2+y**3*sin(x)).atoms(Number))
 697            [2, 3]
 698
 699            >>> sorted((x+y+2+y**2*sin(x)).atoms(Symbol, Number))
 700            [2, x, y]
 701
 702            Or by a type of on object in an impliciy way:
 703
 704            >>> sorted((x+y+2+y**2*sin(x)).atoms(x))
 705            [x, y]
 706
 707         """
 708         if len(types) == 1 and not isinstance(types[0], type):
 709             types = (sympify(types[0]).__class__,)
 710
 711         result = set([])
 712
 713         if self.is_Atom:
 714             if not types or isinstance(self, types):
 715                 result.add(self)
 716         else:
 717             for obj in self.iter_basic_args():
 718                 result |= obj.atoms(*types)
 719
 720         return result
 721
 722     def is_hypergeometric(self, k):
 723         from sympy.simplify import hypersimp
 724         return hypersimp(self, k) is not None
 725
 726     @property
 727     def is_number(self):
 728         """Returns True if 'self' is a number.
 729
 730            >>> from sympy import *
 731            >>> x,y = symbols('xy')
 732
 733            >>> x.is_number
 734            False
 735            >>> (2*x).is_number
 736            False
 737            >>> (2 + log(2)).is_number
 738            True
 739
 740         """
 741         for obj in self.iter_basic_args():
 742             if not obj.is_number:
 743                 return False
 744         else:
 745             return True
 746
 747     @property
 748     def func(self):
 749         """
 750         The top-level function in an expression.
 751
 752         The following should hold for all objects::
 753
 754             >> x == x.func(*x.args)
 755
 756         """
 757         return self.__class__
 758
 759     @property
 760     def args(self):
 761         """Returns a tuple of arguments of 'self'.
 762
 763         Example:
 764
 765         >>> from sympy import symbols, cot
 766         >>> x, y = symbols('xy')
 767
 768         >>> cot(x).args
 769         (x,)
 770
 771         >>> cot(x).args[0]
 772         x
 773
 774         >>> (x*y).args
 775         (x, y)
 776
 777         >>> (x*y).args[1]
 778         y
 779
 780         Note for developers: Never use self._args, always use self.args.
 781         Only when you are creating your own new function, use _args
 782         in the __new__. Don't override .args() from Basic (so that it's
 783         easy to change the interface in the future if needed).
 784         """
 785         return self._args[:]
 786
 787     def iter_basic_args(self):
 788         """Iterates arguments of 'self' with are Basic instances. """
 789         return iter(self.args)
 790
 791     def is_fraction(self, *syms):
 792         p, q = self.as_numer_denom()
 793
 794         if p.is_polynomial(*syms):
 795             if q.is_polynomial(*syms):
 796                 return True
 797
 798         return False
 799
 800     def _eval_is_polynomial(self, syms):
 801         return
 802
 803     def is_polynomial(self, *syms):
 804         if syms:
 805             syms = map(sympify, syms)
 806         else:
 807             syms = list(self.atoms(Symbol))
 808
 809         if not syms: # constant polynomial
 810             return True
 811         else:
 812             return self._eval_is_polynomial(syms)
 813
 814     def as_poly(self, *symbols, **flags):
 815         """Converts 'self' to a polynomial or returns None.
 816
 817            When constructing a polynomial an exception will be raised in
 818            case the input expression is not convertible to a polynomial.
 819            There are situations when it is easier (simpler or prettier)
 820            to receive None on failure.
 821
 822            If no symbols were given and 'self' isn't already a polynomial
 823            then all  available symbols will be collected and used to form
 824            a new polynomial.
 825
 826            >>> from sympy import *
 827            >>> x,y = symbols('xy')
 828
 829            >>> print (x**2 + x*y).as_poly()
 830            Poly(x**2 + x*y, x, y)
 831
 832            >>> print (x**2 + x*y).as_poly(x, y)
 833            Poly(x**2 + x*y, x, y)
 834
 835            >>> print (x**2 + sin(y)).as_poly(x, y)
 836            None
 837
 838         """
 839         from sympy.polys import Poly, PolynomialError
 840
 841         try:
 842             if not symbols:
 843                 if isinstance(self, Poly):
 844                     return self
 845                 else:
 846                     symbols = sorted(self.atoms(Symbol))
 847
 848             return Poly(self, *symbols, **flags)
 849         except PolynomialError:
 850             return None
 851
 852     def as_basic(self):
 853         """Converts polynomial to a valid sympy expression.
 854
 855            >>> from sympy import *
 856            >>> x,y = symbols('xy')
 857
 858            >>> p = (x**2 + x*y).as_poly(x, y)
 859
 860            >>> p.as_basic()
 861            x*y + x**2
 862
 863            >>> f = sin(x)
 864
 865            >>> f.as_basic()
 866            sin(x)
 867
 868         """
 869         return self
 870
 871     def subs(self, *args):
 872         """
 873         Substitutes an expression.
 874
 875         Calls either _subs_old_new, _subs_dict or _subs_list depending
 876         if you give it two arguments (old, new), a dictionary or a list.
 877
 878         Examples:
 879
 880         >>> from sympy import *
 881         >>> x,y = symbols('xy')
 882         >>> (1+x*y).subs(x, pi)
 883         1 + pi*y
 884         >>> (1+x*y).subs({x:pi, y:2})
 885         1 + 2*pi
 886         >>> (1+x*y).subs([(x,pi), (y,2)])
 887         1 + 2*pi
 888
 889         """
 890         if len(args) == 1:
 891             sequence = args[0]
 892             if isinstance(sequence, dict):
 893                 return self._subs_dict(sequence)
 894             elif isinstance(sequence, (list, tuple)):
 895                 return self._subs_list(sequence)
 896             else:
 897                 raise TypeError("Not an iterable container")
 898         elif len(args) == 2:
 899             old, new = args
 900             return self._subs_old_new(old, new)
 901         else:
 902             raise Exception("subs accept either 1 or 2 arguments")
 903
 904     @cacheit
 905     def _subs_old_new(self, old, new):
 906         """Substitutes an expression old -> new."""
 907         old = sympify(old)
 908         new = sympify(new)
 909         return self._eval_subs(old, new)
 910
 911     def _eval_subs(self, old, new):
 912         if self==old:
 913             return new
 914         return self
 915
 916     def _subs_list(self, sequence):
 917         """
 918         Performs an order sensitive substitution from the
 919         input sequence list.
 920
 921         Examples:
 922
 923         >>> from sympy import *
 924         >>> x, y = symbols('xy')
 925         >>> (x+y)._subs_list( [(x, 3),     (y, x**2)] )
 926         3 + x**2
 927         >>> (x+y)._subs_list( [(y, x**2),  (x, 3)   ] )
 928         12
 929
 930         """
 931         if not isinstance(sequence, (list, tuple)):
 932             raise TypeError("Not an iterable container")
 933         result = self
 934         for old, new in sequence:
 935             result = result.subs(old, new)
 936         return result
 937
 938     def _subs_dict(self, sequence):
 939         """Performs sequential substitution.
 940
 941            Given a collection of key, value pairs, which correspond to
 942            old and new expressions respectively,  substitute all given
 943            pairs handling properly all overlapping keys  (according to
 944            'in' relation).
 945
 946            We have to use naive O(n**2) sorting algorithm, as 'in'
 947            gives only partial order and all asymptotically faster
 948            fail (depending on the initial order).
 949
 950            >>> from sympy import *
 951            >>> x, y = symbols('xy')
 952
 953            >>> a,b,c,d,e = symbols('abcde')
 954
 955            >>> A = (sqrt(sin(2*x)), a)
 956            >>> B = (sin(2*x), b)
 957            >>> C = (cos(2*x), c)
 958            >>> D = (x, d)
 959            >>> E = (exp(x), e)
 960
 961            >>> expr = sqrt(sin(2*x))*sin(exp(x)*x)*cos(2*x) + sin(2*x)
 962
 963            >>> expr._subs_dict([A,B,C,D,E])
 964            b + a*c*sin(d*e)
 965
 966         """
 967         if isinstance(sequence, dict):
 968             sequence = sequence.items()
 969         elif not isinstance(sequence, (list, tuple)):
 970             raise TypeError("Not an iterable container")
 971
 972         subst = []
 973
 974         for pattern in sequence:
 975             for i, (expr, _) in enumerate(subst):
 976                 if pattern[0] in expr:
 977                     subst.insert(i, pattern)
 978                     break
 979             else:
 980                 subst.append(pattern)
 981         subst.reverse()
 982         return self._subs_list(subst)
 983
 984     def _seq_subs(self, old, new):
 985         if self==old:
 986             return new
 987         #new functions are initialized differently, than old functions
 988         if isinstance(self.func, FunctionClass):
 989             args = self.args[:]
 990         else:
 991             args = (self.func,)+self[:]
 992         return self.__class__(*[s.subs(old, new) for s in args])
 993
 994     def __contains__(self, what):
 995         if self == what: return True
 996         for x in self._args:
 997             if what in x:
 998                 return True
 999         return False
1000
1001     @cacheit
1002     def has_any_symbols(self, *syms):
1003         """Return True if 'self' has any of the symbols.
1004
1005            >>> from sympy import *
1006            >>> x,y,z = symbols('xyz')
1007
1008            >>> (x**2 + sin(x*y)).has_any_symbols(z)
1009            False
1010
1011            >>> (x**2 + sin(x*y)).has_any_symbols(x, y)
1012            True
1013
1014            >>> (x**2 + sin(x*y)).has_any_symbols(x, y, z)
1015            True
1016
1017         """
1018         syms = set(syms)
1019
1020         if not syms:
1021             return True
1022         else:
1023             def search(expr):
1024                 if expr.is_Atom:
1025                     if expr.is_Symbol:
1026                         return expr in syms
1027                     else:
1028                         return False
1029                 else:
1030                     for term in expr.iter_basic_args():
1031                         if search(term):
1032                             return True
1033                     else:
1034                         return False
1035
1036             return search(self)
1037
1038     @cacheit
1039     def has_all_symbols(self, *syms):
1040         """Return True if 'self' has all of the symbols.
1041
1042            >>> from sympy import *
1043            >>> x,y,z = symbols('xyz')
1044
1045            >>> (x**2 + sin(x*y)).has_all_symbols(x, y)
1046            True
1047
1048            >>> (x**2 + sin(x*y)).has_all_symbols(x, y, z)
1049            False
1050
1051         """
1052         syms = set(syms)
1053
1054         if not syms:
1055             return True
1056         else:
1057             def search(expr):
1058                 if expr.is_Atom:
1059                     if expr.is_Symbol and expr in syms:
1060                         syms.remove(expr)
1061                 else:
1062                     for term in expr.iter_basic_args():
1063                         if not syms:
1064                             break
1065                         else:
1066                             search(term)
1067
1068             search(self)
1069
1070             return not syms
1071
1072     def has(self, *patterns):
1073         """
1074         Return True if self has any of the patterns.
1075         """
1076         if len(patterns)>1:
1077             for p in patterns:
1078                 if self.has(p):
1079                     return True
1080             return False
1081         elif not patterns:
1082             raise TypeError("has() requires at least 1 argument (got none)")
1083         p = sympify(patterns[0])
1084         if p.is_Symbol and not isinstance(p, Wild): # speeds up
1085             return p in self.atoms(p.__class__)
1086         if isinstance(p, BasicType):
1087             #XXX this is very fragile:
1088             if str(self).find(str(p.__name__)) == -1:
1089                 #didn't find p in self, let's try corner cases
1090                 if p is Derivative:
1091                     if str(self).find("D(") != -1:
1092                         return True
1093                 return False
1094             else:
1095                 return True
1096         if p.matches(self) is not None:
1097             return True
1098         if not False:
1099             args = self.args[:]
1100         else:
1101             args = (self.func,)+self.args[:]
1102         for e in args:
1103             if e.has(p):
1104                 return True
1105         return False
1106
1107     def _eval_power(self, other):
1108         return None
1109
1110     def _eval_derivative(self, s):
1111         return
1112
1113     def _eval_fapply(self, *args, **assumptions):
1114         return
1115
1116     def _eval_fpower(b, e):
1117         return
1118
1119     def _eval_apply_evalf(self,*args):
1120         return
1121
1122     def _eval_eq_nonzero(self, other):
1123         return
1124
1125     @classmethod
1126     def _eval_apply_subs(cls, *args):
1127         return
1128
1129     def _eval_conjugate(self):
1130         if self.is_real:
1131             return self
1132
1133     def conjugate(self):
1134         from sympy.functions.elementary.complexes import conjugate as c
1135         return c(self)
1136
1137     def removeO(self):
1138         "Removes the O(..) symbol if there is one"
1139         if self.is_Order:
1140             return Integer(0)
1141         for i,x in enumerate(self.args):
1142             if x.is_Order:
1143                 return Add(*(self.args[:i]+self.args[i+1:]))
1144         return self
1145
1146     #@classmethod
1147     def matches(pattern, expr, repl_dict={}, evaluate=False):
1148         """
1149         Helper method for match() - switches the pattern and expr.
1150
1151         Can be used to solve linear equations:
1152           >>> from sympy import Symbol, Wild, Integer
1153           >>> a,b = map(Symbol, 'ab')
1154           >>> x = Wild('x')
1155           >>> (a+b*x).matches(Integer(0))
1156           {x_: -a/b}
1157
1158         """
1159
1160         # weed out negative one prefixes
1161         sign = 1
1162         if pattern.is_Mul and pattern.args[0] == -1:
1163           pattern = -pattern; sign = -sign
1164         if expr.is_Mul and expr.args[0] == -1:
1165           expr = -expr; sign = -sign
1166
1167         if evaluate:
1168             pat = pattern
1169             for old,new in repl_dict.items():
1170                 pat = pat.subs(old, new)
1171             if pat!=pattern:
1172                 return pat.matches(expr, repl_dict)
1173         expr = sympify(expr)
1174         if not isinstance(expr, pattern.__class__):
1175             # if we can omit the first factor, we can match it to sign * one
1176             if pattern.is_Mul and Mul(*pattern.args[1:]) == expr:
1177                return pattern.args[0].matches(Rational(sign), repl_dict, evaluate)
1178             # two-factor product: if the 2nd factor matches, the first part must be sign * one
1179             if pattern.is_Mul and len(pattern.args[:]) == 2:
1180                dd = pattern.args[1].matches(expr, repl_dict, evaluate)
1181                if dd == None: return None
1182                dd = pattern.args[0].matches(Rational(sign), dd, evaluate)
1183                return dd
1184             return None
1185
1186         if len(pattern.args[:])==0:
1187             if pattern==expr:
1188                 return repl_dict
1189             return None
1190         d = repl_dict.copy()
1191
1192         # weed out identical terms
1193         pp = list(pattern.args)
1194         ee = list(expr.args)
1195         for p in pattern.args:
1196           for e in expr.args:
1197             if e == p:
1198               if e in ee: ee.remove(e)
1199               if p in pp: pp.remove(p)
1200
1201         # only one symbol left in pattern -> match the remaining expression
1202         if len(pp) == 1 and isinstance(pp[0], Wild):
1203           if len(ee) == 1: d[pp[0]] = sign * ee[0]
1204           else: d[pp[0]] = sign * (type(expr)(*ee))
1205           return d
1206
1207         if len(ee) != len(pp):
1208             return None
1209
1210         i = 0
1211         for p,e in zip(pp, ee):
1212             if i == 0 and sign != 1:
1213               try: e = sign * e
1214               except TypeError: return None
1215             d = p.matches(e, d, evaluate=not i)
1216             i += 1
1217             if d is None:
1218                 return None
1219         return d
1220
1221     def match(self, pattern):
1222         """
1223         Pattern matching.
1224
1225         Wild symbols match all.
1226
1227         Return None when expression (self) does not match
1228         with pattern. Otherwise return a dictionary such that
1229
1230           pattern.subs(self.match(pattern)) == self
1231
1232         """
1233         pattern = sympify(pattern)
1234         return pattern.matches(self, {})
1235
1236     def solve4linearsymbol(eqn, rhs, symbols = None):
1237         """
1238         Solve equation "eqn == rhs" with respect to some linear symbol in eqn.
1239
1240         Returns (symbol, solution). If eqn is nonlinear with respect to all
1241         symbols, then return trivial solution (eqn, rhs).
1242         """
1243         if eqn.is_Symbol:
1244             return (eqn, rhs)
1245         if symbols is None:
1246             symbols = eqn.atoms(Symbol)
1247         if symbols:
1248             # find  symbol
1249             for s in symbols:
1250                 deqn = eqn.diff(s)
1251                 if deqn.diff(s) is S.Zero:
1252                     # eqn = a + b*c, a=eqn(c=0),b=deqn(c=0)
1253                     return s, (rhs - eqn.subs(s,0))/deqn.subs(s,0)
1254         # no linear symbol, return trivial solution
1255         return eqn, rhs
1256
1257     @cacheit
1258     def count_ops(self, symbolic=True):
1259         """ Return the number of operations in expressions.
1260
1261         Examples:
1262         >>> (1+a+b**2).count_ops()
1263         POW + 2 * ADD
1264         >>> (sin(x)*x+sin(x)**2).count_ops()
1265         ADD + MUL + POW + 2 * SIN
1266         """
1267         return Integer(len(self[:])-1) + sum([t.count_ops(symbolic=symbolic) for t in self])
1268
1269     def doit(self, **hints):
1270         """Evaluate objects that are not evaluated by default like limits,
1271            integrals, sums and products. All objects of this kind will be
1272            evaluated unless some species were excluded via 'hints'.
1273
1274            >>> from sympy import *
1275            >>> x, y = symbols('xy')
1276
1277            >>> 2*Integral(x, x)
1278            2*Integral(x, x)
1279
1280            >>> (2*Integral(x, x)).doit()
1281            x**2
1282
1283         """
1284         terms = [ term.doit(**hints) for term in self.args ]
1285         return self.new(*terms)
1286
1287     ###########################################################################
1288     ################# EXPRESSION REPRESENTATION METHODS #######################
1289     ###########################################################################
1290
1291     def _eval_expand_basic(self):
1292         terms, rewrite = [], False
1293
1294         for term in self.args:
1295             if not isinstance(term, Basic) or \
1296                    isinstance(term, Atom):
1297                 terms.append(term)
1298             else:
1299                 T = term._eval_expand_basic()
1300
1301                 if T is None:
1302                     terms.append(term)
1303                 else:
1304                     terms.append(T)
1305                     rewrite = True
1306
1307         if rewrite:
1308             return self.new(*terms)
1309         else:
1310             return None
1311
1312     def _eval_expand_power(self, *args):
1313         if self.is_Atom:
1314             return self
1315         if not isinstance(self, C.Apply):   # FIXME Apply -> Function
1316             sargs = self[:]
1317         else:
1318             sargs = (self.func,)+self[:]
1319         terms = [ term._eval_expand_power(*args) for term in sargs ]
1320         return self.new(*terms)
1321
1322     def _eval_expand_complex(self, *args):
1323         if self.is_Atom:
1324             return self
1325         sargs = self.args[:]
1326         terms = [ term._eval_expand_complex(*args) for term in sargs ]
1327         return self.new(*terms)
1328
1329     def _eval_expand_trig(self, *args):
1330         if self.is_Atom:
1331             return self
1332         sargs = self.args[:]
1333         terms = [ term._eval_expand_trig(*args) for term in sargs ]
1334         return self.new(*terms)
1335
1336     def _eval_expand_func(self, *args):
1337         if self.is_Atom:
1338             return self
1339         sargs = self.args
1340         terms = [ term._eval_expand_func(*args) for term in sargs ]
1341         return self.new(*terms)
1342
1343     def expand(self, **hints):
1344         """Expand an expression using hints.
1345
1346            Currently supported hints are basic, power, complex, trig
1347            and func.  Hints are applied with arbitrary order so your
1348            code shouldn't depend on the way hints are passed to this
1349            method. Expand 'basic' is the default and run always,
1350            provided that it isn't turned off by the user.
1351
1352            >>> from sympy import *
1353            >>> x,y = symbols('xy')
1354
1355            >>> (y*(x + y)**2).expand()
1356            y*x**2 + 2*x*y**2 + y**3
1357
1358            >>> (x+y).expand(complex=True)
1359            I*im(x) + I*im(y) + re(x) + re(y)
1360
1361         """
1362         expr = self
1363
1364         for hint in hints:
1365             if hints[hint] == True:
1366                 func = getattr(expr, '_eval_expand_'+hint, None)
1367
1368                 if func is not None:
1369                     expr = func()
1370
1371         if not hints.has_key('basic'):
1372             if not expr.is_Atom:
1373                 result = expr._eval_expand_basic()
1374
1375                 if result is not None:
1376                     expr = result
1377
1378         return expr
1379
1380     def _eval_rewrite(self, pattern, rule, **hints):
1381         if self.is_Atom:
1382             return self
1383         sargs = self.args
1384         terms = [ t._eval_rewrite(pattern, rule, **hints) for t in sargs ]
1385         return self.new(*terms)
1386
1387     def rewrite(self, *args, **hints):
1388         """Rewrites expression containing applications of functions
1389            of one kind in terms of functions of different kind. For
1390            example you can rewrite trigonometric functions as complex
1391            exponentials or combinatorial functions as gamma function.
1392
1393            As a pattern this function accepts a list of functions to
1394            to rewrite (instances of DefinedFunction class). As rule
1395            you can use string or a destination function instance (in
1396            this case rewrite() will use the str() function).
1397
1398            There is also possibility to pass hints on how to rewrite
1399            the given expressions. For now there is only one such hint
1400            defined called 'deep'. When 'deep' is set to False it will
1401            forbid functions to rewrite their contents.
1402
1403            >>> from sympy import *
1404            >>> x, y = symbols('xy')
1405
1406            >>> sin(x).rewrite(sin, exp)
1407            -I*(exp(I*x) - exp(-I*x))/2
1408
1409         """
1410         if self.is_Atom or not args:
1411             return self
1412         else:
1413             pattern, rule = args[:-1], args[-1]
1414
1415             if not isinstance(rule, str):
1416
1417                 if rule == C.tan:
1418                     rule = "tan"
1419                 elif rule == C.exp:
1420                     rule = "exp"
1421                 elif isinstance(rule, FunctionClass):   # new-style functions
1422                     #print rule
1423                     rule = rule.__name__  # XXX proper attribute for name?
1424                     #print rule
1425                 else:
1426                     rule = str(rule)
1427
1428             rule = '_eval_rewrite_as_' + rule
1429
1430             if not pattern:
1431                 return self._eval_rewrite(None, rule, **hints)
1432             else:
1433                 if isinstance(pattern[0], (tuple, list)):
1434                     pattern = pattern[0]
1435
1436                 pattern = [ p.__class__ for p in pattern if self.has(p) ]
1437
1438                 if pattern:
1439                     return self._eval_rewrite(tuple(pattern), rule, **hints)
1440                 else:
1441                     return self
1442
1443     def as_coefficient(self, expr):
1444         """Extracts symbolic coefficient at the given expression. In
1445            other words, this functions separates 'self' into product
1446            of 'expr' and 'expr'-free coefficient. If such separation
1447            is not possible it will return None.
1448
1449            >>> from sympy import *
1450            >>> x, y = symbols('xy')
1451
1452            >>> E.as_coefficient(E)
1453            1
1454            >>> (2*E).as_coefficient(E)
1455            2
1456
1457            >>> (2*E + x).as_coefficient(E)
1458            >>> (2*sin(E)*E).as_coefficient(E)
1459
1460            >>> (2*pi*I).as_coefficient(pi*I)
1461            2
1462
1463            >>> (2*I).as_coefficient(pi*I)
1464
1465         """
1466         if expr.is_Add:
1467             return None
1468         else:
1469             w = Wild('w')
1470
1471             coeff = self.match(w * expr)
1472
1473             if coeff is not None:
1474                 if expr.is_Mul:
1475                     expr = expr.args
1476                 else:
1477                     expr = [expr]
1478
1479                 if coeff[w].has(*expr):
1480                     return None
1481                 else:
1482                     return coeff[w]
1483             else:
1484                 return None
1485
1486     def as_independent(self, *deps):
1487         """Returns a pair with separated parts of a given expression
1488            independent of specified symbols in the first place and
1489            dependent on them in the other. Both parts are valid
1490            SymPy expressions.
1491
1492            >>> from sympy import *
1493            >>> x, y = symbols('xy')
1494
1495            >>> (2*x*sin(x)+y+x).as_independent(x)
1496            (y, x + 2*x*sin(x))
1497
1498            >>> (x*sin(x)*cos(y)).as_independent(x)
1499            (cos(y), x*sin(x))
1500
1501            All other expressions are multiplicative:
1502
1503            >>> (sin(x)).as_independent(x)
1504            (1, sin(x))
1505
1506            >>> (sin(x)).as_independent(y)
1507            (sin(x), 1)
1508
1509         """
1510         indeps, depend = [], []
1511
1512         if self.is_Add or self.is_Mul:
1513             for term in self.args[:]:
1514                 if term.has(*deps):
1515                     depend.append(term)
1516                 else:
1517                     indeps.append(term)
1518
1519             return (self.__class__(*indeps),
1520                     self.__class__(*depend))
1521         else:
1522             if self.has(*deps):
1523                 return (S.One, self)
1524             else:
1525                 return (self, S.One)
1526
1527     def as_real_imag(self):
1528         """Performs complex expansion on 'self' and returns a tuple
1529            containing collected both real and imaginary parts. This
1530            method can't be confused with re() and im() functions,
1531            which does not perform complex expansion at evaluation.
1532
1533            However it is possible to expand both re() and im()
1534            functions and get exactly the same results as with
1535            a single call to this function.
1536
1537            >>> from sympy import *
1538
1539            >>> x, y = symbols('xy', real=True)
1540
1541            >>> (x + y*I).as_real_imag()
1542            (x, y)
1543
1544            >>> z, w = symbols('zw')
1545
1546            >>> (z + w*I).as_real_imag()
1547            (-im(w) + re(z), im(z) + re(w))
1548
1549         """
1550         expr = self.expand(complex=True)
1551
1552         if not expr.is_Add:
1553             expr = [expr]
1554
1555         re_part, im_part = [], []
1556         if isinstance(expr, Basic):
1557             expr = expr.args
1558
1559         for term in expr:
1560             coeff = term.as_coefficient(S.ImaginaryUnit)
1561
1562             if coeff is None:
1563                 re_part.append(term)
1564             else:
1565                 im_part.append(coeff)
1566
1567         return (Add(*re_part), Add(*im_part))
1568
1569     def as_powers_dict(self):
1570         return { self : S.One }
1571
1572     def as_base_exp(self):
1573         # a -> b ** e
1574         return self, S.One
1575
1576     def as_coeff_terms(self, x=None):
1577         # a -> c * t
1578         if x is not None:
1579             if not self.has(x):
1580                 return self, tuple()
1581         return S.One, (self,)
1582
1583     def as_coeff_factors(self, x=None):
1584         # a -> c + f
1585         if x is not None:
1586             if not self.has(x):
1587                 return self, tuple()
1588         return S.Zero, (self,)
1589
1590     def as_numer_denom(self):
1591         # a/b -> a,b
1592         base, exp = self.as_base_exp()
1593         coeff, terms = exp.as_coeff_terms()
1594         if coeff.is_negative:
1595             # b**-e -> 1, b**e
1596             return S.One, base ** (-exp)
1597         return self, S.One
1598
1599     def normal(self):
1600         n, d = self.as_numer_denom()
1601         if d is S.One:
1602             return n
1603         return n/d
1604
1605     def extract_multiplicatively(self, c):
1606         """Return None if it's not possible to make self in the form
1607            c * something in a nice way, i.e. preserving the properties
1608            of arguments of self.
1609
1610            >>> from sympy import *
1611
1612            >>> x, y = symbols('xy', real=True)
1613
1614            >>> ((x*y)**3).extract_multiplicatively(x**2 * y)
1615            x*y**2
1616
1617            >>> ((x*y)**3).extract_multiplicatively(x**4 * y)
1618
1619            >>> (2*x).extract_multiplicatively(2)
1620            x
1621
1622            >>> (2*x).extract_multiplicatively(3)
1623
1624            >>> (Rational(1,2)*x).extract_multiplicatively(3)
1625            x/6
1626
1627         """
1628         c = sympify(c)
1629         if c is S.One:
1630             return self
1631         elif c == self:
1632             return S.One
1633         elif c.is_Mul:
1634             x = self.extract_multiplicatively(c.as_two_terms()[0])
1635             if x != None:
1636                 return x.extract_multiplicatively(c.as_two_terms()[1])
1637         quotient = self / c
1638         if self.is_Number:
1639             if self is S.Infinity:
1640                 if c.is_positive:
1641                     return S.Infinity
1642             elif self is S.NegativeInfinity:
1643                 if c.is_negative:
1644                     return S.Infinity
1645                 elif c.is_positive:
1646                     return S.NegativeInfinity
1647             elif self is S.ComplexInfinity:
1648                 if not c.is_zero:
1649                     return S.ComplexInfinity
1650             elif self is S.NaN:
1651                 return S.NaN
1652             elif self.is_Integer:
1653                 if not quotient.is_Integer:
1654                     return None
1655                 elif self.is_positive and quotient.is_negative:
1656                     return None
1657                 else:
1658                     return quotient
1659             elif self.is_Rational:
1660                 if not quotient.is_Rational:
1661                     return None
1662                 elif self.is_positive and quotient.is_negative:
1663                     return None
1664                 else:
1665                     return quotient
1666             elif self.is_Real:
1667                 if not quotient.is_Real:
1668                     return None
1669                 elif self.is_positive and quotient.is_negative:
1670                     return None
1671                 else:
1672                     return quotient
1673         elif self.is_NumberSymbol or self.is_Symbol or self is S.ImaginaryUnit:
1674             if quotient.is_Mul and len(quotient.args) == 2:
1675                 if quotient.args[0].is_Integer and quotient.args[0].is_positive and quotient.args[1] == self:
1676                     return quotient
1677             elif quotient.is_Integer:
1678                 return quotient
1679         elif self.is_Add:
1680             newargs = []
1681             for arg in self.args:
1682                 newarg = arg.extract_multiplicatively(c)
1683                 if newarg != None:
1684                     newargs.append(newarg)
1685                 else:
1686                     return None
1687             return C.Add(*newargs)
1688         elif self.is_Mul:
1689             for i in xrange(len(self.args)):
1690                 newargs = list(self.args)
1691                 del(newargs[i])
1692                 tmp = C.Mul(*newargs).extract_multiplicatively(c)
1693                 if tmp != None:
1694                     return tmp * self.args[i]
1695         elif self.is_Pow:
1696             if c.is_Pow and c.base == self.base:
1697                 new_exp = self.exp.extract_additively(c.exp)
1698                 if new_exp != None:
1699                     return self.base ** (new_exp)
1700             elif c == self.base:
1701                 new_exp = self.exp.extract_additively(1)
1702                 if new_exp != None:
1703                     return self.base ** (new_exp)
1704
1705     def extract_additively(self, c):
1706         """Return None if it's not possible to make self in the form
1707            something + c in a nice way, i.e. preserving the properties
1708            of arguments of self.
1709
1710            >>> from sympy import *
1711
1712            >>> x, y = symbols('xy', real=True)
1713
1714            >>> ((x*y)**3).extract_additively(1)
1715
1716            >>> (x+1).extract_additively(x)
1717            1
1718
1719            >>> (x+1).extract_additively(2*x)
1720
1721            >>> (x+1).extract_additively(-x)
1722            1 + 2*x
1723
1724            >>> (-x+1).extract_additively(2*x)
1725            1 - 3*x
1726
1727         """
1728         c = sympify(c)
1729         if c is S.Zero:
1730             return self
1731         elif c == self:
1732             return S.Zero
1733         elif self is S.Zero:
1734             return None
1735         elif c.is_Add:
1736             x = self.extract_additively(c.as_two_terms()[0])
1737             if x != None:
1738                 return x.extract_additively(c.as_two_terms()[1])
1739         sub = self - c
1740         if self.is_Number:
1741             if self.is_Integer:
1742                 if not sub.is_Integer:
1743                     return None
1744                 elif self.is_positive and sub.is_negative:
1745                     return None
1746                 else:
1747                     return sub
1748             elif self.is_Rational:
1749                 if not sub.is_Rational:
1750                     return None
1751                 elif self.is_positive and sub.is_negative:
1752                     return None
1753                 else:
1754                     return sub
1755             elif self.is_Real:
1756                 if not sub.is_Real:
1757                     return None
1758                 elif self.is_positive and sub.is_negative:
1759                     return None
1760                 else:
1761                     return sub
1762         elif self.is_NumberSymbol or self.is_Symbol or self is S.ImaginaryUnit:
1763             if sub.is_Mul and len(sub.args) == 2:
1764                 if sub.args[0].is_Integer and sub.args[0].is_positive and sub.args[1] == self:
1765                     return sub
1766             elif sub.is_Integer:
1767                 return sub
1768         elif self.is_Add:
1769             terms = self.as_two_terms()
1770             subs0 = terms[0].extract_additively(c)
1771             if subs0 != None:
1772                 return subs0 + terms[1]
1773             else:
1774                 subs1 = terms[1].extract_additively(c)
1775                 if subs1 != None:
1776                     return subs1 + terms[0]
1777         elif self.is_Mul:
1778             self_coeff, self_terms = self.as_coeff_terms()
1779             if c.is_Mul:
1780                 c_coeff, c_terms = c.as_coeff_terms()
1781                 if c_terms == self_terms:
1782                     new_coeff = self_coeff.extract_additively(c_coeff)
1783                     if new_coeff != None:
1784                         return new_coeff * C.Mul(*self_terms)
1785             elif c == self_terms:
1786                 new_coeff = self_coeff.extract_additively(1)
1787                 if new_coeff != None:
1788                     return new_coeff * C.Mul(*self_terms)
1789
1790     def could_extract_minus_sign(self):
1791         """Canonical way to choose an element in the set {e, -e} where
1792            e is any expression. If the canonical element is e, we have
1793            e.could_extract_minus_sign() == True, else
1794            e.could_extract_minus_sign() == False.
1795
1796            For any expression, the set {e.could_extract_minus_sign(),
1797            (-e).could_extract_minus_sign()} must be {True, False}.
1798
1799            >>> from sympy import *
1800
1801            >>> x, y = symbols("xy")
1802
1803            >>> (x-y).could_extract_minus_sign() != (y-x).could_extract_minus_sign()
1804            True
1805
1806         """
1807         negative_self = -self
1808         self_has_minus = (self.extract_multiplicatively(-1) != None)
1809         negative_self_has_minus = ((negative_self).extract_multiplicatively(-1) != None)
1810         if self_has_minus != negative_self_has_minus:
1811             return self_has_minus
1812         else:
1813             if self.is_Add:
1814                 # We choose the one with less arguments with minus signs
1815                 arg_signs = [arg.could_extract_minus_sign() for arg in self.args]
1816                 positive_args = arg_signs.count(False)
1817                 negative_args = arg_signs.count(True)
1818                 if positive_args > negative_args:
1819                     return False
1820                 elif positive_args < negative_args:
1821                     return True
1822
1823             # As a last resort, we choose the one with greater hash
1824             return hash(self) < hash(negative_self)
1825
1826     ###################################################################################
1827     ##################### DERIVATIVE, INTEGRAL, FUNCTIONAL METHODS ####################
1828     ###################################################################################
1829
1830     def diff(self, *symbols, **assumptions):
1831         new_symbols = map(sympify, symbols)
1832         if not assumptions.has_key("evaluate"):
1833             assumptions["evaluate"] = True
1834         ret = Derivative(self, *new_symbols, **assumptions)
1835         return ret
1836
1837     def fdiff(self, *indices):
1838         # FIXME FApply -> ?
1839         return C.FApply(C.FDerivative(*indices), self)
1840
1841     def integral(self, *symbols, **assumptions):
1842         new_symbols = []
1843         for s in symbols:
1844             s = sympify(s)
1845             if s.is_Integer and new_symbols:
1846                 last_s = new_symbols[-1]
1847                 i = int(s)
1848                 new_symbols += [last_s] * (i-1)
1849             elif s.is_Symbol:
1850                 new_symbols.append(s)
1851             else:
1852                 raise TypeError(".integral() argument must be Symbol|Integer|Equality instance (got %s)" % (s.__class__.__name__))
1853         return C.Integral(self, *new_symbols, **assumptions)
1854
1855     #XXX fix the removeme
1856     def __call__(self, *args, **removeme):
1857         return Function(self[0])(*args)
1858
1859     def __float__(self):
1860         result = self.evalf()
1861         if result.is_Number:
1862             return float(result)
1863         else:
1864             raise ValueError("Symbolic value, can't compute")
1865
1866     def _evalf(self, prec):
1867         """Helper for evalf. Does the same thing but takes binary precision"""
1868         r = self._eval_evalf(prec)
1869         if r is None:
1870             r = self
1871         return r
1872
1873     def _eval_evalf(self, prec):
1874         return
1875
1876     def _seq_eval_evalf(self, prec):
1877         return self.__class__(*[s._evalf(prec) for s in self.args])
1878
1879     def _to_mpmath(self, prec, allow_ints=True):
1880         # mpmath functions accept ints as input
1881         errmsg = "cannot convert to mpmath number"
1882         if allow_ints and self.is_Integer:
1883             return self.p
1884         v = self._eval_evalf(prec)
1885         if v is None:
1886             raise ValueError(errmsg)
1887         if v.is_Real:
1888             return mpmath.make_mpf(v._mpf_)
1889         # Number + Number*I is also fine
1890         re, im = v.as_real_imag()
1891         if allow_ints and re.is_Integer:
1892             re = mpmath.lib.from_int(re.p)
1893         elif re.is_Real:
1894             re = re._mpf_
1895         else:
1896             raise ValueError(errmsg)
1897         if allow_ints and im.is_Integer:
1898             im = mpmath.lib.from_int(im.p)
1899         elif im.is_Real:
1900             im = im._mpf_
1901         else:
1902             raise ValueError(errmsg)
1903         return mpmath.make_mpc((re, im))
1904
1905     @staticmethod
1906     def _from_mpmath(x, prec):
1907         if hasattr(x, "_mpf_"):
1908             return C.Real._new(x._mpf_, prec)
1909         elif hasattr(x, "_mpc_"):
1910             re, im = x._mpc_
1911             re = C.Real._new(re, prec)
1912             im = C.Real._new(im, prec)*S.ImaginaryUnit
1913             return re+im
1914         else:
1915             raise TypeError("expected mpmath number (mpf or mpc)")
1916
1917     ###################################################################################
1918     ##################### SERIES, LEADING TERM, LIMIT, ORDER METHODS ##################
1919     ###################################################################################
1920
1921     def series(self, x, point=0, n=6, with_order=True):
1922         """
1923         Series expansion of "self" around "point".
1924
1925         Usage:
1926             Returns the Taylor (Laurent or generalized) series of "self" around
1927             the point "point" (default 0) with respect to "x" until the n-th
1928             term (default n is 6).
1929
1930             with_order .... if False, the order term (see the class Order) is
1931                 not appended
1932
1933         Notes:
1934             This method is the most high level method and it returns the
1935             series including the O(x**n) term.
1936
1937             Internally, it executes a method oseries(), which takes an
1938             O instance as the only parameter and it is responsible for
1939             returning a series (without the O term) up to the given order.
1940         """
1941         x = sympify(x)
1942         point = sympify(point)
1943         if point != 0:
1944             raise NotImplementedError("series expansion around arbitrary point")
1945             #self = self.subs(x, x + point)
1946         o = C.Order(x**n,x)
1947         r = self.oseries(o)
1948         if r==self:
1949             return self
1950         if with_order:
1951             r += o
1952         return r
1953
1954     @cacheit
1955     def oseries(self, order):
1956         """
1957         Return the series of an expression up to given Order symbol (without the
1958         actual O term).
1959
1960         The general philosophy is this: simply start with the most simple
1961         Taylor (Laurent) term and calculate one be one and use
1962         order.contains(term) method to determine if your term is still
1963         significant and should be added to the series, or we should stop.
1964         """
1965         order = C.Order(order)
1966         if order is S.Zero:
1967             return self
1968         if order.contains(self):
1969             return S.Zero
1970         if len(order.symbols)>1:
1971             r = self
1972             for s in order.symbols:
1973                 o = C.Order(order.expr, s)
1974                 r = r.oseries(o)
1975             return r
1976         x = order.symbols[0]
1977         if not self.has(x):
1978             return self
1979         obj = self._eval_oseries(order)
1980         if obj is not None:
1981             #obj2 = obj.expand(trig=True)
1982             obj2 = obj.expand()
1983             if obj2 != obj:
1984                 r = obj2.oseries(order)
1985                 return r
1986             return obj
1987         raise NotImplementedError('(%s).oseries(%s)' % (self, order))
1988
1989     def nseries(self, x, x0, n):
1990         """
1991         Calculates a generalized series expansion.
1992
1993         The difference between oseries and nseries is that nseries calculates
1994         "n" terms in the innermost expressions and then builds up the final
1995         series just by "cross-mutliplying" everything out.
1996
1997         Advantage -- it's fast, because we don't have to determine how many
1998         terms we need to calculate in advance.
1999
2000         Disadvantage -- you may endup with less terms than you may have
2001         expected, but the O(x**n) term appended will always be correct, so the
2002         result is correct, but maybe shorter.
2003         """
2004         raise NotImplementedError("(%s).nseries(%s, %s, %s)" % (self, x, x0, n))
2005
2006     def _eval_oseries(self, order):
2007         return
2008
2009     def _compute_oseries(self, arg, order, taylor_term, unevaluated_func, correction = 0):
2010         """
2011         compute series sum(taylor_term(i, arg), i=0..n-1) such
2012         that order.contains(taylor_term(n, arg)). Assumes that arg->0 as x->0.
2013         """
2014         x = order.symbols[0]
2015         ln = C.log
2016         o = C.Order(arg, x)
2017         if o is S.Zero:
2018             return unevaluated_func(arg)
2019         if o.expr==1:
2020             e = ln(order.expr*x)/ln(x)
2021         else:
2022             e = ln(order.expr)/ln(o.expr)
2023         n = e.limit(x,0) + 1 + correction
2024         if n.is_unbounded:
2025             # requested accuracy gives infinite series,
2026             # order is probably nonpolynomial e.g. O(exp(-1/x), x).
2027             return unevaluated_func(arg)
2028         try:
2029             n = int(n)
2030         except TypeError:
2031             #well, the n is something more complicated (like 1+log(2))
2032             n = int(n.evalf()) + 1
2033         assert n>=0,`n`
2034         l = []
2035         g = None
2036         for i in xrange(n+2):
2037             g = taylor_term(i, arg, g)
2038             g = g.oseries(order)
2039             l.append(g)
2040         return Add(*l)
2041
2042     def limit(self, x, xlim, direction='+'):
2043         """ Compute limit x->xlim.
2044         """
2045         from sympy.series.limits import limit
2046         return limit(self, x, xlim, direction)
2047
2048     @cacheit
2049     def as_leading_term(self, *symbols):
2050         if len(symbols)>1:
2051             c = self
2052             for x in symbols:
2053                 c = c.as_leading_term(x)
2054             return c
2055         elif not symbols:
2056             return self
2057         x = sympify(symbols[0])
2058         assert x.is_Symbol, `x`
2059         if not self.has(x):
2060             return self
2061         expr = self.expand(trig=True)
2062         obj = expr._eval_as_leading_term(x)
2063         if obj is not None:
2064             return obj
2065         raise NotImplementedError('as_leading_term(%s, %s)' % (self, x))
2066
2067     def as_coeff_exponent(self, x):
2068         """ c*x**e -> c,e where x can be any symbolic expression.
2069         """
2070         x = sympify(x)
2071         wc = Wild('wc')
2072         we = Wild('we')
2073         c, terms = self.as_coeff_terms()
2074         p  = wc*x**we
2075         d = self.match(p)
2076         if d is not None and we in d:
2077             return d[wc], d[we]
2078         return self, S.Zero
2079
2080     def leadterm(self, x):
2081         x = sympify(x)
2082         c,e = self.as_leading_term(x).as_coeff_exponent(x)
2083         if not c.has(x):
2084             return c,e
2085         raise ValueError("cannot compute leadterm(%s, %s), got c=%s" % (self, x, c))
2086
2087
2088     ##########################################################################
2089     ##################### END OF BASIC CLASS #################################
2090     ##########################################################################
2091
2092 class Atom(Basic):
2093     """
2094     A parent class for atomic things.
2095
2096     Examples: Symbol, Number, Rational, Integer, ...
2097     But not: Add, Mul, Pow, ...
2098     """
2099
2100     is_Atom = True
2101
2102     __slots__ = []
2103
2104     def _eval_derivative(self, s):
2105         if self==s: return S.One
2106         return S.Zero
2107
2108     def pattern_match(pattern, expr, repl_dict):
2109         if pattern==expr:
2110             return repl_dict
2111         return None
2112
2113     def as_numer_denom(self):
2114         return self, S.One
2115
2116     def count_ops(self, symbolic=True):
2117         return S.Zero
2118
2119     def doit(self, **hints):
2120         return self
2121
2122     def _eval_is_polynomial(self, syms):
2123         return True
2124
2125     def _eval_oseries(self, order):
2126         # .oseries() method checks for order.contains(self)
2127         return self
2128
2129     def _eval_as_leading_term(self, x):
2130         return self
2131
2132     @property
2133     def is_number(self):
2134         return True
2135
2136     def nseries(self, x, x0, n):
2137         return self
2138
2139
2140 class SingletonMeta(BasicMeta):
2141     """Metaclass for all singletons
2142
2143        All singleton classes should put this into their __metaclass__, and
2144        _not_ to define __new__
2145
2146        example:
2147
2148        class Zero(Integer):
2149            __metaclass__ = SingletonMeta
2150
2151            p = 0
2152            q = 1
2153     """
2154
2155     def __init__(cls, *args, **kw):
2156         BasicMeta.__init__(cls, *args, **kw)
2157
2158         # we are going to inject singletonic __new__, here it is:
2159         def cls_new(cls):
2160             try:
2161                 obj = getattr(SingletonFactory, cls.__name__)
2162
2163             except AttributeError:
2164                 obj = Basic.__new__(cls, *(), **{})
2165                 setattr(SingletonFactory, cls.__name__, obj)
2166
2167             return obj
2168
2169         cls_new.__name__ = '%s.__new__' % (cls.__name__)
2170
2171         assert not cls.__dict__.has_key('__new__'), \
2172                 'Singleton classes are not allowed to redefine __new__'
2173
2174         # inject singletonic __new__
2175         cls.__new__      = staticmethod(cls_new)
2176
2177         # tag the class appropriately (so we could verify it later when doing
2178         # S.<something>
2179         cls.is_Singleton = True
2180
2181 class SingletonFactory:
2182     """
2183     A map between singleton classes and the corresponding instances.
2184     E.g. S.Exp == C.Exp()
2185     """
2186
2187     def __getattr__(self, clsname):
2188         if clsname == "__repr__":
2189             return lambda: "S"
2190
2191         cls = getattr(C, clsname)
2192         assert cls.is_Singleton
2193         obj = cls()
2194
2195         # store found object in own __dict__, so the next lookups will be
2196         # serviced without entering __getattr__, and so will be fast
2197         setattr(self, clsname, obj)
2198         return obj
2199
2200 S = SingletonFactory()
2201
2202 class ClassesRegistry:
2203     """Namespace for SymPy classes
2204
2205        This is needed to avoid problems with cyclic imports.
2206        To get a SymPy class you do this:
2207
2208          C.<class_name>
2209
2210        e.g.
2211
2212          C.Rational
2213          C.Add
2214     """
2215
2216     def __getattr__(self, name):
2217         try:
2218             cls = BasicMeta.classnamespace[name]
2219         except KeyError:
2220             raise AttributeError("No SymPy class '%s'" % name)
2221
2222         setattr(self, name, cls)
2223         return cls
2224
2225 C = ClassesRegistry()
2226
2227 # XXX this is ugly, but needed for Memoizer('str', ...) to work
2228 import cache
2229 cache.C = C
2230 del cache
2231
2232 # /cyclic/
2233 import sympify as _
2234 _.Basic     = Basic
2235 _.BasicType = BasicType
2236 _.S         = S
2237 del _