sympy/core/add.py

   1
   2 from basic import Basic, S, C
   3 from operations import AssocOp
   4 from cache import cacheit
   5
   6 from symbol import Symbol, Wild, Temporary
   7 # from numbers import Number    /cyclic/
   8 # from mul import Mul    /cyclic/
   9 # from function import FunctionClass    /cyclic/
  10
  11 class Add(AssocOp):
  12
  13     __slots__ = []
  14
  15     is_Add = True
  16
  17     @classmethod
  18     def flatten(cls, seq):
  19         """
  20         Takes the sequence "seq" of nested Adds and returns a flatten list.
  21
  22         Returns: (commutative_part, noncommutative_part, order_symbols)
  23
  24         Applies associativity, all terms are commutable with respect to
  25         addition.
  26         """
  27         terms = {}      # term -> coeff
  28                         # e.g. x**2 -> 5   for ... + 5*x**2 + ...
  29
  30         coeff = S.Zero  # standalone term
  31                         # e.g. 3 + ...
  32         order_factors = []
  33
  34         for o in seq:
  35
  36             # O(x)
  37             if o.is_Order:
  38                 for o1 in order_factors:
  39                     if o1.contains(o):
  40                         o = None
  41                         break
  42                 if o is None:
  43                     continue
  44                 order_factors = [o]+[o1 for o1 in order_factors if not o.contains(o1)]
  45                 continue
  46
  47             # 3
  48             elif o.is_Number:
  49                 coeff += o
  50                 continue
  51
  52             # Add([...])
  53             elif o.is_Add:
  54                 # NB: here we assume Add is always commutative
  55                 seq.extend(o.args)  # TODO zerocopy?
  56                 continue
  57
  58             # Mul([...])
  59             elif o.is_Mul:
  60                 c = o.args[0]
  61
  62                 # 3*...
  63                 if c.is_Number:
  64                     if c is S.One:
  65                         s = o
  66                     else:
  67                         s = o.as_two_terms()[1]
  68
  69                 else:
  70                     c = S.One
  71                     s = o
  72
  73             # everything else
  74             else:
  75                 c = S.One
  76                 s = o
  77
  78
  79             # now we have:
  80             # o = c*s, where
  81             #
  82             # c is a Number
  83             # s is an expression with number factor extracted
  84
  85             # let's collect terms with the same s, so e.g.
  86             # 2*x**2 + 3*x**2  ->  5*x**2
  87             if s in terms:
  88                 terms[s] += c
  89             else:
  90                 terms[s] = c
  91
  92
  93         # now let's construct new args:
  94         # [2*x**2, x**3, 7*x**4, pi, ...]
  95         newseq = []
  96         noncommutative = False
  97         for s,c in terms.items():
  98             # 0*s
  99             if c is S.Zero:
 100                 continue
 101             # 1*s
 102             elif c is S.One:
 103                 newseq.append(s)
 104             # c*s
 105             else:
 106                 if s.is_Mul:
 107                     # Mul, already keeps it's arguments in perfect order.
 108                     # so we can simply put c in slot0 and go the fast way.
 109                     cs = s._new_rawargs(*((c,) + s.args))
 110                     newseq.append(cs)
 111
 112                 else:
 113                     # alternatively we have to call all Mul's machinery (slow)
 114                     newseq.append(Mul(c,s))
 115
 116             noncommutative = noncommutative or not s.is_commutative
 117
 118         # nan
 119         if coeff is S.NaN:
 120             # we know for sure the result will be nan
 121             return [S.NaN], [], None
 122
 123         # oo, -oo
 124         elif (coeff is S.Infinity) or (coeff is S.NegativeInfinity):
 125             newseq = [f for f in newseq if not f.is_real]
 126
 127
 128         # process O(x)
 129         if order_factors:
 130             newseq2 = []
 131             for t in newseq:
 132                 for o in order_factors:
 133                     # x + O(x) -> O(x)
 134                     if o.contains(t):
 135                         t = None
 136                         break
 137                 # x + O(x**2) -> x + O(x**2)
 138                 if t is not None:
 139                     newseq2.append(t)
 140             newseq = newseq2 + order_factors
 141             # 1 + O(1) -> O(1)
 142             for o in order_factors:
 143                 if o.contains(coeff):
 144                     coeff = S.Zero
 145                     break
 146
 147
 148         # order args canonically
 149         # Currently we sort things using hashes, as it is quite fast. A better
 150         # solution is not to sort things at all - but this needs some more
 151         # fixing.
 152         newseq.sort(key=hash)
 153
 154         # current code expects coeff to be always in slot-0
 155         if coeff is not S.Zero:
 156             newseq.insert(0, coeff)
 157
 158         # we are done
 159         if noncommutative:
 160             return [], newseq, None
 161         else:
 162             return newseq, [], None
 163
 164
 165     @cacheit
 166     def as_coeff_factors(self, x=None):
 167         if x is not None:
 168             l1 = []
 169             l2 = []
 170             for f in self.args:
 171                 if f.has(x):
 172                     l2.append(f)
 173                 else:
 174                     l1.append(f)
 175             return Add(*l1), tuple(l2)
 176         coeff = self.args[0]
 177         if coeff.is_Number:
 178             return coeff, self.args[1:]
 179         return S.Zero, self.args
 180
 181     def _eval_derivative(self, s):
 182         return Add(*[f.diff(s) for f in self.args])
 183
 184     def _eval_nseries(self, x, x0, n):
 185         terms = [t.nseries(x, x0, n) for t in self.args]
 186         return Add(*terms)
 187
 188     def _matches_simple(pattern, expr, repl_dict):
 189         # handle (w+3).matches('x+5') -> {w: x+2}
 190         coeff, factors = pattern.as_coeff_factors()
 191         if len(factors)==1:
 192             return factors[0].matches(expr - coeff, repl_dict)
 193         return
 194
 195     matches = AssocOp._matches_commutative
 196
 197     @staticmethod
 198     def _combine_inverse(lhs, rhs):
 199         return lhs - rhs
 200
 201     @cacheit
 202     def as_two_terms(self):
 203         if len(self.args) == 1:
 204             return S.Zero, self
 205         return self.args[0], Add(*self.args[1:])
 206
 207     def as_numer_denom(self):
 208         numers, denoms = [],[]
 209         for n,d in [f.as_numer_denom() for f in self.args]:
 210             numers.append(n)
 211             denoms.append(d)
 212         r = xrange(len(numers))
 213         return Add(*[Mul(*(denoms[:i]+[numers[i]]+denoms[i+1:])) for i in r]),Mul(*denoms)
 214
 215     def count_ops(self, symbolic=True):
 216         if symbolic:
 217             return Add(*[t.count_ops(symbolic) for t in self[:]]) + Symbol('ADD') * (len(self[:])-1)
 218         return Add(*[t.count_ops(symbolic) for t in self.args[:]]) + (len(self.args[:])-1)
 219
 220     def _eval_is_polynomial(self, syms):
 221         for term in self.args:
 222             if not term._eval_is_polynomial(syms):
 223                 return False
 224         return True
 225
 226     # assumption methods
 227     _eval_is_real = lambda self: self._eval_template_is_attr('is_real')
 228     _eval_is_bounded = lambda self: self._eval_template_is_attr('is_bounded')
 229     _eval_is_commutative = lambda self: self._eval_template_is_attr('is_commutative')
 230     _eval_is_integer = lambda self: self._eval_template_is_attr('is_integer')
 231     _eval_is_comparable = lambda self: self._eval_template_is_attr('is_comparable')
 232
 233     def _eval_is_odd(self):
 234         l = [f for f in self.args if not (f.is_even==True)]
 235         if not l:
 236             return False
 237         if l[0].is_odd:
 238             return Add(*l[1:]).is_even
 239
 240     def _eval_is_irrational(self):
 241         for t in self.args:
 242             a = t.is_irrational
 243             if a: return True
 244             if a is None: return
 245         return False
 246
 247     def _eval_is_positive(self):
 248         c = self.args[0]
 249         r = Add(*self.args[1:])
 250         if c.is_positive and r.is_positive:
 251             return True
 252         if c.is_unbounded:
 253             if r.is_unbounded:
 254                 # either c or r is negative
 255                 return
 256             else:
 257                 return c.is_positive
 258         elif r.is_unbounded:
 259             return r.is_positive
 260         if c.is_nonnegative and r.is_positive:
 261             return True
 262         if r.is_nonnegative and c.is_positive:
 263             return True
 264         if c.is_nonpositive and r.is_nonpositive:
 265             return False
 266
 267     def _eval_is_negative(self):
 268         c = self.args[0]
 269         r = Add(*self.args[1:])
 270         if c.is_negative and r.is_negative:
 271             return True
 272         if c.is_unbounded:
 273             if r.is_unbounded:
 274                 # either c or r is positive
 275                 return
 276             else:
 277                 return c.is_negative
 278         elif r.is_unbounded:
 279             return r.is_negative
 280         if c.is_nonpositive and r.is_negative:
 281             return True
 282         if r.is_nonpositive and c.is_negative:
 283             return True
 284         if c.is_nonnegative and r.is_nonnegative:
 285             return False
 286
 287     def as_coeff_terms(self, x=None):
 288         # -2 + 2 * a -> -1, 2-2*a
 289         if self.args[0].is_Number and self.args[0].is_negative:
 290             return -S.One,(-self,)
 291         return S.One,(self,)
 292
 293     def _eval_subs(self, old, new):
 294         if self==old: return new
 295         if isinstance(old, FunctionClass):
 296             return self.__class__(*[s.subs(old, new) for s in self.args ])
 297         coeff1,factors1 = self.as_coeff_factors()
 298         coeff2,factors2 = old.as_coeff_factors()
 299         if factors1==factors2: # (2+a).subs(3+a,y) -> 2-3+y
 300             return new + coeff1 - coeff2
 301         if old.is_Add:
 302             l1,l2 = len(factors1),len(factors2)
 303             if l2<l1: # (a+b+c+d).subs(b+c,x) -> a+x+d
 304                 for i in xrange(l1-l2+1):
 305                     if factors2==factors1[i:i+l2]:
 306                         factors1 = list(factors1)
 307                         factors2 = list(factors2)
 308                         return Add(*([coeff1-coeff2]+factors1[:i]+[new]+factors1[i+l2:]))
 309         return self.__class__(*[s.subs(old, new) for s in self.args])
 310
 311     @cacheit
 312     def extract_leading_order(self, *symbols):
 313         """
 314         Returns the leading term and it's order.
 315
 316         Examples:
 317
 318         >>> (x+1+1/x**5).extract_leading_order(x)
 319         ((1/x**5, O(1/x**5)),)
 320         >>> (1+x).extract_leading_order(x)
 321         ((1, O(1, x)),)
 322         >>> (x+x**2).extract_leading_order(x)
 323         ((x, O(x)),)
 324         """
 325         lst = []
 326         seq = [(f, C.Order(f, *symbols)) for f in self.args]
 327         for ef,of in seq:
 328             for e,o in lst:
 329                 if o.contains(of):
 330                     of = None
 331                     break
 332             if of is None:
 333                 continue
 334             new_lst = [(ef,of)]
 335             for e,o in lst:
 336                 if of.contains(o):
 337                     continue
 338                 new_lst.append((e,o))
 339             lst = new_lst
 340         return tuple(lst)
 341
 342     def _eval_as_leading_term(self, x):
 343         coeff, factors = self.as_coeff_factors(x)
 344         has_unbounded = bool([f for f in self.args if f.is_unbounded])
 345         if has_unbounded:
 346             if isinstance(factors, Basic):
 347                 factors = factors.args
 348             factors = [f for f in factors if not f.is_bounded]
 349         if coeff is not S.Zero:
 350             o = C.Order(x)
 351         else:
 352             o = C.Order(factors[0]*x,x)
 353         n = 1
 354         s = self.nseries(x, 0, n)
 355         while s.is_Order:
 356             n +=1
 357             s = self.nseries(x, 0, n)
 358         if s.is_Add:
 359             s = s.removeO()
 360         if s.is_Add:
 361             lst = s.extract_leading_order(x)
 362             return Add(*[e for (e,f) in lst])
 363         return s.as_leading_term(x)
 364
 365     def _eval_conjugate(self):
 366         return Add(*[t.conjugate() for t in self.args])
 367
 368     def __neg__(self):
 369         return Add(*[-t for t in self.args])
 370
 371     def _sage_(self):
 372         s = 0
 373         for x in self.args:
 374             s += x._sage_()
 375         return s
 376
 377
 378 # /cyclic/
 379 import basic as _
 380 _.Add       = Add
 381 del _
 382
 383 import mul as _
 384 _.Add       = Add
 385 del _
 386
 387 import power as _
 388 _.Add       = Add
 389 del _
 390
 391 import operations as _
 392 _.Add       = Add
 393 del _