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