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