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