1   /* Copyright 2002-2019 CS Systèmes d'Information
2    * Licensed to CS Systèmes d'Information (CS) under one or more
3    * contributor license agreements.  See the NOTICE file distributed with
4    * this work for additional information regarding copyright ownership.
5    * CS licenses this file to You under the Apache License, Version 2.0
6    * (the "License"); you may not use this file except in compliance with
7    * the License.  You may obtain a copy of the License at
8    *
9    *   http://www.apache.org/licenses/LICENSE-2.0
10   *
11   * Unless required by applicable law or agreed to in writing, software
12   * distributed under the License is distributed on an "AS IS" BASIS,
13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14   * See the License for the specific language governing permissions and
15   * limitations under the License.
16   */
17  package org.orekit.data;
18  
19  import java.util.HashMap;
20  import java.util.Map;
21  import java.util.regex.Matcher;
22  import java.util.regex.Pattern;
23  
24  import org.hipparchus.util.FastMath;
25  
26  /**
27   * Parser for polynomials in IERS tables.
28   * <p>
29   * IERS conventions tables display polynomial parts using several different formats,
30   * like the following ones:
31   * </p>
32   * <ul>
33   *   <li>125.04455501° − 6962890.5431″t + 7.4722″t² + 0.007702″t³ − 0.00005939″t⁴</li>
34   *   <li>0.02438175 × t + 0.00000538691 × t²</li>
35   *   <li>0''.014506 + 4612''.15739966t + 1''.39667721t^2 - 0''.00009344t^3 + 0''.00001882t^4</li>
36   *   <li>-16616.99 + 2004191742.88 t - 427219.05 t^2 - 198620.54 t^3 - 46.05 t^4 + 5.98 t^5</li>
37   * </ul>
38   * <p>
39   * This class parses all these formats and returns the coefficients.
40   * </p>
41   *
42   * @author Luc Maisonobe
43   * @see SeriesTerm
44   * @see PoissonSeries
45   * @see BodiesElements
46   */
47  public class PolynomialParser {
48  
49      /** Unit for the coefficients. */
50      public enum Unit {
51  
52          /** Radians angles. */
53          RADIANS(1.0),
54  
55          /** Degrees angles. */
56          DEGREES(FastMath.toRadians(1.0)),
57  
58          /** Arc-seconds angles. */
59          ARC_SECONDS(FastMath.toRadians(1.0 / 3600.0)),
60  
61          /** Milli arc-seconds angles. */
62          MILLI_ARC_SECONDS(FastMath.toRadians(1.0 / 3600000.0)),
63  
64          /** Micro arc-seconds angles. */
65          MICRO_ARC_SECONDS(FastMath.toRadians(1.0 / 3600000000.0)),
66  
67          /** No units. */
68          NO_UNITS(1.0);
69  
70          /** Multiplication factor to convert to corresponding SI unit. */
71          private final double factor;
72  
73          /** Simple constructor.
74           * @param factor multiplication factor to convert to corresponding SI unit.
75           */
76          Unit(final double factor) {
77              this.factor = factor;
78          }
79  
80          /** Convert value from instance unit to corresponding SI unit.
81           * @param value value in instance unit
82           * @return value in SI unit
83           */
84          public double toSI(final double value) {
85              return value * factor;
86          }
87  
88      }
89  
90      /** Constants for various characters that can be used as minus sign. */
91      private static final String[] MINUS = new String[] {
92          "-",      // unicode HYPHEN-MINUS
93          "\u2212"  // unicode MINUS SIGN
94      };
95  
96      /** Constants for various characters that can be used as plus sign. */
97      private static final String[] PLUS = new String[] {
98          "+",      // unicode PLUS SIGN
99      };
100 
101     /** Constants for various characters that can be used as multiplication sign. */
102     private static final String[] MULTIPLICATION = new String[] {
103         "*",      // unicode ASTERISK
104         "\u00d7"  // unicode MULTIPLICATION SIGN
105     };
106 
107     /** Constants for various characters that can be used as degree unit. */
108     private static final String[] DEGREES = new String[] {
109         "\u00b0", // unicode DEGREE SIGN
110         "\u25e6"  // unicode WHITE BULLET
111     };
112 
113     /** Constants for various characters that can be used as arc-seconds unit. */
114     private static final String[] ARC_SECONDS = new String[] {
115         "\u2033", // unicode DOUBLE_PRIME
116         "''",     // doubled unicode APOSTROPHE
117         "\""      // unicode QUOTATION MARK
118     };
119 
120     /** Constants for various characters that can be used as powers. */
121     private static final String[] SUPERSCRIPTS = new String[] {
122         "\u2070", // unicode SUPERSCRIPT ZERO
123         "\u00b9", // unicode SUPERSCRIPT ONE
124         "\u00b2", // unicode SUPERSCRIPT TWO
125         "\u00b3", // unicode SUPERSCRIPT THREE
126         "\u2074", // unicode SUPERSCRIPT FOUR
127         "\u2075", // unicode SUPERSCRIPT FIVE
128         "\u2076", // unicode SUPERSCRIPT SIX
129         "\u2077", // unicode SUPERSCRIPT SEVEN
130         "\u2078", // unicode SUPERSCRIPT EIGHT
131         "\u2079", // unicode SUPERSCRIPT NINE
132     };
133 
134     /** Constants for various characters that can be used as powers. */
135     private static final String[] DIGITS = new String[] {
136         "0", // unicode DIGIT ZERO
137         "1", // unicode DIGIT ONE
138         "2", // unicode DIGIT TWO
139         "3", // unicode DIGIT THREE
140         "4", // unicode DIGIT FOUR
141         "5", // unicode DIGIT FIVE
142         "6", // unicode DIGIT SIX
143         "7", // unicode DIGIT SEVEN
144         "8", // unicode DIGIT EIGHT
145         "9", // unicode DIGIT NINE
146     };
147 
148     /** Regular expression pattern for monomials. */
149     private final Pattern pattern;
150 
151     /** Matcher for a definition. */
152     private Matcher matcher;
153 
154     /** Start index for next search. */
155     private int next;
156 
157     /** Last parsed coefficient. */
158     private double parsedCoefficient;
159 
160     /** Last parsed power. */
161     private int parsedPower;
162 
163     /** Unit to use if no unit found while parsing. */
164     private final Unit defaultUnit;
165 
166     /** Simple constructor.
167      * @param freeVariable name of the free variable
168      * @param defaultUnit unit to use if no unit found while parsing
169      */
170     public PolynomialParser(final char freeVariable, final Unit defaultUnit) {
171 
172         this.defaultUnit = defaultUnit;
173 
174         final String space        = "\\p{Space}*";
175         final String unit         = either(quote(merge(DEGREES, ARC_SECONDS)));
176         final String sign         = either(quote(merge(MINUS, PLUS)));
177         final String integer      = "\\p{Digit}+";
178         final String exp          = "[eE]" + zeroOrOne(sign, false) + integer;
179         final String fractional   = "\\.\\p{Digit}*" + zeroOrOne(exp, false);
180         final String embeddedUnit = group(integer, true) +
181                                     group(unit, true) +
182                                     group(fractional, true);
183         final String appendedUnit = group(either(group(integer + zeroOrOne(fractional, false), false),
184                                                  group(fractional, false)),
185                                           true) +
186                                     zeroOrOne(unit, true);
187         final String caretPower   = "\\^" + any(quote(DIGITS));
188         final String superscripts = any(quote(SUPERSCRIPTS));
189         final String power        = zeroOrOne(either(quote(MULTIPLICATION)), false) +
190                                     space + freeVariable +
191                                     either(caretPower, superscripts);
192 
193         // the capturing groups of the following pattern are:
194         //   group  1: sign
195         //
196         //   when unit is embedded within the coefficient, as in 1''.39667721:
197         //   group  2: integer part of the coefficient
198         //   group  3: unit
199         //   group  4: fractional part of the coefficient
200         //
201         //   when unit is appended after the coefficient, as in 125.04455501°
202         //   group  5: complete coefficient
203         //   group  6: unit
204         //
205         //   group  7: complete power, including free variable, for example "× τ^4" or "× τ⁴"
206         //
207         //   when caret and regular digits are used, for example τ^4
208         //   group  8: only exponent part of the power
209         //
210         //   when superscripts are used, for example τ⁴
211         //   group  9: only exponent part of the power
212         pattern = Pattern.compile(space + zeroOrOne(sign, true) + space +
213                                   either(group(embeddedUnit, false), group(appendedUnit, false)) +
214                                   space + zeroOrOne(power, true));
215 
216     }
217 
218     /** Merge two lists of markers.
219      * @param markers1 first list
220      * @param markers2 second list
221      * @return merged list
222      */
223     private String[] merge(final String[] markers1, final String[] markers2) {
224         final String[] merged = new String[markers1.length + markers2.length];
225         System.arraycopy(markers1, 0, merged, 0, markers1.length);
226         System.arraycopy(markers2, 0, merged, markers1.length, markers2.length);
227         return merged;
228     }
229 
230     /** Quote a list of markers.
231      * @param markers markers to quote
232      * @return quoted markers
233      */
234     private String[] quote(final String... markers) {
235         final String[] quoted = new String[markers.length];
236         for (int i = 0; i < markers.length; ++i) {
237             quoted[i] = "\\Q" + markers[i] + "\\E";
238         }
239         return quoted;
240     }
241 
242     /** Create a regular expression for a group.
243      * @param r raw regular expression to group
244      * @param capturing if true, the group is a capturing group
245      * @return group expression
246      */
247     private String group(final CharSequence r, final boolean capturing) {
248         return (capturing ? "(" : "(?:") + r + ")";
249     }
250 
251     /** Create a regular expression for alternative markers.
252      * @param markers allowed markers
253      * @return regular expression recognizing one marker from the list
254      * (the result is a non-capturing group)
255      */
256     private String either(final CharSequence... markers) {
257         final StringBuilder builder = new StringBuilder();
258         for (final CharSequence marker : markers) {
259             if (builder.length() > 0) {
260                 builder.append('|');
261             }
262             builder.append(marker);
263         }
264         return group(builder, false);
265     }
266 
267     /** Create a regular expression for a repeatable part.
268      * @param markers allowed markers
269      * @return regular expression recognizing any number of markers from the list
270      * (the result is a capturing group)
271      */
272     private String any(final CharSequence... markers) {
273         return group(either(markers) + "*", true);
274     }
275 
276     /** Create a regular expression for an optional part.
277      * @param r optional raw regular expression
278      * @param capturing if true, wrap the optional part in a capturing group
279      * @return group expression
280      */
281     private String zeroOrOne(final CharSequence r, final boolean capturing) {
282         final String optional = group(r, false) + "?";
283         return capturing ? group(optional, true) : optional;
284     }
285 
286     /** Check if a substring starts with one marker from an array.
287      * @param s string containing the substring to check
288      * @param offset offset at which substring starts
289      * @param markers markes to check for
290      * @return index of the start marker, or negative if string does not start
291      * with one of the markers
292      */
293     private int startMarker(final String s, final int offset, final String[] markers) {
294         for (int i = 0; i < markers.length; ++i) {
295             if (s.startsWith(markers[i], offset)) {
296                 return i;
297             }
298         }
299         return -1;
300     }
301 
302     /** Parse a polynomial expression.
303      * @param expression polynomial expression to parse
304      * @return polynomial coefficients array in increasing degree order, or
305      * null if expression is not a recognized polynomial
306      */
307     public double[] parse(final String expression) {
308 
309         final Map<Integer, Double> coefficients = new HashMap<Integer, Double>();
310         int maxDegree = -1;
311         matcher = pattern.matcher(expression);
312         next = 0;
313         while (parseMonomial(expression)) {
314             maxDegree = FastMath.max(maxDegree, parsedPower);
315             coefficients.put(parsedPower, parsedCoefficient);
316         }
317 
318         if (maxDegree < 0) {
319             return null;
320         }
321 
322         final double[] parsedPolynomial = new double[maxDegree + 1];
323         for (Map.Entry<Integer, Double> entry : coefficients.entrySet()) {
324             parsedPolynomial[entry.getKey()] = entry.getValue();
325         }
326 
327         return parsedPolynomial;
328 
329     }
330 
331     /** Parse next monomial.
332      * @param expression polynomial expression to parse
333      * @return true if a monomial has been parsed
334      */
335     private boolean parseMonomial(final String expression) {
336 
337         // groups indices
338         final int signGroup         = 1;
339         final int coeffIntGroup     = 2;
340         final int embeddedUnitGroup = 3;
341         final int coeffFracGroup    = 4;
342         final int coeffGroup        = 5;
343         final int appendedUnitGroup = 6;
344         final int powerGroup        = 7;
345         final int caretGroup        = 8;
346         final int superScriptGroup  = 9;
347 
348         // advance matcher
349         matcher.region(next, matcher.regionEnd());
350 
351         if (matcher.lookingAt()) {
352 
353             // parse coefficient, with proper sign and unit
354             final double sign = startMarker(expression, matcher.start(signGroup), MINUS) >= 0 ? -1 : 1;
355             final String coeff;
356             final Unit unit;
357             if (matcher.start(embeddedUnitGroup) >= 0) {
358                 // the unit is embedded between coefficient integer and fractional parts
359                 coeff = matcher.group(coeffIntGroup) + matcher.group(coeffFracGroup);
360                 if (startMarker(expression, matcher.start(embeddedUnitGroup), DEGREES) >= 0) {
361                     unit = Unit.DEGREES;
362                 } else {
363                     // as we recognize only degrees and arc-seconds as explicit settings in the expression
364                     // and as we know here the unit as been set, it must be arc seconds
365                     unit = Unit.ARC_SECONDS;
366                 }
367             } else {
368                 // the unit is either after the coefficient or not present at all
369                 coeff = matcher.group(coeffGroup);
370                 if (startMarker(expression, matcher.start(appendedUnitGroup), DEGREES) >= 0) {
371                     unit = Unit.DEGREES;
372                 } else if (startMarker(expression, matcher.start(appendedUnitGroup), ARC_SECONDS) >= 0) {
373                     unit = Unit.ARC_SECONDS;
374                 } else {
375                     unit = defaultUnit;
376                 }
377             }
378             parsedCoefficient = sign * unit.toSI(Double.parseDouble(coeff));
379 
380             if (matcher.start(powerGroup) < matcher.end(powerGroup)) {
381                 // this a power 1 or more term
382 
383                 if (matcher.start(caretGroup) < matcher.end(caretGroup)) {
384                     // general case: x^1234
385                     parsedPower = 0;
386                     for (int index = matcher.start(caretGroup); index < matcher.end(caretGroup); ++index) {
387                         parsedPower = parsedPower * 10 + startMarker(expression, index, DIGITS);
388                     }
389                 } else if (matcher.start(superScriptGroup) < matcher.end(superScriptGroup)) {
390                     // general case: x¹²³⁴
391                     parsedPower = 0;
392                     for (int index = matcher.start(superScriptGroup); index < matcher.end(superScriptGroup); ++index) {
393                         parsedPower = parsedPower * 10 + startMarker(expression, index, SUPERSCRIPTS);
394                     }
395                 } else {
396                     // special case: x is the same term as either x^1 or x¹
397                     parsedPower = 1;
398                 }
399 
400             } else {
401                 // this is a constant term
402                 parsedPower = 0;
403             }
404 
405             next = matcher.end();
406             return true;
407 
408         } else {
409 
410             parsedCoefficient = Double.NaN;
411             parsedPower       = -1;
412             return false;
413 
414         }
415 
416     }
417 
418 }