KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > lsmp > djep > xjep > SimplificationVisitor


1    
2 package org.lsmp.djep.xjep;
3 //import org.lsmp.djep.matrixParser.*;
4 import org.nfunk.jep.*;
5
6 /**
7  * Simplifies an expression.
8  * To use
9  * <pre>
10  * JEP j = ...; Node in = ...;
11  * SimplificationVisitor sv = new SimplificationVisitor(tu);
12  * Node out = sv.simplify(in);
13  * </pre>
14  *
15  * <p>
16  * Its intended to completly rewrite this class to that simplification
17  * rules can be specified by strings in a way similar to DiffRulesI.
18  * It also would be nice to change the rules depending on the type of
19  * arguments, for example matrix multiplication is not commutative.
20  * But some of the in built rules exploit commutativity.
21  *
22  * @author Rich Morris
23  * Created on 20-Jun-2003
24  */
25
26 public class SimplificationVisitor extends DoNothingVisitor
27 {
28   private NodeFactory nf;
29   private OperatorSet opSet;
30   private TreeUtils tu;
31   
32   public SimplificationVisitor()
33   {
34   }
35
36   /** must be implemented for subclasses. **/
37   public Node simplify(Node node,XJep xjep) throws ParseException,IllegalArgumentException JavaDoc
38   {
39     nf = xjep.getNodeFactory();
40     opSet = xjep.getOperatorSet();
41     tu = xjep.getTreeUtils();
42     
43     if (node == null)
44         throw new IllegalArgumentException JavaDoc(
45             "topNode parameter is null");
46     Node res = (Node) node.jjtAccept(this,null);
47     return res;
48   }
49     /** First create a new node and then simplify it. */
50     public Node simplifyBuiltOperatorNode(Operator op,Node lhs,Node rhs) throws ParseException
51     {
52         ASTFunNode res = nf.buildOperatorNode(op,lhs,rhs);
53         Node res2 = simplifyOp(res,new Node[]{lhs,rhs});
54         return res2;
55     }
56     /**
57      * Simplifies expresions like 2+(3+x) or (2+x)+3
58      *
59      * @param node
60      * @param dimKids
61      * @return null if no rewrite happens or top node or top node of new tree.
62      * @throws ParseException
63      */
64     public Node simplifyTripple(XOperator op,Node lhs,Node rhs) throws ParseException
65     {
66         
67         XOperator rootOp;
68         if(op.isComposite()) rootOp = (XOperator) op.getRootOp();
69         else rootOp = op;
70
71         if(op.isCommutative() && tu.isConstant(rhs))
72         {
73             return simplifyBuiltOperatorNode(op,rhs,lhs);
74         }
75         if(tu.isConstant(lhs) && tu.isBinaryOperator(rhs))
76         {
77             Node rhsChild1 = rhs.jjtGetChild(0);
78             Node rhsChild2 = rhs.jjtGetChild(1);
79             XOperator rhsOp = (XOperator) ((ASTFunNode) rhs).getOperator();
80             XOperator rhsRoot;
81             if(rhsOp.isComposite()) rhsRoot = (XOperator) rhsOp.getRootOp();
82             else rhsRoot = rhsOp;
83     
84             if(tu.isConstant(rhsChild1))
85             {
86                 XOperator op2 = (XOperator) rootOp;
87                 if(op == rhsOp) op2 = rootOp;
88                 else op2 = (XOperator) rootOp.getBinaryInverseOp();
89
90                 // 2 + ~( 3 + ~x ) -> (2+~3) + ~~x
91 if(rootOp == rhsRoot && rootOp.isAssociative())
92                 {
93                     Node newnode = simplifyBuiltOperatorNode(op2,
94                         nf.buildConstantNode(op,lhs,rhsChild1),rhsChild2);
95                     return newnode;
96                 }
97             
98                 if(op.isDistributiveOver(rhsRoot)) // 2 * (3 + ~x) -> (2 * 3) + ~(2 @ x)
99 {
100                     Node newnode = simplifyBuiltOperatorNode(rhsOp,
101                         nf.buildConstantNode(op,lhs,rhsChild1),
102                         simplifyBuiltOperatorNode(op,lhs,rhsChild2));
103                     return newnode;
104                 }
105             }
106
107
108             if(tu.isConstant(rhsChild2))
109             {
110                 // 2 + ~( x + ~3 ) -> (2 + ~~3) + ~x
111
112                 Operator op2 = rootOp;
113                 if(op == rhsOp) op2 = rootOp;
114                 else op2 = rootOp.getBinaryInverseOp();
115
116                 if(rootOp == rhsRoot && rootOp.isCommutative() && rootOp.isAssociative())
117                 {
118                     Node newnode = simplifyBuiltOperatorNode(op,
119                         nf.buildConstantNode(op2,lhs,rhsChild2),rhsChild1);
120                     return newnode;
121                 }
122             
123                 if(op.isDistributiveOver(rhsRoot)) // 2 * (x + ~3) -> (2 * x) + ~(2 * 3)
124 {
125                     Node newnode = simplifyBuiltOperatorNode(rhsOp,
126                         simplifyBuiltOperatorNode(op,lhs,rhsChild1),
127                         nf.buildConstantNode(op,lhs,rhsChild2));
128                     return newnode;
129                 }
130             }
131         }
132
133         if(tu.isBinaryOperator(lhs) && tu.isConstant(rhs))
134         {
135             Node lhsChild1 = lhs.jjtGetChild(0);
136             Node lhsChild2 = lhs.jjtGetChild(1);
137             XOperator lhsOp = (XOperator) ((ASTFunNode) lhs).getOperator();
138             XOperator lhsRoot;
139             if(lhsOp.isComposite()) lhsRoot = (XOperator) lhsOp.getRootOp();
140             else lhsRoot = (XOperator) lhsOp;
141     
142             if(tu.isConstant(lhsChild1))
143             {
144                 // (2 + ~x) + ~3 -> (2 + ~3) + ~x
145 if(rootOp == lhsRoot && rootOp.isAssociative() && rootOp.isCommutative())
146                 {
147                     Node newnode = simplifyBuiltOperatorNode(lhsOp,
148                         nf.buildConstantNode(op,lhsChild1,rhs),
149                         lhsChild2);
150                     return newnode;
151                 }
152             
153                 // (2 + ~x) * 3 --> (2*3) +~ (x*3)
154 if(op.isDistributiveOver(lhsRoot))
155                 {
156                     Node newnode = simplifyBuiltOperatorNode(lhsOp,
157                         nf.buildConstantNode(op,lhsChild1,rhs),
158                         simplifyBuiltOperatorNode(op,lhsChild2,rhs));
159                     return newnode;
160                 }
161             }
162
163
164             if(tu.isConstant(lhsChild2))
165             {
166                 // (x + ~2) + !3 -> x + (~2 + !3) -> x + ~(2+~!3)
167 // (x*2)*3 -> x*(2*3), (x/2)*3 -> x/(2/3)
168 // (x*2)/3 -> x*(2/3), (x/2)/3 -> x/(2*3)
169 if(rootOp == lhsRoot && rootOp.isAssociative())
170                 {
171                     Operator op2 = rootOp;
172                     if(op == lhsOp) op2 = rootOp;
173                     else op2 = rootOp.getBinaryInverseOp();
174                     
175                     Node newnode = simplifyBuiltOperatorNode(lhsOp,
176                         lhsChild1,
177                         nf.buildConstantNode(op2,lhsChild2,rhs));
178                     return newnode;
179                 }
180             
181                 // (x + ~2) * 3 -> (x*3) + ~(2*3)
182 if(op.isDistributiveOver(lhsRoot))
183                 {
184                     Node newnode = simplifyBuiltOperatorNode(lhsOp,
185                         simplifyBuiltOperatorNode(op,lhsChild1,rhs),
186                         nf.buildConstantNode(op,lhsChild2,rhs));
187                     return newnode;
188                 }
189             }
190         }
191         return null;
192     }
193
194   /**
195    * Simplifies an addition. Performs the following rules
196    * <pre>
197    * 0+x -> x
198    * x+0 -> x
199    * m+n -> (m+n) where m,n are numbers
200    * x - (-2) -> x + 2 for any negative number -2
201    * x + (-2) -> x - 2 for any negative number -2
202    * 2 +/- ( 3 +/- x ) -> (2 +/- 3 ) +/- x and similar
203    * </pre>
204    */
205   
206   public Node simplifyAdd(Node lhs,Node rhs) throws ParseException
207   {
208     if(tu.isInfinity(lhs))
209     { // Inf + Inf -> NaN TODO not correct for signed infinity
210 if(tu.isInfinity(rhs))
211             return nf.buildConstantNode(tu.getNAN());
212         else // Inf + x -> Inf
213 return nf.buildConstantNode(tu.getPositiveInfinity());
214     }
215     if(tu.isInfinity(rhs)) // x + Inf -> Inf
216 return nf.buildConstantNode(tu.getPositiveInfinity());
217       
218     if(tu.isZero(lhs)) // 0+x -> x
219 return rhs;
220     if(tu.isZero(rhs)) // x + 0 -> x
221 return lhs;
222
223     if(tu.isNegative(lhs)) // -3 + x -> x - 3
224 {
225         Node newnode = nf.buildOperatorNode(opSet.getSubtract(),
226             rhs,
227             nf.buildConstantNode(opSet.getUMinus(),lhs));
228         return newnode;
229     }
230     if(tu.isNegative(rhs)) // x + -3 -> x - 3
231 {
232         Node newnode = nf.buildOperatorNode(opSet.getSubtract(),
233             lhs,
234             nf.buildConstantNode(opSet.getUMinus(),rhs));
235         return newnode;
236     }
237     return null;
238 // return nf.buildOperatorNode(node.getOperator(),lhs,dimKids[1]);
239 // return opSet.buildAddNode(lhs,dimKids[1]);
240 }
241
242   /**
243    * Simplifies a subtraction. Performs the following rules
244    * <pre>
245    * 0-x -> 0-x
246    * x-0 -> x
247    * m-n -> (m-n) where m,n are numbers
248    * x - (-2) -> x + 2 for any negative number -2
249    * x + (-2) -> x - 2 for any negative number -2
250    * 2 +/- ( 3 +/- x ) -> (2 +/- 3 ) +/- x and similar
251    * </pre>
252    * @param dimKids an array of the simplified children of this node
253    */
254   
255   public Node simplifySubtract(Node lhs,Node rhs) throws ParseException
256   {
257     if(tu.isInfinity(lhs))
258     { // Inf + Inf -> NaN TODO not correct for signed infinity
259 if(tu.isInfinity(rhs))
260             return nf.buildConstantNode(tu.getNAN());
261         else // Inf + x -> Inf
262 return nf.buildConstantNode(tu.getPositiveInfinity());
263     }
264     if(tu.isInfinity(rhs)) // x + Inf -> Inf
265 return nf.buildConstantNode(tu.getPositiveInfinity());
266
267     if(tu.isZero(rhs)) // x - 0 -> x
268 return lhs;
269     // TODO implement 0 - x -> -(x)
270
271     if(tu.isNegative(rhs)) // x - (-2) -> x + 2
272 {
273         Node newnode = simplifyBuiltOperatorNode(opSet.getAdd(),
274             lhs,
275             nf.buildConstantNode(opSet.getUMinus(),rhs));
276         return newnode;
277     }
278     return null;
279 // return nf.buildOperatorNode(((ASTOpNode) node).getOperator(),lhs,rhs);
280 // return tu.buildSubtract(lhs,rhs);
281 }
282   
283   /**
284    * Simplifies a multiplication.
285    * <pre>
286    * 0 * Inf -> NaN
287    * 0 * x -> 0
288    * x * 0 -> 0
289    * 1 * x -> x
290    * x * 1 -> x
291    * Inf * x -> Inf
292    * x * Inf -> Inf
293    * 2 * ( 3 * x) -> (2*3) * x
294    * and similar.
295    * </pre>
296    */
297   
298   public Node simplifyMultiply(Node child1,Node child2) throws ParseException
299   {
300     if(tu.isZero(child1))
301     { // 0*Inf -> NaN
302 if(tu.isInfinity(child2))
303             return nf.buildConstantNode(tu.getNAN());
304         else // 0*x -> 0
305 return nf.buildConstantNode(tu.getZERO());
306     }
307     if(tu.isZero(child2))
308     { // Inf*0 -> NaN
309 if(tu.isInfinity(child1))
310             return nf.buildConstantNode(tu.getNAN());
311         else // 0 * x -> 0
312 return nf.buildConstantNode(tu.getZERO());
313     }
314     if(tu.isInfinity(child1)) // Inf * x -> Inf
315 return nf.buildConstantNode(tu.getPositiveInfinity());
316     if(tu.isInfinity(child2)) // x * Inf -> Inf
317 return nf.buildConstantNode(tu.getPositiveInfinity());
318                   
319     if(tu.isOne(child1)) // 1*x -> x
320 return child2;
321     if(tu.isOne(child2)) // x*1 -> x
322 return child1;
323     
324     if(tu.isMinusOne(child1)) // -1*x -> -x
325 {
326         Node newnode = nf.buildOperatorNode(opSet.getUMinus(),child2);
327         return newnode;
328     }
329
330     if(tu.isMinusOne(child2)) // x*-1 -> -x
331 {
332         Node newnode = nf.buildOperatorNode(opSet.getUMinus(),child1);
333         return newnode;
334     }
335     return null;
336 // return nf.buildOperatorNode(((ASTOpNode) node).getOperator(),child1,child2);
337 // return tu.buildMultiply(child1,child2);
338 }
339     /**
340      * Simplifies a division.
341      * <pre>
342      * 0/0 -> NaN
343      * 0/Inf -> Inf
344      * 0/x -> Inf
345      * x/0 -> Inf
346      * x/1 -> x
347      * Inf / x -> Inf
348      * x / Inf -> 0
349      * 2 / ( 3 * x) -> (2/3) / x
350      * 2 / ( x * 3) -> (2/3) / x
351      * 2 / ( 3 / x) -> (2/3) * x
352      * 2 / ( x / 3) -> (2*3) / x
353      * (2 * x) / 3 -> (2/3) * x
354      * (x * 2) / 3 -> x * (2/3)
355      * (2 / x) / 3 -> (2/3) / x
356      * (x / 2) / 3 -> x / (2*3)
357      * </pre>
358      */
359     public Node simplifyDivide(Node child1,Node child2) throws ParseException
360     {
361       if(tu.isZero(child2))
362       {
363         if(tu.isZero(child1)) // 0/0 -> NaN
364 return nf.buildConstantNode(tu.getNAN());
365         else // x/0 -> Inf
366 return nf.buildConstantNode(tu.getPositiveInfinity());
367       }
368           
369       if(tu.isZero(child1))
370       { // 0/x -> 0
371 return child1;
372       }
373       //if(tu.isOne(child1)) // 1/x -> 1/x
374 // return child2;
375 if(tu.isOne(child2)) // x/1 -> x
376 return child1;
377             
378       if(tu.isInfinity(child1)) // Inf / x -> Inf
379 return nf.buildConstantNode(tu.getPositiveInfinity());
380       if(tu.isInfinity(child2)) // x / Inf -> 0
381 return nf.buildConstantNode(tu.getZERO());
382       return null;
383 // return nf.buildOperatorNode(((ASTOpNode) node).getOperator(),child1,child2);
384 // return opSet.buildDivideNode(child1,child2);
385 }
386
387     /** Simplify a power.
388      * <pre>
389      * x^0 -> 1
390      * x^1 -> x
391      * 0^0 -> NaN
392      * 0^x -> 0
393      * 1^x -> 1
394      * </pre>
395      */
396     public Node simplifyPower(Node child1,Node child2) throws ParseException
397     {
398         if(tu.isZero(child1))
399         {
400             if(tu.isZero(child2)) // 0^0 -> NaN
401 return nf.buildConstantNode(tu.getNAN());
402             else // 0^x -> 0
403 return nf.buildConstantNode(tu.getZERO());
404         }
405         if(tu.isZero(child2)) // x^0 -> 1
406 return nf.buildConstantNode(tu.getONE());
407         if(tu.isOne(child1)) // 1^x -> 1
408 return nf.buildConstantNode(tu.getONE());
409         if(tu.isOne(child2)) // x^1 -> x
410 return child1;
411             
412         if(tu.isConstant(child2) && tu.getOperator(child1) == opSet.getPower())
413         {
414             if(tu.isConstant(child1.jjtGetChild(1)))
415             {
416                 /* (x^3)^4 -> x^(3*4) */
417                 return nf.buildOperatorNode(
418                     opSet.getPower(),
419                     child1.jjtGetChild(0),
420                     nf.buildConstantNode(
421                         opSet.getMultiply(),
422                         child1.jjtGetChild(1),
423                         child2));
424             }
425         }
426         return null;
427 // return nf.buildOperatorNode(((ASTOpNode) node).getOperator(),child1,child2);
428 // return tu.buildPower(child1,child2);
429 }
430
431     /** simplifies operators, does not decend into children */
432
433     public Node simplifyOp(ASTFunNode node,Node children[]) throws ParseException
434     {
435         boolean allConst=true;
436         XOperator op= (XOperator) node.getOperator();
437         // TODO a bit of a hack to prevent lists of constants being converted
438 // what happens is that for [[1,2],[3,4]] the dimension is not passed
439 // into buildConstantNode so list is treated as [1,2,3,4]
440 // Ideally there would be a special simplification rule for List
441 if(op.getPFMC() instanceof org.nfunk.jep.function.List) return node;
442         int nchild=children.length;
443         for(int i=0;i<nchild;++i)
444         {
445             if(!tu.isConstant(children[i]))
446                 allConst=false;
447             if(tu.isNaN(children[i]))
448                 return nf.buildConstantNode(tu.getNAN());
449         }
450         if(allConst)
451             return nf.buildConstantNode(op,children);
452         
453         if(nchild==1)
454         {
455             if(tu.isUnaryOperator(children[0]) && op == tu.getOperator(children[0]))
456             {
457                 if(op.isSelfInverse()) return children[0].jjtGetChild(0);
458             }
459         }
460         if(nchild==2)
461         {
462             Node res=null;
463             if(opSet.getAdd() == op) res = simplifyAdd(children[0],children[1]);
464             if(opSet.getSubtract() == op) res = simplifySubtract(children[0],children[1]);
465             if(opSet.getMultiply() == op) res = simplifyMultiply(children[0],children[1]);
466             if(opSet.getDivide() == op) res = simplifyDivide(children[0],children[1]);
467             if(opSet.getPower() == op) res = simplifyPower(children[0],children[1]);
468             if(res!=null)
469             {
470                 if(tu.isConstant(res)) return res;
471                 if(tu.isOperator(res))
472                 {
473                     Node res2 = simplifyOp((ASTFunNode) res,TreeUtils.getChildrenAsArray(res));
474                     return res2;
475                 }
476                 return res;
477             }
478             res = this.simplifyTripple(op,children[0],children[1]);
479             if(res!=null)
480             {
481                 if(tu.isConstant(res)) return res;
482                 if(tu.isOperator(res))
483                 {
484                     Node res2 = simplifyOp((ASTFunNode) res,TreeUtils.getChildrenAsArray(res));
485                     return res2;
486                 }
487                 return res;
488             }
489         }
490         return node;
491     }
492     
493     public Object JavaDoc visit(ASTFunNode node, Object JavaDoc data) throws ParseException
494     {
495         int nchild = node.jjtGetNumChildren();
496
497         if(node.isOperator())
498         {
499             XOperator op= (XOperator) node.getOperator();
500             if( (op.isBinary() && nchild !=2)
501              || (op.isUnary() && nchild !=1))
502              throw new ParseException("Wrong number of children for "+nchild+" for operator "+op.getName());
503     
504             Node children[] = acceptChildrenAsArray(node,data);
505             TreeUtils.copyChildrenIfNeeded(node,children);
506     
507             Node res = simplifyOp(node,children);
508             if(res == null)
509                 throw new ParseException("null res from simp op");
510             return res;
511         }
512         else
513         {
514             Node children[] = acceptChildrenAsArray(node,data);
515
516             boolean allConst=true;
517             for(int i=0;i<nchild;++i)
518             {
519                 if(!tu.isConstant(children[i]))
520                     allConst=false;
521                 if(tu.isNaN(children[i]))
522                     return nf.buildConstantNode(tu.getNAN());
523             }
524             if(allConst)
525                 return nf.buildConstantNode(node.getPFMC(),children);
526         
527             return TreeUtils.copyChildrenIfNeeded(node,children);
528         }
529     }
530 }
531
Popular Tags