001    package net.sf.cpsolver.ifs.heuristics;
002    
003    import java.util.ArrayList;
004    import java.util.List;
005    
006    import net.sf.cpsolver.ifs.model.Neighbour;
007    import net.sf.cpsolver.ifs.model.Value;
008    import net.sf.cpsolver.ifs.model.Variable;
009    import net.sf.cpsolver.ifs.solution.Solution;
010    import net.sf.cpsolver.ifs.solver.Solver;
011    import net.sf.cpsolver.ifs.util.DataProperties;
012    
013    import org.apache.log4j.Logger;
014    
015    /**
016     * A round robin neighbour selection. Two or more {@link NeighbourSelection}
017     * needs to be registered within the selection. This selection criterion takes
018     * the registered neighbour selections one by one and performs
019     * {@link NeighbourSelection#init(Solver)} and then it is using
020     * {@link NeighbourSelection#selectNeighbour(Solution)} to select a neighbour.
021     * When null is returned by the underlaying selection, next registered neighbour
022     * selection is initialized and used for the following selection(s). If the last
023     * registered selection returns null, the selection is returned to the first
024     * registered neighbour selection (it is initialized before used again).
025     * 
026     * <br>
027     * <br>
028     * 
029     * @version StudentSct 1.2 (Student Sectioning)<br>
030     *          Copyright (C) 2007 - 2010 Tomas Muller<br>
031     *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
032     *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
033     * <br>
034     *          This library is free software; you can redistribute it and/or modify
035     *          it under the terms of the GNU Lesser General Public License as
036     *          published by the Free Software Foundation; either version 3 of the
037     *          License, or (at your option) any later version. <br>
038     * <br>
039     *          This library is distributed in the hope that it will be useful, but
040     *          WITHOUT ANY WARRANTY; without even the implied warranty of
041     *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
042     *          Lesser General Public License for more details. <br>
043     * <br>
044     *          You should have received a copy of the GNU Lesser General Public
045     *          License along with this library; if not see
046     *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
047     */
048    
049    public class RoundRobinNeighbourSelection<V extends Variable<V, T>, T extends Value<V, T>> extends
050            StandardNeighbourSelection<V, T> {
051        private static Logger sLogger = Logger.getLogger(RoundRobinNeighbourSelection.class);
052        private int iSelectionIdx = -1;
053        private List<NeighbourSelection<V, T>> iSelections = new ArrayList<NeighbourSelection<V, T>>();
054        private Solver<V, T> iSolver = null;
055    
056        /**
057         * Constructor
058         * 
059         * @param properties
060         *            configuration
061         * @throws Exception
062         */
063        public RoundRobinNeighbourSelection(DataProperties properties) throws Exception {
064            super(properties);
065        }
066    
067        /** Register a neighbour selection */
068        public void registerSelection(NeighbourSelection<V, T> selection) {
069            iSelections.add(selection);
070        }
071    
072        /** Initialization */
073        @Override
074        public void init(Solver<V, T> solver) {
075            super.init(solver);
076            iSolver = solver;
077        }
078    
079        /**
080         * Select neighbour. A first registered selections is initialized and used
081         * until it returns null, then the second registered selections is
082         * initialized and used and vice versa.
083         */
084        @Override
085        public Neighbour<V, T> selectNeighbour(Solution<V, T> solution) {
086            if (iSelectionIdx == -1) {
087                iSelectionIdx = 0;
088                iSelections.get(iSelectionIdx).init(iSolver);
089            }
090            while (true) {
091                NeighbourSelection<V, T> selection = iSelections.get(iSelectionIdx);
092                Neighbour<V, T> neighbour = selection.selectNeighbour(solution);
093                if (neighbour != null)
094                    return neighbour;
095                changeSelection(solution);
096            }
097        }
098    
099        /** Change selection */
100        public void changeSelection(Solution<V, T> solution) {
101            iSelectionIdx = (1 + iSelectionIdx) % iSelections.size();
102            sLogger.debug("Phase changed to " + (iSelectionIdx + 1));
103            if (solution.getBestInfo() == null || iSolver.getSolutionComparator().isBetterThanBestSolution(solution))
104                solution.saveBest();
105            iSelections.get(iSelectionIdx).init(iSolver);
106        }
107    }