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}