/* * __ .__ .__ ._____. * _/ |_ _______ __|__| ____ | | |__\_ |__ ______ * \ __\/ _ \ \/ / |/ ___\| | | || __ \ / ___/ * | | ( <_> > <| \ \___| |_| || \_\ \\___ \ * |__| \____/__/\_ \__|\___ >____/__||___ /____ > * \/ \/ \/ \/ * * Copyright (c) 2006-2011 Karsten Schmidt * * This library is free software; you can redistribute it and/or * modify it under the terms of the GNU Lesser General Public * License as published by the Free Software Foundation; either * version 2.1 of the License, or (at your option) any later version. * * http://creativecommons.org/licenses/LGPL/2.1/ * * This library is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public * License along with this library; if not, write to the Free Software * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA */ package toxi.util.datatypes; import java.util.ArrayList; import java.util.List; import toxi.math.MathUtils; /** * This class provides a generic random-weight distribution of arbitary objects. * Add elements with their weight to the set and then use the * {@link #getRandom()} method to retrieve objects. The frequency of returned * elements is based on their relative weight. This makes it easy to provide * biased preferences. * * http://www.electricmonk.nl/log/2009/12/23/weighted-random-distribution/ * @param <T> */ public class WeightedRandomSet<T> { /** * */ protected List<WeightedRandomEntry<T>> elements = new ArrayList<>(); /** * */ protected int totalWeight; /** * Add a new element of type T to the set. * * @param item * @param weight * @return itself */ public WeightedRandomSet<T> add(T item, int weight) { WeightedRandomEntry<T> e = new WeightedRandomEntry<>(item, weight); int num = elements.size(); boolean isInserted = false; if (num > 0) { for (int i = 0; i < num; i++) { if (weight < elements.get(i).weight) { elements.add(i, e); isInserted = true; break; } } } if (!isInserted) { elements.add(e); } totalWeight += weight; return this; } /** * @return the elements */ public List<WeightedRandomEntry<T>> getElements() { return elements; } /** * Returns a randomly picked element from the set. The frequency of * occurance depends on the relative weight of each item. * * @return picked element */ public T getRandom() { int rnd = MathUtils.random(totalWeight); T choice = null; int sum = totalWeight; for (WeightedRandomEntry<T> e : elements) { sum -= e.weight; if (sum <= rnd) { choice = e.item; break; } } return choice; } /** * Removes the given item from the set. * * @param item */ public void remove(T item) { for (WeightedRandomEntry<T> e : elements) { if (e.item.equals(item)) { elements.remove(e); totalWeight -= e.weight; return; } } } }