/*
    * Licensed to the Apache Software Foundation (ASF) under one or more
    * contributor license agreements.  See the NOTICE file distributed with
    * this work for additional information regarding copyright ownership.
    * The ASF licenses this file to You under the Apache License, Version 2.0
    * (the "License"); you may not use this file except in compliance with
    * the License.  You may obtain a copy of the License at
    *
    *      https://www.apache.org/licenses/LICENSE-2.0
   *
   * Unless required by applicable law or agreed to in writing, software
   * distributed under the License is distributed on an "AS IS" BASIS,
   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   * See the License for the specific language governing permissions and
   * limitations under the License.
   */
  
  /*
   * This is not the original file distributed by the Apache Software Foundation
   * It has been modified by the Hipparchus project
   */
  package org.hipparchus.fraction;
  
  import java.util.Iterator;
  import java.util.Spliterator;
  import java.util.Spliterators;
  import java.util.function.Predicate;
  import java.util.stream.Stream;
  import java.util.stream.StreamSupport;
  
  import org.hipparchus.exception.LocalizedCoreFormats;
  import org.hipparchus.exception.MathIllegalStateException;
  import org.hipparchus.util.FastMath;
  import org.hipparchus.util.Pair;
  import org.hipparchus.util.Precision;
  
  /**
   * Generator for convergents.
   */
  class ConvergentsIterator {
  
      /** Unused constructor.
       */
      private ConvergentsIterator() {
      } // static use only
  
      /** Container for one convergent step. */
      static class ConvergenceStep {
          /** Numerator of previous convergent. */
          private final long   p0;
  
          /** Denominator of previous convergent. */
          private final long   q0;
  
          /** Numerator of current convergent. */
          private final long   p1;
  
          /** Denominator of current convergent. */
          private final long   q1;
  
          /** Remainder of current convergent. */
          private final double r1;
  
          private ConvergenceStep(final long p0, final long q0, final long p1, final long q1, final double r1) {
              this.p0 = p1;
              this.q0 = q1;
              final long a1 = (long) FastMath.floor(r1);
              try {
                  this.p1 = FastMath.addExact(Math.multiplyExact(a1, p1), p0);
                  this.q1 = FastMath.addExact(Math.multiplyExact(a1, q1), q0);
                  this.r1 = 1.0 / (r1 - a1);
              } catch (ArithmeticException e) { // unlike the name implies FastMath's multiplyExact() is slower
                  throw new MathIllegalStateException(e, LocalizedCoreFormats.FRACTION_CONVERSION_OVERFLOW, r1, p1, q1);
              }
          }
  
          /** Builder from a double value.
           * @param value value to approximate
           * @return first step in approximation
           */
          public static ConvergenceStep start(double value) {
              return new ConvergenceStep(0, 1, 1, 0, value);
          }
  
          /** Compute next step in convergence.
           * @return next convergence step
           */
          public ConvergenceStep next() {
              return new ConvergenceStep(p0, q0, p1, q1, r1);
          }
  
          /** Get the numerator of current convergent.
           * @return numerator of current convergent
           */
          public long getNumerator() {
              return p1;
          }
  
          /** Get the denominator of current convergent.
          * @return denominator of current convergent
          */
         public long getDenominator() {
             return q1;
         }
 
         /** Compute double value of current convergent.
          * @return double value of current convergent
          */
         public double getFractionValue() {
             return getNumerator() / (double) getDenominator();
         }
 
         /** Convert convergent to string representation.
          * @return string representation of convergent
          */
         @Override
         public String toString() {
             return getNumerator() + "/" + getDenominator();
         }
 
     }
 
     /**
      * Returns the last element of the series of convergent-steps to approximate the
      * given value.
      * <p>
      * The series terminates either at the first step that satisfies the given
      * {@code convergenceTest} or after at most {@code maxConvergents} elements. The
      * returned Pair consists of that terminal step and a {@link Boolean} that
      * indicates if it satisfies the given convergence tests. If the returned pair's
      * value is {@code false} the element at position {@code maxConvergents} was
      * examined but failed to satisfy the {@code convergenceTest}.
      *
      * @param value           value to approximate
      * @param maxConvergents  maximum number of convergents to examine
      * @param convergenceTests the test if the series has converged at a step
      * @return the pair of last element of the series of convergents and a boolean
      *         indicating if that element satisfies the specified convergent test
      */
     static Pair<ConvergenceStep, Boolean> convergent(double value, int maxConvergents,
             Predicate<ConvergenceStep> convergenceTests) {
         ConvergenceStep step = ConvergenceStep.start(value);
         for (int i = 1; i < maxConvergents; i++) { // start performs first iteration
             if (convergenceTests.test(step)) {
                 return Pair.create(step, Boolean.TRUE);
             }
             step = step.next();
         }
         return Pair.create(step, convergenceTests.test(step));
     }
 
     /**
      * Generate a {@link Stream stream} of {@code ConvergenceStep convergent-steps}
      * from a real number.
      *
      * @param value           value to approximate
      * @param maxConvergents maximum number of convergent steps.
      * @return stream of {@link ConvergenceStep convergent-steps} approximating
      *         {@code value}
      */
     static Stream<ConvergenceStep> convergents(final double value, final int maxConvergents) {
         return StreamSupport.stream(Spliterators.spliteratorUnknownSize(new Iterator<ConvergenceStep>() {
 
             /** Next convergent. */
             private ConvergenceStep next = ConvergenceStep.start(value);
 
             /** {@inheritDoc} */
             @Override
             public boolean hasNext() {
                 return next != null;
             }
 
             /** {@inheritDoc} */
             @Override
             public ConvergenceStep next() {
                 final ConvergenceStep ret = next;
                 if (Precision.equals(ret.getFractionValue(), value, 1)) {
                     next = null; // stop if precision has been reached
                 } else {
                     next = next.next();
                 }
                 return ret;
             }
 
         }, Spliterator.DISTINCT | Spliterator.NONNULL | Spliterator.IMMUTABLE | Spliterator.ORDERED),
         false).
         limit(maxConvergents);
     }
 }