1 /*
  2     Copyright 2008-2021
  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