match() (find()): use exmap (exset) to store matched subexpressions.

There's no need to re-invent associative arrays and wrap them into
a GiNaC class.

diff --git a/check/match_bug.cpp b/check/match_bug.cpp
index d80faca337daaff09b789e183fcab89ce8ec2b41..df67629b2e421011b3c8a953f4e063090b917e63 100644 (file)
--- a/check/match_bug.cpp
+++ b/check/match_bug.cpp
@@ -25,11 +25,11 @@ static void failed_match_have_side_effects()
        ex e = pow(x, 5);
        ex pattern = pow(wild(0), -1);
        // obviously e does NOT match the pattern
-       lst repl_lst;
-       bool match_p = e.match(pattern, repl_lst);
+       exmap repls;
+       bool match_p = e.match(pattern, repls);
        bug_on(match_p, "match(" << e << ", " << pattern << ") says \"Yes\"");
-       bug_on(repl_lst.nops() != 0,
-               "failed match have side effects: repl_lst = " << repl_lst);
+       bug_on(repls.size() != 0,
+               "failed match have side effects: repls = " << repls);
 }
 
 /*
@@ -49,8 +49,8 @@ static void match_false_negative()
        symbol x("x"), y("y");
        ex e = pow(x, 5)*pow(y, -1);
        ex pattern = pow(wild(0), -1)*pow(x, wild(2));
-       lst repl_lst;
-       bool match_p = e.match(pattern, repl_lst);
+       exmap repls;
+       bool match_p = e.match(pattern, repls);
        bug_on(!match_p, "false negative: " << e << " did not match "
                        << pattern);
 }

diff --git a/doc/tutorial/ginac.texi b/doc/tutorial/ginac.texi
index 2f160c7bfb16459bd1d18fd7c46fb9c43273ad27..7254406289eca0b84d70307c1c5d49df8fc8a289 100644 (file)
--- a/doc/tutorial/ginac.texi
+++ b/doc/tutorial/ginac.texi
@@ -4413,14 +4413,14 @@ matches a given pattern. This is done by the function
 
 @example
 bool ex::match(const ex & pattern);
-bool ex::match(const ex & pattern, lst & repls);
+bool ex::match(const ex & pattern, exmap& repls);
 @end example
 
 This function returns @code{true} when the expression matches the pattern
 and @code{false} if it doesn't. If used in the second form, the actual
-subexpressions matched by the wildcards get returned in the @code{repls}
-object as a list of relations of the form @samp{wildcard == expression}.
-If @code{match()} returns false,  @code{repls} remains unmodified.
+subexpressions matched by the wildcards get returned in the associative
+array @code{repls} with @samp{wildcard} as a key. If @code{match()}
+returns false,  @code{repls} remains unmodified.
 
 The matching algorithm works as follows:
 
@@ -4559,7 +4559,7 @@ Again some examples in @command{ginsh} for illustration (in @command{ginsh},
 The method
 
 @example
-bool ex::find(const ex & pattern, lst & found);
+bool ex::find(const ex & pattern, exset& found);
 @end example
 
 works a bit like @code{has()} but it doesn't stop upon finding the first

diff --git a/ginac/basic.cpp b/ginac/basic.cpp
index 7a0633de19a18221f241292b21742416cdb29dce..e8c893ba26dd59a963e00fd1056daf34f4f47bf8 100644 (file)
--- a/ginac/basic.cpp
+++ b/ginac/basic.cpp
@@ -290,7 +290,7 @@ ex & basic::operator[](size_t i)
  *  but e.has(x+y) is false. */
 bool basic::has(const ex & pattern, unsigned options) const
 {
-       lst repl_lst;
+       exmap repl_lst;
        if (match(pattern, repl_lst))
                return true;
        for (size_t i=0; i<nops(); i++)
@@ -534,9 +534,9 @@ bool basic::contract_with(exvector::iterator self, exvector::iterator other, exv
 }
 
 /** Check whether the expression matches a given pattern. For every wildcard
- *  object in the pattern, an expression of the form "wildcard == matching_expression"
- *  is added to repl_lst. */
-bool basic::match(const ex & pattern, lst & repl_lst) const
+ *  object in the pattern, a pair with the wildcard as a key and matching 
+ *  expression as a value is added to repl_lst. */
+bool basic::match(const ex & pattern, exmap& repl_lst) const
 {
 /*
        Sweet sweet shapes, sweet sweet shapes,
@@ -559,11 +559,11 @@ bool basic::match(const ex & pattern, lst & repl_lst) const
                // Wildcard matches anything, but check whether we already have found
                // a match for that wildcard first (if so, the earlier match must be
                // the same expression)
-               for (lst::const_iterator it = repl_lst.begin(); it != repl_lst.end(); ++it) {
-                       if (it->op(0).is_equal(pattern))
-                               return is_equal(ex_to<basic>(it->op(1)));
+               for (exmap::const_iterator it = repl_lst.begin(); it != repl_lst.end(); ++it) {
+                       if (it->first.is_equal(pattern))
+                               return is_equal(ex_to<basic>(it->second));
                }
-               repl_lst.append(pattern == *this);
+               repl_lst[pattern] = *this;
                return true;
 
        } else {
@@ -589,7 +589,7 @@ bool basic::match(const ex & pattern, lst & repl_lst) const
                // its subexpressions could match it. For example, x^5*y^(-1)
                // does not match the pattern $0^5, but its subexpression x^5
                // does. So, save repl_lst in order to not add bogus entries.
-               lst tmp_repl = repl_lst;
+               exmap tmp_repl = repl_lst;
                // Otherwise the subexpressions must match one-to-one
                for (size_t i=0; i<nops(); i++)
                        if (!op(i).match(pattern.op(i), tmp_repl))
@@ -614,9 +614,10 @@ ex basic::subs_one_level(const exmap & m, unsigned options) const
                return thisex;
        } else {
                for (it = m.begin(); it != m.end(); ++it) {
-                       lst repl_lst;
+                       exmap repl_lst;
                        if (match(ex_to<basic>(it->first), repl_lst))
-                               return it->second.subs(repl_lst, options | subs_options::no_pattern); // avoid infinite recursion when re-substituting the wildcards
+                               return it->second.subs(repl_lst, options | subs_options::no_pattern);
+                       // avoid infinite recursion when re-substituting the wildcards
                }
        }
 

diff --git a/ginac/basic.h b/ginac/basic.h
index 348523791a19afa50abd1c84006c49fe003758c8..ffc508dbee0dd48ae4b4d6e18b18b96a4f68b1da 100644 (file)
--- a/ginac/basic.h
+++ b/ginac/basic.h
@@ -163,7 +163,7 @@ public:
 
        // pattern matching
        virtual bool has(const ex & other, unsigned options = 0) const;
-       virtual bool match(const ex & pattern, lst & repl_lst) const;
+       virtual bool match(const ex & pattern, exmap & repls) const;
 protected:
        virtual bool match_same_type(const basic & other) const;
 public:

diff --git a/ginac/ex.cpp b/ginac/ex.cpp
index 23a30833b5a436375918e34358a4208376cf00d6..377b15b411745057cc61fb187468aee19eab9e5d 100644 (file)
--- a/ginac/ex.cpp
+++ b/ginac/ex.cpp
@@ -95,7 +95,7 @@ ex ex::diff(const symbol & s, unsigned nth) const
 /** Check whether expression matches a specified pattern. */
 bool ex::match(const ex & pattern) const
 {
-       lst repl_lst;
+       exmap repl_lst;
        return bp->match(pattern, repl_lst);
 }
 
@@ -103,12 +103,10 @@ bool ex::match(const ex & pattern) const
  *  the "found" list. If the expression itself matches the pattern, the
  *  children are not further examined. This function returns true when any
  *  matches were found. */
-bool ex::find(const ex & pattern, lst & found) const
+bool ex::find(const ex & pattern, exset& found) const
 {
        if (match(pattern)) {
-               found.append(*this);
-               found.sort();
-               found.unique();
+               found.insert(*this);
                return true;
        }
        bool any_found = false;

diff --git a/ginac/ex.h b/ginac/ex.h
index 783c89ee2fc204cdaed11f95d1477e1009180db0..4a603ce03778d441a9bfb1209cfdb0b3995bce2a 100644 (file)
--- a/ginac/ex.h
+++ b/ginac/ex.h
@@ -141,9 +141,9 @@ public:
 
        // pattern matching
        bool has(const ex & pattern, unsigned options = 0) const { return bp->has(pattern, options); }
-       bool find(const ex & pattern, lst & found) const;
+       bool find(const ex & pattern, exset& found) const;
        bool match(const ex & pattern) const;
-       bool match(const ex & pattern, lst & repl_lst) const { return bp->match(pattern, repl_lst); }
+       bool match(const ex & pattern, exmap & repls) const { return bp->match(pattern, repls); }
 
        // substitutions
        ex subs(const exmap & m, unsigned options = 0) const;
@@ -702,7 +702,7 @@ inline ex imag_part(const ex & thisex)
 inline bool has(const ex & thisex, const ex & pattern, unsigned options = 0)
 { return thisex.has(pattern, options); }
 
-inline bool find(const ex & thisex, const ex & pattern, lst & found)
+inline bool find(const ex & thisex, const ex & pattern, exset& found)
 { return thisex.find(pattern, found); }
 
 inline bool is_polynomial(const ex & thisex, const ex & vars)
@@ -762,7 +762,7 @@ inline ex diff(const ex & thisex, const symbol & s, unsigned nth = 1)
 inline ex series(const ex & thisex, const ex & r, int order, unsigned options = 0)
 { return thisex.series(r, order, options); }
 
-inline bool match(const ex & thisex, const ex & pattern, lst & repl_lst)
+inline bool match(const ex & thisex, const ex & pattern, exmap& repl_lst)
 { return thisex.match(pattern, repl_lst); }
 
 inline ex simplify_indexed(const ex & thisex, unsigned options = 0)

diff --git a/ginac/expairseq.cpp b/ginac/expairseq.cpp
index 229710b2fcc922fb04fa09ae443ed84d48e2609f..67aa4f8ef681bf3453eb83fecc0181076edba70e 100644 (file)
--- a/ginac/expairseq.cpp
+++ b/ginac/expairseq.cpp
@@ -391,7 +391,7 @@ bool expairseq::is_polynomial(const ex & var) const
        return true;
 }
 
-bool expairseq::match(const ex & pattern, lst & repl_lst) const
+bool expairseq::match(const ex & pattern, exmap & repl_lst) const
 {
        // This differs from basic::match() because we want "a+b+c+d" to
        // match "d+*+b" with "*" being "a+c", and we want to honor commutativity
@@ -448,11 +448,11 @@ found:            ;
                        for (size_t i=0; i<num; i++)
                                vp->push_back(split_ex_to_pair(ops[i]));
                        ex rest = thisexpairseq(vp, default_overall_coeff());
-                       for (lst::const_iterator it = repl_lst.begin(); it != repl_lst.end(); ++it) {
-                               if (it->op(0).is_equal(global_wildcard))
-                                       return rest.is_equal(it->op(1));
+                       for (exmap::const_iterator it = repl_lst.begin(); it != repl_lst.end(); ++it) {
+                               if (it->first.is_equal(global_wildcard))
+                                       return rest.is_equal(it->second);
                        }
-                       repl_lst.append(global_wildcard == rest);
+                       repl_lst[global_wildcard] = rest;
                        return true;
 
                } else {

diff --git a/ginac/expairseq.h b/ginac/expairseq.h
index 6abd10074eb2036bf55c76ab8724416423d4284f..5f707f7679e19e9780da6586d3e0613deca1dd02 100644 (file)
--- a/ginac/expairseq.h
+++ b/ginac/expairseq.h
@@ -84,7 +84,7 @@ public:
        ex eval(int level=0) const;
        ex to_rational(exmap & repl) const;
        ex to_polynomial(exmap & repl) const;
-       bool match(const ex & pattern, lst & repl_lst) const;
+       bool match(const ex & pattern, exmap& repl_lst) const;
        ex subs(const exmap & m, unsigned options = 0) const;
        ex conjugate() const;
        bool is_polynomial(const ex & var) const;

diff --git a/ginac/mul.cpp b/ginac/mul.cpp
index 3d33c78a129eeaeaaf9074bc291e76624e403da8..63f92e1492d4fae3af2d8467f66793b0cc40bb68 100644 (file)
--- a/ginac/mul.cpp
+++ b/ginac/mul.cpp
@@ -637,7 +637,7 @@ ex mul::eval_ncmul(const exvector & v) const
        return inherited::eval_ncmul(v);
 }
 
-bool tryfactsubs(const ex & origfactor, const ex & patternfactor, int & nummatches, lst & repls)
+bool tryfactsubs(const ex & origfactor, const ex & patternfactor, int & nummatches, exmap& repls)
 {      
        ex origbase;
        int origexponent;
@@ -669,7 +669,7 @@ bool tryfactsubs(const ex & origfactor, const ex & patternfactor, int & nummatch
                patternexpsign = 1;
        }
 
-       lst saverepls = repls;
+       exmap saverepls = repls;
        if (origexponent < patternexponent || origexpsign != patternexpsign || !origbase.match(patternbase,saverepls))
                return false;
        repls = saverepls;
@@ -688,7 +688,7 @@ bool tryfactsubs(const ex & origfactor, const ex & patternfactor, int & nummatch
   * that already have been replaced by previous substitutions and matched[i]
   * is true for factors that have been matched by the current match.
   */
-bool algebraic_match_mul_with_mul(const mul &e, const ex &pat, lst &repls,
+bool algebraic_match_mul_with_mul(const mul &e, const ex &pat, exmap& repls,
                int factor, int &nummatches, const std::vector<bool> &subsed,
                std::vector<bool> &matched)
 {
@@ -698,7 +698,7 @@ bool algebraic_match_mul_with_mul(const mul &e, const ex &pat, lst &repls,
        for (size_t i=0; i<e.nops(); ++i) {
                if(subsed[i] || matched[i])
                        continue;
-               lst newrepls = repls;
+               exmap newrepls = repls;
                int newnummatches = nummatches;
                if (tryfactsubs(e.op(i), pat.op(factor), newnummatches, newrepls)) {
                        matched[i] = true;
@@ -721,7 +721,7 @@ bool mul::has(const ex & pattern, unsigned options) const
        if(!(options&has_options::algebraic))
                return basic::has(pattern,options);
        if(is_a<mul>(pattern)) {
-               lst repls;
+               exmap repls;
                int nummatches = std::numeric_limits<int>::max();
                std::vector<bool> subsed(seq.size(), false);
                std::vector<bool> matched(seq.size(), false);
@@ -745,7 +745,7 @@ ex mul::algebraic_subs_mul(const exmap & m, unsigned options) const
 retry1:
                        int nummatches = std::numeric_limits<int>::max();
                        std::vector<bool> currsubsed(seq.size(), false);
-                       lst repls;
+                       exmap repls;
                        
                        if(!algebraic_match_mul_with_mul(*this, it->first, repls, 0, nummatches, subsed, currsubsed))
                                continue;
@@ -754,10 +754,10 @@ retry1:
                                if (currsubsed[j])
                                        subsed[j] = true;
                        ex subsed_pattern
-                               = it->first.subs(ex(repls), subs_options::no_pattern);
+                               = it->first.subs(repls, subs_options::no_pattern);
                        divide_by *= power(subsed_pattern, nummatches);
                        ex subsed_result
-                               = it->second.subs(ex(repls), subs_options::no_pattern);
+                               = it->second.subs(repls, subs_options::no_pattern);
                        multiply_by *= power(subsed_result, nummatches);
                        goto retry1;
 
@@ -765,14 +765,14 @@ retry1:
 
                        for (size_t j=0; j<this->nops(); j++) {
                                int nummatches = std::numeric_limits<int>::max();
-                               lst repls;
+                               exmap repls;
                                if (!subsed[j] && tryfactsubs(op(j), it->first, nummatches, repls)){
                                        subsed[j] = true;
                                        ex subsed_pattern
-                                               = it->first.subs(ex(repls), subs_options::no_pattern);
+                                               = it->first.subs(repls, subs_options::no_pattern);
                                        divide_by *= power(subsed_pattern, nummatches);
                                        ex subsed_result
-                                               = it->second.subs(ex(repls), subs_options::no_pattern);
+                                               = it->second.subs(repls, subs_options::no_pattern);
                                        multiply_by *= power(subsed_result, nummatches);
                                }
                        }

diff --git a/ginac/power.cpp b/ginac/power.cpp
index ec339b9a660afc6aac21fa9307b6bec5e26144ce..e4a044cb329ddd2422df5c920fdd187abfd1c796 100644 (file)
--- a/ginac/power.cpp
+++ b/ginac/power.cpp
@@ -635,7 +635,7 @@ bool power::has(const ex & other, unsigned options) const
 }
 
 // from mul.cpp
-extern bool tryfactsubs(const ex &, const ex &, int &, lst &);
+extern bool tryfactsubs(const ex &, const ex &, int &, exmap&);
 
 ex power::subs(const exmap & m, unsigned options) const
 {      
@@ -651,9 +651,13 @@ ex power::subs(const exmap & m, unsigned options) const
 
        for (exmap::const_iterator it = m.begin(); it != m.end(); ++it) {
                int nummatches = std::numeric_limits<int>::max();
-               lst repls;
-               if (tryfactsubs(*this, it->first, nummatches, repls))
-                       return (ex_to<basic>((*this) * power(it->second.subs(ex(repls), subs_options::no_pattern) / it->first.subs(ex(repls), subs_options::no_pattern), nummatches))).subs_one_level(m, options);
+               exmap repls;
+               if (tryfactsubs(*this, it->first, nummatches, repls)) {
+                       ex anum = it->second.subs(repls, subs_options::no_pattern);
+                       ex aden = it->first.subs(repls, subs_options::no_pattern);
+                       ex result = (*this)*power(anum/aden, nummatches);
+                       return (ex_to<basic>(result)).subs_one_level(m, options);
+               }
        }
 
        return subs_one_level(m, options);

diff --git a/ginac/structure.h b/ginac/structure.h
index 26dff67beefd88ed12e38ba4a03b25f4e2b212e2..d00100b13ab60e156a10f1ca9c80b8c40fbcad10 100644 (file)
--- a/ginac/structure.h
+++ b/ginac/structure.h
@@ -156,7 +156,7 @@ public:
 
        // pattern matching
        bool has(const ex & other, unsigned options = 0) const { return inherited::has(other, options); }
-       bool match(const ex & pattern, lst & repl_lst) const { return inherited::match(pattern, repl_lst); }
+       bool match(const ex & pattern, exmap& repl_lst) const { return inherited::match(pattern, repl_lst); }
 protected:
        bool match_same_type(const basic & other) const { return true; }
 public:

diff --git a/ginac/wildcard.cpp b/ginac/wildcard.cpp
index ea2a7f7742948781585716b2484ba01f47599e90..b5abfa1463a18c8bef5bf4696ea1e8bc650fb3fe 100644 (file)
--- a/ginac/wildcard.cpp
+++ b/ginac/wildcard.cpp
@@ -111,7 +111,7 @@ unsigned wildcard::calchash() const
        return hashvalue;
 }
 
-bool wildcard::match(const ex & pattern, lst & repl_lst) const
+bool wildcard::match(const ex & pattern, exmap& repl_lst) const
 {
        // Wildcards must match each other exactly (this is required for
        // subs() to work properly because in the final step it substitutes

diff --git a/ginac/wildcard.h b/ginac/wildcard.h
index ba4141243638ba0c2b39d265d167192d996a6f22..9729237c97573a0aa038f3d3889b1be39c6d3852 100644 (file)
--- a/ginac/wildcard.h
+++ b/ginac/wildcard.h
@@ -41,7 +41,7 @@ public:
 
        // functions overriding virtual functions from base classes
 public:
-       bool match(const ex & pattern, lst & repl_lst) const;
+       bool match(const ex & pattern, exmap& repl_lst) const;
 
 protected:
        unsigned calchash() const;

diff --git a/ginsh/ginsh_parser.yy b/ginsh/ginsh_parser.yy
index b059172ef5166e3b94a6ad1b3690d3e9c9c1088d..6b2c93764a9c14286d2c24a6bea7259d7aa1f00a 100644 (file)
--- a/ginsh/ginsh_parser.yy
+++ b/ginsh/ginsh_parser.yy
@@ -426,9 +426,12 @@ static ex f_evalf2(const exprseq &e)
 
 static ex f_find(const exprseq &e)
 {
-       lst found;
+       exset found;
        e[0].find(e[1], found);
-       return found;
+       lst l;
+       for (exset::const_iterator i = found.begin(); i != found.end(); ++i)
+               l.append(*i);
+       return l;
 }
 
 static ex f_fsolve(const exprseq &e)
@@ -478,11 +481,14 @@ static ex f_map(const exprseq &e)
 
 static ex f_match(const exprseq &e)
 {
-       lst repl_lst;
-       if (e[0].match(e[1], repl_lst))
+       exmap repls;
+       if (e[0].match(e[1], repls)) {
+               lst repl_lst;
+               for (exmap::const_iterator i = repls.begin(); i != repls.end(); ++i)
+                       repl_lst.append(relational(i->first, i->second, relational::equal));
                return repl_lst;
-       else
-               return fail();
+       }
+       throw std::runtime_error("FAIL");
 }
 
 static ex f_normal2(const exprseq &e)