]> www.ginac.de Git - ginac.git/blobdiff - ginac/expairseq.cpp
- Do not bother to rename indices if object has no indices at all [Sheplyakov].
[ginac.git] / ginac / expairseq.cpp
index 9f580d9e768ff4ac58c5fcaaa0865124ad7069fd..788f7834f4a5fc82a1a713e1f770ecaa194abdb0 100644 (file)
@@ -3,7 +3,7 @@
  *  Implementation of sequences of expression pairs. */
 
 /*
- *  GiNaC Copyright (C) 1999-2005 Johannes Gutenberg University Mainz, Germany
+ *  GiNaC Copyright (C) 1999-2007 Johannes Gutenberg University Mainz, Germany
  *
  *  This program is free software; you can redistribute it and/or modify
  *  it under the terms of the GNU General Public License as published by
 #include <algorithm>
 #include <string>
 #include <stdexcept>
+#include <iterator>
 
 #include "expairseq.h"
 #include "lst.h"
+#include "add.h"
 #include "mul.h"
 #include "power.h"
 #include "relational.h"
@@ -67,7 +69,7 @@ public:
 
 // public
 
-expairseq::expairseq() : inherited(TINFO_expairseq)
+expairseq::expairseq() : inherited(&expairseq::tinfo_static)
 #if EXPAIRSEQ_USE_HASHTAB
                                                    , hashtabsize(0)
 #endif // EXPAIRSEQ_USE_HASHTAB
@@ -106,32 +108,32 @@ void expairseq::copy(const expairseq &other)
 // other constructors
 //////////
 
-expairseq::expairseq(const ex &lh, const ex &rh) : inherited(TINFO_expairseq)
+expairseq::expairseq(const ex &lh, const ex &rh) : inherited(&expairseq::tinfo_static)
 {
        construct_from_2_ex(lh,rh);
        GINAC_ASSERT(is_canonical());
 }
 
-expairseq::expairseq(const exvector &v) : inherited(TINFO_expairseq)
+expairseq::expairseq(const exvector &v) : inherited(&expairseq::tinfo_static)
 {
        construct_from_exvector(v);
        GINAC_ASSERT(is_canonical());
 }
 
-expairseq::expairseq(const epvector &v, const ex &oc)
-  : inherited(TINFO_expairseq), overall_coeff(oc)
+expairseq::expairseq(const epvector &v, const ex &oc, bool do_index_renaming)
+  : inherited(&expairseq::tinfo_static), overall_coeff(oc)
 {
        GINAC_ASSERT(is_a<numeric>(oc));
-       construct_from_epvector(v);
+       construct_from_epvector(v, do_index_renaming);
        GINAC_ASSERT(is_canonical());
 }
 
-expairseq::expairseq(std::auto_ptr<epvector> vp, const ex &oc)
-  : inherited(TINFO_expairseq), overall_coeff(oc)
+expairseq::expairseq(std::auto_ptr<epvector> vp, const ex &oc, bool do_index_renaming)
+  : inherited(&expairseq::tinfo_static), overall_coeff(oc)
 {
        GINAC_ASSERT(vp.get()!=0);
        GINAC_ASSERT(is_a<numeric>(oc));
-       construct_from_epvector(*vp);
+       construct_from_epvector(*vp, do_index_renaming);
        GINAC_ASSERT(is_canonical());
 }
 
@@ -144,13 +146,17 @@ expairseq::expairseq(const archive_node &n, lst &sym_lst) : inherited(n, sym_lst
        , hashtabsize(0)
 #endif
 {
-       for (unsigned int i=0; true; i++) {
+       archive_node::archive_node_cit first = n.find_first("rest");
+       archive_node::archive_node_cit last = n.find_last("coeff");
+       ++last;
+       seq.reserve((last-first)/2);
+
+       for (archive_node::archive_node_cit loc = first; loc < last;) {
                ex rest;
                ex coeff;
-               if (n.find_ex("rest", rest, sym_lst, i) && n.find_ex("coeff", coeff, sym_lst, i))
-                       seq.push_back(expair(rest, coeff));
-               else
-                       break;
+               n.find_ex_by_loc(loc++, rest, sym_lst);
+               n.find_ex_by_loc(loc++, coeff, sym_lst);
+               seq.push_back(expair(rest, coeff));
        }
 
        n.find_ex("overall_coeff", overall_coeff, sym_lst);
@@ -262,6 +268,26 @@ void expairseq::do_print_tree(const print_tree & c, unsigned level) const
 
 bool expairseq::info(unsigned inf) const
 {
+       switch(inf) {
+               case info_flags::expanded:
+                       return (flags & status_flags::expanded);
+               case info_flags::has_indices: {
+                       if (flags & status_flags::has_indices)
+                               return true;
+                       else if (flags & status_flags::has_no_indices)
+                               return false;
+                       for (epvector::const_iterator i = seq.begin(); i != seq.end(); ++i) {
+                               if (i->rest.info(info_flags::has_indices)) {
+                                       this->setflag(status_flags::has_indices);
+                                       this->clearflag(status_flags::has_no_indices);
+                                       return true;
+                               }
+                       }
+                       this->clearflag(status_flags::has_indices);
+                       this->setflag(status_flags::has_no_indices);
+                       return false;
+               }
+       }
        return inherited::info(inf);
 }
 
@@ -284,7 +310,7 @@ ex expairseq::op(size_t i) const
 ex expairseq::map(map_function &f) const
 {
        std::auto_ptr<epvector> v(new epvector);
-       v->reserve(seq.size());
+       v->reserve(seq.size()+1);
 
        epvector::const_iterator cit = seq.begin(), last = seq.end();
        while (cit != last) {
@@ -293,9 +319,16 @@ ex expairseq::map(map_function &f) const
        }
 
        if (overall_coeff.is_equal(default_overall_coeff()))
-               return thisexpairseq(v, default_overall_coeff());
-       else
-               return thisexpairseq(v, f(overall_coeff));
+               return thisexpairseq(v, default_overall_coeff(), true);
+       else {
+               ex newcoeff = f(overall_coeff);
+               if(is_a<numeric>(newcoeff))
+                       return thisexpairseq(v, newcoeff, true);
+               else {
+                       v->push_back(split_ex_to_pair(newcoeff));
+                       return thisexpairseq(v, default_overall_coeff(), true);
+               }
+       }
 }
 
 /** Perform coefficient-wise automatic term rewriting rules in this class. */
@@ -347,6 +380,17 @@ ex expairseq::conjugate() const
        return result;
 }
 
+bool expairseq::is_polynomial(const ex & var) const
+{
+       if (!is_exactly_a<add>(*this) && !is_exactly_a<mul>(*this))
+               return basic::is_polynomial(var);
+       for (epvector::const_iterator i=seq.begin(); i!=seq.end(); ++i) {
+               if (!(i->rest).is_polynomial(var))
+                       return false;
+       }
+       return true;
+}
+
 bool expairseq::match(const ex & pattern, lst & repl_lst) const
 {
        // This differs from basic::match() because we want "a+b+c+d" to
@@ -383,10 +427,20 @@ bool expairseq::match(const ex & pattern, lst & repl_lst) const
                                continue;
                        exvector::iterator it = ops.begin(), itend = ops.end();
                        while (it != itend) {
+                               lst::const_iterator last_el = repl_lst.end();
+                               --last_el;
                                if (it->match(p, repl_lst)) {
                                        ops.erase(it);
                                        goto found;
                                }
+                               while(true) {
+                                       lst::const_iterator next_el = last_el;
+                                       ++next_el;
+                                       if(next_el == repl_lst.end())
+                                               break;
+                                       else
+                                               repl_lst.remove_last();
+                               }
                                ++it;
                        }
                        return false; // no match found
@@ -425,7 +479,7 @@ ex expairseq::subs(const exmap & m, unsigned options) const
 {
        std::auto_ptr<epvector> vp = subschildren(m, options);
        if (vp.get())
-               return ex_to<basic>(thisexpairseq(vp, overall_coeff));
+               return ex_to<basic>(thisexpairseq(vp, overall_coeff, true));
        else if ((options & subs_options::algebraic) && is_exactly_a<mul>(*this))
                return static_cast<const mul *>(this)->algebraic_subs_mul(m, options);
        else
@@ -571,7 +625,7 @@ unsigned expairseq::return_type() const
 
 unsigned expairseq::calchash() const
 {
-       unsigned v = golden_ratio_hash(this->tinfo());
+       unsigned v = golden_ratio_hash((p_int)this->tinfo());
        epvector::const_iterator i = seq.begin();
        const epvector::const_iterator end = seq.end();
        while (i != end) {
@@ -620,14 +674,14 @@ ex expairseq::expand(unsigned options) const
  *  ctor because the name (add, mul,...) is unknown on the expaiseq level.  In
  *  order for this trick to work a derived class must of course override this
  *  definition. */
-ex expairseq::thisexpairseq(const epvector &v, const ex &oc) const
+ex expairseq::thisexpairseq(const epvector &v, const ex &oc, bool do_index_renaming) const
 {
-       return expairseq(v, oc);
+       return expairseq(v, oc, do_index_renaming);
 }
 
-ex expairseq::thisexpairseq(std::auto_ptr<epvector> vp, const ex &oc) const
+ex expairseq::thisexpairseq(std::auto_ptr<epvector> vp, const ex &oc, bool do_index_renaming) const
 {
-       return expairseq(vp, oc);
+       return expairseq(vp, oc, do_index_renaming);
 }
 
 void expairseq::printpair(const print_context & c, const expair & p, unsigned upper_precedence) const
@@ -758,8 +812,8 @@ void expairseq::construct_from_2_ex(const ex &lh, const ex &rh)
                                construct_from_2_ex_via_exvector(lh,rh);
                        } else {
 #endif // EXPAIRSEQ_USE_HASHTAB
-                               if(is_a<mul>(lh))
-                               {       
+                               if (is_a<mul>(lh) && lh.info(info_flags::has_indices) && 
+                                       rh.info(info_flags::has_indices)) {
                                        ex newrh=rename_dummy_indices_uniquely(lh, rh);
                                        construct_from_2_expairseq(ex_to<expairseq>(lh),
                                                                   ex_to<expairseq>(newrh));
@@ -861,6 +915,7 @@ void expairseq::construct_from_2_expairseq(const expairseq &s1,
        
        while (first1!=last1 && first2!=last2) {
                int cmpval = (*first1).rest.compare((*first2).rest);
+
                if (cmpval==0) {
                        // combine terms
                        const numeric &newcoeff = ex_to<numeric>(first1->coeff).
@@ -976,14 +1031,14 @@ void expairseq::construct_from_exvector(const exvector &v)
 #endif // EXPAIRSEQ_USE_HASHTAB
 }
 
-void expairseq::construct_from_epvector(const epvector &v)
+void expairseq::construct_from_epvector(const epvector &v, bool do_index_renaming)
 {
        // simplifications: +(a,+(b,c),d) -> +(a,b,c,d) (associativity)
        //                  +(d,b,c,a) -> +(a,b,c,d) (canonicalization)
        //                  +(...,x,*(x,c1),*(x,c2)) -> +(...,*(x,1+c1+c2)) (c1, c2 numeric())
        //                  (same for (+,*) -> (*,^)
 
-       make_flat(v);
+       make_flat(v, do_index_renaming);
 #if EXPAIRSEQ_USE_HASHTAB
        combine_same_terms();
 #else
@@ -1002,6 +1057,7 @@ void expairseq::make_flat(const exvector &v)
        // and their cumulative number of operands
        int nexpairseqs = 0;
        int noperands = 0;
+       bool do_idx_rename = false;
        
        cit = v.begin();
        while (cit!=v.end()) {
@@ -1009,6 +1065,9 @@ void expairseq::make_flat(const exvector &v)
                        ++nexpairseqs;
                        noperands += ex_to<expairseq>(*cit).seq.size();
                }
+               if (is_a<mul>(*this) && (!do_idx_rename) &&
+                               cit->info(info_flags::has_indices))
+                       do_idx_rename = true;
                ++cit;
        }
        
@@ -1016,35 +1075,25 @@ void expairseq::make_flat(const exvector &v)
        seq.reserve(v.size()+noperands-nexpairseqs);
        
        // copy elements and split off numerical part
-       exvector dummy_indices;
+       make_flat_inserter mf(v, do_idx_rename);
        cit = v.begin();
        while (cit!=v.end()) {
                if (ex_to<basic>(*cit).tinfo()==this->tinfo()) {
-                       const expairseq *subseqref;
-                       ex newfactor;
-                       if(is_a<mul>(*cit))
-                       {
-                               exvector dummies_of_factor = get_all_dummy_indices(*cit);
-                               sort(dummies_of_factor.begin(), dummies_of_factor.end(), ex_is_less());
-                               newfactor = rename_dummy_indices_uniquely(dummy_indices, dummies_of_factor, *cit);
-                               subseqref = &(ex_to<expairseq>(newfactor));
-                               exvector new_dummy_indices;
-                               set_union(dummy_indices.begin(), dummy_indices.end(), dummies_of_factor.begin(), dummies_of_factor.end(), std::back_insert_iterator<exvector>(new_dummy_indices), ex_is_less());
-                               dummy_indices.swap(new_dummy_indices);
-                       }
-                       else
-                               subseqref = &ex_to<expairseq>(*cit);
-                       combine_overall_coeff(subseqref->overall_coeff);
-                       epvector::const_iterator cit_s = subseqref->seq.begin();
-                       while (cit_s!=subseqref->seq.end()) {
+                       ex newfactor = mf.handle_factor(*cit, _ex1);
+                       const expairseq &subseqref = ex_to<expairseq>(newfactor);
+                       combine_overall_coeff(subseqref.overall_coeff);
+                       epvector::const_iterator cit_s = subseqref.seq.begin();
+                       while (cit_s!=subseqref.seq.end()) {
                                seq.push_back(*cit_s);
                                ++cit_s;
                        }
                } else {
                        if (is_exactly_a<numeric>(*cit))
                                combine_overall_coeff(*cit);
-                       else
-                               seq.push_back(split_ex_to_pair(*cit));
+                       else {
+                               ex newfactor = mf.handle_factor(*cit, _ex1);
+                               seq.push_back(split_ex_to_pair(newfactor));
+                       }
                }
                ++cit;
        }
@@ -1052,7 +1101,7 @@ void expairseq::make_flat(const exvector &v)
 
 /** Combine this expairseq with argument epvector.
  *  It cares for associativity as well as for special handling of numerics. */
-void expairseq::make_flat(const epvector &v)
+void expairseq::make_flat(const epvector &v, bool do_index_renaming)
 {
        epvector::const_iterator cit;
        
@@ -1060,6 +1109,7 @@ void expairseq::make_flat(const epvector &v)
        // and their cumulative number of operands
        int nexpairseqs = 0;
        int noperands = 0;
+       bool really_need_rename_inds = false;
        
        cit = v.begin();
        while (cit!=v.end()) {
@@ -1067,18 +1117,24 @@ void expairseq::make_flat(const epvector &v)
                        ++nexpairseqs;
                        noperands += ex_to<expairseq>(cit->rest).seq.size();
                }
+               if ((!really_need_rename_inds) && is_a<mul>(*this) &&
+                               cit->rest.info(info_flags::has_indices))
+                       really_need_rename_inds = true;
                ++cit;
        }
+       do_index_renaming = do_index_renaming && really_need_rename_inds;
        
        // reserve seq and coeffseq which will hold all operands
        seq.reserve(v.size()+noperands-nexpairseqs);
+       make_flat_inserter mf(v, do_index_renaming);
        
        // copy elements and split off numerical part
        cit = v.begin();
        while (cit!=v.end()) {
                if (ex_to<basic>(cit->rest).tinfo()==this->tinfo() &&
                    this->can_make_flat(*cit)) {
-                       const expairseq &subseqref = ex_to<expairseq>(cit->rest);
+                       ex newrest = mf.handle_factor(cit->rest, cit->coeff);
+                       const expairseq &subseqref = ex_to<expairseq>(newrest);
                        combine_overall_coeff(ex_to<numeric>(subseqref.overall_coeff),
                                                            ex_to<numeric>(cit->coeff));
                        epvector::const_iterator cit_s = subseqref.seq.begin();
@@ -1091,9 +1147,15 @@ void expairseq::make_flat(const epvector &v)
                        }
                } else {
                        if (cit->is_canonical_numeric())
-                               combine_overall_coeff(cit->rest);
-                       else
-                               seq.push_back(*cit);
+                               combine_overall_coeff(mf.handle_factor(cit->rest, _ex1));
+                       else {
+                               ex rest = cit->rest;
+                               ex newrest = mf.handle_factor(rest, cit->coeff);
+                               if (are_ex_trivially_equal(newrest, rest))
+                                       seq.push_back(*cit);
+                               else
+                                       seq.push_back(expair(newrest, cit->coeff));
+                       }
                }
                ++cit;
        }
@@ -1601,68 +1663,6 @@ std::auto_ptr<epvector> expairseq::evalchildren(int level) const
        return std::auto_ptr<epvector>(0); // signalling nothing has changed
 }
 
-class safe_inserter
-{
-       public:
-               safe_inserter(const ex&, const bool disable_renaming=false);
-               std::auto_ptr<epvector> getseq(){return epv;}
-               void insert_old_pair(const expair &p)
-               {
-                       epv->push_back(p);
-               }
-               void insert_new_pair(const expair &p, const ex &orig_ex);
-       private:
-               std::auto_ptr<epvector> epv;
-               bool dodummies;
-               exvector dummy_indices;
-               void update_dummy_indices(const exvector&);
-};
-
-safe_inserter::safe_inserter(const ex&e, const bool disable_renaming)
-               :epv(new epvector)
-{
-       epv->reserve(e.nops());
-       dodummies=is_a<mul>(e);
-       if(disable_renaming)
-               dodummies=false;
-       if(dodummies) {
-               dummy_indices = get_all_dummy_indices(e);
-               sort(dummy_indices.begin(), dummy_indices.end(), ex_is_less());
-       }
-}
-
-void safe_inserter::update_dummy_indices(const exvector &v)
-{
-       exvector new_dummy_indices;
-       set_union(dummy_indices.begin(), dummy_indices.end(), v.begin(), v.end(),
-               std::back_insert_iterator<exvector>(new_dummy_indices), ex_is_less());
-       dummy_indices.swap(new_dummy_indices);
-}
-
-void safe_inserter::insert_new_pair(const expair &p, const ex &orig_ex)
-{
-       if(!dodummies) {
-               epv->push_back(p);
-               return;
-       }
-       exvector dummies_of_factor = get_all_dummy_indices(p.rest);
-       if(dummies_of_factor.size() == 0) {
-               epv->push_back(p);
-               return;
-       }
-       sort(dummies_of_factor.begin(), dummies_of_factor.end(), ex_is_less());
-       exvector dummies_of_orig_ex = get_all_dummy_indices(orig_ex);
-       sort(dummies_of_orig_ex.begin(), dummies_of_orig_ex.end(), ex_is_less());
-       exvector new_dummy_indices;
-       new_dummy_indices.reserve(dummy_indices.size());
-       set_difference(dummy_indices.begin(), dummy_indices.end(), dummies_of_orig_ex.begin(), dummies_of_orig_ex.end(),
-               std::back_insert_iterator<exvector>(new_dummy_indices), ex_is_less());
-       dummy_indices.swap(new_dummy_indices);
-       ex newfactor = rename_dummy_indices_uniquely(dummy_indices, dummies_of_factor, p.rest);
-       update_dummy_indices(dummies_of_factor);
-       epv -> push_back(expair(newfactor, p.coeff));
-}
-
 /** Member-wise substitute in this sequence.
  *
  *  @see expairseq::subs()
@@ -1697,27 +1697,22 @@ std::auto_ptr<epvector> expairseq::subschildren(const exmap & m, unsigned option
                        if (!are_ex_trivially_equal(orig_ex, subsed_ex)) {
 
                                // Something changed, copy seq, subs and return it
-                               safe_inserter s(*this, options & subs_options::no_index_renaming);
+                               std::auto_ptr<epvector> s(new epvector);
+                               s->reserve(seq.size());
 
                                // Copy parts of seq which are known not to have changed
-                               for(epvector::const_iterator i=seq.begin(); i!=cit; ++i)
-                                       s.insert_old_pair(*i);
+                               s->insert(s->begin(), seq.begin(), cit);
 
                                // Copy first changed element
-                               s.insert_new_pair(split_ex_to_pair(subsed_ex), orig_ex);
+                               s->push_back(split_ex_to_pair(subsed_ex));
                                ++cit;
 
                                // Copy rest
                                while (cit != last) {
-                                       ex orig_ex = recombine_pair_to_ex(*cit);
-                                       ex subsed_ex = orig_ex.subs(m, options);
-                                       if(are_ex_trivially_equal(orig_ex, subsed_ex))
-                                               s.insert_old_pair(*cit);
-                                       else
-                                               s.insert_new_pair(split_ex_to_pair(subsed_ex), orig_ex);
+                                       s->push_back(split_ex_to_pair(recombine_pair_to_ex(*cit).subs(m, options)));
                                        ++cit;
                                }
-                               return s.getseq();
+                               return s;
                        }
 
                        ++cit;
@@ -1733,27 +1728,22 @@ std::auto_ptr<epvector> expairseq::subschildren(const exmap & m, unsigned option
                        if (!are_ex_trivially_equal(cit->rest, subsed_ex)) {
                        
                                // Something changed, copy seq, subs and return it
-                               safe_inserter s(*this, options & subs_options::no_index_renaming);
+                               std::auto_ptr<epvector> s(new epvector);
+                               s->reserve(seq.size());
 
                                // Copy parts of seq which are known not to have changed
-                               for(epvector::const_iterator i=seq.begin(); i!=cit; ++i)
-                                       s.insert_old_pair(*i);
+                               s->insert(s->begin(), seq.begin(), cit);
                        
                                // Copy first changed element
-                               s.insert_new_pair(combine_ex_with_coeff_to_pair(subsed_ex, cit->coeff), cit->rest);
+                               s->push_back(combine_ex_with_coeff_to_pair(subsed_ex, cit->coeff));
                                ++cit;
 
                                // Copy rest
                                while (cit != last) {
-                                       const ex &orig_ex = cit->rest;
-                                       const ex &subsed_ex = cit->rest.subs(m, options);
-                                       if(are_ex_trivially_equal(orig_ex, subsed_ex))
-                                               s.insert_old_pair(*cit);
-                                       else
-                                               s.insert_new_pair(combine_ex_with_coeff_to_pair(subsed_ex, cit->coeff), orig_ex);
+                                       s->push_back(combine_ex_with_coeff_to_pair(cit->rest.subs(m, options), cit->coeff));
                                        ++cit;
                                }
-                               return s.getseq();
+                               return s;
                        }
 
                        ++cit;