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