From 4f596b14ac1cdb03163c74e210cab493358ababf Mon Sep 17 00:00:00 2001
From: Alexei Sheplyakov <varg@theor.jinr.ru>
Date: Fri, 12 Sep 2008 14:55:42 +0400
Subject: [PATCH] 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.
---
 check/match_bug.cpp     | 12 ++++++------
 doc/tutorial/ginac.texi | 10 +++++-----
 ginac/basic.cpp         | 23 ++++++++++++-----------
 ginac/basic.h           |  2 +-
 ginac/ex.cpp            |  8 +++-----
 ginac/ex.h              |  8 ++++----
 ginac/expairseq.cpp     | 10 +++++-----
 ginac/expairseq.h       |  2 +-
 ginac/mul.cpp           | 22 +++++++++++-----------
 ginac/power.cpp         | 12 ++++++++----
 ginac/structure.h       |  2 +-
 ginac/wildcard.cpp      |  2 +-
 ginac/wildcard.h        |  2 +-
 ginsh/ginsh_parser.yy   | 18 ++++++++++++------
 14 files changed, 71 insertions(+), 62 deletions(-)

diff --git a/check/match_bug.cpp b/check/match_bug.cpp
index d80faca3..df67629b 100644
--- 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 2f160c7b..72544062 100644
--- 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 7a0633de..e8c893ba 100644
--- 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 34852379..ffc508db 100644
--- 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 23a30833..377b15b4 100644
--- 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 783c89ee..4a603ce0 100644
--- 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 229710b2..67aa4f8e 100644
--- 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 6abd1007..5f707f76 100644
--- 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 3d33c78a..63f92e14 100644
--- 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 ec339b9a..e4a044cb 100644
--- 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 26dff67b..d00100b1 100644
--- 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 ea2a7f77..b5abfa14 100644
--- 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 ba414124..9729237c 100644
--- 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 b059172e..6b2c9376 100644
--- 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)
-- 
2.44.0