/*
    * 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
    *
    *      http://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.
   */
  package org.apache.commons.rng.sampling.distribution;
  
  import org.apache.commons.rng.UniformRandomProvider;
  
  /**
   * Sampling from an <a href="http://mathworld.wolfram.com/ExponentialDistribution.html">exponential distribution</a>.
   *
   * <p>Sampling uses:</p>
   *
   * <ul>
   *   <li>{@link UniformRandomProvider#nextLong()}
   *   <li>{@link UniformRandomProvider#nextDouble()}
   * </ul>
   *
   * @since 1.0
   */
  public class AhrensDieterExponentialSampler
      extends SamplerBase
      implements SharedStateContinuousSampler {
      /**
       * Table containing the constants
       * \( q_i = sum_{j=1}^i (\ln 2)^j / j! = \ln 2 + (\ln 2)^2 / 2 + ... + (\ln 2)^i / i! \)
       * until the largest representable fraction below 1 is exceeded.
       *
       * Note that
       * \( 1 = 2 - 1 = \exp(\ln 2) - 1 = sum_{n=1}^\infinity (\ln 2)^n / n! \)
       * thus \( q_i \rightarrow 1 as i \rightarrow +\infinity \),
       * so the higher \( i \), the closer we get to 1 (the series is not alternating).
       *
       * By trying, n = 16 in Java is enough to reach 1.
       */
      private static final double[] EXPONENTIAL_SA_QI = new double[16];
      /** The mean of this distribution. */
      private final double mean;
      /** Underlying source of randomness. */
      private final UniformRandomProvider rng;
  
      //
      // Initialize tables.
      //
      static {
          //
          // Filling EXPONENTIAL_SA_QI table.
          // Note that we don't want qi = 0 in the table.
          //
          final double ln2 = Math.log(2);
          double qi = 0;
  
          // Start with 0!
          // This will not overflow a long as the length < 21
          long factorial = 1;
          for (int i = 0; i < EXPONENTIAL_SA_QI.length; i++) {
              factorial *= i + 1;
              qi += Math.pow(ln2, i + 1.0) / factorial;
              EXPONENTIAL_SA_QI[i] = qi;
          }
      }
  
      /**
       * Create an instance.
       *
       * @param rng Generator of uniformly distributed random numbers.
       * @param mean Mean of this distribution.
       * @throws IllegalArgumentException if {@code mean <= 0}
       */
      public AhrensDieterExponentialSampler(UniformRandomProvider rng,
                                            double mean) {
          // Validation before java.lang.Object constructor exits prevents partially initialized object
          this(InternalUtils.requireStrictlyPositive(mean, "mean"), rng);
      }
  
      /**
       * @param mean Mean.
       * @param rng Generator of uniformly distributed random numbers.
       */
      private AhrensDieterExponentialSampler(double mean,
                                             UniformRandomProvider rng) {
          super(null);
          this.rng = rng;
          this.mean = mean;
      }
  
      /** {@inheritDoc} */
     @Override
     public double sample() {
         // Step 1:
         double a = 0;
         // Avoid u=0 which creates an infinite loop
         double u = InternalUtils.makeNonZeroDouble(rng.nextLong());
 
         // Step 2 and 3:
         while (u < 0.5) {
             a += EXPONENTIAL_SA_QI[0];
             u *= 2;
         }
 
         // Step 4 (now u >= 0.5):
         u += u - 1;
 
         // Step 5:
         if (u <= EXPONENTIAL_SA_QI[0]) {
             return mean * (a + u);
         }
 
         // Step 6:
         int i = 0; // Should be 1, be we iterate before it in while using 0.
         double u2 = rng.nextDouble();
         double umin = u2;
 
         // Step 7 and 8:
         do {
             ++i;
             u2 = rng.nextDouble();
 
             if (u2 < umin) {
                 umin = u2;
             }
 
             // Step 8:
         } while (u > EXPONENTIAL_SA_QI[i]); // Ensured to exit since EXPONENTIAL_SA_QI[MAX] = 1.
 
         return mean * (a + umin * EXPONENTIAL_SA_QI[0]);
     }
 
     /** {@inheritDoc} */
     @Override
     public String toString() {
         return "Ahrens-Dieter Exponential deviate [" + rng.toString() + "]";
     }
 
     /**
      * {@inheritDoc}
      *
      * @since 1.3
      */
     @Override
     public SharedStateContinuousSampler withUniformRandomProvider(UniformRandomProvider rng) {
         // Use private constructor without validation
         return new AhrensDieterExponentialSampler(mean, rng);
     }
 
     /**
      * Create a new exponential distribution sampler.
      *
      * @param rng Generator of uniformly distributed random numbers.
      * @param mean Mean of the distribution.
      * @return the sampler
      * @throws IllegalArgumentException if {@code mean <= 0}
      * @since 1.3
      */
     public static SharedStateContinuousSampler of(UniformRandomProvider rng,
                                                   double mean) {
         return new AhrensDieterExponentialSampler(rng, mean);
     }
 }