match() (find()): use exmap (exset) to store matched subexpressions.
authorAlexei Sheplyakov <varg@theor.jinr.ru>
Fri, 12 Sep 2008 10:55:42 +0000 (14:55 +0400)
committerAlexei Sheplyakov <varg@theor.jinr.ru>
Fri, 19 Sep 2008 09:15:49 +0000 (13:15 +0400)
There's no need to re-invent associative arrays and wrap them into
a GiNaC class.

14 files changed:
check/match_bug.cpp
doc/tutorial/ginac.texi
ginac/basic.cpp
ginac/basic.h
ginac/ex.cpp
ginac/ex.h
ginac/expairseq.cpp
ginac/expairseq.h
ginac/mul.cpp
ginac/power.cpp
ginac/structure.h
ginac/wildcard.cpp
ginac/wildcard.h
ginsh/ginsh_parser.yy

index d80faca..df67629 100644 (file)
@@ -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);
 }
index 2f160c7..7254406 100644 (file)
@@ -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
index 7a0633d..e8c893b 100644 (file)
@@ -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
                }
        }
 
index 3485237..ffc508d 100644 (file)
@@ -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:
index 23a3083..377b15b 100644 (file)
@@ -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;
index 783c89e..4a603ce 100644 (file)
@@ -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)
index 229710b..67aa4f8 100644 (file)
@@ -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 {
index 6abd100..5f707f7 100644 (file)
@@ -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;
index 3d33c78..63f92e1 100644 (file)
@@ -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);
                                }
                        }
index ec339b9..e4a044c 100644 (file)
@@ -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);
index 26dff67..d00100b 100644 (file)
@@ -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:
index ea2a7f7..b5abfa1 100644 (file)
@@ -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
index ba41412..9729237 100644 (file)
@@ -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;
index b059172..6b2c937 100644 (file)
@@ -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)