Generated on Tue May 22 09:40:05 2018 for Gecode by doxygen 1.6.3

int.cpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Guido Tack <tack@gecode.org>
00005  *     Christian Schulte <schulte@gecode.org>
00006  *
00007  *  Copyright:
00008  *     Guido Tack, 2004
00009  *     Christian Schulte, 2004
00010  *
00011  *  This file is part of Gecode, the generic constraint
00012  *  development environment:
00013  *     http://www.gecode.org
00014  *
00015  *  Permission is hereby granted, free of charge, to any person obtaining
00016  *  a copy of this software and associated documentation files (the
00017  *  "Software"), to deal in the Software without restriction, including
00018  *  without limitation the rights to use, copy, modify, merge, publish,
00019  *  distribute, sublicense, and/or sell copies of the Software, and to
00020  *  permit persons to whom the Software is furnished to do so, subject to
00021  *  the following conditions:
00022  *
00023  *  The above copyright notice and this permission notice shall be
00024  *  included in all copies or substantial portions of the Software.
00025  *
00026  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00027  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00028  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00029  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00030  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00031  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00032  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00033  *
00034  */
00035 
00036 #include <gecode/set.hh>
00037 
00038 #include <gecode/set/int.hh>
00039 #include <gecode/set/rel.hh>
00040 
00041 namespace Gecode {
00042 
00043   void
00044   rel(Home home, SetVar s, IntRelType rt, IntVar x) {
00045     GECODE_POST;
00046     switch (rt) {
00047     case IRT_EQ:
00048       {
00049         Gecode::Int::IntView xv(x);
00050         Set::SingletonView xsingle(xv);
00051         GECODE_ES_FAIL(
00052                        (Set::Rel::Eq<Set::SetView,Set::SingletonView>
00053                         ::post(home,s,xsingle)));
00054 
00055       }
00056       break;
00057     case IRT_NQ:
00058       {
00059         Gecode::Set::SetView sv(s);
00060         GECODE_ME_FAIL( sv.cardMin(home, 1));
00061         Gecode::Int::IntView xv(x);
00062         Set::SingletonView xsingle(xv);
00063         GECODE_ES_FAIL(
00064                        (Set::Rel::NoSubset<Set::SingletonView,Set::SetView>
00065                         ::post(home,xsingle,sv)));
00066 
00067       }
00068       break;
00069     case IRT_LQ:
00070       {
00071         IntVar tmp(home, Int::Limits::min, Int::Limits::max);
00072         rel(home, tmp, IRT_LQ, x);
00073         GECODE_ES_FAIL(Set::Int::MaxElement<Set::SetView>::post(home,s,tmp));
00074       }
00075       break;
00076     case IRT_LE:
00077       {
00078         IntVar tmp(home, Int::Limits::min, Int::Limits::max);
00079         rel(home, tmp, IRT_LE, x);
00080         GECODE_ES_FAIL(Set::Int::MaxElement<Set::SetView>::post(home,s,tmp));
00081       }
00082       break;
00083     case IRT_GQ:
00084       {
00085         IntVar tmp(home, Int::Limits::min, Int::Limits::max);
00086         rel(home, tmp, IRT_GQ, x);
00087         GECODE_ES_FAIL(Set::Int::MinElement<Set::SetView>::post(home,s,tmp));
00088       }
00089       break;
00090     case IRT_GR:
00091       {
00092         IntVar tmp(home, Int::Limits::min, Int::Limits::max);
00093         rel(home, tmp, IRT_GR, x);
00094         GECODE_ES_FAIL(Set::Int::MinElement<Set::SetView>::post(home,s,tmp));
00095       }
00096       break;
00097     default:
00098       throw Int::UnknownRelation("Set::rel");
00099     }
00100 
00101   }
00102 
00103 }
00104 
00105 namespace Gecode { namespace Set { namespace Int {
00106 
00108   void remin(Home home, SetVar s, IntVar m, Reify r) {
00109     IntVar c(home, 0, static_cast<int>(Set::Limits::card));
00110     cardinality(home, s, c);
00111     // Whether set is not empty
00112     BoolVar ne(home, 0, 1);
00113     rel(home, c, IRT_GR, 0, ne);
00114     if (r.mode() != RM_PMI)
00115       rel(home, r.var(), BOT_IMP, ne, 1);
00116     min(home, s, m, ne);
00117   }
00118 
00120   void remax(Home home, SetVar s, IntVar m, Reify r) {
00121     IntVar c(home, 0, static_cast<int>(Set::Limits::card));
00122     cardinality(home, s, c);
00123     // Whether set is not empty
00124     BoolVar ne(home, 0, 1);
00125     rel(home, c, IRT_GR, 0, ne);
00126     if (r.mode() != RM_PMI)
00127       rel(home, r.var(), BOT_IMP, ne, 1);
00128     max(home, s, m, ne);
00129   }
00130 
00131 }}}
00132 
00133 namespace Gecode {
00134 
00135   void
00136   rel(Home home, SetVar s, IntRelType rt, IntVar x, Reify r) {
00137     GECODE_POST;
00138     switch (rt) {
00139     case IRT_EQ:
00140       {
00141         Gecode::Int::IntView xv(x);
00142         Set::SingletonView xs(xv);
00143         switch (r.mode()) {
00144         case RM_EQV:
00145           GECODE_ES_FAIL((Set::Rel::ReEq<Set::SetView,Set::SingletonView,
00146                           Gecode::Int::BoolView,RM_EQV>
00147                           ::post(home,s,xs,r.var())));
00148           break;
00149         case RM_IMP:
00150           GECODE_ES_FAIL((Set::Rel::ReEq<Set::SetView,Set::SingletonView,
00151                           Gecode::Int::BoolView,RM_IMP>
00152                           ::post(home,s,xs,r.var())));
00153           break;
00154         case RM_PMI:
00155           GECODE_ES_FAIL((Set::Rel::ReEq<Set::SetView,Set::SingletonView,
00156                           Gecode::Int::BoolView,RM_PMI>
00157                           ::post(home,s,xs,r.var())));
00158           break;
00159         default:
00160           throw Gecode::Int::UnknownReifyMode("Set::rel");
00161         }
00162       }
00163       break;
00164     case IRT_NQ:
00165       {
00166         IntVar c(home, 0, static_cast<int>(Set::Limits::card));
00167         cardinality(home, s, c);
00168         // Whether set is not empty
00169         BoolVar ne(home, 0 , 1);
00170         rel(home, c, IRT_GR, 0, ne);
00171         // Whether {x} is a subset of s
00172         BoolVar ss(home, 0 , 1);
00173         rel(home, x, SRT_SUB, s, ss);
00174         BoolVar b;
00175         switch (r.mode()) {
00176         case RM_EQV:
00177           b=r.var();
00178           break;
00179         case RM_IMP:
00180           b=BoolVar(home, 0, 1);
00181           rel(home, r.var(), BOT_IMP, b, 1);
00182           break;
00183         case RM_PMI:
00184           b=BoolVar(home, 0, 1);
00185           rel(home, b, BOT_IMP, r.var(), 1);
00186           break;
00187         default:
00188           throw Gecode::Int::UnknownReifyMode("Set::rel");
00189         }
00190         BoolVarArgs p(1); p[0]=ne;
00191         BoolVarArgs n(1); n[0]=ss;
00192         clause(home, BOT_AND, p, n, b);
00193       }
00194       break;
00195     case IRT_LQ:
00196       {
00197         IntVar tmp(home, Int::Limits::min, Int::Limits::max);
00198         rel(home, tmp, IRT_LQ, x, r);
00199         Gecode::Set::Int::remax(home, s, tmp, r);
00200       }
00201       break;
00202     case IRT_LE:
00203       {
00204         IntVar tmp(home, Int::Limits::min, Int::Limits::max);
00205         rel(home, tmp, IRT_LE, x, r);
00206         Gecode::Set::Int::remax(home, s, tmp, r);
00207       }
00208       break;
00209     case IRT_GQ:
00210       {
00211         IntVar tmp(home, Int::Limits::min, Int::Limits::max);
00212         rel(home, tmp, IRT_GQ, x, r);
00213         Gecode::Set::Int::remin(home, s, tmp, r);
00214       }
00215       break;
00216     case IRT_GR:
00217       {
00218         IntVar tmp(home, Int::Limits::min, Int::Limits::max);
00219         rel(home, tmp, IRT_GR, x, r);
00220         Gecode::Set::Int::remin(home, s, tmp, r);
00221       }
00222       break;
00223     default:
00224       throw Int::UnknownRelation("Set::rel");
00225     }
00226   }
00227 
00228   void
00229   min(Home home, SetVar s, IntVar x) {
00230     GECODE_POST;
00231     GECODE_ES_FAIL(Set::Int::MinElement<Set::SetView>::post(home,s,x));
00232   }
00233 
00234   void
00235   notMin(Home home, SetVar s, IntVar x) {
00236     GECODE_POST;
00237     GECODE_ES_FAIL(Set::Int::NotMinElement<Set::SetView>::post(home,s,x));
00238   }
00239 
00240   void
00241   min(Home home, SetVar s, IntVar x, Reify r) {
00242     GECODE_POST;
00243     switch (r.mode()) {
00244     case RM_EQV:
00245       GECODE_ES_FAIL((Set::Int::ReMinElement<Set::SetView,RM_EQV>
00246                      ::post(home,s,x,r.var())));
00247       break;
00248     case RM_IMP:
00249       GECODE_ES_FAIL((Set::Int::ReMinElement<Set::SetView,RM_IMP>
00250                      ::post(home,s,x,r.var())));
00251       break;
00252     case RM_PMI:
00253       GECODE_ES_FAIL((Set::Int::ReMinElement<Set::SetView,RM_PMI>
00254                      ::post(home,s,x,r.var())));
00255       break;
00256     default: throw Gecode::Int::UnknownReifyMode("Set::min");
00257     }
00258   }
00259 
00260   void
00261   max(Home home, SetVar s, IntVar x) {
00262     GECODE_POST;
00263     GECODE_ES_FAIL(Set::Int::MaxElement<Set::SetView>::post(home,s,x));
00264   }
00265 
00266   void
00267   notMax(Home home, SetVar s, IntVar x) {
00268     GECODE_POST;
00269     GECODE_ES_FAIL(Set::Int::NotMaxElement<Set::SetView>::post(home,s,x));
00270   }
00271 
00272   void
00273   max(Home home, SetVar s, IntVar x, Reify r) {
00274     GECODE_POST;
00275     switch (r.mode()) {
00276     case RM_EQV:
00277       GECODE_ES_FAIL((Set::Int::ReMaxElement<Set::SetView,RM_EQV>
00278                      ::post(home,s,x,r.var())));
00279       break;
00280     case RM_IMP:
00281       GECODE_ES_FAIL((Set::Int::ReMaxElement<Set::SetView,RM_IMP>
00282                      ::post(home,s,x,r.var())));
00283       break;
00284     case RM_PMI:
00285       GECODE_ES_FAIL((Set::Int::ReMaxElement<Set::SetView,RM_PMI>
00286                      ::post(home,s,x,r.var())));
00287       break;
00288     default: throw Gecode::Int::UnknownReifyMode("Set::max");
00289     }
00290   }
00291 
00292   void weights(Home home, IntSharedArray elements, IntSharedArray weights,
00293                SetVar x, IntVar y) {
00294     GECODE_POST;
00295     GECODE_ES_FAIL(Set::Int::Weights<Set::SetView>::post(home,elements,
00296                                                               weights,x,y));
00297   }
00298 
00299 }
00300 
00301 // STATISTICS: set-post