1 /*
  2  JessieCode Computer algebra algorithms
  3 
  4     Copyright 2011-2016
  5         Michael Gerhaeuser,
  6         Alfred Wassermann
  7 
  8     JessieCode is free software dual licensed under the GNU LGPL or MIT License.
  9 
 10     You can redistribute it and/or modify it under the terms of the
 11 
 12       * GNU Lesser General Public License as published by
 13         the Free Software Foundation, either version 3 of the License, or
 14         (at your option) any later version
 15       OR
 16       * MIT License: https://github.com/jsxgraph/jsxgraph/blob/master/LICENSE.MIT
 17 
 18     JessieCode is distributed in the hope that it will be useful,
 19     but WITHOUT ANY WARRANTY; without even the implied warranty of
 20     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 21     GNU Lesser General Public License for more details.
 22 
 23     You should have received a copy of the GNU Lesser General Public License and
 24     the MIT License along with JessieCode. If not, see <http://www.gnu.org/licenses/>
 25     and <http://opensource.org/licenses/MIT/>.
 26  */
 27 
 28  /*global JXG: true, define: true, window: true, console: true, self: true, document: true, parser: true*/
 29  /*jslint nomen: true, plusplus: true*/
 30 
 31  /* depends:
 32   jxg
 33   parser/geonext
 34   base/constants
 35   base/text
 36   math/math
 37   math/geometry
 38   math/statistics
 39   utils/type
 40   utils/uuid
 41   */
 42 
 43  /**
 44   * @fileoverview Here, the computer algebra algorithms are implemented.
 45   */
 46 
 47  define([
 48      'jxg', 'base/constants', 'base/text', 'math/math', 'math/geometry', 'math/statistics', 'utils/type', 'utils/env'
 49  ], function (JXG, Const, Text, Mat, Geometry, Statistics, Type, Env) {
 50 
 51      "use strict";
 52 
 53      /**
 54       * A JessieCode object provides an interface to the parser and stores all variables and objects used within a JessieCode script.
 55       * The optional argument <tt>code</tt> is interpreted after initializing. To evaluate more code after initializing a JessieCode instance
 56       * please use {@link JXG.JessieCode#parse}. For code snippets like single expressions use {@link JXG.JessieCode#snippet}.
 57       * @constructor
 58       * @param {String} [code] Code to parse.
 59       * @param {Boolean} [geonext=false] Geonext compatibility mode.
 60       */
 61      JXG.CA = function (node, createNode, parser) {
 62          this.node = node;
 63          this.createNode = createNode;
 64          this.parser = parser;
 65      };
 66 
 67      JXG.extend(JXG.CA.prototype, /** @lends JXG.CA.prototype */ {
 68          findMapNode: function(mapname, node) {
 69              var i, len, ret;
 70 
 71              //console.log("FINDMAP", node);
 72              if (node.value === 'op_assign' && node.children[0].value === mapname) {
 73                  return node.children[1];
 74              } else if (node.children) {
 75                  len = node.children.length;
 76                  for (i = 0; i < len; ++i) {
 77                      ret = this.findMapNode(mapname, node.children[i]);
 78                      if (ret !== null) {
 79                          return ret;
 80                      }
 81                  }
 82              }
 83              return null;
 84          },
 85 
 86          /**
 87           * Declare all subnodes as math nodes,
 88           * i.e recursively set node.isMath = true;
 89           */
 90          setMath: function(node) {
 91              var i, len;
 92 
 93              if ((node.type == 'node_op' && (
 94                  node.value == 'op_add' || node.value == 'op_sub' ||
 95                  node.value == 'op_mul' || node.value == 'op_div' ||
 96                  node.value == 'op_neg' || node.value == 'op_execfun' ||
 97                  node.value == 'op_exp')) ||
 98                  node.type == 'node_var' || node.type == 'node_const') {
 99 
100                  node.isMath = true;
101              }
102              if (node.children) {
103                  len = node.children.length;
104                  for (i = 0; i < len; ++i) {
105                      this.setMath(node.children[i]);
106                  }
107              }
108          },
109 
110          deriveElementary: function(node, varname) {
111              var fun = node.children[0].value,
112                  arg = node.children[1],
113                  newNode;
114 
115 
116              switch (fun) {
117              case 'abs':
118                  // x / sqrt(x * x)
119                  newNode = this.createNode('node_op', 'op_div',
120                          arg[0],
121                          this.createNode('node_op', 'op_execfun',
122                              this.createNode('node_var', 'sqrt'),
123                              [this.createNode('node_op', 'op_mul',
124                                  Type.deepCopy(arg[0]),
125                                  Type.deepCopy(arg[0])
126                              )]
127                          )
128                      );
129                  break;
130 
131              case 'sqrt':
132                  newNode = this.createNode('node_op', 'op_div',
133                          this.createNode('node_const', 1.0),
134                          this.createNode('node_op', 'op_mul',
135                              this.createNode('node_const', 2.0),
136                              this.createNode(node.type, node.value,
137                                  Type.deepCopy(node.children[0]),
138                                  Type.deepCopy(node.children[1])
139                              )
140                          )
141                      );
142                  break;
143 
144              case 'sin':
145                  newNode = this.createNode('node_op', 'op_execfun',
146                          this.createNode('node_var', 'cos'),
147                          Type.deepCopy(arg)
148                      );
149                  break;
150 
151              case 'cos':
152                  newNode = this.createNode('node_op', 'op_neg',
153                              this.createNode('node_op', 'op_execfun',
154                                  this.createNode('node_var', 'sin'),
155                                  Type.deepCopy(arg)
156                              )
157                          );
158                  break;
159 
160              case 'tan':
161                  newNode = this.createNode('node_op', 'op_div',
162                              this.createNode('node_const', 1.0),
163                              this.createNode('node_op', 'op_exp',
164                                  this.createNode('node_op', 'op_execfun',
165                                      this.createNode('node_var', 'cos'),
166                                      Type.deepCopy(arg)
167                                  ),
168                                  this.createNode('node_const', 2)
169                              )
170                          );
171                  break;
172 
173              case 'exp':
174                  newNode = this.createNode(node.type, node.value,
175                              Type.deepCopy(node.children[0]),
176                              Type.deepCopy(node.children[1])
177                          );
178                  break;
179 
180              case 'pow':
181                  // (f^g)' = f^g*(f'g/f + g' log(f))
182                  newNode = this.createNode('node_op', 'op_mul',
183                          this.createNode('node_op', 'op_execfun',
184                              Type.deepCopy(node.children[0]),
185                              Type.deepCopy(node.children[1])
186                          ),
187                          this.createNode('node_op', 'op_add',
188                              this.createNode('node_op', 'op_mul',
189                                  this.derivative(node.children[1][0], varname),
190                                  this.createNode('node_op', 'op_div',
191                                      Type.deepCopy(node.children[1][1]),
192                                      Type.deepCopy(node.children[1][0])
193                                  )
194                              ),
195                              this.createNode('node_op', 'op_mul',
196                                  this.derivative(node.children[1][1], varname),
197                                  this.createNode('node_op', 'op_execfun',
198                                      this.createNode('node_var', 'log'),
199                                      [Type.deepCopy(node.children[1][0])]
200                                  )
201                              )
202                          )
203                      );
204                  break;
205 
206              case 'log':
207              case 'ln':
208                  newNode = this.createNode('node_op', 'op_div',
209                              this.createNode('node_const', 1.0),
210                              // Attention: single variable mode
211                              Type.deepCopy(arg[0])
212                          );
213                  break;
214 
215              case 'log2':
216              case 'lb':
217              case 'ld':
218                  newNode = this.createNode('node_op', 'op_mul',
219                              this.createNode('node_op', 'op_div',
220                                  this.createNode('node_const', 1.0),
221                                  // Attention: single variable mode
222                                  Type.deepCopy(arg[0])
223                              ),
224                              this.createNode('node_const', 1.4426950408889634)  // 1/log(2)
225                          );
226                  break;
227 
228              case 'log10':
229              case 'lg':
230                  newNode = this.createNode('node_op', 'op_mul',
231                              this.createNode('node_op', 'op_div',
232                                  this.createNode('node_const', 1.0),
233                                  // Attention: single variable mode
234                                  Type.deepCopy(arg[0])
235                              ),
236                              this.createNode('node_const', 0.43429448190325176)  // 1/log(10)
237                          );
238                  break;
239 
240              case 'asin':
241                  newNode = this.createNode('node_op', 'op_div',
242                              this.createNode('node_const', 1.0),
243                              this.createNode('node_op', 'op_execfun',
244                                  this.createNode('node_var', 'sqrt'),
245                                  [
246                                      this.createNode('node_op', 'op_sub',
247                                          this.createNode('node_const', 1.0),
248                                          this.createNode('node_op', 'op_mul',
249                                              Type.deepCopy(arg[0]),
250                                              Type.deepCopy(arg[0])
251                                          )
252                                      )
253                                  ]
254                              )
255                          );
256                  break;
257 
258              case 'acos':
259                  newNode = this.createNode('node_op', 'op_neg',
260                          this.createNode('node_op', 'op_div',
261                              this.createNode('node_const', 1.0),
262                              this.createNode('node_op', 'op_execfun',
263                                  this.createNode('node_var', 'sqrt'),
264                                  [
265                                      this.createNode('node_op', 'op_sub',
266                                          this.createNode('node_const', 1.0),
267                                          this.createNode('node_op', 'op_mul',
268                                              Type.deepCopy(arg[0]),
269                                              Type.deepCopy(arg[0])
270                                          )
271                                      )
272                                  ]
273                              )
274                          )
275                      );
276                  break;
277 
278              case 'atan':
279                  newNode = this.createNode('node_op', 'op_div',
280                              this.createNode('node_const', 1.0),
281                              this.createNode('node_op', 'op_add',
282                                  this.createNode('node_const', 1.0),
283                                  this.createNode('node_op', 'op_mul',
284                                      Type.deepCopy(arg[0]),
285                                      Type.deepCopy(arg[0])
286                                  )
287                              )
288                          );
289                  break;
290 
291              //case 'atan2':
292              case 'sinh':
293                  newNode = this.createNode('node_op', 'op_execfun',
294                              this.createNode('node_var', 'cosh'),
295                              [Type.deepCopy(arg[0])]
296                          );
297                  break;
298 
299              case 'cosh':
300                  newNode = this.createNode('node_op', 'op_execfun',
301                              this.createNode('node_var', 'sinh'),
302                              [Type.deepCopy(arg[0])]
303                          );
304                  break;
305 
306              case 'tanh':
307                  newNode = this.createNode('node_op', 'op_sub',
308                              this.createNode('node_const', 1.0),
309                              this.createNode('node_op', 'op_exp',
310                                  this.createNode('node_op', 'op_execfun',
311                                      this.createNode('node_var', 'tanh'),
312                                      [Type.deepCopy(arg[0])]
313                                  ),
314                                  this.createNode('node_const', 2.0)
315                              )
316                          );
317                  break;
318 
319              case 'asinh':
320                  newNode = this.createNode('node_op', 'op_div',
321                              this.createNode('node_const', 1.0),
322                              this.createNode('node_op', 'op_execfun',
323                                  this.createNode('node_var', 'sqrt'),
324                                  [
325                                      this.createNode('node_op', 'op_add',
326                                          this.createNode('node_op', 'op_mul',
327                                              Type.deepCopy(arg[0]),
328                                              Type.deepCopy(arg[0])
329                                          ),
330                                          this.createNode('node_const', 1.0)
331                                      )
332                                  ]
333                              )
334                          );
335                  break;
336 
337              case 'acosh':
338                  newNode = this.createNode('node_op', 'op_div',
339                              this.createNode('node_const', 1.0),
340                              this.createNode('node_op', 'op_execfun',
341                                  this.createNode('node_var', 'sqrt'),
342                                  [
343                                      this.createNode('node_op', 'op_sub',
344                                          this.createNode('node_op', 'op_mul',
345                                              Type.deepCopy(arg[0]),
346                                              Type.deepCopy(arg[0])
347                                          ),
348                                          this.createNode('node_const', 1.0)
349                                      )
350                                  ]
351                              )
352                          );
353                  break;
354 
355              case 'atanh':
356                  newNode = this.createNode('node_op', 'op_div',
357                              this.createNode('node_const', 1.0),
358                              this.createNode('node_op', 'op_sub',
359                                  this.createNode('node_const', 1.0),
360                                  this.createNode('node_op', 'op_mul',
361                                      Type.deepCopy(arg[0]),
362                                      Type.deepCopy(arg[0])
363                                  )
364                              )
365                          );
366                  break;
367 
368              default:
369                  newNode = this.createNode('node_const', 0.0);
370                  this._error('Derivative of "' + fun + '" not yet implemented');
371              }
372 
373              return newNode;
374          },
375 
376          derivative: function(node, varname) {
377              var i, len, newNode;
378 
379              switch (node.type) {
380              case 'node_op':
381                  switch (node.value) {
382                  /*
383                  case 'op_map':
384                      if (true) {
385                          newNode = this.createNode('node_op', 'op_map',
386                                  Type.deepCopy(node.children[0]),
387                                  this.derivative(node.children[1], varname)
388                              );
389                      } else {
390                          newNode = this.derivative(node.children[1], varname);
391                      }
392                      break;
393                  */
394                  case 'op_execfun':
395                      // f'(g(x))g'(x)
396                      if (node.children[0].value == 'pow') {
397                          newNode = this.deriveElementary(node, varname);
398                      } else {
399                          newNode = this.createNode('node_op', 'op_mul',
400                                      this.deriveElementary(node, varname),
401                                      // Warning: single variable mode
402                                      this.derivative(node.children[1][0], varname)
403                                  );
404 
405                      }
406                      break;
407 
408                  case 'op_div':
409                      // (f'g − g'f )/(g*g)
410                      newNode = this.createNode('node_op', 'op_div',
411                                  this.createNode('node_op', 'op_sub',
412                                      this.createNode('node_op', 'op_mul',
413                                          this.derivative(node.children[0], varname),
414                                          Type.deepCopy(node.children[1])
415                                      ),
416                                      this.createNode('node_op', 'op_mul',
417                                          Type.deepCopy(node.children[0]),
418                                          this.derivative(node.children[1], varname)
419                                      )
420                                  ),
421                                  this.createNode('node_op', 'op_mul',
422                                      Type.deepCopy(node.children[1]),
423                                      Type.deepCopy(node.children[1])
424                                  )
425                              );
426                      break;
427 
428                  case 'op_mul':
429                      // fg' + f'g
430                      newNode = this.createNode('node_op', 'op_add',
431                                  this.createNode('node_op', 'op_mul',
432                                      Type.deepCopy(node.children[0]),
433                                      this.derivative(node.children[1], varname)),
434                                  this.createNode('node_op', 'op_mul',
435                                      this.derivative(node.children[0], varname),
436                                      Type.deepCopy(node.children[1]))
437                              );
438                      break;
439 
440                  case 'op_neg':
441                      newNode = this.createNode('node_op', 'op_neg',
442                                  this.derivative(node.children[0], varname)
443                              );
444                      break;
445 
446                  case 'op_add':
447                  case 'op_sub':
448                      newNode = this.createNode('node_op', node.value,
449                                  this.derivative(node.children[0], varname),
450                                  this.derivative(node.children[1], varname)
451                              );
452                      break;
453 
454                  case 'op_exp':
455                      // (f^g)' = f^g*(f'g/f + g' log(f))
456                      newNode = this.createNode('node_op', 'op_mul',
457                                  Type.deepCopy(node),
458                                  this.createNode('node_op', 'op_add',
459                                      this.createNode('node_op', 'op_mul',
460                                          this.derivative(node.children[0], varname),
461                                          this.createNode('node_op', 'op_div',
462                                              Type.deepCopy(node.children[1]),
463                                              Type.deepCopy(node.children[0])
464                                          )
465                                      ),
466                                      this.createNode('node_op', 'op_mul',
467                                          this.derivative(node.children[1], varname),
468                                          this.createNode('node_op', 'op_execfun',
469                                              this.createNode('node_var', 'log'),
470                                              [Type.deepCopy(node.children[0])]
471                                          )
472                                      )
473                                  )
474                              );
475                      break;
476                  }
477                  break;
478 
479              case 'node_var':
480                  //console.log('node_var', node);
481                  if (node.value === varname) {
482                      newNode = this.createNode('node_const', 1.0);
483                  } else {
484                      newNode = this.createNode('node_const', 0.0);
485                  }
486                  break;
487 
488              case 'node_const':
489                  newNode = this.createNode('node_const', 0.0);
490                  break;
491 
492              case 'node_const_bool':
493                  break;
494 
495              case 'node_str':
496                  break;
497 
498              }
499 
500              return newNode;
501          },
502 
503          /**
504           * f = map (x) -> x*sin(x);
505           * Usages:
506           * h = D(f, x);
507           * h = map (x) -> D(f, x);
508           *
509           */
510          expandDerivatives: function(node, parent, ast) {
511              var len, i, j, mapNode, codeNode, ret, node2, newNode,
512                  mapName, varname, vArray, order;
513 
514              ret = 0;
515              if (!node) {
516                  return ret;
517              }
518 
519              this.line = node.line;
520              this.col = node.col;
521 
522              // First we have to go down in the tree.
523              // This ensures that in cases like D(D(f,x),x) the inner D is expanded first.
524              len = node.children.length;
525              for (i = 0; i < len; ++i) {
526                  if (node.children[i] && node.children[i].type) {
527                      node.children[i] = this.expandDerivatives(node.children[i], node, ast);
528                  } else if (Type.isArray(node.children[i])) {
529                      for (j = 0; j < node.children[i].length; ++j) {
530                          if (node.children[i][j] && node.children[i][j].type) {
531                              node.children[i][j] = this.expandDerivatives(node.children[i][j], node, ast);
532                          }
533                      }
534                  }
535              }
536 
537              switch (node.type) {
538              case 'node_op':
539                  switch (node.value) {
540                  case 'op_execfun':
541                      if (node.children[0] && node.children[0].value === 'D') {
542                          if (node.children[1][0].type == 'node_var') {
543                              /*
544                               * Derive map, that is compute D(f,x)
545                               * where e.g. f = map (x) -> x^2
546                               *
547                               * First step: find node where the map is defined
548                               */
549                              mapName = node.children[1][0].value;
550                              mapNode = this.findMapNode(mapName, ast);
551                              vArray = mapNode.children[0];
552 
553                              // Variable name for differentiation
554                              if (node.children[1].length >= 2) {
555                                  varname = node.children[1][1].value;
556                              } else {
557                                  varname = mapNode.children[0][0]; // Usually it's 'x'
558                              }
559                              codeNode = mapNode.children[1];
560                          } else {
561                              /*
562                               * Derive expression, e.g.
563                               *     D(2*x, x)
564                               */
565                              codeNode = node.children[1][0];
566                              vArray = ['x'];
567 
568                              // Variable name for differentiation and order
569                              if (node.children[1].length >= 2) {
570                                  varname = node.children[1][1].value;
571                              } else {
572                                  varname = 'x';
573                              }
574                          }
575 
576                          // Differentiation order
577                          if (node.children[1].length >= 3) {
578                              order = node.children[1][2].value;
579                          } else {
580                              order = 1;
581                          }
582 
583                          // Create node which contains the derivative
584                          newNode = codeNode;
585                          //newNode = this.removeTrivialNodes(newNode);
586                          if (order >= 1) {
587                              while (order >= 1) {
588                                  newNode = this.derivative(newNode, varname);
589                                  newNode = this.removeTrivialNodes(newNode);
590                                  order--;
591                              }
592                          }
593 
594                          // Replace the node containing e.g. D(f,x) by the derivative.
595                          if (parent.type == 'node_op' && parent.value == 'op_assign') {
596                              // If D is an assignment it has to be replaced by a map
597                              // h = D(f, x)
598                              node2 = this.createNode('node_op', 'op_map',
599                                      vArray,
600                                      newNode
601                                  );
602                          } else {
603                              node2 = newNode;
604                          }
605 
606                          this.setMath(node2);
607                          node.type = node2.type;
608                          node.value = node2.value;
609                          node.children[0] = node2.children[0];
610                          node.children[1] = node2.children[1];
611                      }
612                  }
613                  break;
614 
615              case 'node_var':
616              case 'node_const':
617              case 'node_const_bool':
618              case 'node_str':
619                  break;
620              }
621 
622              return node;
623          },
624 
625          removeTrivialNodes: function(node) {
626              var i, len, n0, n1, swap;
627 
628              // In case of 'op_execfun' the children[1] node is an array.
629              if (Type.isArray(node)) {
630                  len = node.length;
631                  for (i = 0; i < len; ++i) {
632                      node[i] = this.removeTrivialNodes(node[i]);
633                  }
634              }
635              if (node.type != 'node_op' || !node.children) {
636                  return node;
637              }
638 
639              len = node.children.length;
640              for (i = 0; i < len; ++i) {
641                  this.mayNotBeSimplified = false;
642                  do {
643                      node.children[i] = this.removeTrivialNodes(node.children[i]);
644                  } while (this.mayNotBeSimplified);
645 
646              }
647 
648              switch (node.value) {
649              // Allow maps of the form
650              //  map (x) -> x;
651              case 'op_map':
652                  n0 = node.children[0];
653                  n1 = node.children[1];
654                  if (n1.type == 'node_var') {
655                      for (i = 0; i < n0.length; ++i) {
656                          // Allow maps of the form map(x) -> x
657                          if (n0[i] == n1.value) {
658                              n1.isMath = true;
659                              break;
660                          }
661                      }
662                  }
663                  break;
664 
665              // a + 0 -> a
666              // 0 + a -> a
667              case 'op_add':
668                  n0 = node.children[0];
669                  n1 = node.children[1];
670                  if (n0.type == 'node_const' && n0.value === 0.0) {
671                      return n1;
672                  }
673                  if (n1.type == 'node_const' && n1.value === 0.0) {
674                      return n0;
675                  }
676 
677                  // const + const -> const
678                  if (n0.type == 'node_const' && n1.type == 'node_const') {
679                      n0.value += n1.value;
680                      return n0;
681                  }
682                  break;
683 
684              // 1 * a = a
685              // a * 1 = a
686              // a * 0 = 0
687              // 0 * a = 0
688              // - * - = +
689              // Order children
690              case 'op_mul':
691                  n0 = node.children[0];
692                  n1 = node.children[1];
693                  if (n0.type == 'node_const' && n0.value == 1.0) {
694                      return n1;
695                  }
696                  if (n1.type == 'node_const' && n1.value == 1.0) {
697                      return n0;
698                  }
699                  if (n0.type == 'node_const' && n0.value === 0.0) {
700                      return n0;
701                  }
702                  if (n1.type == 'node_const' && n1.value === 0.0) {
703                      return n1;
704                  }
705                  if (n1.type == 'node_const' && n1.value === 0.0) {
706                      return n1;
707                  }
708 
709                  // (-a) * (-b) -> a*b
710                  if (n0.type == 'node_op' && n0.value == 'op_neg' &&
711                      n1.type == 'node_op' && n1.value == 'op_neg' ) {
712                      node.children = [n0.children[0], n1.children[0]];
713                      this.mayNotBeSimplified = true;
714                      return node;
715                  }
716                  // (-a) * b -> -(a*b)
717                  if (n0.value == 'op_neg' && n1.value != 'op_neg' ) {
718                      node.type = 'node_op';
719                      node.value = 'op_neg';
720                      node.children = [this.createNode('node_op', 'op_mul', n0.children[0], n1)];
721                      this.mayNotBeSimplified = true;
722                      return node;
723                  }
724                  // a * (-b) -> -(a*b)
725                  if (n0.value != 'op_neg' && n1.value == 'op_neg' ) {
726                      node.type = 'node_op';
727                      node.value = 'op_neg';
728                      node.children = [this.createNode('node_op', 'op_mul', n0, n1.children[0])];
729                      this.mayNotBeSimplified = true;
730                      return node;
731                  }
732                  // (1 / a) * b -> a / b
733                  if (n0.value == 'op_div' &&
734                      n0.children[0].type == 'node_const' && n0.children[0].value == 1.0) {
735                      node.type = 'node_op';
736                      node.value = 'op_div';
737                      node.children = [n1, n0.children[1]];
738                      this.mayNotBeSimplified = true;
739                      return node;
740                  }
741                  // a * (1 / b) -> a / b
742                  if (n1.value == 'op_div' &&
743                      n1.children[0].type == 'node_const' && n1.children[0].value == 1.0) {
744                      node.type = 'node_op';
745                      node.value = 'op_div';
746                      node.children = [n0, n1.children[1]];
747                      this.mayNotBeSimplified = true;
748                      return node;
749                  }
750 
751                  // Order children
752                  // a * const -> const * a
753                  if (n0.type != 'node_const' && n1.type == 'node_const') {
754                      node.children = [n1, n0];
755                      this.mayNotBeSimplified = true;
756                      return node;
757                  }
758                  // a + (-const) -> -const * a
759                  if (n0.type != 'node_const' && n1.type == 'node_op' &&
760                      n1.value == 'op_neg' && n1.children[0].type == 'node_const') {
761                      node.children = [n1, n0];
762                      this.mayNotBeSimplified = true;
763                      return node;
764                  }
765 
766                  // a * var -> var * a
767                  // a * fun -> fun * a
768                  if (n0.type == 'node_op' && n0.value != 'op_execfun' &&
769                      (n1.type == 'node_var' || (n1.type == 'node_op' && n1.value == 'op_execfun'))) {
770                      node.children = [n1, n0];
771                      this.mayNotBeSimplified = true;
772                      return node;
773                  }
774 
775                  // a + (-var) -> -var * a
776                  if (n0.type != 'node_op' && n1.type == 'node_op' &&
777                      n1.value == 'op_neg' && n1.children[0].type == 'node_var') {
778                      node.children = [n1, n0];
779                      this.mayNotBeSimplified = true;
780                      return node;
781                  }
782                  // a * (const * b) -> const * (a*b)
783                  // a * (const / b) -> const * (a/b)
784                  if (n0.type != 'node_const' && n1.type == 'node_op' &&
785                      (n1.value == 'op_mul' || n1.value == 'op_div') &&
786                      n1.children[0].type == 'node_const') {
787                      swap = n1.children[0];
788                      n1.children[0] = n0;
789                      node.children = [swap, n1];
790                      this.mayNotBeSimplified = true;
791                      return node;
792                  }
793 
794                  // (const * a) * b -> const * (a * b)
795                  if (n1.type != 'node_const' && n0.type == 'node_op' &&
796                      n0.value == 'op_mul' &&
797                      n0.children[0].type == 'node_const') {
798                      node.children = [
799                          n0.children[0],
800                          this.createNode('node_op', 'op_mul', n0.children[1], n1)
801                      ];
802                      this.mayNotBeSimplified = true;
803                      return node;
804                  }
805 
806                  // const * const -> const
807                  if (n0.type == 'node_const' && n1.type == 'node_const') {
808                      n0.value *= n1.value;
809                      return n0;
810                  }
811 
812                  // const * (const * a) -> const * a
813                  // const * (const / a) -> const / a
814                  if (n0.type == 'node_const' && n1.type == 'node_op' &&
815                      (n1.value == 'op_mul' || n1.value == 'op_div') &&
816                      n1.children[0].type == 'node_const') {
817                      n1.children[0].value *= n0.value;
818                      return n1;
819                  }
820 
821                  // a * a-> a^2
822                  n0.hash = this.parser.compile(n0);
823                  n1.hash = this.parser.compile(n1);
824                  if (n0.hash === n1.hash) {
825                      node.value = 'op_exp';
826                      node.children[1] = this.createNode('node_const', 2.0);
827                      return node;
828                  }
829 
830                  if (n0.type == 'node_const' && n1.type == 'node_op' &&
831                      (n1.value == 'op_mul' || n1.value == 'op_div') &&
832                      n1.children[0].type == 'node_const') {
833                      n1.children[0].value *= n0.value;
834                      return n1;
835                  }
836 
837                  // a * a^b -> a^(b+1)
838                  if (n1.type == 'node_op' && n1.value == 'op_exp') {
839                      if (!n0.hash) {
840                          n0.hash = this.parser.compile(n0);
841                      }
842                      if (!n1.children[0].hash) {
843                          n1.children[0].hash = this.parser.compile(n1.children[0]);
844                      }
845                      if (n0.hash === n1.children[0].hash) {
846                          n1.children[1] = this.createNode('node_op', 'op_add',
847                              n1.children[1],
848                              this.createNode('node_const', 1.0)
849                          );
850                          this.mayNotBeSimplified = true;
851                          return n1;
852                      }
853                  }
854 
855                  // a^b * a^c -> a^(b+c)
856                  if (n0.type == 'node_op' && n0.value == 'op_exp' &&
857                      n1.type == 'node_op' && n1.value == 'op_exp') {
858                      n0.children[0].hash = this.parser.compile(n0.children[0]);
859                      n1.children[0].hash = this.parser.compile(n1.children[0]);
860                      if (n0.children[0].hash === n1.children[0].hash) {
861                          n0.children[1] = this.createNode('node_op', 'op_add',
862                              n0.children[1],
863                              n1.children[1]
864                          );
865                          this.mayNotBeSimplified = true;
866                          return n0;
867                      }
868                  }
869 
870                  break;
871 
872              // 0 - a -> -a
873              // a - 0 -> a
874              // a - a -> 0
875              case 'op_sub':
876                 n0 = node.children[0];
877                 n1 = node.children[1];
878                 if (n0.type == 'node_const' && n0.value === 0.0) {
879                      node.value = 'op_neg';
880                      node.children[0] = n1;
881                      return node;
882                  }
883                  if (n1.type == 'node_const' && n1.value === 0.0) {
884                      return n0;
885                  }
886                  if (n0.type == 'node_const' && n1.type == 'node_const' &&
887                      n0.value == n1.value) {
888                      return this.createNode('node_const', 0.0);
889                  }
890                  if (n0.type == 'node_var' && n1.type == 'node_var' &&
891                      n0.value == n1.value) {
892                      return this.createNode('node_const', 0.0);
893                  }
894 
895                  // const - const -> const
896                  if (n0.type == 'node_const' && n1.type == 'node_const') {
897                      n0.value -= n1.value;
898                      return n0;
899                  }
900 
901                  // const * a - const * a -> const * a
902                  if (n0.type == 'node_op' && n0.value == 'op_mul' &&
903                      n1.type == 'node_op' && n1.value == 'op_mul') {
904 
905                     n0.children[1].hash = this.parser.compile(n0.children[1]);
906                     n1.children[1].hash = this.parser.compile(n1.children[1]);
907                     if (n0.children[1].hash === n1.children[1].hash) {
908 
909                         node.value = 'op_mul';
910                         node.children = [
911                             this.createNode('node_op', 'op_sub',
912                                 n0.children[0],
913                                 n1.children[0]),
914                             n0.children[1]
915                             ];
916                         this.mayNotBeSimplified = true;
917                         return node;
918                     }
919                  }
920                  // const * a - a -> (const - 1) * a
921                  if (n0.type == 'node_op' && n0.value == 'op_mul') {
922 
923                     n0.children[1].hash = this.parser.compile(n0.children[1]);
924                     n1.hash = this.parser.compile(n1);
925                     if (n0.children[1].hash === n1.hash) {
926 
927                         node.value = 'op_mul';
928                         node.children = [
929                             this.createNode('node_op', 'op_sub',
930                                 n0.children[0],
931                                 this.createNode('node_const', 1.0)),
932                             n1
933                             ];
934                         this.mayNotBeSimplified = true;
935                         return node;
936                     }
937                  }
938                  // a - const*a -> (const - 1) * a
939                  if (n1.type == 'node_op' && n1.value == 'op_mul') {
940 
941                     n1.children[1].hash = this.parser.compile(n1.children[1]);
942                     n0.hash = this.parser.compile(n0);
943                     if (n1.children[1].hash === n0.hash) {
944 
945                         node.value = 'op_mul';
946                         node.children = [
947                             this.createNode('node_op', 'op_sub',
948                                 this.createNode('node_const', 1.0),
949                                 n1.children[0]),
950                             n0
951                             ];
952                         this.mayNotBeSimplified = true;
953                         return node;
954                     }
955                  }
956 
957                  break;
958 
959              // -0 -> 0
960              // -(-b) = b
961              case 'op_neg':
962                  n0 = node.children[0];
963                  if (n0.type == 'node_const' && n0.value === 0.0) {
964                      return n0;
965                  }
966                  if (n0.type == 'node_op' && n0.value == 'op_neg') {
967                      return n0.children[0];
968                  }
969                  break;
970 
971              // a / a -> 1, a != 0
972              // 0 / a -> 0, a != 0
973              // a / 0 -> Infinity, a != 0
974              // 0 / 0 -> NaN, a == 0
975              case 'op_div':
976                  n0 = node.children[0];
977                  n1 = node.children[1];
978                  if (n0.type == 'node_const' && n1.type == 'node_const' &&
979                      n0.value == n1.value && n0.value !== 0) {
980                      n0.value = 1.0;
981                      return n0;
982                  }
983                  if (n0.type == 'node_const' && n0.value === 0 &&
984                      n1.type == 'node_const' && n1.value !== 0) {
985                      n0.value = 0.0;
986                      return n0;
987                  }
988 
989                  // Risky: 0 / (something != 0) -> 0.0
990                  if (n0.type == 'node_const' && n0.value === 0 &&
991                      (n1.type == 'node_op' || n1.type == 'node_var')) {
992                      node.type = 'node_const';
993                      node.value = 0.0;
994                      return node;
995                  }
996 
997                  if (n0.type == 'node_var' && n1.type == 'node_var' &&
998                      n0.value == n1.value) {
999                      return this.createNode('node_const', 1.0);
1000                  }
1001                  if (n0.type == 'node_const' && n0.value !== 0 &&
1002                      n1.type == 'node_const' && n1.value === 0) {
1003                      if (n0.value > 0.0) {
1004                          n0.value = Infinity;
1005                      } else {
1006                          n0.value = -Infinity; // Do we ever need this?
1007                      }
1008                      return n0;
1009                  }
1010 
1011                  // (-a) / (-b) -> a/b
1012                  if (n0.type == 'node_op' && n0.value == 'op_neg' &&
1013                      n1.type == 'node_op' && n1.value == 'op_neg' ) {
1014                      node.children = [n0.children[0], n1.children[0]];
1015                      this.mayNotBeSimplified = true;
1016                      return node;
1017                  }
1018                  // (-a) / b -> -(a/b)
1019                  if (n0.value == 'op_neg' && n1.value != 'op_neg' ) {
1020                      node.type = 'node_op';
1021                      node.value = 'op_neg';
1022                      node.children = [this.createNode('node_op', 'op_div', n0.children[0], n1)];
1023                      this.mayNotBeSimplified = true;
1024                      return node;
1025                  }
1026                  // a / (-b) -> -(a/b)
1027                  if (n0.value != 'op_neg' && n1.value == 'op_neg' ) {
1028                      node.type = 'node_op';
1029                      node.value = 'op_neg';
1030                      node.children = [this.createNode('node_op', 'op_div', n0, n1.children[0])];
1031                      this.mayNotBeSimplified = true;
1032                      return node;
1033                  }
1034 
1035                  // a^b / a -> a^(b-1)
1036                  if (n0.type == 'node_op' && n0.value == 'op_exp') {
1037                      if (!n1.hash) {
1038                          n1.hash = this.parser.compile(n1);
1039                      }
1040                      if (!n0.children[0].hash) {
1041                          n0.children[0].hash = this.parser.compile(n0.children[0]);
1042                      }
1043                      if (n1.hash === n0.children[0].hash) {
1044                          n0.children[1] = this.createNode('node_op', 'op_sub',
1045                              n0.children[1],
1046                              this.createNode('node_const', 1.0)
1047                          );
1048                          this.mayNotBeSimplified = true;
1049                          return n0;
1050                      }
1051                  }
1052 
1053                  // (const * a) / b -> const * (a / b)
1054                  if (n1.type != 'node_const' && n0.type == 'node_op' &&
1055                      n0.value == 'op_mul' &&
1056                      n0.children[0].type == 'node_const') {
1057                      node.value = 'op_mul';
1058                      node.children = [
1059                          n0.children[0],
1060                          this.createNode('node_op', 'op_div', n0.children[1], n1)
1061                      ];
1062                      this.mayNotBeSimplified = true;
1063                      return node;
1064                  }
1065 
1066                  // a^b / a^c -> a^(b-c)
1067                  if (n0.type == 'node_op' && n0.value == 'op_exp' &&
1068                      n1.type == 'node_op' && n1.value == 'op_exp') {
1069                      n0.children[0].hash = this.parser.compile(n0.children[0]);
1070                      n1.children[0].hash = this.parser.compile(n1.children[0]);
1071                      if (n0.children[0].hash === n1.children[0].hash) {
1072                          n0.children[1] = this.createNode('node_op', 'op_sub',
1073                              n0.children[1],
1074                              n1.children[1]
1075                          );
1076                          this.mayNotBeSimplified = true;
1077                          return n0;
1078                      }
1079                  }
1080 
1081 
1082                  break;
1083 
1084              // a^0 = 1
1085              // a^1 -> a
1086              // 1^a -> 1
1087              // 0^a -> 0: a const != 0
1088              case 'op_exp':
1089                  n0 = node.children[0];
1090                  n1 = node.children[1];
1091                  if (n1.type == 'node_const' && n1.value === 0.0) {
1092                      n1.value = 1.0;
1093                      return n1;
1094                  }
1095                  if (n1.type == 'node_const' && n1.value == 1.0) {
1096                      return n0;
1097                  }
1098                  if (n0.type == 'node_const' && n0.value == 1.0) {
1099                      return n0;
1100                  }
1101                  if (n0.type == 'node_const' && n0.value === 0.0 &&
1102                      n1.type == 'node_const' && n1.value !== 0.0) {
1103                      return n0;
1104                  }
1105 
1106                  // (a^b)^c -> a^(b*c)
1107                  if (n0.type == 'node_op' && n0.value == 'op_exp') {
1108                      node.children = [
1109                          n0.children[0],
1110                          this.createNode('node_op', 'op_mul',
1111                             n0.children[1],
1112                             n1)
1113                      ];
1114                      return node;
1115                  }
1116                  break;
1117              }
1118 
1119              switch (node.value) {
1120              // const_1 + const_2 -> (const_1 + const_2)
1121              // a + a -> 2*a
1122              // a + (-b) = a - b
1123              case 'op_add':
1124                  n0 = node.children[0];
1125                  n1 = node.children[1];
1126                  if (n0.type == 'node_const' && n1.type == 'node_const' &&
1127                      n0.value == n1.value) {
1128                      n0.value += n1.value;
1129                      return n0;
1130                  }
1131 
1132                  if (n0.type == 'node_var' && n1.type == 'node_var' &&
1133                      n0.value == n1.value) {
1134                      node.children[0] = this.createNode('node_const', 2.0);
1135                      node.value = 'op_mul';
1136                      return node;
1137                  }
1138 
1139                  if (n0.type == 'node_op' && n0.value == 'op_neg') {
1140                      node.value = 'op_sub';
1141                      node.children[0] = n1;
1142                      node.children[1] = n0.children[0];
1143                      this.mayNotBeSimplified = true;
1144                      return node;
1145                  }
1146 
1147                  if (n1.type == 'node_op' && n1.value == 'op_neg') {
1148                      node.value = 'op_sub';
1149                      node.children[1] = n1.children[0];
1150                      this.mayNotBeSimplified = true;
1151                      return node;
1152                  }
1153 
1154                  // const * a + const * a -> const * a
1155                  if (n0.type == 'node_op' && n0.value == 'op_mul' &&
1156                      n1.type == 'node_op' && n1.value == 'op_mul') {
1157 
1158                     n0.children[1].hash = this.parser.compile(n0.children[1]);
1159                     n1.children[1].hash = this.parser.compile(n1.children[1]);
1160                     if (n0.children[1].hash === n1.children[1].hash) {
1161 
1162                         node.value = 'op_mul';
1163                         node.children = [
1164                             this.createNode('node_op', 'op_add',
1165                                 n0.children[0],
1166                                 n1.children[0]),
1167                             n0.children[1]
1168                             ];
1169                         this.mayNotBeSimplified = true;
1170                         return node;
1171                     }
1172                  }
1173                  // const * a + a -> (const + 1) * a
1174                  if (n0.type == 'node_op' && n0.value == 'op_mul') {
1175 
1176                     n0.children[1].hash = this.parser.compile(n0.children[1]);
1177                     n1.hash = this.parser.compile(n1);
1178                     if (n0.children[1].hash === n1.hash) {
1179 
1180                         node.value = 'op_mul';
1181                         node.children = [
1182                             this.createNode('node_op', 'op_add',
1183                                 n0.children[0],
1184                                 this.createNode('node_const', 1.0)),
1185                             n1
1186                             ];
1187                         this.mayNotBeSimplified = true;
1188                         return node;
1189                     }
1190                  }
1191                  // a + const*a -> (const + 1) * a
1192                  if (n1.type == 'node_op' && n1.value == 'op_mul') {
1193 
1194                     n1.children[1].hash = this.parser.compile(n1.children[1]);
1195                     n0.hash = this.parser.compile(n0);
1196                     if (n1.children[1].hash === n0.hash) {
1197 
1198                         node.value = 'op_mul';
1199                         node.children = [
1200                             this.createNode('node_op', 'op_add',
1201                                 this.createNode('node_const', 1.0),
1202                                 n1.children[0]),
1203                             n0
1204                             ];
1205                         this.mayNotBeSimplified = true;
1206                         return node;
1207                     }
1208                  }
1209 
1210                  break;
1211 
1212              // a - (-b) = a + b
1213              case 'op_sub':
1214                  n0 = node.children[0];
1215                  n1 = node.children[1];
1216                  if (n1.type == 'node_op' && n1.value == 'op_neg') {
1217                      node.value = 'op_add';
1218                      node.children[1] = n1.children[0];
1219                      this.mayNotBeSimplified = true;
1220                      return node;
1221                  }
1222                  break;
1223 
1224              case 'op_execfun':
1225                  return this.simplifyElementary(node);
1226              }
1227 
1228              return node;
1229          },
1230 
1231          simplifyElementary: function(node) {
1232              var fun = node.children[0].value,
1233                  arg = node.children[1],
1234                  newNode;
1235 
1236              // Catch errors of the form sin()
1237              if (arg.length == 0) {
1238                  return node;
1239              }
1240 
1241              switch (fun) {
1242              // sin(0) -> 0
1243              // sin(PI) -> 0
1244              // sin (int * PI) -> 0
1245              // sin (PI * int) -> 0
1246              // Same for tan()
1247              case 'sin':
1248              case 'tan':
1249                  if (arg[0].type == 'node_const' && arg[0].value === 0) {
1250                      node.type = 'node_const';
1251                      node.value = 0.0;
1252                      return node;
1253                  }
1254                  if (arg[0].type == 'node_var' && arg[0].value == 'PI') {
1255                      node.type = 'node_const';
1256                      node.value = 0.0;
1257                      return node;
1258                  }
1259                  if (arg[0].type == 'node_op' && arg[0].value == 'op_mul' &&
1260                      arg[0].children[0].type == 'node_const' && arg[0].children[0].value % 1 === 0 &&
1261                       arg[0].children[1].type == 'node_var' && arg[0].children[1].value == 'PI') {
1262                      node.type = 'node_const';
1263                      node.value = 0.0;
1264                      return node;
1265                  }
1266                  break;
1267 
1268              // cos(0) -> 1.0
1269              // cos(PI) -> -1.0
1270              // cos(int * PI) -> +/- 1.0
1271              // cos(PI * int) -> +/- 1.0
1272              case 'cos':
1273                  if (arg[0].type == 'node_const' && arg[0].value === 0) {
1274                      node.type = 'node_const';
1275                      node.value = 1.0;
1276                      return node;
1277                  }
1278                  if (arg[0].type == 'node_var' && arg[0].value == 'PI') {
1279                      node.type = 'node_op';
1280                      node.value = 'op_neg';
1281                      node.children = [this.createNode('node_const', 1.0)];
1282                      return node;
1283                  }
1284                  /*
1285                  if (arg[0].type == 'node_op' && arg[0].value == 'op_mul' &&
1286                      ((arg[0].children[0].type == 'node_const' && arg[0].children[0].value % 1 === 0 &&
1287                       arg[0].children[1].type == 'node_var' && arg[0].children[1].value == 'PI') ||
1288                       (arg[0].children[1].type == 'node_const' && arg[0].children[1].value % 1 === 0 &&
1289                        arg[0].children[0].type == 'node_var' && arg[0].children[0].value == 'PI'))) {
1290                      node.type = 'node_const';
1291                      node.value = 1.0;
1292                      return node;
1293                  }
1294                  */
1295                  break;
1296 
1297              // exp(0) -> 1
1298              case 'exp':
1299                  if (arg[0].type == 'node_const' && arg[0].value === 0) {
1300                      node.type = 'node_const';
1301                      node.value = 1.0;
1302                      return node;
1303                  }
1304                  break;
1305 
1306              // pow(a, 0) -> 1
1307              case 'pow':
1308                  if (arg[1].type == 'node_const' && arg[1].value === 0) {
1309                      node.type = 'node_const';
1310                      node.value = 1.0;
1311                      return node;
1312                  }
1313                  break;
1314 
1315              }
1316 
1317              return node;
1318          },
1319 
1320 
1321 
1322      });
1323 
1324      return JXG.CA;
1325  });
1326