generous use of auto_ptr to provide better exception safety and make the code
[ginac.git] / ginac / container.h
1 /** @file container.h
2  *
3  *  Wrapper template for making GiNaC classes out of STL containers. */
4
5 /*
6  *  GiNaC Copyright (C) 1999-2003 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 #ifndef __GINAC_CONTAINER_H__
24 #define __GINAC_CONTAINER_H__
25
26 #include <iterator>
27 #include <stdexcept>
28 #include <algorithm>
29 #include <vector>
30 #include <list>
31 #include <memory>
32
33 #include "ex.h"
34 #include "print.h"
35 #include "archive.h"
36 #include "assertion.h"
37
38 namespace GiNaC {
39
40
41 /** Helper template for encapsulating the reserve() mechanics of STL containers. */
42 template <template <class> class C>
43 class container_storage {
44 protected:
45         typedef C<ex> STLT;
46
47         container_storage() {}
48         container_storage(size_t n, const ex & e) : seq(n, e) {}
49
50         template <class In>
51         container_storage(In b, In e) : seq(b, e) {}
52
53         void reserve(size_t) {}
54         static void reserve(STLT &, size_t) {}
55
56         STLT seq;
57
58         // disallow destruction of container through a container_storage*
59 protected:
60         ~container_storage() {}
61 };
62
63 template <>
64 inline void container_storage<std::vector>::reserve(size_t n) { seq.reserve(n); }
65
66 template <>
67 inline void container_storage<std::vector>::reserve(std::vector<ex> & v, size_t n) { v.reserve(n); }
68
69
70 /** Wrapper template for making GiNaC classes out of STL containers. */
71 template <template <class> class C>
72 class container : public basic, public container_storage<C> {
73         GINAC_DECLARE_REGISTERED_CLASS(container, basic)
74
75         typedef typename container_storage<C>::STLT STLT;
76
77 public:
78         typedef typename STLT::const_iterator const_iterator;
79         typedef typename STLT::const_reverse_iterator const_reverse_iterator;
80
81 protected:
82         // helpers
83         static unsigned get_tinfo() { return TINFO_fail; }
84         static char get_open_delim() { return '('; }
85         static char get_close_delim() { return ')'; }
86
87         // constructors
88 public:
89         container(STLT const & s, bool discardable = false) : inherited(get_tinfo())
90         {
91                 if (discardable)
92                         this->seq.swap(const_cast<STLT &>(s));
93                 else
94                         this->seq = s;
95         }
96
97         explicit container(std::auto_ptr<STLT> vp) : inherited(get_tinfo())
98         {
99                 this->seq.swap(*vp);
100         }
101
102         container(exvector::const_iterator b, exvector::const_iterator e)
103          : inherited(get_tinfo()), container_storage<C>(b, e) {}
104
105         explicit container(const ex & p1)
106          : inherited(get_tinfo()), container_storage<C>(1, p1) {}
107
108         container(const ex & p1, const ex & p2) : inherited(get_tinfo())
109         {
110                 reserve(this->seq, 2);
111                 this->seq.push_back(p1); this->seq.push_back(p2);
112         }
113
114         container(const ex & p1, const ex & p2, const ex & p3) : inherited(get_tinfo())
115         {
116                 reserve(this->seq, 3);
117                 this->seq.push_back(p1); this->seq.push_back(p2); this->seq.push_back(p3);
118         }
119
120         container(const ex & p1, const ex & p2, const ex & p3,
121                            const ex & p4) : inherited(get_tinfo())
122         {
123                 reserve(this->seq, 4);
124                 this->seq.push_back(p1); this->seq.push_back(p2); this->seq.push_back(p3);
125                 this->seq.push_back(p4);
126         }
127
128         container(const ex & p1, const ex & p2, const ex & p3,
129                   const ex & p4, const ex & p5) : inherited(get_tinfo())
130         {
131                 reserve(this->seq, 5);
132                 this->seq.push_back(p1); this->seq.push_back(p2); this->seq.push_back(p3);
133                 this->seq.push_back(p4); this->seq.push_back(p5);
134         }
135
136         container(const ex & p1, const ex & p2, const ex & p3,
137                   const ex & p4, const ex & p5, const ex & p6) : inherited(get_tinfo())
138         {
139                 reserve(this->seq, 6);
140                 this->seq.push_back(p1); this->seq.push_back(p2); this->seq.push_back(p3);
141                 this->seq.push_back(p4); this->seq.push_back(p5); this->seq.push_back(p6);
142         }
143
144         container(const ex & p1, const ex & p2, const ex & p3,
145                   const ex & p4, const ex & p5, const ex & p6,
146                   const ex & p7) : inherited(get_tinfo())
147         {
148                 reserve(this->seq, 7);
149                 this->seq.push_back(p1); this->seq.push_back(p2); this->seq.push_back(p3);
150                 this->seq.push_back(p4); this->seq.push_back(p5); this->seq.push_back(p6);
151                 this->seq.push_back(p7);
152         }
153
154         container(const ex & p1, const ex & p2, const ex & p3,
155                   const ex & p4, const ex & p5, const ex & p6,
156                   const ex & p7, const ex & p8) : inherited(get_tinfo())
157         {
158                 reserve(this->seq, 8);
159                 this->seq.push_back(p1); this->seq.push_back(p2); this->seq.push_back(p3);
160                 this->seq.push_back(p4); this->seq.push_back(p5); this->seq.push_back(p6);
161                 this->seq.push_back(p7); this->seq.push_back(p8);
162         }
163
164         container(const ex & p1, const ex & p2, const ex & p3,
165                   const ex & p4, const ex & p5, const ex & p6,
166                   const ex & p7, const ex & p8, const ex & p9) : inherited(get_tinfo())
167         {
168                 reserve(this->seq, 9);
169                 this->seq.push_back(p1); this->seq.push_back(p2); this->seq.push_back(p3);
170                 this->seq.push_back(p4); this->seq.push_back(p5); this->seq.push_back(p6);
171                 this->seq.push_back(p7); this->seq.push_back(p8); this->seq.push_back(p9);
172         }
173
174         container(const ex & p1, const ex & p2, const ex & p3,
175                   const ex & p4, const ex & p5, const ex & p6,
176                   const ex & p7, const ex & p8, const ex & p9,
177                   const ex & p10) : inherited(get_tinfo())
178         {
179                 reserve(this->seq, 10);
180                 this->seq.push_back(p1); this->seq.push_back(p2); this->seq.push_back(p3);
181                 this->seq.push_back(p4); this->seq.push_back(p5); this->seq.push_back(p6);
182                 this->seq.push_back(p7); this->seq.push_back(p8); this->seq.push_back(p9);
183                 this->seq.push_back(p10);
184         }
185
186         container(const ex & p1, const ex & p2, const ex & p3,
187                   const ex & p4, const ex & p5, const ex & p6,
188                   const ex & p7, const ex & p8, const ex & p9,
189                   const ex & p10, const ex & p11) : inherited(get_tinfo())
190         {
191                 reserve(this->seq, 11);
192                 this->seq.push_back(p1); this->seq.push_back(p2); this->seq.push_back(p3);
193                 this->seq.push_back(p4); this->seq.push_back(p5); this->seq.push_back(p6);
194                 this->seq.push_back(p7); this->seq.push_back(p8); this->seq.push_back(p9);
195                 this->seq.push_back(p10); this->seq.push_back(p11);
196         }
197
198         container(const ex & p1, const ex & p2, const ex & p3,
199                   const ex & p4, const ex & p5, const ex & p6,
200                   const ex & p7, const ex & p8, const ex & p9,
201                   const ex & p10, const ex & p11, const ex & p12) : inherited(get_tinfo())
202         {
203                 reserve(this->seq, 12);
204                 this->seq.push_back(p1); this->seq.push_back(p2); this->seq.push_back(p3);
205                 this->seq.push_back(p4); this->seq.push_back(p5); this->seq.push_back(p6);
206                 this->seq.push_back(p7); this->seq.push_back(p8); this->seq.push_back(p9);
207                 this->seq.push_back(p10); this->seq.push_back(p11); this->seq.push_back(p12);
208         }
209
210         container(const ex & p1, const ex & p2, const ex & p3,
211                   const ex & p4, const ex & p5, const ex & p6,
212                   const ex & p7, const ex & p8, const ex & p9,
213                   const ex & p10, const ex & p11, const ex & p12,
214                   const ex & p13) : inherited(get_tinfo())
215         {
216                 reserve(this->seq, 13);
217                 this->seq.push_back(p1); this->seq.push_back(p2); this->seq.push_back(p3);
218                 this->seq.push_back(p4); this->seq.push_back(p5); this->seq.push_back(p6);
219                 this->seq.push_back(p7); this->seq.push_back(p8); this->seq.push_back(p9);
220                 this->seq.push_back(p10); this->seq.push_back(p11); this->seq.push_back(p12);
221                 this->seq.push_back(p13);
222         }
223
224         container(const ex & p1, const ex & p2, const ex & p3,
225                   const ex & p4, const ex & p5, const ex & p6,
226                   const ex & p7, const ex & p8, const ex & p9,
227                   const ex & p10, const ex & p11, const ex & p12,
228                   const ex & p13, const ex & p14) : inherited(get_tinfo())
229         {
230                 reserve(this->seq, 14);
231                 this->seq.push_back(p1); this->seq.push_back(p2); this->seq.push_back(p3);
232                 this->seq.push_back(p4); this->seq.push_back(p5); this->seq.push_back(p6);
233                 this->seq.push_back(p7); this->seq.push_back(p8); this->seq.push_back(p9);
234                 this->seq.push_back(p10); this->seq.push_back(p11); this->seq.push_back(p12);
235                 this->seq.push_back(p13); this->seq.push_back(p14);
236         }
237
238         container(const ex & p1, const ex & p2, const ex & p3,
239                   const ex & p4, const ex & p5, const ex & p6,
240                   const ex & p7, const ex & p8, const ex & p9,
241                   const ex & p10, const ex & p11, const ex & p12,
242                   const ex & p13, const ex & p14, const ex & p15) : inherited(get_tinfo())
243         {
244                 reserve(this->seq, 15);
245                 this->seq.push_back(p1); this->seq.push_back(p2); this->seq.push_back(p3);
246                 this->seq.push_back(p4); this->seq.push_back(p5); this->seq.push_back(p6);
247                 this->seq.push_back(p7); this->seq.push_back(p8); this->seq.push_back(p9);
248                 this->seq.push_back(p10); this->seq.push_back(p11); this->seq.push_back(p12);
249                 this->seq.push_back(p13); this->seq.push_back(p14); this->seq.push_back(p15);
250         }
251
252         container(const ex & p1, const ex & p2, const ex & p3,
253                   const ex & p4, const ex & p5, const ex & p6,
254                   const ex & p7, const ex & p8, const ex & p9,
255                   const ex & p10, const ex & p11, const ex & p12,
256                   const ex & p13, const ex & p14, const ex & p15,
257                   const ex & p16) : inherited(get_tinfo())
258         {
259                 reserve(this->seq, 16);
260                 this->seq.push_back(p1); this->seq.push_back(p2); this->seq.push_back(p3);
261                 this->seq.push_back(p4); this->seq.push_back(p5); this->seq.push_back(p6);
262                 this->seq.push_back(p7); this->seq.push_back(p8); this->seq.push_back(p9);
263                 this->seq.push_back(p10); this->seq.push_back(p11); this->seq.push_back(p12);
264                 this->seq.push_back(p13); this->seq.push_back(p14); this->seq.push_back(p15);
265                 this->seq.push_back(p16);
266         }
267
268         // functions overriding virtual functions from base classes
269 public:
270         bool info(unsigned inf) const { return inherited::info(inf); }
271         unsigned precedence() const { return 10; }
272         size_t nops() const { return this->seq.size(); }
273         ex op(size_t i) const;
274         ex & let_op(size_t i);
275         ex eval(int level = 0) const;
276         ex subs(const exmap & m, unsigned options = 0) const;
277
278 protected:
279         bool is_equal_same_type(const basic & other) const;
280
281         // new virtual functions which can be overridden by derived classes
282 protected:
283         /** Similar to duplicate(), but with a preset sequence. Must be
284          *  overridden by derived classes. */
285         virtual ex thiscontainer(const STLT & v) const { return container(v); }
286
287         /** Similar to duplicate(), but with a preset sequence (which gets
288          *  deleted). Must be overridden by derived classes. */
289         virtual ex thiscontainer(std::auto_ptr<STLT> vp) const { return container(vp); }
290
291         virtual void printseq(const print_context & c, char openbracket, char delim,
292                               char closebracket, unsigned this_precedence,
293                               unsigned upper_precedence = 0) const;
294
295         // non-virtual functions in this class
296 private:
297         void sort_(std::random_access_iterator_tag)
298         {
299                 std::sort(this->seq.begin(), this->seq.end(), ex_is_less());
300         }
301
302         void sort_(std::input_iterator_tag)
303         {
304                 this->seq.sort(ex_is_less());
305         }
306
307         void unique_()
308         {
309                 typename STLT::iterator p = std::unique(this->seq.begin(), this->seq.end(), ex_is_equal());
310                 this->seq.erase(p, this->seq.end());
311         }
312
313 public:
314         container & prepend(const ex & b);
315         container & append(const ex & b);
316         container & remove_first();
317         container & remove_last();
318         container & remove_all();
319         container & sort();
320         container & unique();
321
322         const_iterator begin() const {return this->seq.begin();}
323         const_iterator end() const {return this->seq.end();}
324         const_reverse_iterator rbegin() const {return this->seq.rbegin();}
325         const_reverse_iterator rend() const {return this->seq.rend();}
326
327 protected:
328         void do_print(const print_context & c, unsigned level) const;
329         void do_print_tree(const print_tree & c, unsigned level) const;
330         void do_print_python(const print_python & c, unsigned level) const;
331         void do_print_python_repr(const print_python_repr & c, unsigned level) const;
332         STLT evalchildren(int level) const;
333         std::auto_ptr<STLT> subschildren(const exmap & m, unsigned options = 0) const;
334 };
335
336 /** Default constructor */
337 template <template <class> class C>
338 container<C>::container() : inherited(get_tinfo()) {}
339
340 /** Construct object from archive_node. */
341 template <template <class> class C>
342 container<C>::container(const archive_node &n, lst &sym_lst) : inherited(n, sym_lst)
343 {
344         for (unsigned int i=0; true; i++) {
345                 ex e;
346                 if (n.find_ex("seq", e, sym_lst, i))
347                         this->seq.push_back(e);
348                 else
349                         break;
350         }
351 }
352
353 /** Unarchive the object. */
354 template <template <class> class C>
355 ex container<C>::unarchive(const archive_node &n, lst &sym_lst)
356 {
357         return (new container(n, sym_lst))->setflag(status_flags::dynallocated);
358 }
359
360 /** Archive the object. */
361 template <template <class> class C>
362 void container<C>::archive(archive_node &n) const
363 {
364         inherited::archive(n);
365         const_iterator i = this->seq.begin(), end = this->seq.end();
366         while (i != end) {
367                 n.add_ex("seq", *i);
368                 ++i;
369         }
370 }
371
372 template <template <class> class C>
373 void container<C>::do_print(const print_context & c, unsigned level) const
374 {
375         // always print brackets around seq, ignore upper_precedence
376         printseq(c, get_open_delim(), ',', get_close_delim(), precedence(), precedence()+1);
377 }
378
379 template <template <class> class C>
380 void container<C>::do_print_tree(const print_tree & c, unsigned level) const
381 {
382         c.s << std::string(level, ' ') << class_name()
383             << std::hex << ", hash=0x" << hashvalue << ", flags=0x" << flags << std::dec
384             << ", nops=" << nops()
385             << std::endl;
386         const_iterator i = this->seq.begin(), end = this->seq.end();
387         while (i != end) {
388                 i->print(c, level + c.delta_indent);
389                 ++i;
390         }
391         c.s << std::string(level + c.delta_indent,' ') << "=====" << std::endl;
392 }
393
394 template <template <class> class C>
395 void container<C>::do_print_python(const print_python & c, unsigned level) const
396 {
397         printseq(c, '[', ',', ']', precedence(), precedence()+1);
398 }
399
400 template <template <class> class C>
401 void container<C>::do_print_python_repr(const print_python_repr & c, unsigned level) const
402 {
403         c.s << class_name();
404         printseq(c, '(', ',', ')', precedence(), precedence()+1);
405 }
406
407 template <template <class> class C>
408 ex container<C>::op(size_t i) const
409 {
410         GINAC_ASSERT(i < nops());
411
412         const_iterator it = this->seq.begin();
413         advance(it, i);
414         return *it;
415 }
416
417 template <template <class> class C>
418 ex & container<C>::let_op(size_t i)
419 {
420         GINAC_ASSERT(i < nops());
421
422         ensure_if_modifiable();
423         typename STLT::iterator it = this->seq.begin();
424         advance(it, i);
425         return *it;
426 }
427
428 template <template <class> class C>
429 ex container<C>::eval(int level) const
430 {
431         if (level == 1)
432                 return hold();
433         else
434                 return thiscontainer(evalchildren(level));
435 }
436
437 template <template <class> class C>
438 ex container<C>::subs(const exmap & m, unsigned options) const
439 {
440         std::auto_ptr<STLT> vp = subschildren(m, options);
441         if (vp.get())
442                 return ex_to<basic>(thiscontainer(vp)).subs_one_level(m, options);
443         else
444                 return subs_one_level(m, options);
445 }
446
447 /** Compare two containers of the same type. */
448 template <template <class> class C>
449 int container<C>::compare_same_type(const basic & other) const
450 {
451         GINAC_ASSERT(is_a<container>(other));
452         const container & o = static_cast<const container &>(other);
453
454         const_iterator it1 = this->seq.begin(), it1end = this->seq.end(),
455                        it2 = o.seq.begin(), it2end = o.seq.end();
456
457         while (it1 != it1end && it2 != it2end) {
458                 int cmpval = it1->compare(*it2);
459                 if (cmpval)
460                         return cmpval;
461                 ++it1; ++it2;
462         }
463
464         return (it1 == it1end) ? (it2 == it2end ? 0 : -1) : 1;
465 }
466
467 template <template <class> class C>
468 bool container<C>::is_equal_same_type(const basic & other) const
469 {
470         GINAC_ASSERT(is_a<container>(other));
471         const container & o = static_cast<const container &>(other);
472
473         if (this->seq.size() != o.seq.size())
474                 return false;
475
476         const_iterator it1 = this->seq.begin(), it1end = this->seq.end(), it2 = o.seq.begin();
477         while (it1 != it1end) {
478                 if (!it1->is_equal(*it2))
479                         return false;
480                 ++it1; ++it2;
481         }
482
483         return true;
484 }
485
486 /** Add element at front. */
487 template <template <class> class C>
488 container<C> & container<C>::prepend(const ex & b)
489 {
490         ensure_if_modifiable();
491         this->seq.push_front(b);
492         return *this;
493 }
494
495 /** Add element at back. */
496 template <template <class> class C>
497 container<C> & container<C>::append(const ex & b)
498 {
499         ensure_if_modifiable();
500         this->seq.push_back(b);
501         return *this;
502 }
503
504 /** Remove first element. */
505 template <template <class> class C>
506 container<C> & container<C>::remove_first()
507 {
508         ensure_if_modifiable();
509         this->seq.pop_front();
510         return *this;
511 }
512
513 /** Remove last element. */
514 template <template <class> class C>
515 container<C> & container<C>::remove_last()
516 {
517         ensure_if_modifiable();
518         this->seq.pop_back();
519         return *this;
520 }
521
522 /** Remove all elements. */
523 template <template <class> class C>
524 container<C> & container<C>::remove_all()
525 {
526         ensure_if_modifiable();
527         this->seq.clear();
528         return *this;
529 }
530
531 /** Sort elements. */
532 template <template <class> class C>
533 container<C> & container<C>::sort()
534 {
535         ensure_if_modifiable();
536         sort_(typename std::iterator_traits<typename STLT::iterator>::iterator_category());
537         return *this;
538 }
539
540 /** Specialization of container::unique_() for std::list. */
541 inline void container<std::list>::unique_()
542 {
543         this->seq.unique(ex_is_equal());
544 }
545
546 /** Remove adjacent duplicate elements. */
547 template <template <class> class C>
548 container<C> & container<C>::unique()
549 {
550         ensure_if_modifiable();
551         unique_();
552         return *this;
553 }
554
555 /** Print sequence of contained elements. */
556 template <template <class> class C>
557 void container<C>::printseq(const print_context & c, char openbracket, char delim,
558                             char closebracket, unsigned this_precedence,
559                             unsigned upper_precedence) const
560 {
561         if (this_precedence <= upper_precedence)
562                 c.s << openbracket;
563
564         if (!this->seq.empty()) {
565                 const_iterator it = this->seq.begin(), itend = this->seq.end();
566                 --itend;
567                 while (it != itend) {
568                         it->print(c, this_precedence);
569                         c.s << delim;
570                         ++it;
571                 }
572                 it->print(c, this_precedence);
573         }
574
575         if (this_precedence <= upper_precedence)
576                 c.s << closebracket;
577 }
578
579 template <template <class> class C>
580 typename container<C>::STLT container<C>::evalchildren(int level) const
581 {
582         if (level == 1)
583                 return this->seq;
584         else if (level == -max_recursion_level)
585                 throw std::runtime_error("max recursion level reached");
586
587         STLT s;
588         reserve(s, this->seq.size());
589
590         --level;
591         const_iterator it = this->seq.begin(), itend = this->seq.end();
592         while (it != itend) {
593                 s.push_back(it->eval(level));
594                 ++it;
595         }
596
597         return s;
598 }
599
600 template <template <class> class C>
601 std::auto_ptr<typename container<C>::STLT> container<C>::subschildren(const exmap & m, unsigned options) const
602 {
603         // returns a NULL pointer if nothing had to be substituted
604         // returns a pointer to a newly created epvector otherwise
605         // (and relinquishes responsibility for the epvector)
606
607         const_iterator cit = this->seq.begin(), end = this->seq.end();
608         while (cit != end) {
609                 const ex & subsed_ex = cit->subs(m, options);
610                 if (!are_ex_trivially_equal(*cit, subsed_ex)) {
611
612                         // copy first part of seq which hasn't changed
613                         std::auto_ptr<STLT> s(new STLT(this->seq.begin(), cit));
614                         reserve(*s, this->seq.size());
615
616                         // insert changed element
617                         s->push_back(subsed_ex);
618                         ++cit;
619
620                         // copy rest
621                         while (cit != end) {
622                                 s->push_back(cit->subs(m, options));
623                                 ++cit;
624                         }
625
626                         return s;
627                 }
628
629                 ++cit;
630         }
631         
632         return std::auto_ptr<STLT>(0); // nothing has changed
633 }
634
635 } // namespace GiNaC
636
637 #endif // ndef __GINAC_CONTAINER_H__