- modified the comment blocks so the copyright message no longer appears in
[ginac.git] / ginac / lst.cpp
1 /** @file lst.cpp
2  *
3  *  Implementation of GiNaC's lst. 
4  *  This file was generated automatically by container.pl.
5  *  Please do not modify it directly, edit the perl script instead!
6  *  container.pl options: $CONTAINER=lst
7  *                        $STLHEADER=list
8  *                        $reserve=0
9  *                        $prepend=1
10  *                        $let_op=1
11  *                        $open_bracket=[
12  *                        $close_bracket=] */
13
14 /*
15  *  GiNaC Copyright (C) 1999 Johannes Gutenberg University Mainz, Germany
16  *
17  *  This program is free software; you can redistribute it and/or modify
18  *  it under the terms of the GNU General Public License as published by
19  *  the Free Software Foundation; either version 2 of the License, or
20  *  (at your option) any later version.
21  *
22  *  This program is distributed in the hope that it will be useful,
23  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
24  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
25  *  GNU General Public License for more details.
26  *
27  *  You should have received a copy of the GNU General Public License
28  *  along with this program; if not, write to the Free Software
29  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
30  */
31
32 #include <iostream>
33 #include <stdexcept>
34
35 #include "lst.h"
36 #include "ex.h"
37
38 #define RESERVE(s,size) // no reserve needed for list
39
40 //////////
41 // default constructor, destructor, copy constructor assignment operator and helpers
42 //////////
43
44 // public
45
46 lst::lst() : basic(TINFO_lst)
47 {
48     debugmsg("lst default constructor",LOGLEVEL_CONSTRUCT);
49 }
50
51 lst::~lst()
52 {
53     debugmsg("lst destructor",LOGLEVEL_DESTRUCT);
54     destroy(0);
55 }
56
57 lst::lst(lst const & other)
58 {
59     debugmsg("lst copy constructor",LOGLEVEL_CONSTRUCT);
60     copy(other);
61 }
62
63 lst const & lst::operator=(lst const & other)
64 {
65     debugmsg("lst operator=",LOGLEVEL_ASSIGNMENT);
66     if (this != &other) {
67         destroy(1);
68         copy(other);
69     }
70     return *this;
71 }
72
73 // protected
74
75 void lst::copy(lst const & other)
76 {
77     basic::copy(other);
78     seq=other.seq;
79 }
80
81 void lst::destroy(bool call_parent)
82 {
83     seq.clear();
84     if (call_parent) basic::destroy(call_parent);
85 }
86
87 //////////
88 // other constructors
89 //////////
90
91 // public
92
93 lst::lst(exlist const & s, bool discardable) :  basic(TINFO_lst)
94 {
95     debugmsg("lst constructor from exlist",
96              LOGLEVEL_CONSTRUCT);
97     if (discardable) {
98         seq.swap(const_cast<exlist &>(s));
99     } else {
100         seq=s;
101     }
102 }
103
104 lst::lst(exlist * vp) : basic(TINFO_lst)
105 {
106     debugmsg("lst constructor from exlist *",LOGLEVEL_CONSTRUCT);
107     ASSERT(vp!=0);
108     seq.swap(*vp);
109     delete vp;
110 }
111
112 lst::lst(ex const & e1) :  basic(TINFO_lst)
113 {
114     debugmsg("lst constructor from 1 ex",
115              LOGLEVEL_CONSTRUCT);
116     RESERVE(seq,1);
117     seq.push_back(e1);
118 }
119
120 lst::lst(ex const & e1, ex const & e2) : basic(TINFO_lst)
121 {
122     debugmsg("lst constructor from 2 ex",
123              LOGLEVEL_CONSTRUCT);
124     RESERVE(seq,2);
125     seq.push_back(e1);
126     seq.push_back(e2);
127 }
128
129 lst::lst(ex const & e1, ex const & e2, ex const & e3)
130     : basic(TINFO_lst)
131 {
132     debugmsg("lst constructor from 3 ex",
133              LOGLEVEL_CONSTRUCT);
134     RESERVE(seq,3);
135     seq.push_back(e1);
136     seq.push_back(e2);
137     seq.push_back(e3);
138 }
139
140 lst::lst(ex const & e1, ex const & e2, ex const & e3,
141                      ex const & e4) : basic(TINFO_lst)
142 {
143     debugmsg("lst constructor from 4 ex",
144              LOGLEVEL_CONSTRUCT);
145     RESERVE(seq,4);
146     seq.push_back(e1);
147     seq.push_back(e2);
148     seq.push_back(e3);
149     seq.push_back(e4);
150 }
151
152 lst::lst(ex const & e1, ex const & e2, ex const & e3,
153                      ex const & e4, ex const & e5) : basic(TINFO_lst)
154 {
155     debugmsg("lst constructor from 5 ex",
156              LOGLEVEL_CONSTRUCT);
157     RESERVE(seq,5);
158     seq.push_back(e1);
159     seq.push_back(e2);
160     seq.push_back(e3);
161     seq.push_back(e4);
162     seq.push_back(e5);
163 }
164
165 lst::lst(ex const & e1, ex const & e2, ex const & e3,
166                      ex const & e4, ex const & e5, ex const & e6)
167     : basic(TINFO_lst)
168 {
169     debugmsg("lst constructor from 6 ex",
170              LOGLEVEL_CONSTRUCT);
171     RESERVE(seq,6);
172     seq.push_back(e1);
173     seq.push_back(e2);
174     seq.push_back(e3);
175     seq.push_back(e4);
176     seq.push_back(e5);
177     seq.push_back(e6);
178 }
179
180 lst::lst(ex const & e1, ex const & e2, ex const & e3,
181                      ex const & e4, ex const & e5, ex const & e6,
182                      ex const & e7) : basic(TINFO_lst)
183 {
184     debugmsg("lst constructor from 7 ex",
185              LOGLEVEL_CONSTRUCT);
186     RESERVE(seq,7);
187     seq.push_back(e1);
188     seq.push_back(e2);
189     seq.push_back(e3);
190     seq.push_back(e4);
191     seq.push_back(e5);
192     seq.push_back(e6);
193     seq.push_back(e7);
194 }
195
196 lst::lst(ex const & e1, ex const & e2, ex const & e3,
197                      ex const & e4, ex const & e5, ex const & e6,
198                      ex const & e7, ex const & e8) : basic(TINFO_lst)
199 {
200     debugmsg("lst constructor from 8 ex",
201              LOGLEVEL_CONSTRUCT);
202     RESERVE(seq,8);
203     seq.push_back(e1);
204     seq.push_back(e2);
205     seq.push_back(e3);
206     seq.push_back(e4);
207     seq.push_back(e5);
208     seq.push_back(e6);
209     seq.push_back(e7);
210     seq.push_back(e8);
211 }
212
213 lst::lst(ex const & e1, ex const & e2, ex const & e3,
214                      ex const & e4, ex const & e5, ex const & e6,
215                      ex const & e7, ex const & e8, ex const & e9)
216     : basic(TINFO_lst)
217 {
218     debugmsg("lst constructor from 9 ex",
219              LOGLEVEL_CONSTRUCT);
220     RESERVE(seq,9);
221     seq.push_back(e1);
222     seq.push_back(e2);
223     seq.push_back(e3);
224     seq.push_back(e4);
225     seq.push_back(e5);
226     seq.push_back(e6);
227     seq.push_back(e7);
228     seq.push_back(e8);
229     seq.push_back(e9);
230 }
231
232 lst::lst(ex const & e1, ex const & e2, ex const & e3,
233                      ex const & e4, ex const & e5, ex const & e6,
234                      ex const & e7, ex const & e8, ex const & e9,
235                      ex const &e10)
236     : basic(TINFO_lst)
237 {
238     debugmsg("lst constructor from 10 ex",
239              LOGLEVEL_CONSTRUCT);
240     RESERVE(seq,10);
241     seq.push_back(e1);
242     seq.push_back(e2);
243     seq.push_back(e3);
244     seq.push_back(e4);
245     seq.push_back(e5);
246     seq.push_back(e6);
247     seq.push_back(e7);
248     seq.push_back(e8);
249     seq.push_back(e9);
250     seq.push_back(e10);
251 }
252
253 //////////
254 // functions overriding virtual functions from bases classes
255 //////////
256
257 // public
258
259 basic * lst::duplicate() const
260 {
261     debugmsg("lst duplicate",LOGLEVEL_DUPLICATE);
262     return new lst(*this);
263 }
264
265 void lst::printraw(ostream & os) const
266 {
267     debugmsg("lst printraw",LOGLEVEL_PRINT);
268
269     os << "lst(";
270     for (exlist::const_iterator cit=seq.begin(); cit!=seq.end(); ++cit) {
271         (*cit).bp->printraw(os);
272         os << ",";
273     }
274     os << ")";
275 }
276
277 void lst::print(ostream & os, unsigned upper_precedence) const
278 {
279     debugmsg("lst print",LOGLEVEL_PRINT);
280     // always print brackets around seq, ignore upper_precedence
281     printseq(os,'[',',',']',precedence,precedence+1);
282 }
283
284 void lst::printtree(ostream & os, unsigned indent) const
285 {
286     debugmsg("lst printtree",LOGLEVEL_PRINT);
287
288     os << string(indent,' ') << "type=" << typeid(*this).name()
289        << ", hash=" << hashvalue << " (0x" << hex << hashvalue << dec << ")"
290        << ", flags=" << flags
291        << ", nops=" << nops() << endl;
292     for (exlist::const_iterator cit=seq.begin(); cit!=seq.end(); ++cit) {
293         (*cit).printtree(os,indent+delta_indent);
294     }
295     os << string(indent+delta_indent,' ') << "=====" << endl;
296 }
297
298 // lst::info() will be implemented by user elsewhere";
299
300 int lst::nops() const
301 {
302     return seq.size();
303 }
304
305 ex & lst::let_op(int const i)
306 {
307     ASSERT(i>=0);
308     ASSERT(i<nops());
309
310     exlist::iterator it=seq.begin();
311     for (int j=0; j<i; j++) {
312         ++it;
313     }
314     return *it;
315 }
316
317
318 ex lst::expand(unsigned options) const
319 {
320     exlist s;
321     RESERVE(s,seq.size());
322     for (exlist::const_iterator it=seq.begin(); it!=seq.end(); ++it) {
323         s.push_back((*it).expand(options));
324     }
325
326     return thislst(s);
327 }
328
329 // a lst 'has' an expression if it is this expression itself or a child 'has' it
330
331 bool lst::has(ex const & other) const
332 {
333     ASSERT(other.bp!=0);
334     if (is_equal(*other.bp)) return true;
335     for (exlist::const_iterator it=seq.begin(); it!=seq.end(); ++it) {
336         if ((*it).has(other)) return true;
337     }
338     return false;
339 }
340
341 ex lst::eval(int level) const
342 {
343     if (level==1) {
344         return this->hold();
345     }
346     return thislst(evalchildren(level));
347 }
348
349 ex lst::evalf(int level) const
350 {
351     return thislst(evalfchildren(level));
352 }
353
354 /** Implementation of ex::normal() for lsts. It normalizes the arguments
355  *  and replaces the lst by a temporary symbol.
356  *  @see ex::normal */
357 ex lst::normal(lst &sym_lst, lst &repl_lst, int level) const
358 {
359     ex n=thislst(normalchildren(level));
360     return n.bp->basic::normal(sym_lst,repl_lst,level);
361 }
362
363 ex lst::diff(symbol const & s) const
364 {
365     return thislst(diffchildren(s));
366 }
367
368 ex lst::subs(lst const & ls, lst const & lr) const
369 {
370     exlist * vp=subschildren(ls,lr);
371     if (vp==0) {
372         return *this;
373     }
374     return thislst(vp);
375 }
376
377 // protected
378
379 int lst::compare_same_type(basic const & other) const
380 {
381     ASSERT(is_of_type(other,lst));
382     lst const & o=static_cast<lst const &>
383                                     (const_cast<basic &>(other));
384     int cmpval;
385     exlist::const_iterator it1=seq.begin();
386     exlist::const_iterator it2=o.seq.begin();
387
388     for (; (it1!=seq.end())&&(it2!=o.seq.end()); ++it1, ++it2) {
389         cmpval=(*it1).compare(*it2);
390         if (cmpval!=0) return cmpval;
391     }
392
393     if (it1==seq.end()) {
394         return (it2==o.seq.end() ? 0 : -1);
395     }
396
397     return 1;
398 }
399
400 bool lst::is_equal_same_type(basic const & other) const
401 {
402     ASSERT(is_of_type(other,lst));
403     lst const & o=static_cast<lst const &>
404                                     (const_cast<basic &>(other));
405     if (seq.size()!=o.seq.size()) return false;
406
407     exlist::const_iterator it1=seq.begin();
408     exlist::const_iterator it2=o.seq.begin();
409
410     for (; it1!=seq.end(); ++it1, ++it2) {
411         if (!(*it1).is_equal(*it2)) return false;
412     }
413
414     return true;
415 }
416
417 unsigned lst::return_type(void) const
418 {
419     return return_types::noncommutative_composite;
420 }
421
422 //////////
423 // new virtual functions which can be overridden by derived classes
424 //////////
425
426 // public
427
428 lst & lst::append(ex const & b)
429 {
430     ensure_if_modifiable();
431     seq.push_back(b);
432     return *this;
433 }
434
435 lst & lst::prepend(ex const & b)
436 {
437     ensure_if_modifiable();
438     seq.push_front(b);
439     return *this;
440 }
441
442
443 // protected
444
445 void lst::printseq(ostream & os, char openbracket, char delim,
446                          char closebracket, unsigned this_precedence,
447                          unsigned upper_precedence) const
448 {
449     if (this_precedence<=upper_precedence) os << openbracket;
450     if (seq.size()!=0) {
451         exlist::const_iterator it,it_last;
452         it=seq.begin();
453         it_last=seq.end();
454         --it_last;
455         for (; it!=it_last; ++it) {
456             (*it).bp->print(os,this_precedence);
457             os << delim;
458         }
459         (*it).bp->print(os,this_precedence);
460     }
461     if (this_precedence<=upper_precedence) os << closebracket;
462 }
463
464 ex lst::thislst(exlist const & v) const
465 {
466     return lst(v);
467 }
468
469 ex lst::thislst(exlist * vp) const
470 {
471     return lst(vp);
472 }
473
474 //////////
475 // non-virtual functions in this class
476 //////////
477
478 // public
479
480 // none
481
482 // protected
483
484 bool lst::is_canonical() const
485 {
486     if (seq.size()<=1) { return 1; }
487
488     exlist::const_iterator it=seq.begin();
489     exlist::const_iterator it_last=it;
490     for (++it; it!=seq.end(); it_last=it, ++it) {
491         if ((*it_last).compare(*it)>0) {
492             if ((*it_last).compare(*it)>0) {
493                 cout << *it_last << ">" << *it << "\n";
494                 return 0;
495                 }
496         }
497     }
498     return 1;
499 }
500
501
502 exlist lst::evalchildren(int level) const
503 {
504     exlist s;
505     RESERVE(s,seq.size());
506
507     if (level==1) {
508         return seq;
509     }
510     if (level == -max_recursion_level) {
511         throw(std::runtime_error("max recursion level reached"));
512     }
513     --level;
514     for (exlist::const_iterator it=seq.begin(); it!=seq.end(); ++it) {
515         s.push_back((*it).eval(level));
516     }
517     return s;
518 }
519
520 exlist lst::evalfchildren(int level) const
521 {
522     exlist s;
523     RESERVE(s,seq.size());
524
525     if (level==1) {
526         return seq;
527     }
528     if (level == -max_recursion_level) {
529         throw(std::runtime_error("max recursion level reached"));
530     }
531     --level;
532     for (exlist::const_iterator it=seq.begin(); it!=seq.end(); ++it) {
533         s.push_back((*it).evalf(level));
534     }
535     return s;
536 }
537
538 exlist lst::normalchildren(int level) const
539 {
540     exlist s;
541     RESERVE(s,seq.size());
542
543     if (level==1) {
544         return seq;
545     }
546     if (level == -max_recursion_level) {
547         throw(std::runtime_error("max recursion level reached"));
548     }
549     --level;
550     for (exlist::const_iterator it=seq.begin(); it!=seq.end(); ++it) {
551         s.push_back((*it).normal(level));
552     }
553     return s;
554 }
555
556 exlist lst::diffchildren(symbol const & y) const
557 {
558     exlist s;
559     RESERVE(s,seq.size());
560     for (exlist::const_iterator it=seq.begin(); it!=seq.end(); ++it) {
561         s.push_back((*it).diff(y));
562     }
563     return s;
564 }
565
566 /* obsolete subschildren
567 exlist lst::subschildren(lst const & ls, lst const & lr) const
568 {
569     exlist s;
570     RESERVE(s,seq.size());
571     for (exlist::const_iterator it=seq.begin(); it!=seq.end(); ++it) {
572         s.push_back((*it).subs(ls,lr));
573     }
574     return s;
575 }
576 */
577
578 exlist * lst::subschildren(lst const & ls, lst const & lr) const
579 {
580     // returns a NULL pointer if nothing had to be substituted
581     // returns a pointer to a newly created epvector otherwise
582     // (which has to be deleted somewhere else)
583
584     exlist::const_iterator last=seq.end();
585     exlist::const_iterator cit=seq.begin();
586     while (cit!=last) {
587         ex const & subsed_ex=(*cit).subs(ls,lr);
588         if (!are_ex_trivially_equal(*cit,subsed_ex)) {
589
590             // something changed, copy seq, subs and return it
591             exlist *s=new exlist;
592             RESERVE(*s,seq.size());
593
594             // copy parts of seq which are known not to have changed
595             exlist::const_iterator cit2=seq.begin();
596             while (cit2!=cit) {
597                 s->push_back(*cit2);
598                 ++cit2;
599             }
600             // copy first changed element
601             s->push_back(subsed_ex);
602             ++cit2;
603             // copy rest
604             while (cit2!=last) {
605                 s->push_back((*cit2).subs(ls,lr));
606                 ++cit2;
607             }
608             return s;
609         }
610         ++cit;
611     }
612     
613     return 0; // nothing has changed
614 }
615
616 //////////
617 // static member variables
618 //////////
619
620 // protected
621
622 unsigned lst::precedence=10;
623
624 //////////
625 // global constants
626 //////////
627
628 const lst some_lst;
629 type_info const & typeid_lst=typeid(some_lst);
630