1 /* Copyright 2002-2013 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.apache.commons.math3.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 private 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 }