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}