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}