PolynomialParser.java

  1. /* Copyright 2002-2024 CS GROUP
  2.  * Licensed to CS GROUP (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. import java.util.HashMap;
  19. import java.util.Map;
  20. import java.util.regex.Matcher;
  21. import java.util.regex.Pattern;

  22. import org.hipparchus.util.FastMath;

  23. /**
  24.  * Parser for polynomials in IERS tables.
  25.  * <p>
  26.  * IERS conventions tables display polynomial parts using several different formats,
  27.  * like the following ones:
  28.  * </p>
  29.  * <ul>
  30.  *   <li>125.04455501° − 6962890.5431″t + 7.4722″t² + 0.007702″t³ − 0.00005939″t⁴</li>
  31.  *   <li>0.02438175 × t + 0.00000538691 × t²</li>
  32.  *   <li>0''.014506 + 4612''.15739966t + 1''.39667721t^2 - 0''.00009344t^3 + 0''.00001882t^4</li>
  33.  *   <li>-16616.99 + 2004191742.88 t - 427219.05 t^2 - 198620.54 t^3 - 46.05 t^4 + 5.98 t^5</li>
  34.  * </ul>
  35.  * <p>
  36.  * This class parses all these formats and returns the coefficients.
  37.  * </p>
  38.  *
  39.  * @author Luc Maisonobe
  40.  * @see SeriesTerm
  41.  * @see PoissonSeries
  42.  * @see BodiesElements
  43.  */
  44. public class PolynomialParser {

  45.     /** Unit for the coefficients. */
  46.     public enum Unit {

  47.         /** Radians angles. */
  48.         RADIANS(1.0),

  49.         /** Degrees angles. */
  50.         DEGREES(FastMath.toRadians(1.0)),

  51.         /** Arc-seconds angles. */
  52.         ARC_SECONDS(FastMath.toRadians(1.0 / 3600.0)),

  53.         /** Milli arc-seconds angles. */
  54.         MILLI_ARC_SECONDS(FastMath.toRadians(1.0 / 3600000.0)),

  55.         /** Micro arc-seconds angles. */
  56.         MICRO_ARC_SECONDS(FastMath.toRadians(1.0 / 3600000000.0)),

  57.         /** No units. */
  58.         NO_UNITS(1.0);

  59.         /** Multiplication factor to convert to corresponding SI unit. */
  60.         private final double factor;

  61.         /** Simple constructor.
  62.          * @param factor multiplication factor to convert to corresponding SI unit.
  63.          */
  64.         Unit(final double factor) {
  65.             this.factor = factor;
  66.         }

  67.         /** Convert value from instance unit to corresponding SI unit.
  68.          * @param value value in instance unit
  69.          * @return value in SI unit
  70.          */
  71.         public double toSI(final double value) {
  72.             return value * factor;
  73.         }

  74.     }

  75.     /** Constants for various characters that can be used as minus sign. */
  76.     private static final String[] MINUS = new String[] {
  77.         "-",      // unicode HYPHEN-MINUS
  78.         "\u2212"  // unicode MINUS SIGN
  79.     };

  80.     /** Constants for various characters that can be used as plus sign. */
  81.     private static final String[] PLUS = new String[] {
  82.         "+",      // unicode PLUS SIGN
  83.     };

  84.     /** Constants for various characters that can be used as multiplication sign. */
  85.     private static final String[] MULTIPLICATION = new String[] {
  86.         "*",      // unicode ASTERISK
  87.         "\u00d7"  // unicode MULTIPLICATION SIGN
  88.     };

  89.     /** Constants for various characters that can be used as degree unit. */
  90.     private static final String[] DEGREES = new String[] {
  91.         "\u00b0", // unicode DEGREE SIGN
  92.         "\u25e6"  // unicode WHITE BULLET
  93.     };

  94.     /** Constants for various characters that can be used as arc-seconds unit. */
  95.     private static final String[] ARC_SECONDS = new String[] {
  96.         "\u2033", // unicode DOUBLE_PRIME
  97.         "''",     // doubled unicode APOSTROPHE
  98.         "\""      // unicode QUOTATION MARK
  99.     };

  100.     /** Constants for various characters that can be used as powers. */
  101.     private static final String[] SUPERSCRIPTS = new String[] {
  102.         "\u2070", // unicode SUPERSCRIPT ZERO
  103.         "\u00b9", // unicode SUPERSCRIPT ONE
  104.         "\u00b2", // unicode SUPERSCRIPT TWO
  105.         "\u00b3", // unicode SUPERSCRIPT THREE
  106.         "\u2074", // unicode SUPERSCRIPT FOUR
  107.         "\u2075", // unicode SUPERSCRIPT FIVE
  108.         "\u2076", // unicode SUPERSCRIPT SIX
  109.         "\u2077", // unicode SUPERSCRIPT SEVEN
  110.         "\u2078", // unicode SUPERSCRIPT EIGHT
  111.         "\u2079", // unicode SUPERSCRIPT NINE
  112.     };

  113.     /** Constants for various characters that can be used as powers. */
  114.     private static final String[] DIGITS = new String[] {
  115.         "0", // unicode DIGIT ZERO
  116.         "1", // unicode DIGIT ONE
  117.         "2", // unicode DIGIT TWO
  118.         "3", // unicode DIGIT THREE
  119.         "4", // unicode DIGIT FOUR
  120.         "5", // unicode DIGIT FIVE
  121.         "6", // unicode DIGIT SIX
  122.         "7", // unicode DIGIT SEVEN
  123.         "8", // unicode DIGIT EIGHT
  124.         "9", // unicode DIGIT NINE
  125.     };

  126.     /** Regular expression pattern for monomials. */
  127.     private final Pattern pattern;

  128.     /** Matcher for a definition. */
  129.     private Matcher matcher;

  130.     /** Start index for next search. */
  131.     private int next;

  132.     /** Last parsed coefficient. */
  133.     private double parsedCoefficient;

  134.     /** Last parsed power. */
  135.     private int parsedPower;

  136.     /** Unit to use if no unit found while parsing. */
  137.     private final Unit defaultUnit;

  138.     /** Simple constructor.
  139.      * @param freeVariable name of the free variable
  140.      * @param defaultUnit unit to use if no unit found while parsing
  141.      */
  142.     public PolynomialParser(final char freeVariable, final Unit defaultUnit) {

  143.         this.defaultUnit = defaultUnit;

  144.         final String space        = "\\p{Space}*";
  145.         final String unit         = either(quote(merge(DEGREES, ARC_SECONDS)));
  146.         final String sign         = either(quote(merge(MINUS, PLUS)));
  147.         final String integer      = "\\p{Digit}+";
  148.         final String exp          = "[eE]" + zeroOrOne(sign, false) + integer;
  149.         final String fractional   = "\\.\\p{Digit}*" + zeroOrOne(exp, false);
  150.         final String embeddedUnit = group(integer, true) +
  151.                                     group(unit, true) +
  152.                                     group(fractional, true);
  153.         final String appendedUnit = group(either(group(integer + zeroOrOne(fractional, false), false),
  154.                                                  group(fractional, false)),
  155.                                           true) +
  156.                                     zeroOrOne(unit, true);
  157.         final String caretPower   = "\\^" + any(quote(DIGITS));
  158.         final String superscripts = any(quote(SUPERSCRIPTS));
  159.         final String power        = zeroOrOne(either(quote(MULTIPLICATION)), false) +
  160.                                     space + freeVariable +
  161.                                     either(caretPower, superscripts);

  162.         // the capturing groups of the following pattern are:
  163.         //   group  1: sign
  164.         //
  165.         //   when unit is embedded within the coefficient, as in 1''.39667721:
  166.         //   group  2: integer part of the coefficient
  167.         //   group  3: unit
  168.         //   group  4: fractional part of the coefficient
  169.         //
  170.         //   when unit is appended after the coefficient, as in 125.04455501°
  171.         //   group  5: complete coefficient
  172.         //   group  6: unit
  173.         //
  174.         //   group  7: complete power, including free variable, for example "× τ^4" or "× τ⁴"
  175.         //
  176.         //   when caret and regular digits are used, for example τ^4
  177.         //   group  8: only exponent part of the power
  178.         //
  179.         //   when superscripts are used, for example τ⁴
  180.         //   group  9: only exponent part of the power
  181.         pattern = Pattern.compile(space + zeroOrOne(sign, true) + space +
  182.                                   either(group(embeddedUnit, false), group(appendedUnit, false)) +
  183.                                   space + zeroOrOne(power, true));

  184.     }

  185.     /** Merge two lists of markers.
  186.      * @param markers1 first list
  187.      * @param markers2 second list
  188.      * @return merged list
  189.      */
  190.     private String[] merge(final String[] markers1, final String[] markers2) {
  191.         final String[] merged = new String[markers1.length + markers2.length];
  192.         System.arraycopy(markers1, 0, merged, 0, markers1.length);
  193.         System.arraycopy(markers2, 0, merged, markers1.length, markers2.length);
  194.         return merged;
  195.     }

  196.     /** Quote a list of markers.
  197.      * @param markers markers to quote
  198.      * @return quoted markers
  199.      */
  200.     private String[] quote(final String... markers) {
  201.         final String[] quoted = new String[markers.length];
  202.         for (int i = 0; i < markers.length; ++i) {
  203.             quoted[i] = "\\Q" + markers[i] + "\\E";
  204.         }
  205.         return quoted;
  206.     }

  207.     /** Create a regular expression for a group.
  208.      * @param r raw regular expression to group
  209.      * @param capturing if true, the group is a capturing group
  210.      * @return group expression
  211.      */
  212.     private String group(final CharSequence r, final boolean capturing) {
  213.         return (capturing ? "(" : "(?:") + r + ")";
  214.     }

  215.     /** Create a regular expression for alternative markers.
  216.      * @param markers allowed markers
  217.      * @return regular expression recognizing one marker from the list
  218.      * (the result is a non-capturing group)
  219.      */
  220.     private String either(final CharSequence... markers) {
  221.         final StringBuilder builder = new StringBuilder();
  222.         for (final CharSequence marker : markers) {
  223.             if (builder.length() > 0) {
  224.                 builder.append('|');
  225.             }
  226.             builder.append(marker);
  227.         }
  228.         return group(builder, false);
  229.     }

  230.     /** Create a regular expression for a repeatable part.
  231.      * @param markers allowed markers
  232.      * @return regular expression recognizing any number of markers from the list
  233.      * (the result is a capturing group)
  234.      */
  235.     private String any(final CharSequence... markers) {
  236.         return group(either(markers) + "*", true);
  237.     }

  238.     /** Create a regular expression for an optional part.
  239.      * @param r optional raw regular expression
  240.      * @param capturing if true, wrap the optional part in a capturing group
  241.      * @return group expression
  242.      */
  243.     private String zeroOrOne(final CharSequence r, final boolean capturing) {
  244.         final String optional = group(r, false) + "?";
  245.         return capturing ? group(optional, true) : optional;
  246.     }

  247.     /** Check if a substring starts with one marker from an array.
  248.      * @param s string containing the substring to check
  249.      * @param offset offset at which substring starts
  250.      * @param markers markes to check for
  251.      * @return index of the start marker, or negative if string does not start
  252.      * with one of the markers
  253.      */
  254.     private int startMarker(final String s, final int offset, final String[] markers) {
  255.         for (int i = 0; i < markers.length; ++i) {
  256.             if (s.startsWith(markers[i], offset)) {
  257.                 return i;
  258.             }
  259.         }
  260.         return -1;
  261.     }

  262.     /** Parse a polynomial expression.
  263.      * @param expression polynomial expression to parse
  264.      * @return polynomial coefficients array in increasing degree order, or
  265.      * null if expression is not a recognized polynomial
  266.      */
  267.     public double[] parse(final String expression) {

  268.         final Map<Integer, Double> coefficients = new HashMap<Integer, Double>();
  269.         int maxDegree = -1;
  270.         matcher = pattern.matcher(expression);
  271.         next = 0;
  272.         while (parseMonomial(expression)) {
  273.             maxDegree = FastMath.max(maxDegree, parsedPower);
  274.             coefficients.put(parsedPower, parsedCoefficient);
  275.         }

  276.         if (maxDegree < 0) {
  277.             return null;
  278.         }

  279.         final double[] parsedPolynomial = new double[maxDegree + 1];
  280.         for (Map.Entry<Integer, Double> entry : coefficients.entrySet()) {
  281.             parsedPolynomial[entry.getKey()] = entry.getValue();
  282.         }

  283.         return parsedPolynomial;

  284.     }

  285.     /** Parse next monomial.
  286.      * @param expression polynomial expression to parse
  287.      * @return true if a monomial has been parsed
  288.      */
  289.     private boolean parseMonomial(final String expression) {

  290.         // groups indices
  291.         final int signGroup         = 1;
  292.         final int coeffIntGroup     = 2;
  293.         final int embeddedUnitGroup = 3;
  294.         final int coeffFracGroup    = 4;
  295.         final int coeffGroup        = 5;
  296.         final int appendedUnitGroup = 6;
  297.         final int powerGroup        = 7;
  298.         final int caretGroup        = 8;
  299.         final int superScriptGroup  = 9;

  300.         // advance matcher
  301.         matcher.region(next, matcher.regionEnd());

  302.         if (matcher.lookingAt()) {

  303.             // parse coefficient, with proper sign and unit
  304.             final double sign = startMarker(expression, matcher.start(signGroup), MINUS) >= 0 ? -1 : 1;
  305.             final String coeff;
  306.             final Unit unit;
  307.             if (matcher.start(embeddedUnitGroup) >= 0) {
  308.                 // the unit is embedded between coefficient integer and fractional parts
  309.                 coeff = matcher.group(coeffIntGroup) + matcher.group(coeffFracGroup);
  310.                 if (startMarker(expression, matcher.start(embeddedUnitGroup), DEGREES) >= 0) {
  311.                     unit = Unit.DEGREES;
  312.                 } else {
  313.                     // as we recognize only degrees and arc-seconds as explicit settings in the expression
  314.                     // and as we know here the unit as been set, it must be arc seconds
  315.                     unit = Unit.ARC_SECONDS;
  316.                 }
  317.             } else {
  318.                 // the unit is either after the coefficient or not present at all
  319.                 coeff = matcher.group(coeffGroup);
  320.                 if (startMarker(expression, matcher.start(appendedUnitGroup), DEGREES) >= 0) {
  321.                     unit = Unit.DEGREES;
  322.                 } else if (startMarker(expression, matcher.start(appendedUnitGroup), ARC_SECONDS) >= 0) {
  323.                     unit = Unit.ARC_SECONDS;
  324.                 } else {
  325.                     unit = defaultUnit;
  326.                 }
  327.             }
  328.             parsedCoefficient = sign * unit.toSI(Double.parseDouble(coeff));

  329.             if (matcher.start(powerGroup) < matcher.end(powerGroup)) {
  330.                 // this a power 1 or more term

  331.                 if (matcher.start(caretGroup) < matcher.end(caretGroup)) {
  332.                     // general case: x^1234
  333.                     parsedPower = 0;
  334.                     for (int index = matcher.start(caretGroup); index < matcher.end(caretGroup); ++index) {
  335.                         parsedPower = parsedPower * 10 + startMarker(expression, index, DIGITS);
  336.                     }
  337.                 } else if (matcher.start(superScriptGroup) < matcher.end(superScriptGroup)) {
  338.                     // general case: x¹²³⁴
  339.                     parsedPower = 0;
  340.                     for (int index = matcher.start(superScriptGroup); index < matcher.end(superScriptGroup); ++index) {
  341.                         parsedPower = parsedPower * 10 + startMarker(expression, index, SUPERSCRIPTS);
  342.                     }
  343.                 } else {
  344.                     // special case: x is the same term as either x^1 or x¹
  345.                     parsedPower = 1;
  346.                 }

  347.             } else {
  348.                 // this is a constant term
  349.                 parsedPower = 0;
  350.             }

  351.             next = matcher.end();
  352.             return true;

  353.         } else {

  354.             parsedCoefficient = Double.NaN;
  355.             parsedPower       = -1;
  356.             return false;

  357.         }

  358.     }

  359. }