unsigned result = 0;
symbol x("x"), y("y");
- ex e = ex(x*x*x*y*y).subs(x*y==2, subs_options::subs_algebraic);
+ ex e = ex(x*x*x*y*y).subs(x*y==2, subs_options::algebraic);
if (e != 4*x) {
- clog << "(x^3*y^2).subs(x*y==2,subs_options::subs_algebraic) erroneously returned " << e << endl;
+ clog << "(x^3*y^2).subs(x*y==2,subs_options::algebraic) erroneously returned " << e << endl;
++result;
}
- e = ex(x*x*x*x*x).subs(x*x==y, subs_options::subs_algebraic);
+ e = ex(x*x*x*x*x).subs(x*x==y, subs_options::algebraic);
if (e != y*y*x) {
- clog << "x^5.subs(x^2==y,subs_options::subs_algebraic) erroneously returned " << e << endl;
+ clog << "x^5.subs(x^2==y,subs_options::algebraic) erroneously returned " << e << endl;
++result;
}
-
+
+ e=x*x*y;
+ if (!e.has(x*y, has_options::algebraic))
+ { clog << "(x^2*y).has(x*y, has_options::algebraic) erroneously returned false." << endl;
+ ++result;
+ }
+
+ if (e.has(x*y*y, has_options::algebraic))
+ { clog << "(x^2*y).has(x*y*y, has_options::algebraic) erroneously returned true." << endl;
+ ++result;
+ }
+
+ e=x*x*x*y;
+ if (!e.has(x*x, has_options::algebraic))
+ { clog << "(x^3*y).has(x*x, has_options::algebraic) erroneously returned false." << endl;
+ ++result;
+ }
+
+ if (e.has(y*y, has_options::algebraic))
+ { clog << "(x^3*y).has(y*y, has_options::algebraic) erroneously returned true." << endl;
+ ++result;
+ }
+
return result;
}
dnl Check for data types which are needed by the hash function
dnl (golden_ratio_hash).
-AC_CHECK_SIZEOF(long, 4)
-AC_CHECK_SIZEOF(long long, 8)
-AC_CHECK_SIZEOF(long double, 12)
+AC_CHECK_SIZEOF(int)
+AC_CHECK_SIZEOF(long)
+AC_CHECK_SIZEOF(long long)
+AC_CHECK_SIZEOF(long double)
+AC_CHECK_SIZEOF(void *)
dnl Switch to C++ language mode for the following libraries and headers.
AC_LANG([C++])
@}
@end example
-@subsection Algebraic substitutions
-Supplying the @code{subs_options::algebraic} option to @code{subs()}
-enables smarter, algebraic substitutions in products and powers. If you want
-to substitute some factors of a product, you only need to list these factors
-in your pattern. Furthermore, if an (integer) power of some expression occurs
-in your pattern and in the expression that you want the substitution to occur
-in, it can be substituted as many times as possible, without getting negative
-powers.
-
-An example clarifies it all (hopefully):
-
-@example
-cout << (a*a*a*a+b*b*b*b+pow(x+y,4)).subs(wild()*wild()==pow(wild(),3),
- subs_options::algebraic) << endl;
-// --> (y+x)^6+b^6+a^6
-
-cout << ((a+b+c)*(a+b+c)).subs(a+b==x,subs_options::algebraic) << endl;
-// --> (c+b+a)^2
-// Powers and products are smart, but addition is just the same.
-
-cout << ((a+b+c)*(a+b+c)).subs(a+b+wild()==x+wild(), subs_options::algebraic)
- << endl;
-// --> (x+c)^2
-// As I said: addition is just the same.
-
-cout << (pow(a,5)*pow(b,7)+2*b).subs(b*b*a==x,subs_options::algebraic) << endl;
-// --> x^3*b*a^2+2*b
-
-cout << (pow(a,-5)*pow(b,-7)+2*b).subs(1/(b*b*a)==x,subs_options::algebraic)
- << endl;
-// --> 2*b+x^3*b^(-1)*a^(-2)
-
-cout << (4*x*x*x-2*x*x+5*x-1).subs(x==a,subs_options::algebraic) << endl;
-// --> -1-2*a^2+4*a^3+5*a
-
-cout << (4*x*x*x-2*x*x+5*x-1).subs(pow(x,wild())==pow(a,wild()),
- subs_options::algebraic) << endl;
-// --> -1+5*x+4*x^3-2*x^2
-// You should not really need this kind of patterns very often now.
-// But perhaps this it's-not-a-bug-it's-a-feature (c/sh)ould still change.
-
-cout << ex(sin(1+sin(x))).subs(sin(wild())==cos(wild()),
- subs_options::algebraic) << endl;
-// --> cos(1+cos(x))
-
-cout << expand((a*sin(x+y)*sin(x+y)+a*cos(x+y)*cos(x+y)+b)
- .subs((pow(cos(wild()),2)==1-pow(sin(wild()),2)),
- subs_options::algebraic)) << endl;
-// --> b+a
-@end example
+@subsection The option algebraic
+Both @code{has()} and @code{subs()} take an optional argument to pass them
+extra options. This section describes what happens if you give the former
+the option @code{has_options::algebraic} or the latter
+@code{subs:options::algebraic}. In that case the matching condition for
+powers and multiplications is changed in such a way that they become
+more intuitive. Intuition says that @code{x*y} is a part of @code{x*y*z}.
+If you use these options you will find that
+@code{(x*y*z).has(x*y, has_options::algebraic)} indeed returns true.
+Besides matching some of the factors of a product also powers match as
+often as is possible without getting negative exponents. For example
+@code{(x^5*y^2*z).subs(x^2*y^2==c, subs_options::algebraic)} will return
+@code{x*c^2*z}. This also works with negative powers:
+@code{(x^(-3)*y^(-2)*z).subs(1/(x*y)==c, subs_options::algebraic)} will
+return @code{x^(-1)*c^2*z}. Note that this only works for multiplications
+and not for locating @code{x+y} within @code{x+y+z}.
@node Applying a Function on Subexpressions, Visitors and Tree Traversal, Pattern Matching and Advanced Substitutions, Methods and Functions
* the pattern itself or one of the children 'has' it. As a consequence
* (according to the definition of children) given e=x+y+z, e.has(x) is true
* but e.has(x+y) is false. */
-bool basic::has(const ex & pattern) const
+bool basic::has(const ex & pattern, unsigned options) const
{
lst repl_lst;
if (match(pattern, repl_lst))
return true;
for (size_t i=0; i<nops(); i++)
- if (op(i).has(pattern))
+ if (op(i).has(pattern, options))
return true;
return false;
* would all end up with the same hashvalue. */
unsigned basic::calchash() const
{
- unsigned v = golden_ratio_hash((unsigned)tinfo());
+ unsigned v = golden_ratio_hash((p_int)tinfo());
for (size_t i=0; i<nops(); i++) {
v = rotate_left(v);
v ^= this->op(i).gethash();
virtual ex & operator[](size_t i);
// pattern matching
- virtual bool has(const ex & other) const;
+ virtual bool has(const ex & other, unsigned options = 0) const;
virtual bool match(const ex & pattern, lst & repl_lst) const;
protected:
virtual bool match_same_type(const basic & other) const;
unsigned constant::calchash() const
{
- hashvalue = golden_ratio_hash((unsigned)tinfo() ^ serial);
+ hashvalue = golden_ratio_hash((p_int)tinfo() ^ serial);
setflag(status_flags::hash_calculated);
ex conjugate() const { return bp->conjugate(); }
// pattern matching
- bool has(const ex & pattern) const { return bp->has(pattern); }
+ bool has(const ex & pattern, unsigned options = 0) const { return bp->has(pattern, options); }
bool find(const ex & pattern, lst & found) const;
bool match(const ex & pattern) const;
bool match(const ex & pattern, lst & repl_lst) const { return bp->match(pattern, repl_lst); }
inline ex conjugate(const ex & thisex)
{ return thisex.conjugate(); }
-inline bool has(const ex & thisex, const ex & pattern)
-{ return thisex.has(pattern); }
+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)
{ return thisex.find(pattern, found); }
unsigned expairseq::calchash() const
{
- unsigned v = golden_ratio_hash((unsigned)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) {
};
};
+/** Flags to control the behavior of has(). */
+class has_options {
+public:
+ enum {
+ algebraic = 0x0001, ///< enable algebraic matching
+ };
+};
+
/** Flags to control the behavior of subs(). */
class subs_options {
public:
// hash keys. That is, the hash values must not depend on the index
// dimensions or other attributes (variance etc.).
// The compare_same_type() methods will take care of the rest.
- unsigned v = golden_ratio_hash((unsigned)tinfo());
+ unsigned v = golden_ratio_hash((p_int)tinfo());
v = rotate_left(v);
v ^= value.gethash();
return false;
}
+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;
+ int nummatches = std::numeric_limits<int>::max();
+ std::vector<bool> subsed(seq.size(), false);
+ std::vector<bool> matched(seq.size(), false);
+ if(algebraic_match_mul_with_mul(*this, pattern, repls, 0, nummatches,
+ subsed, matched))
+ return true;
+ }
+ return basic::has(pattern, options);
+}
+
ex mul::algebraic_subs_mul(const exmap & m, unsigned options) const
{
std::vector<bool> subsed(seq.size(), false);
int degree(const ex & s) const;
int ldegree(const ex & s) const;
ex coeff(const ex & s, int n = 1) const;
+ bool has(const ex & other, unsigned options = 0) const;
ex eval(int level=0) const;
ex evalf(int level=0) const;
ex evalm() const;
* results: (2+I).has(-2) -> true. But this is consistent, since we also
* would like to have (-2+I).has(2) -> true and we want to think about the
* sign as a multiplicative factor. */
-bool numeric::has(const ex &other) const
+bool numeric::has(const ex &other, unsigned options) const
{
if (!is_exactly_a<numeric>(other))
return false;
int degree(const ex & s) const;
int ldegree(const ex & s) const;
ex coeff(const ex & s, int n = 1) const;
- bool has(const ex &other) const;
+ bool has(const ex &other, unsigned options = 0) const;
ex eval(int level = 0) const;
ex evalf(int level = 0) const;
ex subs(const exmap & m, unsigned options = 0) const { return subs_one_level(m, options); } // overwrites basic::subs() for performance reasons
return (new power(ebasis, eexponent))->setflag(status_flags::dynallocated);
}
+bool power::has(const ex & other, unsigned options) const
+{
+ if (!(options & has_options::algebraic))
+ return basic::has(other, options);
+ if (!is_a<power>(other))
+ return basic::has(other, options);
+ if (!exponent.info(info_flags::integer)
+ || !other.op(1).info(info_flags::integer))
+ return basic::has(other, options);
+ if (exponent.info(info_flags::posint)
+ && other.op(1).info(info_flags::posint)
+ && ex_to<numeric>(exponent).to_int()
+ > ex_to<numeric>(other.op(1)).to_int()
+ && basis.match(other.op(0)))
+ return true;
+ if (exponent.info(info_flags::negint)
+ && other.op(1).info(info_flags::negint)
+ && ex_to<numeric>(exponent).to_int()
+ < ex_to<numeric>(other.op(1)).to_int()
+ && basis.match(other.op(0)))
+ return true;
+ return basic::has(other, options);
+}
+
// from mul.cpp
extern bool tryfactsubs(const ex &, const ex &, int &, lst &);
ex evalm() const;
ex series(const relational & s, int order, unsigned options = 0) const;
ex subs(const exmap & m, unsigned options = 0) const;
+ bool has(const ex & other, unsigned options = 0) const;
ex normal(exmap & repl, exmap & rev_lookup, int level = 0) const;
ex to_rational(exmap & repl) const;
ex to_polynomial(exmap & repl) const;
unsigned relational::calchash() const
{
- unsigned v = golden_ratio_hash((unsigned)tinfo());
+ unsigned v = golden_ratio_hash((p_int)tinfo());
unsigned lhash = lh.gethash();
unsigned rhash = rh.gethash();
ex & operator[](size_t i) { return inherited::operator[](i); }
// pattern matching
- bool has(const ex & other) const { return inherited::has(other); }
+ 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); }
protected:
bool match_same_type(const basic & other) const { return true; }
unsigned symbol::calchash() const
{
- hashvalue = golden_ratio_hash((unsigned)tinfo() ^ serial);
+ hashvalue = golden_ratio_hash((p_int)tinfo() ^ serial);
setflag(status_flags::hash_calculated);
return hashvalue;
}
return (n & 0x80000000U) ? (n << 1 | 0x00000001U) : (n << 1);
}
+#if SIZEOF_VOID_P == SIZEOF_INT
+typedef unsigned int p_int;
+#elif SIZEOF_VOID_P == SIZEOF_LONG
+typedef unsigned long p_int;
+#elif SIZEOF_VOID_P == SIZEOF_LONG_LONG
+typedef unsigned long long p_int;
+#else
+typedef unsigned long p_int;
+#endif
+
/** Truncated multiplication with golden ratio, for computing hash values. */
-inline unsigned golden_ratio_hash(unsigned n)
+inline unsigned golden_ratio_hash(p_int n)
{
// This function works much better when fast arithmetic with at
// least 64 significant bits is available.
// this is where the schoolbook method
// (golden_ratio_hash(tinfo()) ^ label)
// is not good enough yet...
- hashvalue = golden_ratio_hash(golden_ratio_hash((unsigned)tinfo()) ^ label);
+ hashvalue = golden_ratio_hash(golden_ratio_hash((p_int)tinfo()) ^ label);
setflag(status_flags::hash_calculated);
return hashvalue;
}