1 /*
  2     Copyright 2008-2013
  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      * @namespace
 55      */
 56     Mat.Poly = {};
 57 
 58     /**
 59      * Define a polynomial ring over R.
 60      * @class
 61      * @name JXG.Math.Poly.Ring
 62      * @param {Array} variables List of indeterminates.
 63      */
 64     Mat.Poly.Ring = function (variables) {
 65         /**
 66          * A list of variables in this polynomial ring.
 67          * @type Array
 68          */
 69         this.vars = variables;
 70     };
 71 
 72     JXG.extend(Mat.Poly.Ring.prototype, /** @lends JXG.Math.Poly.Ring.prototype */ {
 73         // nothing yet.
 74     });
 75 
 76 
 77     /**
 78      * Define a monomial over the polynomial ring <tt>ring</tt>.
 79      * @class
 80      * @name JXG.Math.Poly.Monomial
 81      * @param {JXG.Math.Poly.Ring} ring
 82      * @param {Number} coefficient
 83      * @param {Array} exponents An array of exponents, corresponding to ring
 84      */
 85     Mat.Poly.Monomial = function (ring, coefficient, exponents) {
 86         var i;
 87 
 88         if (!Type.exists(ring)) {
 89             throw new Error('JSXGraph error: In JXG.Math.Poly.monomial missing parameter \'ring\'.');
 90         }
 91 
 92         if (!Type.isArray(exponents)) {
 93             exponents = [];
 94         }
 95 
 96         exponents = exponents.slice(0, ring.vars.length);
 97 
 98         for (i = exponents.length; i < ring.vars.length; i++) {
 99             exponents.push(0);
100         }
101 
102         /**
103          * A polynomial ring.
104          * @type JXG.Math.Poly.Ring
105          */
106         this.ring = ring;
107 
108         /**
109          * The monomial's coefficient
110          * @type Number
111          */
112         this.coefficient = coefficient || 0;
113 
114         /**
115          * Exponent vector, the order depends on the order of the variables
116          * in the ring definition.
117          * @type Array
118          */
119         this.exponents = Type.deepCopy(exponents);
120     };
121 
122     JXG.extend(Mat.Poly.Monomial.prototype, /** @lends JXG.Math.Poly.Monomial.prototype */ {
123 
124         /**
125          * Creates a deep copy of the monomial.
126          * @returns {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         print: function () {
137             var s = [],
138                 i;
139 
140             for (i = 0; i < this.ring.vars.length; i++) {
141                 s.push(this.ring.vars[i] + '^' + this.exponents[i]);
142             }
143 
144             return this.coefficient + '*' + s.join('*');
145         }
146     });
147 
148 
149     /**
150      * A polynomial is a sum of monomials.
151      * @class
152      * @name JXG.Math.Poly.Polynomial
153      * @param {JXG.Math.Poly.Ring} ring A polynomial ring.
154      * @param {String} str TODO String representation of the polynomial, will be parsed.
155      */
156     Mat.Poly.Polynomial = function (ring, str) {
157         var parse = function () {
158 
159             },
160             mons;
161 
162         if (!Type.exists(ring)) {
163             throw new Error('JSXGraph error: In JXG.Math.Poly.polynomial missing parameter \'ring\'.');
164         }
165 
166         if (Type.exists(str) && typeof str === 'string') {
167             mons = parse(str);
168         } else {
169             mons = [];
170         }
171 
172         /**
173          * A polynomial ring.
174          * @type JXG.Math.Poly.Ring
175          */
176         this.ring = ring;
177 
178         /**
179          * List of monomials.
180          * @type Array
181          */
182         this.monomials = mons;
183     };
184 
185     JXG.extend(Mat.Poly.Polynomial.prototype, /** @lends JXG.Math.Poly.Polynomial.prototype */ {
186         /**
187          * Find a monomial with the given signature, i.e. exponent vector.
188          * @param {Array} sig An array of numbers
189          * @returns {Number} The index of the first monomial with the given signature, or -1
190          * if no monomial could be found.
191          */
192         findSignature: function (sig) {
193             var i;
194 
195             for (i = 0; i < this.monomials.length; i++) {
196                 if (Type.cmpArrays(this.monomials[i].exponents, sig)) {
197                     return i;
198                 }
199             }
200 
201             return -1;
202         },
203 
204         /**
205          * Adds a monomial to the polynomial. Checks the existing monomials for the added
206          * monomial's signature and just adds the coefficient if one is found.
207          * @param {JXG.Math.Poly.Monomial} m
208          * @param {Number} factor Either <tt>1</tt> or <tt>-1</tt>.
209          */
210         addSubMonomial: function (m, factor) {
211             var i;
212 
213             i = this.findSignature(m.exponents);
214             if (i > -1) {
215                 this.monomials[i].coefficient += factor * m.coefficient;
216             } else {
217                 m.coefficient *= factor;
218                 this.monomials.push(m);
219             }
220         },
221 
222         /**
223          * Adds another polynomial or monomial to this one and merges them by checking for the
224          * signature of each new monomial in the existing monomials.
225          * @param {JXG.Math.Poly.Polynomial|JXG.Math.Poly.Monomial} mp
226          */
227         add: function (mp) {
228             var i;
229 
230             if (Type.exists(mp) && mp.ring === this.ring) {
231                 if (Type.isArray(mp.exponents)) {
232                     // mp is a monomial
233                     this.addSubMonomial(mp, 1);
234                 } else {
235                     // mp is a polynomial
236                     for (i = 0; i < mp.monomials.length; i++) {
237                         this.addSubMonomial(mp.monomials[i], 1);
238                     }
239                 }
240             } else {
241                 throw new Error('JSXGraph error: In JXG.Math.Poly.polynomial.add either summand is undefined or rings don\'t match.');
242             }
243         },
244 
245         /**
246          * Subtracts another polynomial or monomial from this one and merges them by checking for the
247          * signature of each new monomial in the existing monomials.
248          * @param {JXG.Math.Poly.Polynomial|JXG.Math.Poly.Monomial} mp
249          */
250         sub: function (mp) {
251             var i;
252 
253             if (Type.exists(mp) && mp.ring === this.ring) {
254                 if (Type.isArray(mp.exponents)) {
255                     // mp is a monomial
256                     this.addSubMonomial(mp, -1);
257                 } else {
258                     // mp is a polynomial
259                     for (i = 0; i < mp.monomials.length; i++) {
260                         this.addSubMonomial(mp.monomials[i], -1);
261                     }
262                 }
263             } else {
264                 throw new Error('JSXGraph error: In JXG.Math.Poly.polynomial.sub either summand is undefined or rings don\'t match.');
265             }
266         },
267 
268         /**
269          * Creates a deep copy of the polynomial.
270          * @returns {JXG.Math.Poly.Polynomial}
271          */
272         copy: function () {
273             var i, p;
274 
275             p = new Mat.Poly.Polynomial(this.ring);
276 
277             for (i = 0; i < this.monomials.length; i++) {
278                 p.monomials.push(this.monomials[i].copy());
279             }
280             return p;
281         },
282 
283         /**
284          * Prints the polynomial.
285          * @returns {String} A string representation of the polynomial.
286          */
287         print: function () {
288             var s = [],
289                 i;
290 
291             for (i = 0; i < this.monomials.length; i++) {
292                 s.push('(' + this.monomials[i].print() + ')');
293             }
294 
295             return s.join('+');
296         }
297     });
298 
299     return Mat.Poly;
300 });