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);
}
/*
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);
}
@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:
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
* 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++)
}
/** 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,
// 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 {
// 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))
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
}
}
// 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:
/** 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);
}
* 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;
// 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;
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)
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)
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
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 {
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;
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;
patternexpsign = 1;
}
- lst saverepls = repls;
+ exmap saverepls = repls;
if (origexponent < patternexponent || origexpsign != patternexpsign || !origbase.match(patternbase,saverepls))
return false;
repls = saverepls;
* 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)
{
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;
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);
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;
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;
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);
}
}
}
// 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
{
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);
// 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:
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
// 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;
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)
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)