    001package net.sf.cpsolver.ifs.heuristics;
    002
    003import java.util.ArrayList;
    004import java.util.Enumeration;
    005import java.util.List;
    006
    007import net.sf.cpsolver.ifs.util.ToolBox;
    008
    009/**
    010 * A general roulette wheel selection. An object is selected randomly,
    011 * proportionaly to the provided weight. This class also supports multiple
    012 * selections (it implements {@link Enumeration} interface).
    013 *
    014 * <br>
    015 * <br>
    016 *
    017 * @version StudentSct 1.2 (Student Sectioning)<br>
    018 *          Copyright (C) 2007 - 2010 Tomáš Müller<br>
    019 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    020 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    021 * <br>
    022 *          This library is free software; you can redistribute it and/or modify
    023 *          it under the terms of the GNU Lesser General Public License as
    024 *          published by the Free Software Foundation; either version 3 of the
    025 *          License, or (at your option) any later version. <br>
    026 * <br>
    027 *          This library is distributed in the hope that it will be useful, but
    028 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    029 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    030 *          Lesser General Public License for more details. <br>
    031 * <br>
    032 *          You should have received a copy of the GNU Lesser General Public
    033 *          License along with this library; if not see
    034 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    035 */
    036
    037public class RouletteWheelSelection<E> implements Enumeration<E> {
    038    private List<E> iAdepts = new ArrayList<E>();
    039    private List<Double> iPoints = new ArrayList<Double>();
    040    private double iTotalPoints = 0, iUsedPoints = 0;
    041    private int iFirst = 0;
    042
    043    /**
    044     * Add an adept to the selection
    045     *
    046     * @param adept
    047     *            an object
    048     * @param points
    049     *            object weight (more points, better chance to be selected)
    050     */
    051    public void add(E adept, double points) {
    052        iAdepts.add(adept);
    053        iPoints.add(points);
    054        iTotalPoints += points;
    055    }
    056
    057    private void swap(int idx1, int idx2) {
    058        E a1 = iAdepts.get(idx1);
    059        E a2 = iAdepts.get(idx2);
    060        iAdepts.set(idx1, a2);
    061        iAdepts.set(idx2, a1);
    062        Double p1 = iPoints.get(idx1);
    063        Double p2 = iPoints.get(idx2);
    064        iPoints.set(idx1, p2);
    065        iPoints.set(idx2, p1);
    066    }
    067
    068    /** Are there still some adepts that have not been yet selected */
    069    @Override
    070    public boolean hasMoreElements() {
    071        return iFirst < iAdepts.size();
    072    }
    073
    074    /**
    075     * Perform selection. An object is selected randomly with the probability
    076     * proportional to the provided weight. Each object can be selected only
    077     * once.
    078     */
    079    @Override
    080    public E nextElement() {
    081        if (!hasMoreElements())
    082            return null;
    083        double rx = ToolBox.random() * iTotalPoints;
    084
    085        int iIdx = iFirst;
    086        rx -= iPoints.get(iIdx);
    087        while (rx > 0 && iIdx + 1 < iAdepts.size()) {
    088            iIdx++;
    089            rx -= iPoints.get(iIdx);
    090        }
    091
    092        E selectedObject = iAdepts.get(iIdx);
    093        double points = iPoints.get(iIdx);
    094        iTotalPoints -= points;
    095        iUsedPoints += points;
    096        swap(iFirst, iIdx);
    097        iFirst++;
    098
    099        return selectedObject;
    100    }
    101
    102    /** Number of objects in the set */
    103    public int size() {
    104        return iAdepts.size();
    105    }
    106
    107    /** Total value of objects that were already returned by the selection. */
    108    public double getUsedPoints() {
    109        return iUsedPoints;
    110    }
    111
    112    /** Total value of objects that are still in the selection. */
    113    public double getRemainingPoints() {
    114        return iTotalPoints;
    115    }
    116
    117    /** Total value of objects that were added into the selection. */
    118    public double getTotalPoints() {
    119        return iTotalPoints + iUsedPoints;
    120    }
    121}