      1 /*
      2     Copyright 2008-2014
      3         Matthias Ehmann,
      4         Michael Gerhaeuser,
      5         Carsten Miller,
      6         Bianca Valentin,
      7         Alfred Wassermann,
      8         Peter Wilfahrt
      9
     10     This file is part of JSXGraph.
     11
     12     JSXGraph is free software dual licensed under the GNU LGPL or MIT License.
     13
     14     You can redistribute it and/or modify it under the terms of the
     15
     16       * GNU Lesser General Public License as published by
     17         the Free Software Foundation, either version 3 of the License, or
     18         (at your option) any later version
     19       OR
     20       * MIT License: https://github.com/jsxgraph/jsxgraph/blob/master/LICENSE.MIT
     21
     22     JSXGraph is distributed in the hope that it will be useful,
     23     but WITHOUT ANY WARRANTY; without even the implied warranty of
     24     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
     25     GNU Lesser General Public License for more details.
     26
     27     You should have received a copy of the GNU Lesser General Public License and
     28     the MIT License along with JSXGraph. If not, see <http://www.gnu.org/licenses/>
     29     and <http://opensource.org/licenses/MIT/>.
     30  */
     31
     32
     33 /*global JXG: true, define: true*/
     34 /*jslint nomen: true, plusplus: true*/
     35
     36 /* depends:
     37  jxg
     38  math/math
     39  utils/type
     40  */
     41
     42 /**
     43  * @fileoverview In this file the namespace Math.Poly is defined, which holds algorithms to create and
     44  * manipulate polynomials.
     45  */
     46
     47 define(['jxg', 'math/math', 'utils/type'], function (JXG, Mat, Type) {
     48
     49     "use strict";
     50
     51     /**
     52      * The JXG.Math.Poly namespace holds algorithms to create and manipulate polynomials.
     53      * @name JXG.Math.Poly
     54      * @exports Mat.Poly as JXG.Math.Poly
     55      * @namespace
     56      */
     57     Mat.Poly = {};
     58
     59     /**
     60      * Define a polynomial ring over R.
     61      * @class
     62      * @name JXG.Math.Poly.Ring
     63      * @param {Array} variables List of indeterminates.
     64      */
     65     Mat.Poly.Ring = function (variables) {
     66         /**
     67          * A list of variables in this polynomial ring.
     68          * @type Array
     69          */
     70         this.vars = variables;
     71     };
     72
     73     JXG.extend(Mat.Poly.Ring.prototype, /** @lends JXG.Math.Poly.Ring.prototype */ {
     74         // nothing yet.
     75     });
     76
     77
     78     /**
     79      * Define a monomial over the polynomial ring <tt>ring</tt>.
     80      * @class
     81      * @name JXG.Math.Poly.Monomial
     82      * @param {JXG.Math.Poly.Ring} ring
     83      * @param {Number} coefficient
     84      * @param {Array} exponents An array of exponents, corresponding to ring
     85      */
     86     Mat.Poly.Monomial = function (ring, coefficient, exponents) {
     87         var i;
     88
     89         if (!Type.exists(ring)) {
     90             throw new Error('JSXGraph error: In JXG.Math.Poly.monomial missing parameter \'ring\'.');
     91         }
     92
     93         if (!Type.isArray(exponents)) {
     94             exponents = [];
     95         }
     96
     97         exponents = exponents.slice(0, ring.vars.length);
     98
     99         for (i = exponents.length; i < ring.vars.length; i++) {
    100             exponents.push(0);
    101         }
    102
    103         /**
    104          * A polynomial ring.
    105          * @type JXG.Math.Poly.Ring
    106          */
    107         this.ring = ring;
    108
    109         /**
    110          * The monomial's coefficient
    111          * @type Number
    112          */
    113         this.coefficient = coefficient || 0;
    114
    115         /**
    116          * Exponent vector, the order depends on the order of the variables
    117          * in the ring definition.
    118          * @type Array
    119          */
    120         this.exponents = Type.deepCopy(exponents);
    121     };
    122
    123     JXG.extend(Mat.Poly.Monomial.prototype, /** @lends JXG.Math.Poly.Monomial.prototype */ {
    124
    125         /**
    126          * Creates a deep copy of the monomial.
    127          *
    128          * @returns {JXG.Math.Poly.Monomial}
    129          *
    130          * @memberof JXG.Math.Poly.Monomial
    131          */
    132         copy: function () {
    133             return new Mat.Poly.Monomial(this.ring, this.coefficient, this.exponents);
    134         },
    135
    136         /**
    137          * Print the monomial.
    138          * @returns {String} String representation of the monomial
    139
    140          * @memberof JXG.Math.Poly.Monomial
    141          */
    142         print: function () {
    143             var s = [],
    144                 i;
    145
    146             for (i = 0; i < this.ring.vars.length; i++) {
    147                 s.push(this.ring.vars[i] + '^' + this.exponents[i]);
    148             }
    149
    150             return this.coefficient + '*' + s.join('*');
    151         }
    152     });
    153
    154
    155     /**
    156      * A polynomial is a sum of monomials.
    157      * @class
    158      * @name JXG.Math.Poly.Polynomial
    159      * @param {JXG.Math.Poly.Ring} ring A polynomial ring.
    160      * @param {String} str TODO String representation of the polynomial, will be parsed.
    161      */
    162     Mat.Poly.Polynomial = function (ring, str) {
    163         var parse = function () {
    164
    165             },
    166             mons;
    167
    168         if (!Type.exists(ring)) {
    169             throw new Error('JSXGraph error: In JXG.Math.Poly.polynomial missing parameter \'ring\'.');
    170         }
    171
    172         if (Type.exists(str) && Type.isString(str)) {
    173             mons = parse(str);
    174         } else {
    175             mons = [];
    176         }
    177
    178         /**
    179          * A polynomial ring.
    180          * @type JXG.Math.Poly.Ring
    181          */
    182         this.ring = ring;
    183
    184         /**
    185          * List of monomials.
    186          * @type Array
    187          */
    188         this.monomials = mons;
    189     };
    190
    191     JXG.extend(Mat.Poly.Polynomial.prototype, /** @lends JXG.Math.Poly.Polynomial.prototype */ {
    192         /**
    193          * Find a monomial with the given signature, i.e. exponent vector.
    194          * @param {Array} sig An array of numbers
    195          * @returns {Number} The index of the first monomial with the given signature, or -1
    196          * if no monomial could be found.
    197          * @memberof JXG.Math.Poly.Polynomial
    198          */
    199         findSignature: function (sig) {
    200             var i;
    201
    202             for (i = 0; i < this.monomials.length; i++) {
    203                 if (Type.cmpArrays(this.monomials[i].exponents, sig)) {
    204                     return i;
    205                 }
    206             }
    207
    208             return -1;
    209         },
    210
    211         /**
    212          * Adds a monomial to the polynomial. Checks the existing monomials for the added
    213          * monomial's signature and just adds the coefficient if one is found.
    214          * @param {JXG.Math.Poly.Monomial} m
    215          * @param {Number} factor Either <tt>1</tt> or <tt>-1</tt>.
    216          * @memberof JXG.Math.Poly.Polynomial
    217          */
    218         addSubMonomial: function (m, factor) {
    219             var i;
    220
    221             i = this.findSignature(m.exponents);
    222             if (i > -1) {
    223                 this.monomials[i].coefficient += factor * m.coefficient;
    224             } else {
    225                 m.coefficient *= factor;
    226                 this.monomials.push(m);
    227             }
    228         },
    229
    230         /**
    231          * Adds another polynomial or monomial to this one and merges them by checking for the
    232          * signature of each new monomial in the existing monomials.
    233          * @param {JXG.Math.Poly.Polynomial|JXG.Math.Poly.Monomial} mp
    234          * @memberof JXG.Math.Poly.Polynomial
    235          */
    236         add: function (mp) {
    237             var i;
    238
    239             if (Type.exists(mp) && mp.ring === this.ring) {
    240                 if (Type.isArray(mp.exponents)) {
    241                     // mp is a monomial
    242                     this.addSubMonomial(mp, 1);
    243                 } else {
    244                     // mp is a polynomial
    245                     for (i = 0; i < mp.monomials.length; i++) {
    246                         this.addSubMonomial(mp.monomials[i], 1);
    247                     }
    248                 }
    249             } else {
    250                 throw new Error('JSXGraph error: In JXG.Math.Poly.polynomial.add either summand is undefined or rings don\'t match.');
    251             }
    252         },
    253
    254         /**
    255          * Subtracts another polynomial or monomial from this one and merges them by checking for the
    256          * signature of each new monomial in the existing monomials.
    257          * @param {JXG.Math.Poly.Polynomial|JXG.Math.Poly.Monomial} mp
    258          * @memberof JXG.Math.Poly.Polynomial
    259          */
    260         sub: function (mp) {
    261             var i;
    262
    263             if (Type.exists(mp) && mp.ring === this.ring) {
    264                 if (Type.isArray(mp.exponents)) {
    265                     // mp is a monomial
    266                     this.addSubMonomial(mp, -1);
    267                 } else {
    268                     // mp is a polynomial
    269                     for (i = 0; i < mp.monomials.length; i++) {
    270                         this.addSubMonomial(mp.monomials[i], -1);
    271                     }
    272                 }
    273             } else {
    274                 throw new Error('JSXGraph error: In JXG.Math.Poly.polynomial.sub either summand is undefined or rings don\'t match.');
    275             }
    276         },
    277
    278         /**
    279          * Creates a deep copy of the polynomial.
    280          * @returns {JXG.Math.Poly.Polynomial}
    281          * @memberof JXG.Math.Poly.Polynomial
    282          */
    283         copy: function () {
    284             var i, p;
    285
    286             p = new Mat.Poly.Polynomial(this.ring);
    287
    288             for (i = 0; i < this.monomials.length; i++) {
    289                 p.monomials.push(this.monomials[i].copy());
    290             }
    291             return p;
    292         },
    293
    294         /**
    295          * Prints the polynomial.
    296          * @returns {String} A string representation of the polynomial.
    297          * @memberof JXG.Math.Poly.Polynomial
    298          */
    299         print: function () {
    300             var s = [],
    301                 i;
    302
    303             for (i = 0; i < this.monomials.length; i++) {
    304                 s.push('(' + this.monomials[i].print() + ')');
    305             }
    306
    307             return s.join('+');
    308         }
    309     });
    310
    311     return Mat.Poly;
    312 });
    313