001    package net.sf.cpsolver.ifs.example.rpp;
002    
003    import java.util.Set;
004    
005    import net.sf.cpsolver.ifs.model.Constraint;
006    import net.sf.cpsolver.ifs.util.ToolBox;
007    
008    /**
009     * Resource constraint (rectangular area where the rectangles are to be placed).
010     * It prohibits overlapping of the placed rectangles.
011     * 
012     * @version IFS 1.2 (Iterative Forward Search)<br>
013     *          Copyright (C) 2006 - 2010 Tomas Muller<br>
014     *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
015     *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
016     * <br>
017     *          This library is free software; you can redistribute it and/or modify
018     *          it under the terms of the GNU Lesser General Public License as
019     *          published by the Free Software Foundation; either version 3 of the
020     *          License, or (at your option) any later version. <br>
021     * <br>
022     *          This library is distributed in the hope that it will be useful, but
023     *          WITHOUT ANY WARRANTY; without even the implied warranty of
024     *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
025     *          Lesser General Public License for more details. <br>
026     * <br>
027     *          You should have received a copy of the GNU Lesser General Public
028     *          License along with this library; if not see
029     *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
030     */
031    public class ResourceConstraint extends Constraint<Rectangle, Location> {
032        private static org.apache.log4j.Logger sLogger = org.apache.log4j.Logger.getLogger(ResourceConstraint.class);
033        private Rectangle[][] iResource;
034        private int iWidth, iHeight;
035    
036        /**
037         * Constructor.
038         * 
039         * @param width
040         *            area width
041         * @param height
042         *            area height
043         */
044        public ResourceConstraint(int width, int height) {
045            super();
046            iWidth = width;
047            iHeight = height;
048            iResource = new Rectangle[width][height];
049            for (int x = 0; x < width; x++)
050                for (int y = 0; y < height; y++)
051                    iResource[x][y] = null;
052        }
053    
054        /**
055         * Compute conflicts with the given placement of the rectangle. This means
056         * the rectangles which are already placed and which are overlapping with
057         * the given assignment.
058         */
059        @Override
060        public void computeConflicts(Location placement, Set<Location> conflicts) {
061            Rectangle rectangle = placement.variable();
062            for (int x = placement.getX(); x < Math.min(iWidth, placement.getX() + rectangle.getWidth()); x++)
063                for (int y = placement.getY(); y < Math.min(iHeight, placement.getY() + rectangle.getHeight()); y++)
064                    if (iResource[x][y] != null)
065                        conflicts.add(iResource[x][y].getAssignment());
066        }
067    
068        /**
069         * Returns true if there is a rectangle which overlaps with the given
070         * assignment.
071         */
072        @Override
073        public boolean inConflict(Location placement) {
074            Rectangle rectangle = placement.variable();
075            for (int x = placement.getX(); x < Math.min(iWidth, placement.getX() + rectangle.getWidth()); x++)
076                for (int y = placement.getY(); y < Math.min(iHeight, placement.getY() + rectangle.getHeight()); y++)
077                    if (iResource[x][y] != null)
078                        return true;
079            return false;
080        }
081    
082        /**
083         * Returns true if the given rectangles (assignments) do not overlap.
084         */
085        @Override
086        public boolean isConsistent(Location p1, Location p2) {
087            Rectangle r1 = p1.variable();
088            Rectangle r2 = p2.variable();
089            if (p2.getX() + r2.getWidth() <= p1.getX())
090                return true;
091            if (p2.getX() >= p1.getX() + r1.getWidth())
092                return true;
093            if (p2.getY() + r2.getHeight() <= p1.getY())
094                return true;
095            if (p2.getY() >= p1.getY() + r1.getHeight())
096                return true;
097            return false;
098        }
099    
100        /**
101         * Notification, when a rectangle is placed. It memorizes the rectangle's
102         * new position in 2D ([0..width][0..height]) array. It is used for faster
103         * lookup when computing conflicts.
104         */
105        @Override
106        public void assigned(long iteration, Location placement) {
107            super.assigned(iteration, placement);
108            Rectangle rectangle = placement.variable();
109            for (int x = placement.getX(); x < Math.min(iWidth, placement.getX() + rectangle.getWidth()); x++)
110                for (int y = placement.getY(); y < Math.min(iHeight, placement.getY() + rectangle.getHeight()); y++) {
111                    iResource[x][y] = rectangle;
112                }
113        }
114    
115        /**
116         * Notification, when a rectangle is unplaced. It removes the rectangle from
117         * the 2D ([0..width][0..height]) array.
118         */
119        @Override
120        public void unassigned(long iteration, Location placement) {
121            super.unassigned(iteration, placement);
122            Rectangle rectangle = placement.variable();
123            for (int x = placement.getX(); x < Math.min(iWidth, placement.getX() + rectangle.getWidth()); x++)
124                for (int y = placement.getY(); y < Math.min(iHeight, placement.getY() + rectangle.getHeight()); y++) {
125                    iResource[x][y] = null;
126                }
127        }
128    
129        public void check() {
130            sLogger.debug("check");
131            for (Rectangle rectangle : variables()) {
132                Location placement = rectangle.getAssignment();
133                if (placement == null) {
134                    sLogger.warn("Rectangle " + rectangle.getName() + " is not assigned.");
135                    continue;
136                }
137                sLogger.debug("Checking " + rectangle.getName() + "    (assigned:" + placement.getName() + ", prohibited:"
138                        + rectangle.isProhibited(placement.getX(), placement.getY()) + ", initial:"
139                        + rectangle.getInitialAssignment() + ", prohibited:[" + rectangle.getProhibitedX() + ","
140                        + rectangle.getProhibitedY() + "])");
141                if (placement.getX() == rectangle.getProhibitedX() || placement.getY() == rectangle.getProhibitedY())
142                    sLogger.error("Placement is prohibited.");
143                if (placement.getX() < rectangle.getMinX() || placement.getX() > rectangle.getMaxX()
144                        || placement.getY() < rectangle.getMinY() || placement.getY() > rectangle.getMaxY())
145                    sLogger.error("Placement is outside bounds.");
146                for (int x = placement.getX(); x < Math.min(iWidth, placement.getX() + rectangle.getWidth()); x++)
147                    for (int y = placement.getY(); y < Math.min(iHeight, placement.getY() + rectangle.getHeight()); y++) {
148                        if (iResource[x][y] == null || !iResource[x][y].equals(rectangle))
149                            sLogger.error("Problem at [" + x + "," + y + "], " + iResource[x][y] + " is assigned there.");
150                    }
151            }
152            sLogger.debug(toString());
153        }
154    
155        /**
156         * String representation of the constraint (for debugging and printing
157         * purposes).
158         */
159        @Override
160        public String toString() {
161            StringBuffer sb = new StringBuffer("ResourceConstraint{\n        ");
162            for (int y = 0; y < iHeight; y++) {
163                for (int x = 0; x < iWidth; x++) {
164                    sb.append(ToolBox.trim(iResource[x][y] == null ? "" : iResource[x][y].getName().substring(4), 4));
165                }
166                sb.append("\n        ");
167            }
168            sb.append("\n      }");
169            return sb.toString();
170        }
171    }