Generated on Fri Oct 19 11:25:03 2018 for Gecode by doxygen 1.6.3

distinct.cpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *     Gabor Szokoli <szokoli@gecode.org>
00006  *
00007  *  Contributing authors:
00008  *     Roberto Castaņeda Lozano <rcas@kth.se>
00009  *
00010  *  Copyright:
00011  *     Roberto Castaņeda Lozano, 2015
00012  *     Christian Schulte, 2002
00013  *     Gabor Szokoli, 2003
00014  *
00015  *  This file is part of Gecode, the generic constraint
00016  *  development environment:
00017  *     http://www.gecode.org
00018  *
00019  *  Permission is hereby granted, free of charge, to any person obtaining
00020  *  a copy of this software and associated documentation files (the
00021  *  "Software"), to deal in the Software without restriction, including
00022  *  without limitation the rights to use, copy, modify, merge, publish,
00023  *  distribute, sublicense, and/or sell copies of the Software, and to
00024  *  permit persons to whom the Software is furnished to do so, subject to
00025  *  the following conditions:
00026  *
00027  *  The above copyright notice and this permission notice shall be
00028  *  included in all copies or substantial portions of the Software.
00029  *
00030  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00031  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00032  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00033  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00034  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00035  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00036  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00037  *
00038  */
00039 
00040 #include <gecode/int/distinct.hh>
00041 #include <gecode/int/bool.hh>
00042 
00043 namespace Gecode {
00044 
00045   void
00046   distinct(Home home, const IntVarArgs& x, IntPropLevel ipl) {
00047     using namespace Int;
00048     if (same(x))
00049       throw ArgumentSame("Int::distinct");
00050     GECODE_POST;
00051     ViewArray<IntView> xv(home,x);
00052     switch (vbd(ipl)) {
00053     case IPL_BND:
00054       GECODE_ES_FAIL(Distinct::Bnd<IntView>::post(home,xv));
00055       break;
00056     case IPL_DOM:
00057       GECODE_ES_FAIL(Distinct::Dom<IntView>::post(home,xv));
00058       break;
00059     default:
00060       GECODE_ES_FAIL(Distinct::Val<IntView>::post(home,xv));
00061     }
00062   }
00063 
00064   void
00065   distinct(Home home, const IntArgs& c, const IntVarArgs& x,
00066            IntPropLevel ipl) {
00067     using namespace Int;
00068     if (same(x))
00069       throw ArgumentSame("Int::distinct");
00070     if (c.size() != x.size())
00071       throw ArgumentSizeMismatch("Int::distinct");
00072     GECODE_POST;
00073     ViewArray<OffsetView> cx(home,x.size());
00074     for (int i=0; i<c.size(); i++) {
00075       long long int cx_min = (static_cast<long long int>(c[i]) +
00076                               static_cast<long long int>(x[i].min()));
00077       long long int cx_max = (static_cast<long long int>(c[i]) +
00078                               static_cast<long long int>(x[i].max()));
00079       Limits::check(c[i],"Int::distinct");
00080       Limits::check(cx_min,"Int::distinct");
00081       Limits::check(cx_max,"Int::distinct");
00082       cx[i] = OffsetView(x[i],c[i]);
00083     }
00084     switch (vbd(ipl)) {
00085     case IPL_BND:
00086       GECODE_ES_FAIL(Distinct::Bnd<OffsetView>::post(home,cx));
00087       break;
00088     case IPL_DOM:
00089       GECODE_ES_FAIL(Distinct::Dom<OffsetView>::post(home,cx));
00090       break;
00091     default:
00092       GECODE_ES_FAIL(Distinct::Val<OffsetView>::post(home,cx));
00093     }
00094   }
00095 
00096   void
00097   distinct(Home home, const BoolVarArgs& b, const IntVarArgs& x,
00098            IntPropLevel ipl) {
00099     using namespace Int;
00100     if (same(x))
00101       throw ArgumentSame("Int::distinct");
00102     if (b.size() != x.size())
00103       throw ArgumentSizeMismatch("Int::distinct");
00104     GECODE_POST;
00105 
00106     int n = x.size();
00107     int min = Limits::max;
00108     int max = Limits::min;
00109     int m = 0;
00110     for (int i=0; i<n; i++)
00111       if (!b[i].zero()) {
00112         min = std::min(min,x[i].min());
00113         max = std::max(max,x[i].max());
00114         m++;
00115       }
00116 
00117     if (m < 2)
00118       return;
00119 
00120     int start;
00121     if (max < Limits::max-m)
00122       start = max+1;
00123     else if (min > Limits::min+m)
00124       start = min-(m+1);
00125     else
00126       throw OutOfLimits("Int::distinct");
00127 
00128     ViewArray<IntView> y(home,m);
00129     int j = 0;
00130     for (int i=0; i<n; i++)
00131       if (b[i].one()) {
00132         y[j] = x[i]; j++;
00133       } else if (b[i].none()) {
00134         y[j] = IntVar(home, Limits::min, Limits::max);
00135         GECODE_ES_FAIL((Bool::IteDom<IntView,ConstIntView,IntView>::post
00136                         (home, b[i], x[i], start+j, y[j])));
00137         j++;
00138       }
00139     assert(j == m);
00140 
00141     switch (vbd(ipl)) {
00142     case IPL_BND:
00143       GECODE_ES_FAIL(Distinct::Bnd<IntView>::post(home,y));
00144       break;
00145     case IPL_DOM:
00146       GECODE_ES_FAIL(Distinct::Dom<IntView>::post(home,y));
00147       break;
00148     default:
00149       GECODE_ES_FAIL(Distinct::Val<IntView>::post(home,y));
00150     }
00151   }
00152 
00153   void
00154   distinct(Home home, const IntVarArgs& x, int c,
00155            IntPropLevel ipl) {
00156     using namespace Int;
00157     if (same(x))
00158       throw ArgumentSame("Int::distinct");
00159     GECODE_POST;
00160 
00161     int n = x.size();
00162     int min = Limits::max;
00163     int max = Limits::min;
00164     int m = 0;
00165     for (int i=0; i<n; i++)
00166       if (!(x[i].assigned() && (x[i].val() == c))) {
00167         min = std::min(min,x[i].min());
00168         max = std::max(max,x[i].max());
00169         m++;
00170       }
00171 
00172     if (m < 2)
00173       return;
00174 
00175     int start;
00176     if (max < Limits::max-m)
00177       start = max+1;
00178     else if (min > Limits::min+m)
00179       start = min-(m+1);
00180     else
00181       throw OutOfLimits("Int::distinct");
00182 
00183     ViewArray<IntView> y(home,m);
00184     int j = 0;
00185     for (int i=0; i<n; i++)
00186       if (!x[i].in(c)) {
00187         y[j] = x[i]; j++;
00188       } else if (!(x[i].assigned() && (x[i].val() == c))) {
00189         y[j] = IntVar(home, Limits::min, Limits::max);
00190         GECODE_ES_FAIL(Distinct::EqIte::post
00191                        (home, x[i], y[j], c, start+j));
00192         j++;
00193       }
00194     assert(j == m);
00195 
00196     switch (vbd(ipl)) {
00197     case IPL_BND:
00198       GECODE_ES_FAIL(Distinct::Bnd<IntView>::post(home,y));
00199       break;
00200     case IPL_DOM:
00201       GECODE_ES_FAIL(Distinct::Dom<IntView>::post(home,y));
00202       break;
00203     default:
00204       GECODE_ES_FAIL(Distinct::Val<IntView>::post(home,y));
00205     }
00206   }
00207 
00208 }
00209 
00210 // STATISTICS: int-post