no-overlap.cpp

00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Christian Schulte, 2011
00008  *
00009  *  Last modified:
00010  *     $Date: 2011-08-10 10:38:22 +0200 (Wed, 10 Aug 2011) $ by $Author: schulte $
00011  *     $Revision: 12264 $
00012  *
00013  *  This file is part of Gecode, the generic constraint
00014  *  development environment:
00015  *     http://www.gecode.org
00016  *
00017  *  Permission is hereby granted, free of charge, to any person obtaining
00018  *  a copy of this software and associated documentation files (the
00019  *  "Software"), to deal in the Software without restriction, including
00020  *  without limitation the rights to use, copy, modify, merge, publish,
00021  *  distribute, sublicense, and/or sell copies of the Software, and to
00022  *  permit persons to whom the Software is furnished to do so, subject to
00023  *  the following conditions:
00024  *
00025  *  The above copyright notice and this permission notice shall be
00026  *  included in all copies or substantial portions of the Software.
00027  *
00028  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00029  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00030  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00031  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00032  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00033  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00034  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00035  *
00036  */
00037 
00038 #include <gecode/int/no-overlap.hh>
00039 
00040 namespace Gecode {
00041 
00042   namespace Int { namespace NoOverlap {
00043 
00044     bool
00045     optional(const BoolVarArgs& m) {
00046       for (int i=m.size(); i--; )
00047         if (m[i].none())
00048           return true;
00049       return false;
00050     }
00051 
00052   }}
00053 
00054   void
00055   nooverlap(Home home, 
00056             const IntVarArgs& x, const IntArgs& w, 
00057             const IntVarArgs& y, const IntArgs& h,
00058             IntConLevel) {
00059     using namespace Int;
00060     using namespace NoOverlap;
00061     if (x.same(home) || y.same(home))
00062       throw ArgumentSame("Int::nooverlap");
00063     if ((x.size() != w.size()) || (x.size() != y.size()) || 
00064         (x.size() != h.size()))
00065       throw ArgumentSizeMismatch("Int::nooverlap");      
00066     for (int i=x.size(); i--; ) {
00067       Limits::nonnegative(w[i],"Int::nooverlap");
00068       Limits::nonnegative(h[i],"Int::nooverlap");
00069       Limits::check(static_cast<double>(x[i].max()) + w[i],
00070                     "Int::nooverlap");
00071       Limits::check(static_cast<double>(y[i].max()) + h[i],
00072                     "Int::nooverlap");
00073     }
00074     if (home.failed()) return;
00075 
00076     ManBox<FixDim,2>* b 
00077       = static_cast<Space&>(home).alloc<ManBox<FixDim,2> >(x.size());
00078     for (int i=x.size(); i--; ) {
00079       b[i][0] = FixDim(x[i],w[i]);
00080       b[i][1] = FixDim(y[i],h[i]);
00081     }
00082 
00083     GECODE_ES_FAIL((NoOverlap::ManProp<FixDim,2>::post(home,b,x.size())));
00084   }
00085 
00086   void
00087   nooverlap(Home home, 
00088             const IntVarArgs& x, const IntArgs& w, 
00089             const IntVarArgs& y, const IntArgs& h,
00090             const BoolVarArgs& m,
00091             IntConLevel) {
00092     using namespace Int;
00093     using namespace NoOverlap;
00094     if (x.same(home) || y.same(home) || m.same(home))
00095       throw ArgumentSame("Int::nooverlap");
00096     if ((x.size() != w.size()) || (x.size() != y.size()) ||
00097         (x.size() != h.size()) || (x.size() != m.size()))
00098       throw ArgumentSizeMismatch("Int::nooverlap");      
00099     for (int i=x.size(); i--; ) {
00100       Limits::nonnegative(w[i],"Int::nooverlap");
00101       Limits::nonnegative(h[i],"Int::nooverlap");
00102       Limits::check(static_cast<double>(x[i].max()) + w[i],
00103                     "Int::nooverlap");
00104       Limits::check(static_cast<double>(y[i].max()) + h[i],
00105                     "Int::nooverlap");
00106     }
00107     if (home.failed()) return;
00108     
00109     if (optional(m)) {
00110       OptBox<FixDim,2>* b 
00111         = static_cast<Space&>(home).alloc<OptBox<FixDim,2> >(x.size());
00112       for (int i=x.size(); i--; ) {
00113         b[i][0] = FixDim(x[i],w[i]);
00114         b[i][1] = FixDim(y[i],h[i]);
00115         b[i].optional(m[i]);
00116       }
00117       GECODE_ES_FAIL((NoOverlap::OptProp<FixDim,2>::post(home,b,x.size())));
00118     } else {
00119       ManBox<FixDim,2>* b 
00120         = static_cast<Space&>(home).alloc<ManBox<FixDim,2> >(x.size());
00121       int n = 0;
00122       for (int i=0; i<x.size(); i++)
00123         if (m[i].one()) {
00124           b[n][0] = FixDim(x[i],w[i]);
00125           b[n][1] = FixDim(y[i],h[i]);
00126           n++;
00127         }
00128       GECODE_ES_FAIL((NoOverlap::ManProp<FixDim,2>::post(home,b,n)));
00129     }
00130   }
00131 
00132   void
00133   nooverlap(Home home, 
00134             const IntVarArgs& x0, const IntVarArgs& w, const IntVarArgs& x1,
00135             const IntVarArgs& y0, const IntVarArgs& h, const IntVarArgs& y1,
00136             IntConLevel) {
00137     using namespace Int;
00138     using namespace NoOverlap;
00139     if ((x0.size() != w.size())  || (x0.size() != x1.size()) || 
00140         (x0.size() != y0.size()) || (x0.size() != h.size()) || 
00141         (x0.size() != y1.size()))
00142       throw ArgumentSizeMismatch("Int::nooverlap");
00143     if (x0.same(home) || w.same(home) || x1.same(home) ||
00144         y0.same(home) || h.same(home) || y1.same(home))
00145       throw ArgumentSame("Int::nooverlap");
00146     if (home.failed()) return;
00147 
00148     for (int i=x0.size(); i--; ) {
00149       GECODE_ME_FAIL(IntView(w[i]).gq(home,0));
00150       GECODE_ME_FAIL(IntView(h[i]).gq(home,0));
00151     }
00152 
00153     if (w.assigned() && h.assigned()) {
00154       IntArgs wc(x0.size()), hc(x0.size());
00155       for (int i=x0.size(); i--; ) {
00156         wc[i] = w[i].val();
00157         hc[i] = h[i].val();
00158       }
00159       nooverlap(home, x0, wc, y0, hc);
00160     } else {
00161       ManBox<FlexDim,2>* b 
00162         = static_cast<Space&>(home).alloc<ManBox<FlexDim,2> >(x0.size());
00163       for (int i=x0.size(); i--; ) {
00164         b[i][0] = FlexDim(x0[i],w[i],x1[i]);
00165         b[i][1] = FlexDim(y0[i],h[i],y1[i]);
00166       }
00167       GECODE_ES_FAIL((NoOverlap::ManProp<FlexDim,2>::post(home,b,x0.size())));
00168     }
00169   }
00170 
00171   void
00172   nooverlap(Home home, 
00173             const IntVarArgs& x0, const IntVarArgs& w, const IntVarArgs& x1,
00174             const IntVarArgs& y0, const IntVarArgs& h, const IntVarArgs& y1,
00175             const BoolVarArgs& m,
00176             IntConLevel) {
00177     using namespace Int;
00178     using namespace NoOverlap;
00179     if ((x0.size() != w.size())  || (x0.size() != x1.size()) || 
00180         (x0.size() != y0.size()) || (x0.size() != h.size()) || 
00181         (x0.size() != y1.size()) || (x0.size() != m.size()))
00182       throw ArgumentSizeMismatch("Int::nooverlap");
00183     if (x0.same(home) || w.same(home) || x1.same(home) ||
00184         y0.same(home) || h.same(home) || y1.same(home) ||
00185         m.same(home))
00186       throw ArgumentSame("Int::nooverlap");
00187     if (home.failed()) return;
00188 
00189     for (int i=x0.size(); i--; ) {
00190       GECODE_ME_FAIL(IntView(w[i]).gq(home,0));
00191       GECODE_ME_FAIL(IntView(h[i]).gq(home,0));
00192     }
00193 
00194     if (w.assigned() && h.assigned()) {
00195       IntArgs wc(x0.size()), hc(x0.size());
00196       for (int i=x0.size(); i--; ) {
00197         wc[i] = w[i].val();
00198         hc[i] = h[i].val();
00199       }
00200       nooverlap(home, x0, wc, y0, hc, m);
00201     } else if (optional(m)) {
00202       OptBox<FlexDim,2>* b 
00203         = static_cast<Space&>(home).alloc<OptBox<FlexDim,2> >(x0.size());
00204       for (int i=x0.size(); i--; ) {
00205         b[i][0] = FlexDim(x0[i],w[i],x1[i]);
00206         b[i][1] = FlexDim(y0[i],h[i],y1[i]);
00207         b[i].optional(m[i]);
00208       }
00209       GECODE_ES_FAIL((NoOverlap::OptProp<FlexDim,2>::post(home,b,x0.size())));
00210     } else {
00211       ManBox<FlexDim,2>* b 
00212         = static_cast<Space&>(home).alloc<ManBox<FlexDim,2> >(x0.size());
00213       int n = 0;
00214       for (int i=0; i<x0.size(); i++)
00215         if (m[i].one()) {
00216           b[n][0] = FlexDim(x0[i],w[i],x1[i]);
00217           b[n][1] = FlexDim(y0[i],h[i],y1[i]);
00218           n++;
00219         }
00220       GECODE_ES_FAIL((NoOverlap::ManProp<FlexDim,2>::post(home,b,n)));
00221     }
00222   }
00223 
00224 }
00225 
00226 // STATISTICS: int-post