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