- modified the comment blocks so the copyright message no longer appears in
[ginac.git] / ginac / add.cpp
1 /** @file add.cpp
2  *
3  *  Implementation of GiNaC's sums of expressions. */
4
5 /*
6  *  GiNaC Copyright (C) 1999 Johannes Gutenberg University Mainz, Germany
7  *
8  *  This program is free software; you can redistribute it and/or modify
9  *  it under the terms of the GNU General Public License as published by
10  *  the Free Software Foundation; either version 2 of the License, or
11  *  (at your option) any later version.
12  *
13  *  This program is distributed in the hope that it will be useful,
14  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
15  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16  *  GNU General Public License for more details.
17  *
18  *  You should have received a copy of the GNU General Public License
19  *  along with this program; if not, write to the Free Software
20  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
21  */
22
23 #include <iostream>
24 #include <stdexcept>
25
26 #include "add.h"
27 #include "mul.h"
28
29 //////////
30 // default constructor, destructor, copy constructor assignment operator and helpers
31 //////////
32
33 // public
34
35 add::add()
36 {
37     debugmsg("add default constructor",LOGLEVEL_CONSTRUCT);
38     tinfo_key = TINFO_add;
39 }
40
41 add::~add()
42 {
43     debugmsg("add destructor",LOGLEVEL_DESTRUCT);
44     destroy(0);
45 }
46
47 add::add(add const & other)
48 {
49     debugmsg("add copy constructor",LOGLEVEL_CONSTRUCT);
50     copy(other);
51 }
52
53 add const & add::operator=(add const & other)
54 {
55     debugmsg("add operator=",LOGLEVEL_ASSIGNMENT);
56     if (this != &other) {
57         destroy(1);
58         copy(other);
59     }
60     return *this;
61 }
62
63 // protected
64
65 void add::copy(add const & other)
66 {
67     expairseq::copy(other);
68 }
69
70 void add::destroy(bool call_parent)
71 {
72     if (call_parent) expairseq::destroy(call_parent);
73 }
74
75 //////////
76 // other constructors
77 //////////
78
79 // public
80
81 add::add(ex const & lh, ex const & rh)
82 {
83     debugmsg("add constructor from ex,ex",LOGLEVEL_CONSTRUCT);
84     tinfo_key = TINFO_add;
85     overall_coeff=exZERO();
86     construct_from_2_ex(lh,rh);
87     ASSERT(is_canonical());
88 }
89
90 add::add(exvector const & v)
91 {
92     debugmsg("add constructor from exvector",LOGLEVEL_CONSTRUCT);
93     tinfo_key = TINFO_add;
94     overall_coeff=exZERO();
95     construct_from_exvector(v);
96     ASSERT(is_canonical());
97 }
98
99 /*
100 add::add(epvector const & v, bool do_not_canonicalize)
101 {
102     debugmsg("add constructor from epvector,bool",LOGLEVEL_CONSTRUCT);
103     tinfo_key = TINFO_add;
104     if (do_not_canonicalize) {
105         seq=v;
106 #ifdef EXPAIRSEQ_USE_HASHTAB
107         combine_same_terms(); // to build hashtab
108 #endif // def EXPAIRSEQ_USE_HASHTAB
109     } else {
110         construct_from_epvector(v);
111     }
112     ASSERT(is_canonical());
113 }
114 */
115
116 add::add(epvector const & v)
117 {
118     debugmsg("add constructor from epvector",LOGLEVEL_CONSTRUCT);
119     tinfo_key = TINFO_add;
120     overall_coeff=exZERO();
121     construct_from_epvector(v);
122     ASSERT(is_canonical());
123 }
124
125 add::add(epvector const & v, ex const & oc)
126 {
127     debugmsg("add constructor from epvector,ex",LOGLEVEL_CONSTRUCT);
128     tinfo_key = TINFO_add;
129     overall_coeff=oc;
130     construct_from_epvector(v);
131     ASSERT(is_canonical());
132 }
133
134 add::add(epvector * vp, ex const & oc)
135 {
136     debugmsg("add constructor from epvector *,ex",LOGLEVEL_CONSTRUCT);
137     tinfo_key = TINFO_add;
138     ASSERT(vp!=0);
139     overall_coeff=oc;
140     construct_from_epvector(*vp);
141     delete vp;
142     ASSERT(is_canonical());
143 }
144
145 //////////
146 // functions overriding virtual functions from bases classes
147 //////////
148
149 // public
150
151 basic * add::duplicate() const
152 {
153     debugmsg("add duplicate",LOGLEVEL_DUPLICATE);
154     return new add(*this);
155 }
156
157 bool add::info(unsigned inf) const
158 {
159     // TODO: optimize
160     if (inf==info_flags::polynomial || inf==info_flags::integer_polynomial || inf==info_flags::rational_polynomial || inf==info_flags::rational_function) {
161         for (epvector::const_iterator it=seq.begin(); it!=seq.end(); ++it) {
162             if (!(recombine_pair_to_ex(*it).info(inf)))
163                 return false;
164         }
165         return true;
166     } else {
167         return expairseq::info(inf);
168     }
169 }
170
171 int add::degree(symbol const & s) const
172 {
173     int deg=INT_MIN;
174     if (!overall_coeff.is_equal(exZERO())) {
175         deg=0;
176     }
177     int cur_deg;
178     for (epvector::const_iterator cit=seq.begin(); cit!=seq.end(); ++cit) {
179         cur_deg=(*cit).rest.degree(s);
180         if (cur_deg>deg) deg=cur_deg;
181     }
182     return deg;
183 }
184
185 int add::ldegree(symbol const & s) const
186 {
187     int deg=INT_MAX;
188     if (!overall_coeff.is_equal(exZERO())) {
189         deg=0;
190     }
191     int cur_deg;
192     for (epvector::const_iterator cit=seq.begin(); cit!=seq.end(); ++cit) {
193         cur_deg=(*cit).rest.ldegree(s);
194         if (cur_deg<deg) deg=cur_deg;
195     }
196     return deg;
197 }
198
199 ex add::coeff(symbol const & s, int const n) const
200 {
201     epvector coeffseq;
202     coeffseq.reserve(seq.size());
203
204     epvector::const_iterator it=seq.begin();
205     while (it!=seq.end()) {
206         coeffseq.push_back(combine_ex_with_coeff_to_pair((*it).rest.coeff(s,n),
207                                                          (*it).coeff));
208         ++it;
209     }
210     if (n==0) {
211         return (new add(coeffseq,overall_coeff))->setflag(status_flags::dynallocated);
212     }
213     return (new add(coeffseq))->setflag(status_flags::dynallocated);
214 }
215
216 /*
217 ex add::eval(int level) const
218 {
219     // simplifications: +(...,x,c1,c2) -> +(...,x,c1+c2) (c1, c2 numeric())
220     //                  +(...,(c1,c2)) -> (...,(c1*c2,1)) (normalize)
221     //                  +(...,x,0) -> +(...,x)
222     //                  +(x) -> x
223     //                  +() -> 0
224
225     debugmsg("add eval",LOGLEVEL_MEMBER_FUNCTION);
226
227     epvector newseq=seq;
228     epvector::iterator it1,it2;
229     
230     // +(...,x,c1,c2) -> +(...,x,c1+c2) (c1, c2 numeric())
231     it2=newseq.end()-1;
232     it1=it2-1;
233     while ((newseq.size()>=2)&&is_exactly_of_type(*(*it1).rest.bp,numeric)&&
234                                is_exactly_of_type(*(*it2).rest.bp,numeric)) {
235         *it1=expair(ex_to_numeric((*it1).rest).mul(ex_to_numeric((*it1).coeff))
236                     .add(ex_to_numeric((*it2).rest).mul(ex_to_numeric((*it2).coeff))),exONE());
237         newseq.pop_back();
238         it2=newseq.end()-1;
239         it1=it2-1;
240     }
241
242     if ((newseq.size()>=1)&&is_exactly_of_type(*(*it2).rest.bp,numeric)) {
243         // +(...,(c1,c2)) -> (...,(c1*c2,1)) (normalize)
244         *it2=expair(ex_to_numeric((*it2).rest).mul(ex_to_numeric((*it2).coeff)),exONE());
245         // +(...,x,0) -> +(...,x)
246         if (ex_to_numeric((*it2).rest).compare(0)==0) {
247             newseq.pop_back();
248         }
249     }
250
251     if (newseq.size()==0) {
252         // +() -> 0
253         return exZERO();
254     } else if (newseq.size()==1) {
255         // +(x) -> x
256         return recombine_pair_to_ex(*(newseq.begin()));
257     }
258
259     return (new add(newseq,1))->setflag(status_flags::dynallocated  |
260                                         status_flags::evaluated );
261 }
262 */
263
264 /*
265 ex add::eval(int level) const
266 {
267     // simplifications: +(...,x,c1,c2) -> +(...,x,c1+c2) (c1, c2 numeric())
268     //                  +(...,(c1,c2)) -> (...,(c1*c2,1)) (normalize)
269     //                  +(...,x,0) -> +(...,x)
270     //                  +(x) -> x
271     //                  +() -> 0
272
273     debugmsg("add eval",LOGLEVEL_MEMBER_FUNCTION);
274
275     if ((level==1)&&(flags & status_flags::evaluated)) {
276 #ifdef DOASSERT
277         for (epvector::const_iterator cit=seq.begin(); cit!=seq.end(); ++cit) {
278             ASSERT(!is_ex_exactly_of_type((*cit).rest,add));
279             ASSERT(!(is_ex_exactly_of_type((*cit).rest,numeric)&&
280                      (ex_to_numeric((*cit).coeff).compare(numONE())!=0)));
281         }
282 #endif // def DOASSERT
283         return *this;
284     }
285
286     epvector newseq;
287     epvector::iterator it1,it2;
288     bool seq_copied=false;
289
290     epvector * evaled_seqp=evalchildren(level);
291     if (evaled_seqp!=0) {
292         // do more evaluation later
293         return (new add(evaled_seqp))->setflag(status_flags::dynallocated);
294     }
295
296 #ifdef DOASSERT
297     for (epvector::const_iterator cit=seq.begin(); cit!=seq.end(); ++cit) {
298         ASSERT(!is_ex_exactly_of_type((*cit).rest,add));
299         ASSERT(!(is_ex_exactly_of_type((*cit).rest,numeric)&&
300                  (ex_to_numeric((*cit).coeff).compare(numONE())!=0)));
301     }
302 #endif // def DOASSERT
303
304     if (flags & status_flags::evaluated) {
305         return *this;
306     }
307     
308     expair const & last_expair=*(seq.end()-1);
309     expair const & next_to_last_expair=*(seq.end()-2);
310     int seq_size = seq.size();
311
312     // +(...,x,c1,c2) -> +(...,x,c1+c2) (c1, c2 numeric())
313     if ((!seq_copied)&&(seq_size>=2)&&
314         is_ex_exactly_of_type(last_expair.rest,numeric)&&
315         is_ex_exactly_of_type(next_to_last_expair.rest,numeric)) {
316         newseq=seq;
317         seq_copied=true;
318         it2=newseq.end()-1;
319         it1=it2-1;
320     }
321     while (seq_copied&&(newseq.size()>=2)&&
322            is_ex_exactly_of_type((*it1).rest,numeric)&&
323            is_ex_exactly_of_type((*it2).rest,numeric)) {
324         *it1=expair(ex_to_numeric((*it1).rest).mul(ex_to_numeric((*it1).coeff))
325                     .add_dyn(ex_to_numeric((*it2).rest).mul(ex_to_numeric((*it2).coeff))),exONE());
326         newseq.pop_back();
327         it2=newseq.end()-1;
328         it1=it2-1;
329     }
330
331     // +(...,(c1,c2)) -> (...,(c1*c2,1)) (normalize)
332     if ((!seq_copied)&&(seq_size>=1)&&
333         (is_ex_exactly_of_type(last_expair.rest,numeric))&&
334         (ex_to_numeric(last_expair.coeff).compare(numONE())!=0)) {
335         newseq=seq;
336         seq_copied=true;
337         it2=newseq.end()-1;
338     }
339     if (seq_copied&&(newseq.size()>=1)&&
340         (is_ex_exactly_of_type((*it2).rest,numeric))&&
341         (ex_to_numeric((*it2).coeff).compare(numONE())!=0)) {
342         *it2=expair(ex_to_numeric((*it2).rest).mul_dyn(ex_to_numeric((*it2).coeff)),exONE());
343     }
344         
345     // +(...,x,0) -> +(...,x)
346     if ((!seq_copied)&&(seq_size>=1)&&
347         (is_ex_exactly_of_type(last_expair.rest,numeric))&&
348         (ex_to_numeric(last_expair.rest).is_zero())) {
349         newseq=seq;
350         seq_copied=true;
351         it2=newseq.end()-1;
352     }
353     if (seq_copied&&(newseq.size()>=1)&&
354         (is_ex_exactly_of_type((*it2).rest,numeric))&&
355         (ex_to_numeric((*it2).rest).is_zero())) {
356         newseq.pop_back();
357     }
358
359     // +() -> 0
360     if ((!seq_copied)&&(seq_size==0)) {
361         return exZERO();
362     } else if (seq_copied&&(newseq.size()==0)) {
363         return exZERO();
364     }
365
366     // +(x) -> x
367     if ((!seq_copied)&&(seq_size==1)) {
368         return recombine_pair_to_ex(*(seq.begin()));
369     } else if (seq_copied&&(newseq.size()==1)) {
370         return recombine_pair_to_ex(*(newseq.begin()));
371     }
372
373     if (!seq_copied) return this->hold();
374
375     return (new add(newseq,1))->setflag(status_flags::dynallocated  |
376                                         status_flags::evaluated );
377 }
378 */
379
380 ex add::eval(int level) const
381 {
382     // simplifications: +(;c) -> c
383     //                  +(x;1) -> x
384
385     debugmsg("add eval",LOGLEVEL_MEMBER_FUNCTION);
386
387     epvector * evaled_seqp=evalchildren(level);
388     if (evaled_seqp!=0) {
389         // do more evaluation later
390         return (new add(evaled_seqp,overall_coeff))->
391                    setflag(status_flags::dynallocated);
392     }
393
394 #ifdef DOASSERT
395     for (epvector::const_iterator cit=seq.begin(); cit!=seq.end(); ++cit) {
396         ASSERT(!is_ex_exactly_of_type((*cit).rest,add));
397         if (is_ex_exactly_of_type((*cit).rest,numeric)) {
398             dbgprint();
399         }
400         ASSERT(!is_ex_exactly_of_type((*cit).rest,numeric));
401     }
402 #endif // def DOASSERT
403
404     if (flags & status_flags::evaluated) {
405         ASSERT(seq.size()>0);
406         ASSERT((seq.size()>1)||!overall_coeff.is_equal(exZERO()));
407         return *this;
408     }
409
410     int seq_size=seq.size();
411     if (seq_size==0) {
412         // +(;c) -> c
413         return overall_coeff;
414     } else if ((seq_size==1)&&overall_coeff.is_equal(exZERO())) {
415         // +(x;0) -> x
416         return recombine_pair_to_ex(*(seq.begin()));
417     }
418     return this->hold();
419 }
420
421 exvector add::get_indices(void) const
422 {
423     // all terms in the sum should have the same indices (compatible tensors)
424     // however this is not checked, since there is no function yet which
425     // compares indices (idxvector can be unsorted) !!!!!!!!!!!
426     if (seq.size()==0) {
427         return exvector();
428     }
429     return (seq.begin())->rest.get_indices();
430 }    
431
432 ex add::simplify_ncmul(exvector const & v) const
433 {
434     if (seq.size()==0) {
435         return expairseq::simplify_ncmul(v);
436     }
437     return (*seq.begin()).rest.simplify_ncmul(v);
438 }    
439
440 // protected
441
442 int add::compare_same_type(basic const & other) const
443 {
444     return expairseq::compare_same_type(other);
445 }
446
447 bool add::is_equal_same_type(basic const & other) const
448 {
449     return expairseq::is_equal_same_type(other);
450 }
451
452 unsigned add::return_type(void) const
453 {
454     if (seq.size()==0) {
455         return return_types::commutative;
456     }
457     return (*seq.begin()).rest.return_type();
458 }
459    
460 unsigned add::return_type_tinfo(void) const
461 {
462     if (seq.size()==0) {
463         return tinfo_key;
464     }
465     return (*seq.begin()).rest.return_type_tinfo();
466 }
467
468 ex add::thisexpairseq(epvector const & v, ex const & oc) const
469 {
470     return (new add(v,oc))->setflag(status_flags::dynallocated);
471 }
472
473 ex add::thisexpairseq(epvector * vp, ex const & oc) const
474 {
475     return (new add(vp,oc))->setflag(status_flags::dynallocated);
476 }
477
478 /*
479 expair add::split_ex_to_pair(ex const & e) const
480 {
481     if (is_ex_exactly_of_type(e,mul)) {
482         mul const & mulref=ex_to_mul(e);
483         ASSERT(mulref.seq.size()>1);
484         ex const & lastfactor_rest=(*(mulref.seq.end()-1)).rest;
485         ex const & lastfactor_coeff=(*(mulref.seq.end()-1)).coeff;
486         if (is_ex_exactly_of_type(lastfactor_rest,numeric) &&
487             ex_to_numeric(lastfactor_coeff).is_equal(numONE())) {
488             epvector s=mulref.seq;
489             //s.pop_back();
490             //return expair((new mul(s,1))->setflag(status_flags::dynallocated),
491             //              lastfactor);
492             mul * mulp=static_cast<mul *>(mulref.duplicate());
493 #ifdef EXPAIRSEQ_USE_HASHTAB
494             mulp->remove_hashtab_entry(mulp->seq.end()-1);
495 #endif // def EXPAIRSEQ_USE_HASHTAB
496             mulp->seq.pop_back();
497 #ifdef EXPAIRSEQ_USE_HASHTAB
498             mulp->shrink_hashtab();
499 #endif // def EXPAIRSEQ_USE_HASHTAB
500             mulp->clearflag(status_flags::evaluated);
501             mulp->clearflag(status_flags::hash_calculated);
502             return expair(mulp->setflag(status_flags::dynallocated),lastfactor_rest);
503         }
504     }
505     return expair(e,exONE());
506 }
507 */
508
509 expair add::split_ex_to_pair(ex const & e) const
510 {
511     if (is_ex_exactly_of_type(e,mul)) {
512         mul const & mulref=ex_to_mul(e);
513         ex numfactor=mulref.overall_coeff;
514         // mul * mulcopyp=static_cast<mul *>(mulref.duplicate());
515         mul * mulcopyp=new mul(mulref);
516         mulcopyp->overall_coeff=exONE();
517         mulcopyp->clearflag(status_flags::evaluated);
518         mulcopyp->clearflag(status_flags::hash_calculated);
519         return expair(mulcopyp->setflag(status_flags::dynallocated),numfactor);
520     }
521     return expair(e,exONE());
522 }
523
524 /*
525 expair add::combine_ex_with_coeff_to_pair(ex const & e,
526                                           ex const & c) const
527 {
528     ASSERT(is_ex_exactly_of_type(c,numeric));
529     if (is_ex_exactly_of_type(e,mul)) {
530         mul const & mulref=ex_to_mul(e);
531         ASSERT(mulref.seq.size()>1);
532         ex const & lastfactor_rest=(*(mulref.seq.end()-1)).rest;
533         ex const & lastfactor_coeff=(*(mulref.seq.end()-1)).coeff;
534         if (is_ex_exactly_of_type(lastfactor_rest,numeric) &&
535             ex_to_numeric(lastfactor_coeff).is_equal(numONE())) {
536             //epvector s=mulref.seq;
537             //s.pop_back();
538             //return expair((new mul(s,1))->setflag(status_flags::dynallocated),
539             //              ex_to_numeric(lastfactor).mul_dyn(ex_to_numeric(c)));
540             mul * mulp=static_cast<mul *>(mulref.duplicate());
541 #ifdef EXPAIRSEQ_USE_HASHTAB
542             mulp->remove_hashtab_entry(mulp->seq.end()-1);
543 #endif // def EXPAIRSEQ_USE_HASHTAB
544             mulp->seq.pop_back();
545 #ifdef EXPAIRSEQ_USE_HASHTAB
546             mulp->shrink_hashtab();
547 #endif // def EXPAIRSEQ_USE_HASHTAB
548             mulp->clearflag(status_flags::evaluated);
549             mulp->clearflag(status_flags::hash_calculated);
550             if (are_ex_trivially_equal(c,exONE())) {
551                 return expair(mulp->setflag(status_flags::dynallocated),lastfactor_rest);
552             } else if (are_ex_trivially_equal(lastfactor_rest,exONE())) {
553                 return expair(mulp->setflag(status_flags::dynallocated),c);
554             }                
555             return expair(mulp->setflag(status_flags::dynallocated),
556                           ex_to_numeric(lastfactor_rest).mul_dyn(ex_to_numeric(c)));
557         }
558     }
559     return expair(e,c);
560 }
561 */
562
563 expair add::combine_ex_with_coeff_to_pair(ex const & e,
564                                           ex const & c) const
565 {
566     ASSERT(is_ex_exactly_of_type(c,numeric));
567     if (is_ex_exactly_of_type(e,mul)) {
568         mul const & mulref=ex_to_mul(e);
569         ex numfactor=mulref.overall_coeff;
570         //mul * mulcopyp=static_cast<mul *>(mulref.duplicate());
571         mul * mulcopyp=new mul(mulref);
572         mulcopyp->overall_coeff=exONE();
573         mulcopyp->clearflag(status_flags::evaluated);
574         mulcopyp->clearflag(status_flags::hash_calculated);
575         if (are_ex_trivially_equal(c,exONE())) {
576             return expair(mulcopyp->setflag(status_flags::dynallocated),numfactor);
577         } else if (are_ex_trivially_equal(numfactor,exONE())) {
578             return expair(mulcopyp->setflag(status_flags::dynallocated),c);
579         }
580         return expair(mulcopyp->setflag(status_flags::dynallocated),
581                           ex_to_numeric(numfactor).mul_dyn(ex_to_numeric(c)));
582     } else if (is_ex_exactly_of_type(e,numeric)) {
583         if (are_ex_trivially_equal(c,exONE())) {
584             return expair(e,exONE());
585         }
586         return expair(ex_to_numeric(e).mul_dyn(ex_to_numeric(c)),exONE());
587     }
588     return expair(e,c);
589 }
590     
591 expair add::combine_pair_with_coeff_to_pair(expair const & p,
592                                             ex const & c) const
593 {
594     ASSERT(is_ex_exactly_of_type(p.coeff,numeric));
595     ASSERT(is_ex_exactly_of_type(c,numeric));
596
597     if (is_ex_exactly_of_type(p.rest,numeric)) {
598         ASSERT(ex_to_numeric(p.coeff).is_equal(numONE())); // should be normalized
599         return expair(ex_to_numeric(p.rest).mul_dyn(ex_to_numeric(c)),exONE());
600     }
601
602     return expair(p.rest,ex_to_numeric(p.coeff).mul_dyn(ex_to_numeric(c)));
603 }
604     
605 ex add::recombine_pair_to_ex(expair const & p) const
606 {
607     //if (p.coeff.compare(exONE())==0) {
608     //if (are_ex_trivially_equal(p.coeff,exONE())) {
609     if (ex_to_numeric(p.coeff).is_equal(numONE())) {
610         return p.rest;
611     } else {
612         return p.rest*p.coeff;
613     }
614 }
615
616 ex add::expand(unsigned options) const
617 {
618     epvector * vp=expandchildren(options);
619     if (vp==0) {
620         return *this;
621     }
622     return (new add(vp,overall_coeff))->setflag(status_flags::expanded    |
623                                                 status_flags::dynallocated );
624 }
625
626 //////////
627 // new virtual functions which can be overridden by derived classes
628 //////////
629
630 // none
631
632 //////////
633 // non-virtual functions in this class
634 //////////
635
636 // none
637
638 //////////
639 // static member variables
640 //////////
641
642 // protected
643
644 unsigned add::precedence=40;
645
646 //////////
647 // global constants
648 //////////
649
650 const add some_add;
651 type_info const & typeid_add=typeid(some_add);
652
653
654