1 /*
  2     Copyright 2008-2023
  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 <https://www.gnu.org/licenses/>
 29     and <https://opensource.org/licenses/MIT/>.
 30  */
 31 
 32 /*global JXG: true, define: true*/
 33 /*jslint nomen: true, plusplus: true*/
 34 
 35 /**
 36  * @fileoverview In this file the namespace Math.Poly is defined, which holds algorithms to create and
 37  * manipulate polynomials.
 38  */
 39 
 40 import JXG from "../jxg";
 41 import Mat from "./math";
 42 import Type from "../utils/type";
 43 
 44 /**
 45  * The JXG.Math.Poly namespace holds algorithms to create and manipulate polynomials.
 46  * @name JXG.Math.Poly
 47  * @exports Mat.Poly as JXG.Math.Poly
 48  * @namespace
 49  */
 50 Mat.Poly = {};
 51 
 52 /**
 53  * Define a polynomial ring over R.
 54  * @class
 55  * @name JXG.Math.Poly.Ring
 56  * @param {Array} variables List of indeterminates.
 57  */
 58 Mat.Poly.Ring = function (variables) {
 59     /**
 60      * A list of variables in this polynomial ring.
 61      * @type Array
 62      */
 63     this.vars = variables;
 64 };
 65 
 66 JXG.extend(
 67     Mat.Poly.Ring.prototype,
 68     /** @lends JXG.Math.Poly.Ring.prototype */ {
 69         // nothing yet.
 70     }
 71 );
 72 
 73 /**
 74  * Define a monomial over the polynomial ring <tt>ring</tt>.
 75  * @class
 76  * @name JXG.Math.Poly.Monomial
 77  * @param {JXG.Math.Poly.Ring} ring
 78  * @param {Number} coefficient
 79  * @param {Array} exponents An array of exponents, corresponding to ring
 80  */
 81 Mat.Poly.Monomial = function (ring, coefficient, exponents) {
 82     var i;
 83 
 84     if (!Type.exists(ring)) {
 85         throw new Error("JSXGraph error: In JXG.Math.Poly.monomial missing parameter 'ring'.");
 86     }
 87 
 88     if (!Type.isArray(exponents)) {
 89         exponents = [];
 90     }
 91 
 92     exponents = exponents.slice(0, ring.vars.length);
 93 
 94     for (i = exponents.length; i < ring.vars.length; i++) {
 95         exponents.push(0);
 96     }
 97 
 98     /**
 99      * A polynomial ring.
100      * @type JXG.Math.Poly.Ring
101      */
102     this.ring = ring;
103 
104     /**
105      * The monomial's coefficient
106      * @type Number
107      */
108     this.coefficient = coefficient || 0;
109 
110     /**
111      * Exponent vector, the order depends on the order of the variables
112      * in the ring definition.
113      * @type Array
114      */
115     this.exponents = Type.deepCopy(exponents);
116 };
117 
118 JXG.extend(
119     Mat.Poly.Monomial.prototype,
120     /** @lends JXG.Math.Poly.Monomial.prototype */ {
121         /**
122          * Creates a deep copy of the monomial.
123          *
124          * @returns {JXG.Math.Poly.Monomial}
125          *
126          * @memberof JXG.Math.Poly.Monomial
127          */
128         copy: function () {
129             return new Mat.Poly.Monomial(this.ring, this.coefficient, this.exponents);
130         },
131 
132         /**
133          * Print the monomial.
134          * @returns {String} String representation of the monomial
135 
136          * @memberof JXG.Math.Poly.Monomial
137          */
138         print: function () {
139             var s = [],
140                 i;
141 
142             for (i = 0; i < this.ring.vars.length; i++) {
143                 s.push(this.ring.vars[i] + "^" + this.exponents[i]);
144             }
145 
146             return this.coefficient + "*" + s.join("*");
147         }
148     }
149 );
150 
151 /**
152  * A polynomial is a sum of monomials.
153  * @class
154  * @name JXG.Math.Poly.Polynomial
155  * @param {JXG.Math.Poly.Ring} ring A polynomial ring.
156  * @param {String} str TODO String representation of the polynomial, will be parsed.
157  */
158 Mat.Poly.Polynomial = function (ring, str) {
159     var parse = function () {},
160         mons;
161 
162     if (!Type.exists(ring)) {
163         throw new Error(
164             "JSXGraph error: In JXG.Math.Poly.polynomial missing parameter 'ring'."
165         );
166     }
167 
168     if (Type.exists(str) && Type.isString(str)) {
169         mons = parse(str);
170     } else {
171         mons = [];
172     }
173 
174     /**
175      * A polynomial ring.
176      * @type JXG.Math.Poly.Ring
177      */
178     this.ring = ring;
179 
180     /**
181      * List of monomials.
182      * @type Array
183      */
184     this.monomials = mons;
185 };
186 
187 JXG.extend(
188     Mat.Poly.Polynomial.prototype,
189     /** @lends JXG.Math.Poly.Polynomial.prototype */ {
190         /**
191          * Find a monomial with the given signature, i.e. exponent vector.
192          * @param {Array} sig An array of numbers
193          * @returns {Number} The index of the first monomial with the given signature, or -1
194          * if no monomial could be found.
195          * @memberof JXG.Math.Poly.Polynomial
196          */
197         findSignature: function (sig) {
198             var i;
199 
200             for (i = 0; i < this.monomials.length; i++) {
201                 if (Type.cmpArrays(this.monomials[i].exponents, sig)) {
202                     return i;
203                 }
204             }
205 
206             return -1;
207         },
208 
209         /**
210          * Adds a monomial to the polynomial. Checks the existing monomials for the added
211          * monomial's signature and just adds the coefficient if one is found.
212          * @param {JXG.Math.Poly.Monomial} m
213          * @param {Number} factor Either <tt>1</tt> or <tt>-1</tt>.
214          * @memberof JXG.Math.Poly.Polynomial
215          */
216         addSubMonomial: function (m, factor) {
217             var i;
218 
219             i = this.findSignature(m.exponents);
220             if (i > -1) {
221                 this.monomials[i].coefficient += factor * m.coefficient;
222             } else {
223                 m.coefficient *= factor;
224                 this.monomials.push(m);
225             }
226         },
227 
228         /**
229          * Adds another polynomial or monomial to this one and merges them by checking for the
230          * signature of each new monomial in the existing monomials.
231          * @param {JXG.Math.Poly.Polynomial|JXG.Math.Poly.Monomial} mp
232          * @memberof JXG.Math.Poly.Polynomial
233          */
234         add: function (mp) {
235             var i;
236 
237             if (Type.exists(mp) && mp.ring === this.ring) {
238                 if (Type.isArray(mp.exponents)) {
239                     // mp is a monomial
240                     this.addSubMonomial(mp, 1);
241                 } else {
242                     // mp is a polynomial
243                     for (i = 0; i < mp.monomials.length; i++) {
244                         this.addSubMonomial(mp.monomials[i], 1);
245                     }
246                 }
247             } else {
248                 throw new Error(
249                     "JSXGraph error: In JXG.Math.Poly.polynomial.add either summand is undefined or rings don't match."
250                 );
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(
275                     "JSXGraph error: In JXG.Math.Poly.polynomial.sub either summand is undefined or rings don't match."
276                 );
277             }
278         },
279 
280         /**
281          * Creates a deep copy of the polynomial.
282          * @returns {JXG.Math.Poly.Polynomial}
283          * @memberof JXG.Math.Poly.Polynomial
284          */
285         copy: function () {
286             var i, p;
287 
288             p = new Mat.Poly.Polynomial(this.ring);
289 
290             for (i = 0; i < this.monomials.length; i++) {
291                 p.monomials.push(this.monomials[i].copy());
292             }
293             return p;
294         },
295 
296         /**
297          * Prints the polynomial.
298          * @returns {String} A string representation of the polynomial.
299          * @memberof JXG.Math.Poly.Polynomial
300          */
301         print: function () {
302             var s = [],
303                 i;
304 
305             for (i = 0; i < this.monomials.length; i++) {
306                 s.push("(" + this.monomials[i].print() + ")");
307             }
308 
309             return s.join("+");
310         }
311     }
312 );
313 
314 export default Mat.Poly;
315