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