001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  You may obtain a copy of the License at
008 *
009 *      http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017
018package org.apache.commons.rng.sampling;
019
020import java.util.List;
021import java.util.Map;
022import java.util.ArrayList;
023
024import org.apache.commons.rng.UniformRandomProvider;
025import org.apache.commons.rng.sampling.distribution.GuideTableDiscreteSampler;
026import org.apache.commons.rng.sampling.distribution.SharedStateDiscreteSampler;
027
028/**
029 * Sampling from a collection of items with user-defined
030 * <a href="http://en.wikipedia.org/wiki/Probability_distribution#Discrete_probability_distribution">
031 * probabilities</a>.
032 * Note that if all unique items are assigned the same probability,
033 * it is much more efficient to use {@link CollectionSampler}.
034 *
035 * <p>Sampling uses {@link UniformRandomProvider#nextDouble()}.</p>
036 *
037 * @param <T> Type of items in the collection.
038 *
039 * @since 1.1
040 */
041public class DiscreteProbabilityCollectionSampler<T>
042    implements SharedStateSampler<DiscreteProbabilityCollectionSampler<T>> {
043    /** The error message for an empty collection. */
044    private static final String EMPTY_COLLECTION = "Empty collection";
045    /** Collection to be sampled from. */
046    private final List<T> items;
047    /** Sampler for the probabilities. */
048    private final SharedStateDiscreteSampler sampler;
049
050    /**
051     * Creates a sampler.
052     *
053     * @param rng Generator of uniformly distributed random numbers.
054     * @param collection Collection to be sampled, with the probabilities
055     * associated to each of its items.
056     * A (shallow) copy of the items will be stored in the created instance.
057     * The probabilities must be non-negative, but zero values are allowed
058     * and their sum does not have to equal one (input will be normalized
059     * to make the probabilities sum to one).
060     * @throws IllegalArgumentException if {@code collection} is empty, a
061     * probability is negative, infinite or {@code NaN}, or the sum of all
062     * probabilities is not strictly positive.
063     */
064    public DiscreteProbabilityCollectionSampler(UniformRandomProvider rng,
065                                                Map<T, Double> collection) {
066        if (collection.isEmpty()) {
067            throw new IllegalArgumentException(EMPTY_COLLECTION);
068        }
069
070        // Extract the items and probabilities
071        final int size = collection.size();
072        items = new ArrayList<T>(size);
073        final double[] probabilities = new double[size];
074
075        int count = 0;
076        for (final Map.Entry<T, Double> e : collection.entrySet()) {
077            items.add(e.getKey());
078            probabilities[count++] = e.getValue();
079        }
080
081        // Delegate sampling
082        sampler = createSampler(rng, probabilities);
083    }
084
085    /**
086     * Creates a sampler.
087     *
088     * @param rng Generator of uniformly distributed random numbers.
089     * @param collection Collection to be sampled.
090     * A (shallow) copy of the items will be stored in the created instance.
091     * @param probabilities Probability associated to each item of the
092     * {@code collection}.
093     * The probabilities must be non-negative, but zero values are allowed
094     * and their sum does not have to equal one (input will be normalized
095     * to make the probabilities sum to one).
096     * @throws IllegalArgumentException if {@code collection} is empty or
097     * a probability is negative, infinite or {@code NaN}, or if the number
098     * of items in the {@code collection} is not equal to the number of
099     * provided {@code probabilities}.
100     */
101    public DiscreteProbabilityCollectionSampler(UniformRandomProvider rng,
102                                                List<T> collection,
103                                                double[] probabilities) {
104        if (collection.isEmpty()) {
105            throw new IllegalArgumentException(EMPTY_COLLECTION);
106        }
107        final int len = probabilities.length;
108        if (len != collection.size()) {
109            throw new IllegalArgumentException("Size mismatch: " +
110                                               len + " != " +
111                                               collection.size());
112        }
113        // Shallow copy the list
114        items = new ArrayList<T>(collection);
115        // Delegate sampling
116        sampler = createSampler(rng, probabilities);
117    }
118
119    /**
120     * @param rng Generator of uniformly distributed random numbers.
121     * @param source Source to copy.
122     */
123    private DiscreteProbabilityCollectionSampler(UniformRandomProvider rng,
124                                                 DiscreteProbabilityCollectionSampler<T> source) {
125        this.items = source.items;
126        this.sampler = source.sampler.withUniformRandomProvider(rng);
127    }
128
129    /**
130     * Picks one of the items from the collection passed to the constructor.
131     *
132     * @return a random sample.
133     */
134    public T sample() {
135        return items.get(sampler.sample());
136    }
137
138    /**
139     * {@inheritDoc}
140     *
141     * @since 1.3
142     */
143    @Override
144    public DiscreteProbabilityCollectionSampler<T> withUniformRandomProvider(UniformRandomProvider rng) {
145        return new DiscreteProbabilityCollectionSampler<T>(rng, this);
146    }
147
148    /**
149     * Creates the sampler of the enumerated probability distribution.
150     *
151     * @param rng Generator of uniformly distributed random numbers.
152     * @param probabilities Probability associated to each item.
153     * @return the sampler
154     */
155    private static SharedStateDiscreteSampler createSampler(UniformRandomProvider rng,
156                                                            double[] probabilities) {
157        return GuideTableDiscreteSampler.of(rng, probabilities);
158    }
159}