<commit_before>/*
 * Copyright 2015 <NAME> <https://github.com/ogregoire>.
 *
 * Licensed 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 be.fror.common.collection;

import static com.google.common.base.Preconditions.checkArgument;
import static com.google.common.base.Preconditions.checkNotNull;
import static java.util.Spliterator.ORDERED;
import static java.util.Spliterators.spliteratorUnknownSize;

import com.google.common.collect.Multiset;

import java.util.Arrays;
import java.util.Collection;
import java.util.Iterator;
import java.util.Random;
import java.util.Set;
import java.util.stream.Stream;
import java.util.stream.StreamSupport;

import javax.annotation.concurrent.ThreadSafe;

/**
 *
 * @author <NAME> &lt;https://github.com/ogregoire&gt;
 * @param <T>
 */
@ThreadSafe
public final class RandomSelector<T> {

  /**
   * Creates a new random selector based on a uniform distribution.
   *
   * @param <T>
   * @param collection
   * @return
   */
  public static <T> RandomSelector uniform(final Collection<T> collection) {
    checkNotNull(collection, "collection must not be null");
    checkArgument(!collection.isEmpty(), "collection must not be empty");

    final int size = collection.size();
    final T[] elements = collection.toArray((T[]) new Object[size]);

    return new RandomSelector<>(elements, (r) -> r.nextInt(size));
  }

  /**
   * Creates a new random selector based on a weighted distribution.
   *
   * @param <T>
   * @param probabilities
   * @return
   */
  public static <T> RandomSelector weighted(final Multiset<T> probabilities) {
    checkNotNull(probabilities, "probabilities must not be null");
    checkArgument(!probabilities.isEmpty(), "probabilities must not be empty");

    final Set<Multiset.Entry<T>> entries = probabilities.entrySet();
    final double totalSize = probabilities.size();
    final int entriesSize = entries.size();
    final T[] elements = (T[]) new Object[entriesSize];
    final double[] discreteProbabilities = new double[entriesSize];
    int i = 0;
    for (Multiset.Entry<T> entry : entries) {
      elements[i] = entry.getElement();
      discreteProbabilities[i] = entry.getCount() / totalSize;
      i++;
    }
    return new RandomSelector<>(elements, new RandomWeightedSelection(discreteProbabilities));
  }

  private final T[] elements;
  private final Selection selection;

  RandomSelector(final T[] elements, final Selection selection) {
    this.elements = elements;
    this.selection = selection;
  }

  /**
   * Returns the next element using <tt>random</tt>.
   *
   * @param random
   * @return
   */
  public T next(final Random random) {
    return this.elements[this.selection.next(random)];
  }

  /**
   * Returns a stream of elements using <tt>random</tt>. The stream must use a terminal operation to
   * become closed and free the resources it's been using.
   *
   * <p>
   * Even though this instance is thread-safe and for performance reasons, it is recommended to use
   * a different stream per thread given that Random has performance drawbacks in multi-threaded
   * environments.
   *
   * @param random
   * @return
   */
  public Stream<T> stream(final Random random) {
    checkNotNull(random, "random must not be null");
    return StreamSupport.stream(spliteratorUnknownSize(new BaseIterator(random), ORDERED), false);
  }

  private class BaseIterator implements Iterator<T> {

    private final Random random;

    BaseIterator(final Random random) {
      this.random = random;
    }

    @Override
    public boolean hasNext() {
      return true;
    }

    @Override
    public T next() {
      return RandomSelector.this.next(this.random);
    }
  }

  static interface Selection {

    int next(final Random random);
  }

  private static class RandomWeightedSelection implements Selection {
    // Alias method implementation O(1)
    // using Vose's algorithm to initialize O(n)

    private final double[] probabilities;
    private final int[] alias;

    RandomWeightedSelection(double[] probabilities) {
      final int size = probabilities.length;

      // No defensive copy yet.

      final double average = 1d / size;
      final int[] small = new int[size];
      int smallSize = 0;
      final int[] large = new int[size];
      int largeSize = 0;

      for (int i = 0; i < size; i++) {
        if (probabilities[i] < average) {
          small[smallSize++] = i;
        } else {
          large[largeSize++] = i;
        }
      }

      double[] pr = new double[size];
      int[] al = new int[size];
      this.probabilities = pr;
      this.alias = al;

      while (largeSize != 0 && smallSize != 0) {
        final int less = small[--smallSize];
        final int more = large[--largeSize];
        pr[less] = probabilities[less] * size;
        al[less] = more;
        probabilities[more] += probabilities[less] - average;
        if (probabilities[more] < average) {
          small[smallSize++] = more;
        } else {
          large[largeSize++] = more;
        }
      }
      while (smallSize != 0) {
        pr[small[--smallSize]] = 1d;
      }
      while (largeSize != 0) {
        pr[large[--largeSize]] = 1d;
      }
    }

    @Override
    public int next(final Random random) {
      final int column = random.nextInt(this.probabilities.length);
      return random.nextDouble() < this.probabilities[column]
          ? column
          : this.alias[column];
    }
  }
}
<commit_msg>Fix signatures and documentation<commit_after>/*
 * Copyright 2015 <NAME> <https://github.com/ogregoire>.
 *
 * Licensed 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 be.fror.common.collection;

import static com.google.common.base.Preconditions.checkArgument;
import static com.google.common.base.Preconditions.checkNotNull;
import static java.util.Spliterator.ORDERED;
import static java.util.Spliterators.spliteratorUnknownSize;

import com.google.common.collect.Multiset;

import java.util.Collection;
import java.util.Iterator;
import java.util.Random;
import java.util.Set;
import java.util.stream.Stream;
import java.util.stream.StreamSupport;

import javax.annotation.concurrent.ThreadSafe;

/**
 * A tool to randomly select elements from collections.
 *
 * <p>
 * Example usages:
 *
 * <pre><code>
 * Random random = ...
 * ImmutableMultiset&lt;String&gt; weightedStrings = ImmutableMultiset.&lt;String&gt;builder()
 *   .addCopies("a", 4)
 *   .addCopies("b", 3)
 *   .addCopies("c", 12)
 *   .addCopies("d", 1)
 *   .build();
 * RandomSelector&lt;String&gt; selector = RandomSelector.weighted(weightedElements);
 * List&lt;String&gt; selection = new ArrayList&lt;&gt;();
 * for (int i = 0; i &lt; 10; i++) {
 *   selection.add(selector.next(random));
 * }
 * </code></pre>
 *
 *
 * @author <NAME> &lt;https://github.com/ogregoire&gt;
 * @param <T>
 */
@ThreadSafe
public final class RandomSelector<T> {

  /**
   * Creates a new random selector based on a uniform distribution.
   *
   * @param <T>
   * @param collection
   * @return
   * @throws IllegalArgumentException if <tt>collection</tt> is empty.
   */
  public static <T> RandomSelector uniform(final Collection<T> collection)
      throws IllegalArgumentException {
    checkNotNull(collection, "collection must not be null");
    checkArgument(!collection.isEmpty(), "collection must not be empty");

    final int size = collection.size();
    final T[] elements = collection.toArray((T[]) new Object[size]);

    return new RandomSelector<>(elements, (r) -> r.nextInt(size));
  }

  /**
   * Creates a new random selector based on a weighted distribution.
   *
   * @param <T>
   * @param probabilities
   * @return
   * @throws IllegalArgumentException if <tt>probabilities</tt> is empty.
   */
  public static <T> RandomSelector weighted(final Multiset<T> probabilities)
      throws IllegalArgumentException {
    checkNotNull(probabilities, "probabilities must not be null");
    checkArgument(!probabilities.isEmpty(), "probabilities must not be empty");

    final Set<Multiset.Entry<T>> entries = probabilities.entrySet();
    final double totalSize = probabilities.size();
    final int entriesSize = entries.size();
    final T[] elements = (T[]) new Object[entriesSize];
    final double[] discreteProbabilities = new double[entriesSize];
    int i = 0;
    for (final Multiset.Entry<T> entry : entries) {
      elements[i] = entry.getElement();
      discreteProbabilities[i] = entry.getCount() / totalSize;
      i++;
    }
    return new RandomSelector<>(elements, new RandomWeightedSelection(discreteProbabilities));
  }

  private final T[] elements;
  private final Selection selection;

  RandomSelector(final T[] elements, final Selection selection) {
    this.elements = elements;
    this.selection = selection;
  }

  /**
   * Returns the next element using <tt>random</tt>.
   *
   * @param random
   * @return
   */
  public T next(final Random random) {
    return this.elements[this.selection.next(random)];
  }

  /**
   * Returns a stream of elements using <tt>random</tt>. The stream must use a terminal operation to
   * become closed and free the resources it's been using.
   *
   * <p>
   * Even though this instance is thread-safe and for performance reasons, it is recommended to use
   * a different stream per thread given that Random has performance drawbacks in multi-threaded
   * environments.
   *
   * @param random
   * @return
   */
  public Stream<T> stream(final Random random) {
    checkNotNull(random, "random must not be null");
    return StreamSupport.stream(spliteratorUnknownSize(new BaseIterator(random), ORDERED), false);
  }

  private class BaseIterator implements Iterator<T> {

    private final Random random;

    BaseIterator(final Random random) {
      this.random = random;
    }

    @Override
    public boolean hasNext() {
      return true;
    }

    @Override
    public T next() {
      return RandomSelector.this.next(this.random);
    }
  }

  static interface Selection {

    int next(final Random random);
  }

  private static class RandomWeightedSelection implements Selection {
    // Alias method implementation O(1)
    // using Vose's algorithm to initialize O(n)

    private final double[] probabilities;
    private final int[] alias;

    RandomWeightedSelection(final double[] probabilities) {
      final int size = probabilities.length;

      final double average = 1d / size;
      final int[] small = new int[size];
      int smallSize = 0;
      final int[] large = new int[size];
      int largeSize = 0;

      for (int i = 0; i < size; i++) {
        if (probabilities[i] < average) {
          small[smallSize++] = i;
        } else {
          large[largeSize++] = i;
        }
      }

      final double[] pr = new double[size];
      final int[] al = new int[size];
      this.probabilities = pr;
      this.alias = al;

      while (largeSize != 0 && smallSize != 0) {
        final int less = small[--smallSize];
        final int more = large[--largeSize];
        pr[less] = probabilities[less] * size;
        al[less] = more;
        probabilities[more] += probabilities[less] - average;
        if (probabilities[more] < average) {
          small[smallSize++] = more;
        } else {
          large[largeSize++] = more;
        }
      }
      while (smallSize != 0) {
        pr[small[--smallSize]] = 1d;
      }
      while (largeSize != 0) {
        pr[large[--largeSize]] = 1d;
      }
    }

    @Override
    public int next(final Random random) {
      final int column = random.nextInt(this.probabilities.length);
      return random.nextDouble() < this.probabilities[column]
          ? column
          : this.alias[column];
    }
  }
}

{'fraction_non_alphanumeric': 0.11113650213284583, 'fraction_numerical': 0.003656307129798903, 'mean_word_length': 2.71505376344086, 'pattern_counts': {'":': 0, '<': 66, '<?xml version=': 0, '>': 60, 'https://': 4, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '7587810', 'n_tokens_mistral': 3796, 'n_tokens_neox': 3551, 'n_words': 1110}