package org.opentrafficsim.core.distributions;
   
   import java.util.ArrayList;
   import java.util.List;
   
   import nl.tudelft.simulation.jstats.distributions.DistUniform;
   import nl.tudelft.simulation.jstats.streams.StreamInterface;
   
   /**
   * Generic implementation of a set of objects that have a draw method with corresponding probabilities / frequencies.
   * <p>
   * Copyright (c) 2013-2015 Delft University of Technology, PO Box 5, 2600 AA, Delft, the Netherlands. All rights reserved. <br>
   * BSD-style license. See <a href="http://opentrafficsim.org/node/13">OpenTrafficSim License</a>.
   * <p>
   * @version $Revision$, $LastChangedDate$, by $Author$, initial version Mar 1, 2016 <br>
   * @author <a href="http://www.tudelft.nl/pknoppers">Peter Knoppers</a>
   * @param <O> Type of the object returned by the draw method
   */
  public class Distribution<O> implements Generator<O>
  {
      /** The generators (with their probabilities or frequencies). */
      private final List<FrequencyAndObject<O>> generators = new ArrayList<>();
  
      /** Sum of all probabilities or frequencies. */
      private double cumulativeTotal;
  
      /** The uniform random generator used to select a Generator. */
      private final DistUniform random;
  
      /**
       * Construct a new Distribution.
       * @param generators List&lt;FrequencyAndObject&lt;O&gt;&gt;; the generators and their frequencies (or probabilities)
       * @param stream StreamInterface; source for randomness
       * @throws ProbabilityException when a frequency (or probability) is negative, or when generators is null or stream is null
       */
      public Distribution(final List<FrequencyAndObject<O>> generators, final StreamInterface stream)
          throws ProbabilityException
      {
          this(stream);
          ProbabilityException.failIf(null == generators, "generators may not be null");
          // Store a defensive copy of the generator list (the generators are immutable; a list of them is not) and make sure it
          // is a List that supports add, remove, etc.
          this.generators.addAll(generators);
          fixProbabilities();
      }
  
      /**
       * Construct a new Distribution with no generators.
       * @param stream StreamInterface; source for randomness
       * @throws ProbabilityException when a frequency (or probability) is negative, or when generators is null or stream is null
       */
      public Distribution(final StreamInterface stream) throws ProbabilityException
      {
          ProbabilityException.failIf(null == stream, "random stream may not be null");
          this.random = new DistUniform(stream, 0, 1);
      }
  
      /**
       * Compute the cumulative frequencies of the storedGenerators.
       * @throws ProbabilityException on negative frequency
       */
      private void fixProbabilities() throws ProbabilityException
      {
          if (0 == this.generators.size())
          {
              return;
          }
          this.cumulativeTotal = 0;
          for (FrequencyAndObject<O> generator : this.generators)
          {
              double frequency = generator.getFrequency();
              ProbabilityException.failIf(frequency < 0, "Negative frequency or probability is not allowed (got "
                  + frequency + ")");
              this.cumulativeTotal += frequency;
          }
      }
  
      /** {@inheritDoc} */
      public final O draw() throws ProbabilityException
      {
          ProbabilityException.failIf(0 == this.generators.size(), "Cannot draw from empty collection");
          ProbabilityException.failIf(0 == this.cumulativeTotal, "Sum of frequencies or probabilities must be > 0");
  
          double randomValue = this.random.draw() * this.cumulativeTotal;
          for (FrequencyAndObject<O> fAndO : this.generators)
          {
              double frequency = fAndO.getFrequency();
              if (frequency >= randomValue)
              {
                  return fAndO.getObject();
              }
              randomValue -= frequency;
          }
          // If we get here we missed the intended object by a few ULP; return the first object that has non-zero frequency
          FrequencyAndObject<O> useThisOne = this.generators.get(0);
          for (FrequencyAndObject<O> fAndO : this.generators)
          {
              if (fAndO.getFrequency() > 0)
              {
                 useThisOne = fAndO;
                 break;
             }
         }
         return useThisOne.getObject();
     }
 
     /**
      * Append a generator to the internally stored list.
      * @param generator FrequencyAndObject&lt;O&gt;; the generator to add
      * @return Distribution&lt;O&gt;; this
      * @throws ProbabilityException when frequency less than zero
      */
     public final Distribution<O> add(final FrequencyAndObject<O> generator) throws ProbabilityException
     {
         return add(this.generators.size(), generator);
     }
 
     /**
      * Insert a generator at the specified position in the internally stored list.
      * @param index int; position to store the generator
      * @param generator FrequencyAndObject&lt;O&gt;; the generator to add
      * @return Distribution&lt;O&gt;; this
      * @throws ProbabilityException when frequency less than zero
      */
     public final Distribution<O> add(final int index, final FrequencyAndObject<O> generator)
         throws ProbabilityException
     {
         ProbabilityException.failIf(generator.getFrequency() < 0, "frequency (or probability) must be >= 0 (got "
             + generator.getFrequency() + ")");
         this.generators.add(index, generator);
         fixProbabilities();
         return this;
     }
 
     /**
      * Remove the generator at the specified position from the internally stored list.
      * @param index int; the position
      * @return this
      * @throws IndexOutOfBoundsException when index is &lt; 0 or &gt;= size
      * @throws ProbabilityException if the sum of the remaining probabilities or frequencies adds up to 0
      */
     public final Distribution<O> remove(final int index) throws IndexOutOfBoundsException, ProbabilityException
     {
         this.generators.remove(index);
         fixProbabilities();
         return this;
     }
 
     /**
      * Replace the generator at the specified position.
      * @param index int; the position of the generator that must be replaced
      * @param generator FrequencyAndObject; the new generator and the frequency (or probability)
      * @return this
      * @throws ProbabilityException when the frequency (or probability) &lt; 0, or when index is &lt; 0 or &gt;= size
      */
     public final Distribution<O> set(final int index, final FrequencyAndObject<O> generator)
         throws ProbabilityException
     {
         ProbabilityException.failIf(generator.getFrequency() < 0, "frequency (or probability) must be >= 0 (got "
             + generator.getFrequency() + ")");
         try
         {
             this.generators.set(index, generator);
         }
         catch (IndexOutOfBoundsException ie)
         {
             throw new ProbabilityException("Index out of bounds for set operation, index=" + index);
         }
         fixProbabilities();
         return this;
     }
 
     /**
      * Alter the frequency (or probability) of one of the stored generators.
      * @param index int; index of the stored generator
      * @param frequency double; new frequency (or probability)
      * @return this
      * @throws ProbabilityException when the frequency (or probability) &lt; 0, or when index is &lt; 0 or &gt;= size
      */
     public final Distribution<O> modifyFrequency(final int index, final double frequency) throws ProbabilityException
     {
         return set(index, new FrequencyAndObject<O>(frequency, this.generators.get(index).getObject()));
     }
 
     /**
      * Empty the internally stored list.
      * @return this
      */
     public final Distribution<O> clear()
     {
         this.generators.clear();
         return this;
     }
 
     /**
      * Retrieve one of the internally stored generators.
      * @param index int; the index of the FrequencyAndObject to retrieve
      * @return FrequencyAndObject&lt;O&gt;; the generator stored at position <cite>index</cite>
      * @throws ProbabilityException when index &lt; 0 or &gt;= size()
      */
     public final FrequencyAndObject<O> get(final int index) throws ProbabilityException
     {
         try
         {
             return this.generators.get(index);
         }
         catch (IndexOutOfBoundsException ie)
         {
             throw new ProbabilityException("Index out of bounds for set operation, index=" + index);
         }
     }
 
     /**
      * Report the number of generators.
      * @return int; the number of generators
      */
     public final int size()
     {
         return this.generators.size();
     }
 
     /** {@inheritDoc} */
     @Override
     public final int hashCode()
     {
         final int prime = 31;
         int result = 1;
         long temp;
         temp = Double.doubleToLongBits(this.cumulativeTotal);
         result = prime * result + (int) (temp ^ (temp >>> 32));
         result = prime * result + ((this.generators == null) ? 0 : this.generators.hashCode());
         result = prime * result + ((this.random == null) ? 0 : this.random.hashCode());
         return result;
     }
 
     /** {@inheritDoc} */
     @Override
     @SuppressWarnings("checkstyle:needbraces")
     public final boolean equals(final Object obj)
     {
         if (this == obj)
             return true;
         if (obj == null)
             return false;
         if (getClass() != obj.getClass())
             return false;
         Distribution<?> other = (Distribution<?>) obj;
         if (Double.doubleToLongBits(this.cumulativeTotal) != Double.doubleToLongBits(other.cumulativeTotal))
             return false;
         if (this.generators == null)
         {
             if (other.generators != null)
                 return false;
         }
         else if (!this.generators.equals(other.generators))
             return false;
         if (this.random == null)
         {
             if (other.random != null)
                 return false;
         }
         else if (!this.random.equals(other.random))
             return false;
         return true;
     }
 
     /** {@inheritDoc} */
     public final String toString()
     {
         StringBuilder result = new StringBuilder();
         result.append("Distribution [");
         String separator = "";
         for (FrequencyAndObject<O> fAndO : this.generators)
         {
             result.append(separator + fAndO.getFrequency() + "->" + fAndO.getObject());
             separator = ", ";
         }
         result.append(']');
         return result.toString();
     }
 
     /**
      * Immutable storage for a frequency (or probability) plus a Generator.
      * <p>
      * Copyright (c) 2013-2015 Delft University of Technology, PO Box 5, 2600 AA, Delft, the Netherlands.<br>
      * All rights reserved. <br>
      * BSD-style license. See <a href="http://opentrafficsim.org/node/13">OpenTrafficSim License</a>.
      * <p>
      * @version $Revision$, $LastChangedDate$, by $Author$, initial version Mar 1, 2016 <br>
      * @author <a href="http://www.tbm.tudelft.nl/averbraeck">Alexander Verbraeck</a>
      * @author <a href="http://www.tudelft.nl/pknoppers">Peter Knoppers</a>
      * @param <O> Type of the object returned by the draw method
      */
     public static class FrequencyAndObject<O>
     {
         /** Frequency (or probability) of an object. */
         private final double frequency;
 
         /** The object. */
         private final O object;
 
         /**
          * Construct a new FrequencyAndObject instance.
          * @param frequency double; the (<b>not cumulative</b>) frequency (or probability) of the <cite>generatingObject</cite>
          * @param object O; an object
          */
         public FrequencyAndObject(final double frequency, final O object)
         {
             this.frequency = frequency;
             this.object = object;
         }
 
         /**
          * Retrieve the frequency (or probability) of this FrequencyAndObject.
          * @return double; the frequency (or probability) of this FrequencyAndObject
          */
         public final double getFrequency()
         {
             return this.frequency;
         }
 
         /**
          * Call the draw method of the generatingObject and return its result.
          * @return O; the result of a call to the draw method of the generatingObject
          */
         public final O getObject()
         {
             return this.object;
         }
 
         /** {@inheritDoc} */
         @Override
         public final int hashCode()
         {
             final int prime = 31;
             int result = 1;
             long temp;
             temp = Double.doubleToLongBits(this.frequency);
             result = prime * result + (int) (temp ^ (temp >>> 32));
             result = prime * result + ((this.object == null) ? 0 : this.object.hashCode());
             return result;
         }
 
         /** {@inheritDoc} */
         @Override
         @SuppressWarnings("checkstyle:needbraces")
         public final boolean equals(final Object obj)
         {
             if (this == obj)
                 return true;
             if (obj == null)
                 return false;
             if (getClass() != obj.getClass())
                 return false;
             FrequencyAndObject<?> other = (FrequencyAndObject<?>) obj;
             if (Double.doubleToLongBits(this.frequency) != Double.doubleToLongBits(other.frequency))
                 return false;
             if (this.object == null)
             {
                 if (other.object != null)
                     return false;
             }
             else if (!this.object.equals(other.object))
                 return false;
             return true;
         }
 
         /** {@inheritDoc} */
         @Override
         public final String toString()
         {
             return "FrequencyAndObject [frequency=" + this.frequency + ", object=" + this.object + "]";
         }
         
     }
 
 }