content: /*
   * 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.cassandra.simulator;
  
  import java.lang.reflect.Array;
  import java.util.Arrays;
  import java.util.List;
  import java.util.Map;
  import java.util.Random;
  import java.util.Set;
  import java.util.function.IntSupplier;
  import java.util.function.LongSupplier;
  import java.util.stream.IntStream;
  import java.util.stream.LongStream;
  
  import com.google.common.collect.Iterators;
  
  import org.apache.cassandra.utils.Shared;
  
  import static org.apache.cassandra.utils.Shared.Scope.SIMULATION;
  
  @Shared(scope = SIMULATION)
  public interface RandomSource
  {
      public static class Choices<T>
      {
          final float[] cumulativeProbabilities;
          public final T[] options;
  
          private Choices(float[] cumulativeProbabilities, T[] options)
          {
              this.cumulativeProbabilities = cumulativeProbabilities;
              this.options = options;
          }
  
          public T choose(RandomSource random)
          {
              return choose(random.uniformFloat());
          }
  
          public T choose(accord.utils.RandomSource random)
          {
              return choose(random.nextFloat());
          }
  
          private T choose(float choose)
          {
              if (options.length == 0)
                  return null;
  
              int i = Arrays.binarySearch(cumulativeProbabilities, choose);
  
              if (i < 0) i = -1 - i;
              return options[i];
          }
  
          public Choices<T> without(T option)
          {
              for (int i = 0 ; i < options.length ; ++i)
              {
                  if (option.equals(options[i]))
                  {
                      float[] prob = new float[cumulativeProbabilities.length - 1];
                      T[] opts = (T[]) Array.newInstance(options.getClass().getComponentType(), options.length - 1);
                      System.arraycopy(cumulativeProbabilities, 0, prob, 0, i);
                      System.arraycopy(cumulativeProbabilities, i + 1, prob, i, this.options.length - (i + 1));
                      System.arraycopy(options, 0, opts, 0, i);
                      System.arraycopy(options, i + 1, opts, i, options.length - (i + 1));
                      for (int j = prob.length - 1 ; j > 1 ; --j)
                          prob[j] -= prob[j - 1];
                      return build(prob, opts);
                  }
              }
              return this;
          }
  
          private static float[] randomCumulativeProbabilities(RandomSource random, int count)
          {
              float[] nonCumulativeProbabilities = new float[count];
              for (int i = 0 ; i < count ; ++i)
                  nonCumulativeProbabilities[i] = random.uniformFloat();
              return cumulativeProbabilities(nonCumulativeProbabilities);
          }
  
          private static float[] cumulativeProbabilities(float[] nonCumulativeProbabilities)
          {
              int count = nonCumulativeProbabilities.length;
              if (count == 0)
                  return new float[0];
  
              float[] result = new float[nonCumulativeProbabilities.length];
              float sum = 0;
              for (int i = 0 ; i < count ; ++i)
                  result[i] = sum += nonCumulativeProbabilities[i];
              result[result.length - 1] = 1.0f;
              for (int i = 0 ; i < count - 1 ; ++i)
                  result[i] = result[i] /= sum;
              return result;
          }
  
          public static <T> Choices<T> random(RandomSource random, T[] options)
          {
              return new Choices<>(randomCumulativeProbabilities(random, options.length), options);
          }
  
          public static <T> Choices<T> random(RandomSource random, T[] options, Map<T, float[]> bounds)
          {
              float[] nonCumulativeProbabilities = new float[options.length];
              for (int i = 0 ; i < options.length ; ++i)
              {
                  float[] minmax = bounds.get(options[i]);
                  float uniform = random.uniformFloat();
                  nonCumulativeProbabilities[i] = minmax == null ? uniform : minmax[0] + (uniform * (minmax[1] - minmax[0]));
              }
              return new Choices<>(cumulativeProbabilities(nonCumulativeProbabilities), options);
          }
  
          public static <T> Choices<T> build(float[] nonCumulativeProbabilities, T[] options)
          {
              if (nonCumulativeProbabilities.length != options.length)
                  throw new IllegalArgumentException();
              return new Choices<>(cumulativeProbabilities(nonCumulativeProbabilities), options);
          }
  
          public static <T> Choices<T> uniform(T ... options)
          {
              float[] nonCumulativeProbabilities = new float[options.length];
              Arrays.fill(nonCumulativeProbabilities, 1f / options.length);
              return new Choices<>(cumulativeProbabilities(nonCumulativeProbabilities), options);
          }
  
          public static <T> T choose(RandomSource rs, Set<T> set)
          {
              return choose(rs.uniform(0, set.size()), set);
          }
  
          public static <T> T choose(accord.utils.RandomSource rs, Set<T> set)
          {
              return choose(rs.nextInt(set.size()), set);
          }
  
          private static <T> T choose(int i, Set<T> set)
          {
              return Iterators.get(set.iterator(), i);
          }
  
          public static <T> T choose(RandomSource rs, List<T> list)
          {
              return list.get(rs.uniform(0, list.size()));
          }
  
          public static <T> T choose(accord.utils.RandomSource rs, List<T> list)
          {
              return list.get(rs.nextInt(list.size()));
          }
  
          public static <T> T choose(RandomSource rs, T ... array)
          {
              return array[rs.uniform(0, array.length)];
          }
  
          public static <T> T choose(accord.utils.RandomSource rs, T ... array)
          {
              return array[rs.nextInt(array.length)];
          }
      }
  
      public static abstract class Abstract implements RandomSource
      {
          public abstract float uniformFloat();
          public abstract int uniform(int min, int max);
          public abstract long uniform(long min, long max);
  
          public LongSupplier uniqueUniformSupplier(long min, long max)
          {
              return uniqueUniformStream(min, max).iterator()::nextLong;
          }
  
          public LongStream uniqueUniformStream(long min, long max)
          {
              return uniformStream(min, max).distinct();
          }
  
          public LongStream uniformStream(long min, long max)
          {
              return LongStream.generate(() -> uniform(min, max));
          }
  
          public LongSupplier uniformSupplier(long min, long max)
          {
              return () -> uniform(min, max);
          }
  
          public IntSupplier uniqueUniformSupplier(int min, int max)
          {
              return uniqueUniformStream(min, max).iterator()::nextInt;
          }
  
          public IntStream uniqueUniformStream(int min, int max)
          {
              return uniformStream(min, max).distinct();
          }
  
          public IntStream uniformStream(int min, int max)
          {
              return IntStream.generate(() -> uniform(min, max));
          }
  
          public boolean decide(float chance)
          {
              return uniformFloat() < chance;
          }
  
          public int log2uniform(int min, int max)
          {
              return (int) log2uniform((long) min, max);
          }
  
          public long log2uniform(long min, long max)
          {
              return qlog2uniform(min, max, 64);
          }
  
          public long qlog2uniform(long min, long max, int quantizations)
          {
              return min + log2uniform(max - min, quantizations);
          }
  
          private long log2uniform(long max, int quantizations)
          {
              int maxBits = 64 - Long.numberOfLeadingZeros(max - 1);
              if (maxBits == 0)
                  return 0;
  
              long min;
              if (maxBits <= quantizations)
              {
                  int bits = uniform(0, maxBits);
                  min = 1L << (bits - 1);
                  max = Math.min(max, min * 2);
              }
              else
              {
                  int bitsPerRange = (maxBits / quantizations);
                  int i = uniform(0, quantizations);
                  min = 1L << (i * bitsPerRange);
                  max = Math.min(max, 1L << ((i + 1) * bitsPerRange));
              }
  
              return uniform(min, max);
          }
  
          public float qlog2uniformFloat(int quantizations)
          {
              return qlog2uniform(0, 1 << 24, quantizations) / (float)(1 << 24);
          }
      }
  
      public static class Default extends Abstract
      {
          private final Random random = new Random(0);
  
          public float uniformFloat() { return random.nextFloat(); }
  
          @Override
          public double uniformDouble()
          {
              return random.nextDouble();
          }
  
          public int uniform(int min, int max)
          {
              int delta = max - min;
              if (delta > 1) return min + random.nextInt(max - min);
              if (delta == 1) return min;
              if (min >= max)
                  throw new IllegalArgumentException(String.format("Min (%s) should be less than max (%d).", min, max));
              return (int)uniform(min, (long)max);
          }
  
          public long uniform(long min, long max)
          {
              if (min >= max) throw new IllegalArgumentException();
  
              long delta = max - min;
              if (delta == 1) return min;
              if (delta == Long.MIN_VALUE && max == Long.MAX_VALUE) return random.nextLong();
              if (delta < 0) return random.longs(min, max).iterator().nextLong();
              if (delta <= Integer.MAX_VALUE) return min + uniform(0, (int) delta);
  
              long result = min + 1 == max ? min : min + ((random.nextLong() & 0x7fffffff) % (max - min));
              assert result >= min && result < max;
              return result;
          }
  
          public void reset(long seed)
          {
              random.setSeed(seed);
          }
  
          public long reset()
          {
              long seed = random.nextLong();
              reset(seed);
              return seed;
          }
      }
  
      IntStream uniqueUniformStream(int min, int max);
  
      LongSupplier uniqueUniformSupplier(long min, long max);
      LongStream uniqueUniformStream(long min, long max);
      LongStream uniformStream(long min, long max);
  
      // [min...max)
      int uniform(int min, int max);
      // [min...max)
      long uniform(long min, long max);
  
      /**
       * Select a number in the range [min, max), with a power of two in the range [0, max-min)
       * selected uniformly and a uniform value less than this power of two added to it
       */
      int log2uniform(int min, int max);
      long log2uniform(long min, long max);
  
      /**
       * Select a number in the range [min, max), with the range being split into
       * {@code quantizations} adjacent powers of two, a range being select from these
       * with uniform probability, and the value within that range being selected uniformly
       */
      long qlog2uniform(long min, long max, int quantizations);
  
      float uniformFloat();
  
      /**
       * Select a number in the range [0, 1), with the range being split into
       * {@code quantizations} adjacent powers of two; a range being select from these
       * with uniform probability, and the value within that range being selected uniformly
       *
       * This is used to distribute behavioural toggles more extremely between different runs of the simulator.
       */
      float qlog2uniformFloat(int quantizations);
      double uniformDouble();
  
      // options should be cumulative probability in range [0..1]
      boolean decide(float chance);
  
      void reset(long seed);
      long reset();
  }
  
  