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