001    package net.sf.cpsolver.ifs.heuristics;
002    
003    import java.util.ArrayList;
004    import java.util.Enumeration;
005    import java.util.List;
006    
007    import 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 Tomas Muller<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    
037    public 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    }