RpEval


1   /* @author rich
2    * Created on 14-Apr-2004
3    *
4    * This code is covered by a Creative Commons
5    * Attribution, Non Commercial, Share Alike license
6    * <a HREF="http://creativecommons.org/licenses/by-nc-sa/1.0">License</a>
7    */
8   package org.lsmp.djep.rpe;
9   import org.nfunk.jep.*;
10  import org.nfunk.jep.function.*;
11  import java.util.*;
12  /**
13   * A fast evaluation algorithm for equations over Doubles, does not work with vectors or matricies.
14   * This is based around reverse polish notation
15   * and is optimised for speed at every oportunity.
16   * <p>
17   * To use do
18   * <pre>
19   * JEP j = ...;
20   * Node node = ...; 
21   * RpEval rpe = new RpEval(j);
22   * RpCommandList list = rpe.compile(node);
23   * double val rpRes = rpe.evaluate(list);
24   * System.out.println(val);
25   * rpe.cleanUp();
26   * </pre>
27   * The compile methods converts the expresion represented by node
28   * into a string of commands. For example the expresion "1+2*3" will
29   * be converted into the sequence of commands
30   * <pre>
31   * Constant no 1 (pushes constant onto stack)
32   * Constant no 2
33   * Constant no 3
34   * Multiply scalers (multiplies last two entries on stack)
35   * Add scalers (adds last two entries on stack)
36   * </pre>
37   * The evaluate method executes these methods sequentially
38   * using a stack 
39   * and returns thoe last object on the stack. 
40   * <p>
41   * A few cautionary notes:
42   * Its very unlikely to be thread safe. It only works over doubles
43   * expresions with complex numbers or strings will cause problems.
44   * It only works for expressions involving scalers.
45   * <p>
46   * <b>Implementation notes</b>
47   * A lot of things have been done to make it as fast as posible:
48   * <ul>
49   * <li>Everything is final which maximises the possibility for inlining.</li>
50   * <li>All object creation happens during compile.</li>
51   * <li>All calculations done using double values.</li>
52   * <li>Each operator/function is hand coded. To extend functionality you will have to modify the source.</li>
53   * </ul>
54   *  
55   * @author Rich Morris
56   * Created on 14-Apr-2004
57   */
58  public final class RpEval implements ParserVisitor {
59  
60      /** The mjep reference **/
61      private JEP jep;
62      private OperatorSet opSet;
63      private ScalerStore scalerStore = new ScalerStore();
64      /** Contains the constant values **/
65      private double constVals[] = new double[0];
66  
67      /** Tempoary holder for command list used during compilation */
68      private RpCommandList curCommandList;
69  
70      public RpEval(JEP jep) {
71          this.jep = jep;
72          this.opSet = jep.getOperatorSet();
73      }
74  
75      private RpEval() {}
76      
77      /** Index for each command */
78      static final short CONST = 0;
79      static final short VAR = 1;
80  
81      static final short ADD = 2;
82      static final short SUB = 3;
83      static final short MUL = 4;
84      
85      static final short DIV = 5;
86      static final short MOD = 6;
87      static final short POW = 7;
88  
89      static final short AND = 8;
90      static final short OR  = 9;
91      static final short NOT = 10;
92  
93      static final short LT = 11;
94      static final short LE = 12;
95      static final short GT = 13;
96      static final short GE = 14;
97      static final short NE = 15;
98      static final short EQ = 16;
99      
100     static final short LIST = 17;
101     static final short DOT = 18;
102     static final short CROSS = 19;
103 
104     static final short ASSIGN = 20;
105     static final short VLIST = 21;
106     static final short MLIST = 22;
107     static final short FUN = 23;
108     static final short UMINUS = 24;
109     
110     /** Standard functions **/
111     
112     private static final short SIN = 1;
113     private static final short COS = 2;
114     private static final short TAN = 3;
115     private static final short ASIN = 4;
116     private static final short ACOS = 5;
117     private static final short ATAN = 6;
118     private static final short SINH = 7;
119     private static final short COSH = 8;
120     private static final short TANH = 9;
121     private static final short ASINH = 10;
122     private static final short ACOSH = 11;
123     private static final short ATANH = 12;
124     
125     private static final short ABS = 13;
126     private static final short EXP = 14;
127     private static final short LOG = 15;
128     private static final short LN = 16;
129     private static final short SQRT = 17;
130     
131     private static final short SEC = 18;
132     private static final short COSEC = 19;
133     private static final short COT = 20;
134     
135     // 2 argument functions
136     private static final short ANGLE = 21;
137     private static final short MODULUS = 22;
138 
139 
140     /** Hashtable for function name lookup **/
141     
142     private static final Hashtable functionHash = new Hashtable();
143     {
144         functionHash.put("sin",new Short  (SIN));
145         functionHash.put("cos",new Short  (COS));
146         functionHash.put("tan",new Short  (TAN));
147         functionHash.put("asin",new Short  (ASIN));
148         functionHash.put("acos",new Short  (ACOS));
149         functionHash.put("atan",new Short  (ATAN));
150         functionHash.put("sinh",new Short  (SINH));
151         functionHash.put("cosh",new Short  (COSH));
152         functionHash.put("tanh",new Short  (TANH));
153         functionHash.put("asinh",new Short  (ASINH));
154         functionHash.put("acosh",new Short  (ACOSH));
155         functionHash.put("atanh",new Short  (ATANH));
156 
157         functionHash.put("abs",new Short  (ABS));
158         functionHash.put("exp",new Short  (EXP));
159         functionHash.put("log",new Short  (LOG));
160         functionHash.put("ln",new Short  (LN));
161         functionHash.put("sqrt",new Short  (SQRT));
162 
163         functionHash.put("sec",new Short  (SEC));
164         functionHash.put("cosec",new Short  (COSEC));
165         functionHash.put("cot",new Short  (COT));
166     }
167 
168     
169 
170     /**
171      * Base class for storage for each type of data.
172      * Each subclass should define
173      * <pre>
174      * private Obj stack[];
175      * private Obj heep[];
176      * private Obj vars[]= new Obj[0];
177      * </pre>
178      * where Obj is an Object of the specific type, eg V2Obj.
179      * Memory for the data is allocated from the heep
180      * and the stack is the current data used for calculations.
181      * Data for Variables is stored in vars and references to the Variables
182      * in varRefs. 
183      */
184     private abstract static class ObjStore implements Observer {
185         /** Contains references to Variables of this type */
186         Hashtable varRefs = new Hashtable();
187         /** The stack pointer */
188         int sp=0;
189         /** Maximum size of stack */
190         int stackMax=0;
191         final void incStack()   {sp++; if(sp > stackMax) stackMax = sp; }
192         final void decStack()   throws ParseException {--sp; if(sp <0 ) throw new ParseException("RPEval: stack error");}
193         /** call this to reset pointers as first step in evaluation */
194         final void reset() { sp = 0; }
195         /** Add a reference to this variable. 
196          * @return the index of variable in table
197          */
198         final int addVar(Variable var){
199             Object   index = varRefs.get(var);
200             if(index==null)
201             {
202                 int size = varRefs.size();
203                 expandVarArray(size+1);
204                 varRefs.put(var,new Integer  (size));
205                 copyFromVar(var,size);
206                 var.addObserver(this);
207                 return size;
208             }
209             else
210             {
211                 return ((Integer  ) index).intValue();
212             }
213         }
214         final public void update(Observable obs, Object   arg1) 
215         {
216             Variable var = (Variable) obs;
217             Object   index = varRefs.get(var);
218             copyFromVar(var,((Integer  ) index).intValue());
219         }
220         /** allocates space needed */
221         abstract void alloc();
222         
223         final void cleanUp()
224         {
225             for(Enumeration e=varRefs.keys();e.hasMoreElements();)
226             {
227                 Variable var = (Variable) e.nextElement();
228                 var.deleteObserver(this);
229             }
230             varRefs.clear();
231         }
232         /** Copy variable values into into private storage. 
233          * 
234          * @param var The variable
235          * @param i index of element in array
236          */
237         abstract void copyFromVar(Variable var,int i);
238         /** expand size of array used to hold variable values. */
239         abstract void expandVarArray(int i);
240         /** add two objects of same type */
241         abstract void add();
242         /** subtract two objects of same type */
243         abstract void sub();
244         /** multiply by a scaler either of left or right */
245         abstract void mulS();
246         /** assign a variable to stack value
247          * @param i index of variable */
248         abstract void assign(int i);
249     }
250 
251     private final class ScalerStore extends ObjStore {
252         private double stack[]=new double[0];
253         private double vars[]= new double[0];
254         final void alloc() { 
255             stack = new double[stackMax];
256             }
257         final void expandVarArray(int size)
258         {
259             double newvars[] = new double[size];
260             System.arraycopy(vars,0,newvars,0,vars.length);
261             vars = newvars;
262         }
263             
264         final void copyFromVar(Variable var,int i){
265             if(var.hasValidValue())
266             {
267                 Double   val = (Double  ) var.getValue();
268                 vars[i]=val.doubleValue();
269             }
270         }
271         final void add(){
272             double r = stack[--sp];
273             stack[sp-1] += r;
274         }
275         final void sub(){
276             double r = stack[--sp];
277             stack[sp-1] -= r;
278         }
279         final void uminus(){
280             double r = stack[--sp];
281                 stack[sp++] = -r;
282         }
283         final void mulS(){
284             double r = stack[--sp];
285             stack[sp-1] *= r;
286         } 
287         final void div(){
288             double r = stack[--sp];
289             stack[sp-1] /= r;
290         } 
291         final void mod(){
292             double r = stack[--sp];
293             stack[sp-1] %= r;
294         } 
295         final void pow(){
296             double r = stack[--sp];
297             double l = stack[--sp];
298             stack[sp++] = Math.pow(l,r);
299         } 
300         final void powN(int n){
301             double r = stack[--sp];
302             switch(n){
303                 case 0: r = 1.0; break;
304                 case 1: break;
305                 case 2: r *= r; break;
306                 case 3: r *= r*r; break;
307                 case 4: r *= r*r*r; break;
308                 case 5: r *= r*r*r*r; break;
309                 default:
310                     r = Math.pow(r,n); break;
311             }
312             stack[sp++] = r;
313         } 
314         final void assign(int i) {
315             vars[i] = stack[--sp]; ++sp;
316         } 
317         final void and(){
318             double r = stack[--sp];
319             double l = stack[--sp];
320             if((l != 0.0) && (r != 0.0))
321                 stack[sp++] = 1.0;
322             else
323                 stack[sp++] = 0.0;
324         }
325         final void or(){
326             double r = stack[--sp];
327             double l = stack[--sp];
328             if((l != 0.0) || (r != 0.0))
329                 stack[sp++] = 1.0;
330             else
331                 stack[sp++] = 0.0;
332         }
333         final void not(){
334             double r = stack[--sp];
335             if(r == 0.0)
336                 stack[sp++] = 1.0;
337             else
338                 stack[sp++] = 0.0;
339         }
340         final void lt(){
341             double r = stack[--sp];
342             double l = stack[--sp];
343             if(l < r)
344                 stack[sp++] = 1.0;
345             else
346                 stack[sp++] = 0.0;
347         }
348         final void gt(){
349             double r = stack[--sp];
350             double l = stack[--sp];
351             if(l > r)
352                 stack[sp++] = 1.0;
353             else
354                 stack[sp++] = 0.0;
355         }
356         final void le(){
357             double r = stack[--sp];
358             double l = stack[--sp];
359             if(l <= r)
360                 stack[sp++] = 1.0;
361             else
362                 stack[sp++] = 0.0;
363         }
364         final void ge(){
365             double r = stack[--sp];
366             double l = stack[--sp];
367             if(l >= r)
368                 stack[sp++] = 1.0;
369             else
370                 stack[sp++] = 0.0;
371         }
372         final void eq(){
373             double r = stack[--sp];
374             double l = stack[--sp];
375             if(l == r)
376                 stack[sp++] = 1.0;
377             else
378                 stack[sp++] = 0.0;
379         }
380         final void neq(){
381             double r = stack[--sp];
382             double l = stack[--sp];
383             if(l != r)
384                 stack[sp++] = 1.0;
385             else
386                 stack[sp++] = 0.0;
387         }
388         /* (non-Javadoc)
389          * @see java.util.Observer#update(java.util.Observable, java.lang.Object)
390          */
391 
392     }
393     
394     /**
395      * Compile the expresions to produce a set of commands in reverse Polish notation.
396      */
397     public final RpCommandList compile(Node node) throws ParseException
398     {
399         curCommandList = new RpCommandList();
400         node.jjtAccept(this,null);
401         scalerStore.alloc();
402         return curCommandList;
403     }
404     
405     public final Object   visit(ASTStart node, Object   data) throws ParseException {
406         throw new ParseException("RpeEval: Start node encountered");
407     }
408     public final Object   visit(SimpleNode node, Object   data) throws ParseException {
409         throw new ParseException("RpeEval: Simple node encountered");
410     }
411 
412     public final Object   visit(ASTConstant node, Object   data) throws ParseException {
413         Object   obj = node.getValue();
414         double val;
415         if(obj instanceof Double  )
416             val = ((Double  ) node.getValue()).doubleValue();
417         else
418             throw new ParseException("RpeEval: only constants of double type allowed");
419         
420         scalerStore.incStack();
421         for(short i=0;i<constVals.length;++i)
422         {
423             if(val == constVals[i])
424             {
425                 curCommandList.addCommand(CONST,i);
426                 return null;
427             }
428         }
429         // create a new const
430         double newConst[] = new double[constVals.length+1];
431         System.arraycopy(constVals,0,newConst,0,constVals.length);
432         newConst[constVals.length] = val;
433         curCommandList.addCommand(CONST,(short) constVals.length);
434         constVals = newConst;
435         return null;
436     }
437 
438     public final Object   visit(ASTVarNode node, Object   data) throws ParseException 
439     {
440         Variable var = (Variable) node.getVar();
441         // find appropriate table
442         short vRef = (short) scalerStore.addVar(var);
443         scalerStore.incStack();
444         curCommandList.addCommand(VAR,vRef);
445         return null;
446     }
447 
448     public final Object   visit(ASTFunNode node, Object   data) throws ParseException 
449     {
450         int nChild = node.jjtGetNumChildren();
451 
452         if(node.getPFMC() instanceof SpecialEvaluationI )
453         {               
454         }
455         else
456             node.childrenAccept(this,null);
457 
458         if(node.isOperator())
459         {
460             Operator op = node.getOperator();
461 
462             if(op == opSet.getAdd())
463             {
464                 curCommandList.addCommand(ADD);
465                 scalerStore.decStack();
466                 return null;
467             }
468             else if(op == opSet.getSubtract())
469             {
470                 curCommandList.addCommand(SUB);
471                 scalerStore.decStack();
472                 return null;
473             }
474             else if(op == opSet.getUMinus())
475             {
476                 curCommandList.addCommand(UMINUS);
477                 return null;
478             }
479             else if(op == opSet.getMultiply())
480             {
481                 scalerStore.decStack();
482                 curCommandList.addCommand(MUL);
483                 return null;
484             }
485             else if(op == opSet.getAssign())
486             {
487                 Node rightnode = node.jjtGetChild(1);
488                 rightnode.jjtAccept(this,null);
489                 Variable var = (Variable) ((ASTVarNode)node.jjtGetChild(0)).getVar();
490                 short vRef = (short) scalerStore.addVar(var);
491                 scalerStore.decStack();
492                 curCommandList.addCommand(ASSIGN,vRef);
493                 return null;
494             }
495             else if(op == opSet.getEQ())
496             {
497                 scalerStore.decStack();
498                 curCommandList.addCommand(EQ); return null;
499             }
500             else if(op == opSet.getNE())
501             {
502                 scalerStore.decStack();
503                 curCommandList.addCommand(NE); return null;
504             }
505             else if(op == opSet.getLT())
506             {
507                 scalerStore.decStack();
508                 curCommandList.addCommand(LT); return null;
509             }
510             else if(op == opSet.getGT())
511             {
512                 scalerStore.decStack();
513                 curCommandList.addCommand(GT); return null;
514             }
515             else if(op == opSet.getLE())
516             {
517                 scalerStore.decStack();
518                 curCommandList.addCommand(LE); return null;
519             }
520             else if(op == opSet.getGE())
521             {
522                 scalerStore.decStack();
523                 curCommandList.addCommand(GE); return null;
524             }
525             else if(op == opSet.getAnd())
526             {
527                 scalerStore.decStack();
528                 curCommandList.addCommand(AND); return null;
529             }
530             else if(op == opSet.getOr())
531             {
532                 scalerStore.decStack();
533                 curCommandList.addCommand(OR); return null;
534             }
535             else if(op == opSet.getNot())
536             {
537                 //scalerStore.decStack();
538                 curCommandList.addCommand(NOT); return null;
539             }
540             else if(op == opSet.getDivide())
541             {
542                 scalerStore.decStack();
543                 curCommandList.addCommand(DIV); return null;
544             }
545             else if(op == opSet.getMod())
546             {
547                 scalerStore.decStack();
548                 curCommandList.addCommand(MOD); return null;
549             }
550             else if(op == opSet.getPower())
551             {
552                 scalerStore.decStack();
553                 curCommandList.addCommand(POW); return null;
554             }
555             throw new ParseException("RpeEval: Sorry unsupported operator/function: "+ node.getName());
556         }
557         else    // other functions
558         {
559             Short   val = (Short  ) functionHash.get(node.getName());
560             if(val == null)
561                 throw new ParseException("RpeEval: Sorry unsupported operator/function: "+ node.getName());
562             if(node.getPFMC().getNumberOfParameters() == 1 && nChild == 1)
563             {
564                 //scalerStore.decStack();
565                 curCommandList.addCommand(FUN,val.shortValue()); 
566                 return null;
567             }
568             else
569                 throw new ParseException("RpeEval: sorry can currently only support single argument functions");
570         }
571     }
572 
573     /***************************** evaluation *****************************/
574     
575     /** Evaluate the expression.
576      * 
577      * @return the double value of the equation
578      */
579     public final double evaluate(RpCommandList comList)
580     {
581         scalerStore.reset();
582     
583         // Now actually process the commands
584         int num = comList.getNumCommands();
585         for(short commandNum=0;commandNum<num;++commandNum)
586         {
587             RpCommandList.RpCommand command = comList.commands[commandNum];
588             short aux1 = command.aux1;
589             switch(command.command)
590             {
591             case CONST:
592                 scalerStore.stack[scalerStore.sp++]=constVals[aux1]; break;
593             case VAR:
594                 scalerStore.stack[scalerStore.sp++]=scalerStore.vars[aux1]; break;
595                 
596             case ADD: scalerStore.add(); break;
597             case SUB: scalerStore.sub(); break; 
598             case MUL: scalerStore.mulS(); break;
599             case DIV: scalerStore.div(); break;
600             case MOD: scalerStore.mod(); break;
601             case POW: scalerStore.pow(); break;
602 
603             case AND: scalerStore.and(); break;
604             case OR:  scalerStore.or(); break;
605             case NOT: scalerStore.not(); break;
606 
607             case LT: scalerStore.lt(); break;
608             case LE: scalerStore.le(); break;
609             case GT: scalerStore.gt(); break;
610             case GE: scalerStore.ge(); break;
611             case NE: scalerStore.neq(); break;
612             case EQ: scalerStore.eq(); break;
613             case ASSIGN: scalerStore.assign(aux1); break;
614             case FUN: unitaryFunction(aux1); break;
615             case UMINUS: scalerStore.uminus(); break;
616             }
617         }
618 
619         return scalerStore.stack[--scalerStore.sp];
620     }
621 
622     
623     private static final double LOG10 = Math.log(10.0);
624 
625     private final void unitaryFunction(short fun)
626     {
627         double r = scalerStore.stack[--scalerStore.sp];
628         switch(fun) {
629             case SIN: r = Math.sin(r); break;
630             case COS: r = Math.cos(r); break;
631             case TAN: r = Math.tan(r); break;
632 
633             case ASIN: r = Math.asin(r); break;
634             case ACOS: r = Math.acos(r); break;
635             case ATAN: r = Math.atan(r); break;
636 
637             case SINH: r = (Math.exp(r)-Math.exp(-r))/2; break;
638             case COSH: r = (Math.exp(r)+Math.exp(-r))/2; break;
639             case TANH: 
640                 {double ex = Math.exp(r*2);
641                  r = (ex-1)/(ex+1); break;
642                 }
643 
644             case ASINH: r = Math.log(r+Math.sqrt(1+r*r)); break;
645             case ACOSH: r = Math.log(r+Math.sqrt(r*r-1)); break;
646             case ATANH: r = Math.log((1+r)/(1-r))/2.0; break;
647 
648             case ABS: r = Math.abs(r); break;
649             case EXP: r = Math.exp(r); break;
650             case LOG: r = Math.log(r) / LOG10; break;
651             case LN:  r = Math.log(r); break;
652             case SQRT: r = Math.sqrt(r); break;
653 
654             case SEC: r = 1.0/Math.cos(r); break;
655             case COSEC:  r = 1.0/Math.sin(r); break;
656             case COT: r = 1.0/Math.tan(r); break;
657         }
658         scalerStore.stack[scalerStore.sp++] = r;
659     }
660     
661     /**
662      * Removes observers and other cleanup needed when evaluator no longer used.
663      */
664     public void cleanUp()
665     {
666         scalerStore.cleanUp();
667     }
668 }
669
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags