- first implementation of pattern matching
authorChristian Bauer <Christian.Bauer@uni-mainz.de>
Thu, 24 May 2001 00:43:11 +0000 (00:43 +0000)
committerChristian Bauer <Christian.Bauer@uni-mainz.de>
Thu, 24 May 2001 00:43:11 +0000 (00:43 +0000)
26 files changed:
NEWS
doc/tutorial/ginac.texi
ginac/Makefile.am
ginac/basic.cpp
ginac/basic.h
ginac/color.cpp
ginac/container.pl
ginac/ex.h
ginac/expairseq.cpp
ginac/expairseq.h
ginac/function.pl
ginac/ginac.h
ginac/idx.cpp
ginac/idx.h
ginac/matrix.cpp
ginac/matrix.h
ginac/power.cpp
ginac/power.h
ginac/pseries.cpp
ginac/pseries.h
ginac/tinfos.h
ginac/wildcard.cpp [new file with mode: 0644]
ginac/wildcard.h [new file with mode: 0644]
ginsh/ginsh.1.in
ginsh/ginsh_lexer.ll
ginsh/ginsh_parser.yy

diff --git a/NEWS b/NEWS
index d349c8f..d08e730 100644 (file)
--- a/NEWS
+++ b/NEWS
@@ -5,6 +5,11 @@ This file records noteworthy changes.
   simplified to "2*a.i*a.i".
 * Added canonicalize_clifford() function that can be helpful when comparing
   expressions containing Dirac matrices.
+* Added a new function match() for performing pattern matching. subs() and
+  has() also accept patterns as arguments. A pattern can be any expression,
+  optionally containing wildcard objects. These are constructed with the
+  call "wild(<unsigned>)" and are denoted as "$0", "$1" etc. in the output
+  and in ginsh.
 * Fixed possible crash when calling subs() on expressions with non-commutative
   products.
 
index 4dc9945..46e3777 100644 (file)
@@ -4216,8 +4216,14 @@ work in the GiNaC framework. For a real algebraic class, there are probably
 some more functions that you will want to re-implement, such as
 @code{evalf()}, @code{series()} or @code{op()}. Have a look at @file{basic.h}
 or the header file of the class you want to make a subclass of to see
-what's there. You can, of course, also add your own new member functions.
-In this case you will probably want to define a little helper function like
+what's there. One member function that you will most likely want to
+implement for terminal classes like the described string class is
+@code{calcchash()} that returns an @code{unsigned} hash value for the object
+which will allow GiNaC to compare and canonicalize expressions much more
+efficiently.
+
+You can, of course, also add your own new member functions. In this case you
+will probably want to define a little helper function like
 
 @example
 inline const mystring &ex_to_mystring(const ex &e)
@@ -4226,9 +4232,9 @@ inline const mystring &ex_to_mystring(const ex &e)
 @}
 @end example
 
-that let's you get at the object inside an expression (after you have verified
-that the type is correct) so you can call member functions that are specific
-to the class.
+that let's you get at the object inside an expression (after you have
+verified that the type is correct) so you can call member functions that are
+specific to the class.
 
 That's it. May the source be with you!
 
index faaa66e..595e1f5 100644 (file)
@@ -8,7 +8,7 @@ libginac_la_SOURCES = add.cpp archive.cpp basic.cpp constant.cpp ex.cpp \
   symbol.cpp pseries.cpp utils.cpp ncmul.cpp structure.cpp exprseq_suppl.cpp \
   lst.cpp lst_suppl.cpp input_parser.yy input_lexer.ll input_lexer.h \
   remember.h remember.cpp debugmsg.h utils.h idx.cpp indexed.cpp tensor.cpp \
-  color.cpp clifford.cpp
+  color.cpp clifford.cpp wildcard.cpp
 libginac_la_LDFLAGS = -version-info $(LT_CURRENT):$(LT_REVISION):$(LT_AGE) \
   -release $(LT_RELEASE)
 ginacincludedir = $(includedir)/ginac
@@ -16,7 +16,7 @@ ginacinclude_HEADERS = ginac.h add.h archive.h basic.h constant.h ex.h \
   expair.h expairseq.h exprseq.h fail.h flags.h function.h inifcns.h \
   lst.h matrix.h mul.h ncmul.h normal.h numeric.h operators.h power.h \
   registrar.h relational.h pseries.h structure.h symbol.h tinfos.h assertion.h \
-  version.h idx.h indexed.h tensor.h color.h clifford.h print.h
+  version.h idx.h indexed.h tensor.h color.h clifford.h wildcard.h print.h
 LFLAGS = -Pginac_yy -olex.yy.c
 YFLAGS = -p ginac_yy -d
 EXTRA_DIST = container.pl function.pl structure.pl input_parser.h version.h.in
index bf5bd6c..c899d19 100644 (file)
@@ -33,6 +33,7 @@
 #include "symbol.h"
 #include "lst.h"
 #include "ncmul.h"
+#include "relational.h"
 #include "print.h"
 #include "archive.h"
 #include "utils.h"
@@ -219,7 +220,8 @@ ex basic::operator[](int i) const
 bool basic::has(const ex & other) const
 {
        GINAC_ASSERT(other.bp!=0);
-       if (is_equal(*other.bp)) return true;
+       lst repl_lst;
+       if (match(*other.bp, repl_lst)) return true;
        if (nops()>0) {
                for (unsigned i=0; i<nops(); i++)
                        if (op(i).has(other))
@@ -398,15 +400,66 @@ bool basic::contract_with(exvector::iterator self, exvector::iterator other, exv
        return false;
 }
 
+/** 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
+{
+//clog << "match " << *this << " with " << pattern << ", repl_lst = " << repl_lst << endl;
+       if (is_ex_exactly_of_type(pattern, wildcard)) {
+
+               // Wildcard matches anything, but check whether we already have found
+               // a match for that wildcard first (if so, it the earlier match must
+               // be the same expression)
+               for (unsigned i=0; i<repl_lst.nops(); i++) {
+                       if (repl_lst.op(i).op(0).is_equal(pattern))
+                               return is_equal(*repl_lst.op(i).op(1).bp);
+               }
+               repl_lst.append(pattern == *this);
+               return true;
+
+       } else {
+
+               // Expression must be of the same type as the pattern
+               if (tinfo() != pattern.bp->tinfo())
+                       return false;
+
+               // Number of subexpressions must match
+               if (nops() != pattern.nops())
+                       return false;
+
+               // No subexpressions? Then just compare the objects (there can't be
+               // wildcards in the pattern)
+               if (nops() == 0)
+                       return is_equal(*pattern.bp);
+
+               // Otherwise the subexpressions must match one-to-one
+               for (unsigned i=0; i<nops(); i++)
+                       if (!op(i).match(pattern.op(i), repl_lst))
+                               return false;
+
+               // Looks similar enough, match found
+               return true;
+       }
+}
+
 /** Substitute a set of objects by arbitrary expressions. The ex returned
  *  will already be evaluated. */
-ex basic::subs(const lst & ls, const lst & lr) const
+ex basic::subs(const lst & ls, const lst & lr, bool no_pattern) const
 {
        GINAC_ASSERT(ls.nops() == lr.nops());
 
-       for (unsigned i=0; i<ls.nops(); i++) {
-               if (is_equal(*ls.op(i).bp))
-                       return lr.op(i);
+       if (no_pattern) {
+               for (unsigned i=0; i<ls.nops(); i++) {
+                       if (is_equal(*ls.op(i).bp))
+                               return lr.op(i);
+               }
+       } else {
+               for (unsigned i=0; i<ls.nops(); i++) {
+                       lst repl_lst;
+                       if (match(*ls.op(i).bp, repl_lst))
+                               return lr.op(i).bp->subs(repl_lst, true); // avoid recursion when re-substituting the wildcards
+               }
        }
 
        return *this;
@@ -535,10 +588,10 @@ ex basic::expand(unsigned options) const
  *  replacement arguments: 1) a relational like object==ex and 2) a list of
  *  relationals lst(object1==ex1,object2==ex2,...), which is converted to
  *  subs(lst(object1,object2,...),lst(ex1,ex2,...)). */
-ex basic::subs(const ex & e) const
+ex basic::subs(const ex & e, bool no_pattern) const
 {
        if (e.info(info_flags::relation_equal)) {
-               return subs(lst(e));
+               return subs(lst(e), no_pattern);
        }
        if (!e.info(info_flags::list)) {
                throw(std::invalid_argument("basic::subs(ex): argument must be a list"));
@@ -553,7 +606,7 @@ ex basic::subs(const ex & e) const
                ls.append(r.op(0));
                lr.append(r.op(1));
        }
-       return subs(ls, lr);
+       return subs(ls, lr, no_pattern);
 }
 
 /** Compare objects to establish canonical ordering.
index 33a9d20..446d6d1 100644 (file)
@@ -118,7 +118,8 @@ public: // only const functions please (may break reference counting)
        virtual ex eval(int level = 0) const;
        virtual ex evalf(int level = 0) const;
        virtual ex series(const relational & r, int order, unsigned options = 0) const;
-       virtual ex subs(const lst & ls, const lst & lr) const;
+       virtual bool match(const ex & pattern, lst & repl_lst) const;
+       virtual ex subs(const lst & ls, const lst & lr, bool no_pattern = false) const;
        virtual ex normal(lst &sym_lst, lst &repl_lst, int level = 0) const;
        virtual ex to_rational(lst &repl_lst) const;
        virtual numeric integer_content(void) const;
@@ -141,7 +142,7 @@ protected: // non-const functions should be called from class ex only
        
        // non-virtual functions in this class
 public:
-       ex subs(const ex & e) const;
+       ex subs(const ex & e, bool no_pattern = false) const;
        ex diff(const symbol & s, unsigned nth=1) const;
        int compare(const basic & other) const;
        bool is_equal(const basic & other) const;
index 234c2b9..92f890a 100644 (file)
@@ -24,7 +24,6 @@
 #include <stdexcept>
 
 #include "color.h"
-#include "ex.h"
 #include "idx.h"
 #include "ncmul.h"
 #include "numeric.h"
index 8a02503..f13c965 100755 (executable)
@@ -211,12 +211,11 @@ public:
        unsigned nops() const;
        ex & let_op(int i);
        ex expand(unsigned options=0) const;
-       bool has(const ex & other) const;
        ex eval(int level=0) const;
        ex evalf(int level=0) const;
        ex normal(lst &sym_lst, lst &repl_lst, int level=0) const;
        ex derivative(const symbol & s) const;
-       ex subs(const lst & ls, const lst & lr) const;
+       ex subs(const lst & ls, const lst & lr, bool no_pattern = false) const;
 protected:
        bool is_equal_same_type(const basic & other) const;
        unsigned return_type(void) const;
@@ -238,7 +237,7 @@ protected:
        ${STLT} evalfchildren(int level) const;
        ${STLT} normalchildren(int level) const;
        ${STLT} diffchildren(const symbol & s) const;
-       ${STLT} * subschildren(const lst & ls, const lst & lr) const;
+       ${STLT} * subschildren(const lst & ls, const lst & lr, bool no_pattern = false) const;
 
 protected:
        ${STLT} seq;
@@ -442,18 +441,6 @@ ex ${CONTAINER}::expand(unsigned options) const
        return this${CONTAINER}(s);
 }
 
-// a ${CONTAINER} 'has' an expression if it is this expression itself or a child 'has' it
-
-bool ${CONTAINER}::has(const ex & other) const
-{
-       GINAC_ASSERT(other.bp!=0);
-       if (is_equal(*other.bp)) return true;
-       for (${STLT}::const_iterator it=seq.begin(); it!=seq.end(); ++it) {
-               if ((*it).has(other)) return true;
-       }
-       return false;
-}
-
 ex ${CONTAINER}::eval(int level) const
 {
        if (level==1) {
@@ -481,13 +468,13 @@ ex ${CONTAINER}::derivative(const symbol & s) const
        return this${CONTAINER}(diffchildren(s));
 }
 
-ex ${CONTAINER}::subs(const lst & ls, const lst & lr) const
+ex ${CONTAINER}::subs(const lst & ls, const lst & lr, bool no_pattern) const
 {
-       ${STLT} * vp=subschildren(ls,lr);
-       if (vp==0)
-               return inherited::subs(ls, lr);
-
-       return this${CONTAINER}(vp);
+       ${STLT} *vp = subschildren(ls, lr, no_pattern);
+       if (vp)
+               return this${CONTAINER}(vp).bp->basic::subs(ls, lr, no_pattern);
+       else
+               return basic::subs(ls, lr, no_pattern);
 }
 
 // protected
@@ -676,19 +663,7 @@ ${STLT} ${CONTAINER}::diffchildren(const symbol & y) const
        return s;
 }
 
-/* obsolete subschildren
-${STLT} ${CONTAINER}::subschildren(const lst & ls, const lst & lr) const
-{
-       ${STLT} s;
-       RESERVE(s,seq.size());
-       for (${STLT}::const_iterator it=seq.begin(); it!=seq.end(); ++it) {
-               s.push_back((*it).subs(ls,lr));
-       }
-       return s;
-}
-*/
-
-${STLT} * ${CONTAINER}::subschildren(const lst & ls, const lst & lr) const
+${STLT} * ${CONTAINER}::subschildren(const lst & ls, const lst & lr, bool no_pattern) const
 {
        // returns a NULL pointer if nothing had to be substituted
        // returns a pointer to a newly created epvector otherwise
@@ -697,7 +672,7 @@ ${STLT} * ${CONTAINER}::subschildren(const lst & ls, const lst & lr) const
        ${STLT}::const_iterator last=seq.end();
        ${STLT}::const_iterator cit=seq.begin();
        while (cit!=last) {
-               const ex & subsed_ex=(*cit).subs(ls,lr);
+               const ex & subsed_ex=(*cit).subs(ls,lr,no_pattern);
                if (!are_ex_trivially_equal(*cit,subsed_ex)) {
 
                        // something changed, copy seq, subs and return it
@@ -715,7 +690,7 @@ ${STLT} * ${CONTAINER}::subschildren(const lst & ls, const lst & lr) const
                        ++cit2;
                        // copy rest
                        while (cit2!=last) {
-                               s->push_back((*cit2).subs(ls,lr));
+                               s->push_back((*cit2).subs(ls,lr,no_pattern));
                                ++cit2;
                        }
                        return s;
index 7b36eff..1449b63 100644 (file)
@@ -105,8 +105,9 @@ public:
        ex evalf(int level = 0) const { return bp->evalf(level); }
        ex diff(const symbol & s, unsigned nth = 1) const;
        ex series(const ex & r, int order, unsigned options = 0) const;
-       ex subs(const lst & ls, const lst & lr) const { return bp->subs(ls, lr); }
-       ex subs(const ex & e) const { return bp->subs(e); }
+       bool match(const ex & pattern, lst & repl_lst) const { return bp->match(pattern, repl_lst); }
+       ex subs(const lst & ls, const lst & lr, bool no_pattern = false) const { return bp->subs(ls, lr, no_pattern); }
+       ex subs(const ex & e, bool no_pattern = false) const { return bp->subs(e, no_pattern); }
        exvector get_free_indices(void) const { return bp->get_free_indices(); }
        ex simplify_indexed(void) const;
        ex simplify_indexed(const scalar_products & sp) const;
@@ -370,6 +371,9 @@ 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)
+{ return thisex.match(pattern, repl_lst); }
+
 inline ex subs(const ex & thisex, const ex & e)
 { return thisex.subs(e); }
 
index b14ffb3..2d9a8f6 100644 (file)
@@ -26,6 +26,7 @@
 
 #include "expairseq.h"
 #include "lst.h"
+#include "relational.h"
 #include "print.h"
 #include "archive.h"
 #include "debugmsg.h"
@@ -321,13 +322,87 @@ ex expairseq::normal(lst &sym_lst, lst &repl_lst, int level) const
        return n.bp->basic::normal(sym_lst,repl_lst,level);
 }
 
-ex expairseq::subs(const lst &ls, const lst &lr) const
+bool expairseq::match(const ex & pattern, lst & repl_lst) const
 {
-       epvector *vp = subschildren(ls,lr);
-       if (vp==0)
-               return inherited::subs(ls, lr);
-       
-       return thisexpairseq(vp,overall_coeff);
+//clog << "match " << *this << " with " << pattern << ", repl_lst = " << repl_lst << endl;
+       // 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
+
+       if (tinfo() == pattern.bp->tinfo()) {
+
+               // Check whether global wildcard (one that matches the "rest of the
+               // expression", like "*" above) is present
+               bool has_global_wildcard = false;
+               ex global_wildcard;
+               for (unsigned int i=0; i<pattern.nops(); i++) {
+                       if (is_ex_exactly_of_type(pattern.op(i), wildcard)) {
+                               has_global_wildcard = true;
+                               global_wildcard = pattern.op(i);
+                               break;
+                       }
+               }
+
+               // Unfortunately, this is an O(N^2) operation because we can't
+               // sort the pattern in a useful way...
+
+               // Chop into terms
+               exvector ops;
+               ops.reserve(nops());
+               for (unsigned i=0; i<nops(); i++)
+                       ops.push_back(op(i));
+
+               // Now, for every term of the pattern, look for a matching term in
+               // the expression and remove the match
+               for (unsigned i=0; i<pattern.nops(); i++) {
+                       ex p = pattern.op(i);
+                       if (has_global_wildcard && p.is_equal(global_wildcard))
+                               continue;
+                       exvector::iterator it = ops.begin(), itend = ops.end();
+                       while (it != itend) {
+                               if (it->match(p, repl_lst)) {
+                                       ops.erase(it);
+                                       goto found;
+                               }
+                               it++;
+                       }
+                       return false; // no match found
+found:         ;
+               }
+
+               if (has_global_wildcard) {
+
+                       // Assign all the remaining terms to the global wildcard (unless
+                       // it has already been matched before, in which case the matches
+                       // must be equal)
+                       epvector *vp = new epvector();
+                       vp->reserve(ops.size());
+                       for (unsigned i=0; i<ops.size(); i++)
+                               vp->push_back(split_ex_to_pair(ops[i]));
+                       ex rest = thisexpairseq(vp, default_overall_coeff());
+                       for (unsigned i=0; i<repl_lst.nops(); i++) {
+                               if (repl_lst.op(i).op(0).is_equal(global_wildcard))
+                                       return rest.is_equal(*repl_lst.op(i).op(1).bp);
+                       }
+                       repl_lst.append(global_wildcard == rest);
+                       return true;
+
+               } else {
+
+                       // No global wildcard, then the match fails if there are any
+                       // unmatched terms left
+                       return ops.empty();
+               }
+       }
+       return inherited::match(pattern, repl_lst);
+}
+
+ex expairseq::subs(const lst &ls, const lst &lr, bool no_pattern) const
+{
+       epvector *vp = subschildren(ls, lr, no_pattern);
+       if (vp)
+               return thisexpairseq(vp, overall_coeff).bp->basic::subs(ls, lr, no_pattern);
+       else
+               return basic::subs(ls, lr, no_pattern);
 }
 
 // protected
@@ -1586,7 +1661,7 @@ epvector expairseq::diffchildren(const symbol &y) const
  *  @see expairseq::subs()
  *  @return pointer to epvector containing pairs after application of subs or zero
  *  pointer, if no members were changed. */
-epvector * expairseq::subschildren(const lst &ls, const lst &lr) const
+epvector * expairseq::subschildren(const lst &ls, const lst &lr, bool no_pattern) const
 {
        // returns a NULL pointer if nothing had to be substituted
        // returns a pointer to a newly created epvector otherwise
@@ -1596,7 +1671,7 @@ epvector * expairseq::subschildren(const lst &ls, const lst &lr) const
        epvector::const_iterator last = seq.end();
        epvector::const_iterator cit = seq.begin();
        while (cit!=last) {
-               const ex &subsed_ex=(*cit).rest.subs(ls,lr);
+               const ex &subsed_ex=(*cit).rest.subs(ls,lr,no_pattern);
                if (!are_ex_trivially_equal((*cit).rest,subsed_ex)) {
                        
                        // something changed, copy seq, subs and return it
@@ -1615,7 +1690,7 @@ epvector * expairseq::subschildren(const lst &ls, const lst &lr) const
                        ++cit2;
                        // copy rest
                        while (cit2!=last) {
-                               s->push_back(combine_ex_with_coeff_to_pair((*cit2).rest.subs(ls,lr),
+                               s->push_back(combine_ex_with_coeff_to_pair((*cit2).rest.subs(ls,lr,no_pattern),
                                                                           (*cit2).coeff));
                                ++cit2;
                        }
index fac36ee..3851a57 100644 (file)
@@ -97,7 +97,8 @@ public:
        ex evalf(int level=0) const;
        ex normal(lst &sym_lst, lst &repl_lst, int level=0) const;
        ex to_rational(lst &repl_lst) const;
-       ex subs(const lst & ls, const lst & lr) const;
+       bool match(const ex & pattern, lst & repl_lst) const;
+       ex subs(const lst & ls, const lst & lr, bool no_pattern = false) const;
 protected:
        ex derivative(const symbol & s) const;
        int compare_same_type(const basic & other) const;
@@ -168,7 +169,7 @@ protected:
        epvector evalfchildren(int level) const;
        epvector normalchildren(int level) const;
        epvector diffchildren(const symbol & s) const;
-       epvector * subschildren(const lst & ls, const lst & lr) const;
+       epvector * subschildren(const lst & ls, const lst & lr, bool no_pattern = false) const;
        
 // member variables
        
index a08d35f..b0564e6 100755 (executable)
@@ -344,6 +344,7 @@ public:
        ex evalf(int level=0) const;
        unsigned calchash(void) const;
        ex series(const relational & r, int order, unsigned options = 0) const;
+       bool match(const ex & pattern, lst & repl_lst) const;
        ex thisexprseq(const exvector & v) const;
        ex thisexprseq(exvector * vp) const;
 protected:
@@ -801,6 +802,14 @@ ${series_switch_statement}
        throw(std::logic_error("function::series(): invalid nparams"));
 }
 
+bool function::match(const ex & pattern, lst & repl_lst) const
+{
+       // Serial number must match
+       if (is_ex_of_type(pattern, function) && serial != ex_to_function(pattern).serial)
+               return false;
+       return inherited::match(pattern, repl_lst);
+}
+
 // protected
 
 
index 1dc48fe..e7684e5 100644 (file)
@@ -41,6 +41,7 @@
 #include "relational.h"
 #include "structure.h"
 #include "symbol.h"
+#include "wildcard.h"
 
 #include "expair.h"
 #include "expairseq.h"
index d54f519..117a02b 100644 (file)
@@ -318,7 +318,7 @@ int spinidx::compare_same_type(const basic & other) const
        return 0;
 }
 
-ex idx::subs(const lst & ls, const lst & lr) const
+ex idx::subs(const lst & ls, const lst & lr, bool no_pattern) const
 {
        GINAC_ASSERT(ls.nops() == lr.nops());
 
@@ -339,7 +339,7 @@ ex idx::subs(const lst & ls, const lst & lr) const
        }
 
        // None, substitute objects in value (not in dimension)
-       const ex &subsed_value = value.subs(ls, lr);
+       const ex &subsed_value = value.subs(ls, lr, no_pattern);
        if (are_ex_trivially_equal(value, subsed_value))
                return *this;
 
index f8c1f06..02caba5 100644 (file)
@@ -52,7 +52,7 @@ public:
        unsigned nops() const;
        ex & let_op(int i);
 protected:
-       ex subs(const lst & ls, const lst & lr) const;
+       ex subs(const lst & ls, const lst & lr, bool no_pattern = false) const;
 
        // new virtual functions in this class
 public:
index 8a68b66..65b1254 100644 (file)
@@ -208,22 +208,6 @@ ex matrix::expand(unsigned options) const
        return matrix(row, col, tmp);
 }
 
-/** Search ocurrences.  A matrix 'has' an expression if it is the expression
- *  itself or one of the elements 'has' it. */
-bool matrix::has(const ex & other) const
-{
-       GINAC_ASSERT(other.bp!=0);
-       
-       // tautology: it is the expression itself
-       if (is_equal(*other.bp)) return true;
-       
-       // search all the elements
-       for (exvector::const_iterator r=m.begin(); r!=m.end(); ++r)
-               if ((*r).has(other)) return true;
-       
-       return false;
-}
-
 /** Evaluate matrix entry by entry. */
 ex matrix::eval(int level) const
 {
@@ -272,14 +256,14 @@ ex matrix::evalf(int level) const
        return matrix(row, col, m2);
 }
 
-ex matrix::subs(const lst & ls, const lst & lr) const
+ex matrix::subs(const lst & ls, const lst & lr, bool no_pattern) const
 {
        exvector m2(row * col);
        for (unsigned r=0; r<row; ++r)
                for (unsigned c=0; c<col; ++c)
-                       m2[r*col+c] = m[r*col+c].subs(ls, lr);
+                       m2[r*col+c] = m[r*col+c].subs(ls, lr, no_pattern);
 
-       return matrix(row, col, m2);
+       return ex(matrix(row, col, m2)).bp->basic::subs(ls, lr, no_pattern);
 }
 
 // protected
index 53929bc..5642887 100644 (file)
@@ -47,10 +47,9 @@ public:
        ex op(int i) const;
        ex & let_op(int i);
        ex expand(unsigned options=0) const;
-       bool has(const ex & other) const;
        ex eval(int level=0) const;
        ex evalf(int level=0) const;
-       ex subs(const lst & ls, const lst & lr) const;
+       ex subs(const lst & ls, const lst & lr, bool no_pattern = false) const;
        ex eval_indexed(const basic & i) const;
        ex add_indexed(const ex & self, const ex & other) const;
        ex scalar_mul_indexed(const ex & self, const numeric & other) const;
index eee137b..d4c12c1 100644 (file)
@@ -472,17 +472,16 @@ ex power::evalf(int level) const
        return power(ebasis,eexponent);
 }
 
-ex power::subs(const lst & ls, const lst & lr) const
+ex power::subs(const lst & ls, const lst & lr, bool no_pattern) const
 {
-       const ex & subsed_basis=basis.subs(ls,lr);
-       const ex & subsed_exponent=exponent.subs(ls,lr);
+       const ex &subsed_basis = basis.subs(ls, lr, no_pattern);
+       const ex &subsed_exponent = exponent.subs(ls, lr, no_pattern);
 
-       if (are_ex_trivially_equal(basis,subsed_basis)&&
-               are_ex_trivially_equal(exponent,subsed_exponent)) {
-               return inherited::subs(ls, lr);
-       }
-       
-       return power(subsed_basis, subsed_exponent);
+       if (are_ex_trivially_equal(basis, subsed_basis)
+        && are_ex_trivially_equal(exponent, subsed_exponent))
+               return basic::subs(ls, lr, no_pattern);
+       else
+               return ex(power(subsed_basis, subsed_exponent)).bp->basic::subs(ls, lr, no_pattern);
 }
 
 ex power::simplify_ncmul(const exvector & v) const
index 480e091..8f7ac50 100644 (file)
@@ -59,7 +59,7 @@ public:
        ex eval(int level=0) const;
        ex evalf(int level=0) const;
        ex series(const relational & s, int order, unsigned options = 0) const;
-       ex subs(const lst & ls, const lst & lr) const;
+       ex subs(const lst & ls, const lst & lr, bool no_pattern = false) const;
        ex normal(lst &sym_lst, lst &repl_lst, int level = 0) const;
        ex to_rational(lst &repl_lst) const;
        exvector get_free_indices(void) const;
index 9d04f6a..1477449 100644 (file)
@@ -393,13 +393,13 @@ ex pseries::evalf(int level) const
        return (new pseries(relational(var,point), new_seq))->setflag(status_flags::dynallocated | status_flags::evaluated);
 }
 
-ex pseries::subs(const lst & ls, const lst & lr) const
+ex pseries::subs(const lst & ls, const lst & lr, bool no_pattern) const
 {
        // If expansion variable is being substituted, convert the series to a
        // polynomial and do the substitution there because the result might
        // no longer be a power series
        if (ls.has(var))
-               return convert_to_poly(true).subs(ls, lr);
+               return convert_to_poly(true).subs(ls, lr, no_pattern);
        
        // Otherwise construct a new series with substituted coefficients and
        // expansion point
@@ -407,10 +407,10 @@ ex pseries::subs(const lst & ls, const lst & lr) const
        newseq.reserve(seq.size());
        epvector::const_iterator it = seq.begin(), itend = seq.end();
        while (it != itend) {
-               newseq.push_back(expair(it->rest.subs(ls, lr), it->coeff));
+               newseq.push_back(expair(it->rest.subs(ls, lr, no_pattern), it->coeff));
                ++it;
        }
-       return (new pseries(relational(var,point.subs(ls, lr)), newseq))->setflag(status_flags::dynallocated);
+       return (new pseries(relational(var,point.subs(ls, lr, no_pattern)), newseq))->setflag(status_flags::dynallocated);
 }
 
 /** Implementation of ex::expand() for a power series.  It expands all the
index 18baed3..72586ea 100644 (file)
@@ -54,7 +54,7 @@ public:
        ex eval(int level=0) const;
        ex evalf(int level=0) const;
        ex series(const relational & r, int order, unsigned options = 0) const;
-       ex subs(const lst & ls, const lst & lr) const;
+       ex subs(const lst & ls, const lst & lr, bool no_pattern = false) const;
        ex normal(lst &sym_lst, lst &repl_lst, int level = 0) const;
        ex expand(unsigned options = 0) const;
 protected:
index 2a5fad6..3faea2f 100644 (file)
@@ -82,6 +82,8 @@ const unsigned TINFO_diracone      = 0x000e100cU;
 const unsigned TINFO_diracgamma    = 0x000e100dU;
 const unsigned TINFO_diracgamma5   = 0x000e100eU;
 
+const unsigned TINFO_wildcard      = 0x000f0001U;
+
 } // namespace GiNaC
 
 #endif // ndef __GINAC_TINFOS_H__
diff --git a/ginac/wildcard.cpp b/ginac/wildcard.cpp
new file mode 100644 (file)
index 0000000..0d78262
--- /dev/null
@@ -0,0 +1,124 @@
+/** @file wildcard.cpp
+ *
+ *  Implementation of GiNaC's wildcard objects. */
+
+/*
+ *  GiNaC Copyright (C) 1999-2001 Johannes Gutenberg University Mainz, Germany
+ *
+ *  This program is free software; you can redistribute it and/or modify
+ *  it under the terms of the GNU General Public License as published by
+ *  the Free Software Foundation; either version 2 of the License, or
+ *  (at your option) any later version.
+ *
+ *  This program is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *  GNU General Public License for more details.
+ *
+ *  You should have received a copy of the GNU General Public License
+ *  along with this program; if not, write to the Free Software
+ *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ */
+
+#include "wildcard.h"
+#include "print.h"
+#include "archive.h"
+#include "utils.h"
+#include "debugmsg.h"
+
+namespace GiNaC {
+
+GINAC_IMPLEMENT_REGISTERED_CLASS(wildcard, basic)
+
+//////////
+// default constructor, destructor, copy constructor assignment operator and helpers
+//////////
+
+wildcard::wildcard() : label(0)
+{
+       debugmsg("wildcard default constructor", LOGLEVEL_CONSTRUCT);
+       tinfo_key = TINFO_wildcard;
+}
+
+void wildcard::copy(const wildcard & other)
+{
+       inherited::copy(other);
+       label = other.label;
+}
+
+DEFAULT_DESTROY(wildcard)
+
+//////////
+// other constructors
+//////////
+
+wildcard::wildcard(unsigned l) : label(l)
+{
+       debugmsg("wildcard constructor from unsigned", LOGLEVEL_CONSTRUCT);
+       tinfo_key = TINFO_wildcard;
+}
+
+//////////
+// archiving
+//////////
+
+wildcard::wildcard(const archive_node &n, const lst &sym_lst) : inherited(n, sym_lst)
+{
+       debugmsg("wildcard constructor from archive_node", LOGLEVEL_CONSTRUCT);
+       n.find_unsigned("label", label);
+}
+
+void wildcard::archive(archive_node &n) const
+{
+       inherited::archive(n);
+       n.add_unsigned("label", label);
+}
+
+DEFAULT_UNARCHIVE(wildcard)
+
+//////////
+// functions overriding virtual functions from bases classes
+//////////
+
+int wildcard::compare_same_type(const basic & other) const
+{
+       GINAC_ASSERT(is_of_type(other, wildcard));
+       const wildcard &o = static_cast<const wildcard &>(other);
+
+       if (label == o.label)
+               return 0;
+       else
+               return label < o.label ? -1 : 1;
+}
+
+void wildcard::print(const print_context & c, unsigned level = 0) const
+{
+       debugmsg("wildcard print", LOGLEVEL_PRINT);
+
+       if (is_of_type(c, print_tree)) {
+               c.s << std::string(level, ' ') << class_name() << " (" << label << ")"
+                   << std::hex << ", hash=0x" << hashvalue << ", flags=0x" << flags << std::dec
+                   << std::endl;
+       } else
+               c.s << "$" << label;
+}
+
+unsigned wildcard::calchash(void) const
+{
+       // this is where the schoolbook method
+       // (golden_ratio_hash(tinfo()) ^ label)
+       // is not good enough yet...
+       hashvalue = golden_ratio_hash(golden_ratio_hash(tinfo()) ^ label);
+       setflag(status_flags::hash_calculated);
+       return hashvalue;
+}
+
+bool wildcard::match(const ex & pattern, lst & repl_lst) const
+{
+       // Wildcards must match exactly (this is required for subs() to work
+       // properly because in the final step it substitues all wildcards by
+       // their matching expressions)
+       return is_equal(*pattern.bp);
+}
+
+} // namespace GiNaC
diff --git a/ginac/wildcard.h b/ginac/wildcard.h
new file mode 100644 (file)
index 0000000..e55788e
--- /dev/null
@@ -0,0 +1,72 @@
+/** @file wildcard.h
+ *
+ *  Interface to GiNaC's wildcard objects. */
+
+/*
+ *  GiNaC Copyright (C) 1999-2001 Johannes Gutenberg University Mainz, Germany
+ *
+ *  This program is free software; you can redistribute it and/or modify
+ *  it under the terms of the GNU General Public License as published by
+ *  the Free Software Foundation; either version 2 of the License, or
+ *  (at your option) any later version.
+ *
+ *  This program is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *  GNU General Public License for more details.
+ *
+ *  You should have received a copy of the GNU General Public License
+ *  along with this program; if not, write to the Free Software
+ *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ */
+
+#ifndef __GINAC_WILDCARD_H__
+#define __GINAC_WILDCARD_H__
+
+#include "ex.h"
+
+namespace GiNaC {
+
+
+/** This class acts as a wildcard for subs() and matches(). An integer label
+ *  is used to identify different wildcards. */
+class wildcard : public basic
+{
+       GINAC_DECLARE_REGISTERED_CLASS(wildcard, basic)
+
+       // other constructors
+public:
+       /** Construct wildcard with specified label. */
+       wildcard(unsigned label);
+
+       // functions overriding virtual functions from bases classes
+public:
+       void print(const print_context & c, unsigned level = 0) const;
+       unsigned calchash(void) const;
+       bool match(const ex & pattern, lst & repl_lst) const;
+
+       // non-virtual functions in this class
+public:
+       unsigned get_label(void) const {return label;}
+
+       // member variables
+private:
+       unsigned label; /**< Label used to distinguish different wildcards */
+};
+
+
+// global functions
+inline const wildcard &ex_to_wildcard(const ex &e)
+{
+       return static_cast<const wildcard &>(*e.bp);
+}
+
+/** Create a wildcard object with the specified label. */
+inline ex wild(unsigned label = 0)
+{
+       return wildcard(label);
+}
+
+} // namespace GiNaC
+
+#endif // ndef __GINAC_WILDCARD_H__
index 97c0bbb..a19be9c 100644 (file)
@@ -292,6 +292,9 @@ detail here. Please refer to the GiNaC documentation.
 .BI lsolve( equation-list ", " symbol-list )
 \- solve system of linear equations
 .br
+.BI match( expression ", " pattern )
+\- check whether expression matches a pattern; returns a list of wildcard substitutions or "FAIL" if there is no match
+.br
 .BI nops( expression )
 \- number of operands in expression
 .br
index 20cb329..a8a2b10 100644 (file)
@@ -113,6 +113,9 @@ score                       return T_SCORE;
                                return T_SYMBOL;
                        }
 
+                       /* wildcards */
+\${D}+                 yylval = wild(atoi(yytext + 1)); return T_LITERAL;
+
                        /* everything else */
 .                      return *yytext;
 
index 3f862bd..48d839a 100644 (file)
@@ -400,6 +400,15 @@ static ex f_ldegree(const exprseq &e)
        return e[0].ldegree(e[1]);
 }
 
+static ex f_match(const exprseq &e)
+{
+       lst repl_lst;
+       if (e[0].match(e[1], repl_lst))
+               return repl_lst;
+       else
+               return fail();
+}
+
 static ex f_normal2(const exprseq &e)
 {
        CHECK_ARG(1, numeric, normal);
@@ -530,6 +539,7 @@ static const fcn_init builtin_fcns[] = {
        {"lcoeff", fcn_desc(f_lcoeff, 2)},
        {"ldegree", fcn_desc(f_ldegree, 2)},
        {"lsolve", fcn_desc(f_lsolve, 2)},
+       {"match", fcn_desc(f_match, 2)},
        {"nops", fcn_desc(f_nops, 1)},
        {"normal", fcn_desc(f_normal1, 1)},
        {"normal", fcn_desc(f_normal2, 2)},