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