+++ /dev/null
-/**
- * Copyright (c) 2009, the JUNG Project and the Regents of the University
- * of California
- * All rights reserved.
- *
- * This software is open-source under the BSD license; see either
- * "license.txt" or
- * http://jung.sourceforge.net/license.txt for a description.
- * Created on Jan 8, 2009
- *
- */
-package edu.uci.ics.jung.algorithms.util;
-
-import java.util.ArrayList;
-import java.util.LinkedList;
-import java.util.List;
-import java.util.Map;
-import java.util.Queue;
-import java.util.Random;
-
-/**
- * Selects items according to their probability in an arbitrary probability
- * distribution. The distribution is specified by a {@code Map} from
- * items (of type {@code T}) to weights of type {@code Number}, supplied
- * to the constructor; these weights are normalized internally to act as
- * probabilities.
- *
- * <p>This implementation selects items in O(1) time, and requires O(n) space.
- *
- * @author Joshua O'Madadhain
- */
-public class WeightedChoice<T>
-{
- private List<ItemPair> item_pairs;
- private Random random;
-
- /**
- * The default minimum value that is treated as a valid probability
- * (as opposed to rounding error from floating-point operations).
- */
- public static final double DEFAULT_THRESHOLD = 0.00000000001;
-
- /**
- * Equivalent to {@code this(item_weights, new Random(), DEFAULT_THRESHOLD)}.
- * @param item_weights
- */
- public WeightedChoice(Map<T, ? extends Number> item_weights)
- {
- this(item_weights, new Random(), DEFAULT_THRESHOLD);
- }
-
- /**
- * Equivalent to {@code this(item_weights, new Random(), threshold)}.
- */
- public WeightedChoice(Map<T, ? extends Number> item_weights, double threshold)
- {
- this(item_weights, new Random(), threshold);
- }
-
- /**
- * Equivalent to {@code this(item_weights, random, DEFAULT_THRESHOLD)}.
- */
- public WeightedChoice(Map<T, ? extends Number> item_weights, Random random)
- {
- this(item_weights, random, DEFAULT_THRESHOLD);
- }
-
- /**
- * Creates an instance with the specified mapping from items to weights,
- * random number generator, and threshold value.
- *
- * <p>The mapping defines the weight for each item to be selected; this
- * will be proportional to the probability of its selection.
- * <p>The random number generator specifies the mechanism which will be
- * used to provide uniform integer and double values.
- * <p>The threshold indicates default minimum value that is treated as a valid
- * probability (as opposed to rounding error from floating-point operations).
- */
- public WeightedChoice(Map<T, ? extends Number> item_weights, Random random,
- double threshold)
- {
- if (item_weights.isEmpty())
- throw new IllegalArgumentException("Item weights must be non-empty");
-
- int item_count = item_weights.size();
- item_pairs = new ArrayList<ItemPair>(item_count);
-
- double sum = 0;
- for (Map.Entry<T, ? extends Number> entry : item_weights.entrySet())
- {
- double value = entry.getValue().doubleValue();
- if (value <= 0)
- throw new IllegalArgumentException("Weights must be > 0");
- sum += value;
- }
- double bucket_weight = 1.0 / item_weights.size();
-
- Queue<ItemPair> light_weights = new LinkedList<ItemPair>();
- Queue<ItemPair> heavy_weights = new LinkedList<ItemPair>();
- for (Map.Entry<T, ? extends Number> entry : item_weights.entrySet())
- {
- double value = entry.getValue().doubleValue() / sum;
- enqueueItem(entry.getKey(), value, bucket_weight, light_weights, heavy_weights);
- }
-
- // repeat until both queues empty
- while (!heavy_weights.isEmpty() || !light_weights.isEmpty())
- {
- ItemPair heavy_item = heavy_weights.poll();
- ItemPair light_item = light_weights.poll();
- double light_weight = 0;
- T light = null;
- T heavy = null;
- if (light_item != null)
- {
- light_weight = light_item.weight;
- light = light_item.light;
- }
- if (heavy_item != null)
- {
- heavy = heavy_item.heavy;
- // put the 'left over' weight from the heavy item--what wasn't
- // needed to make up the difference between the light weight and
- // 1/n--back in the appropriate queue
- double new_weight = heavy_item.weight - (bucket_weight - light_weight);
- if (new_weight > threshold)
- enqueueItem(heavy, new_weight, bucket_weight, light_weights, heavy_weights);
- }
- light_weight *= item_count;
-
- item_pairs.add(new ItemPair(light, heavy, light_weight));
- }
-
- this.random = random;
- }
-
- /**
- * Adds key/value to the appropriate queue. Keys with values less than
- * the threshold get added to {@code light_weights}, all others get added
- * to {@code heavy_weights}.
- */
- private void enqueueItem(T key, double value, double threshold,
- Queue<ItemPair> light_weights, Queue<ItemPair> heavy_weights)
- {
- if (value < threshold)
- light_weights.offer(new ItemPair(key, null, value));
- else
- heavy_weights.offer(new ItemPair(null, key, value));
- }
-
- /**
- * Sets the seed used by the internal random number generator.
- */
- public void setRandomSeed(long seed)
- {
- this.random.setSeed(seed);
- }
-
- /**
- * Retrieves an item with probability proportional to its weight in the
- * {@code Map} provided in the input.
- */
- public T nextItem()
- {
- ItemPair item_pair = item_pairs.get(random.nextInt(item_pairs.size()));
- if (random.nextDouble() < item_pair.weight)
- return item_pair.light;
- return item_pair.heavy;
- }
-
- /**
- * Manages light object/heavy object/light conditional probability tuples.
- */
- private class ItemPair
- {
- T light;
- T heavy;
- double weight;
-
- private ItemPair(T light, T heavy, double weight)
- {
- this.light = light;
- this.heavy = heavy;
- this.weight = weight;
- }
-
- @Override
- public String toString()
- {
- return String.format("[L:%s, H:%s, %.3f]", light, heavy, weight);
- }
- }
-}
Code Review / controller.git / blobdiff