rel-op-const.cc

00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Guido Tack <tack@gecode.org>
00005  *
00006  *  Contributing authors:
00007  *     Gabor Szokoli <szokoli@gecode.org>
00008  *
00009  *  Copyright:
00010  *     Guido Tack, 2004, 2005
00011  *
00012  *  Last modified:
00013  *     $Date: 2008-02-20 18:17:24 +0100 (Wed, 20 Feb 2008) $ by $Author: tack $
00014  *     $Revision: 6253 $
00015  *
00016  *  This file is part of Gecode, the generic constraint
00017  *  development environment:
00018  *     http://www.gecode.org
00019  *
00020  *  Permission is hereby granted, free of charge, to any person obtaining
00021  *  a copy of this software and associated documentation files (the
00022  *  "Software"), to deal in the Software without restriction, including
00023  *  without limitation the rights to use, copy, modify, merge, publish,
00024  *  distribute, sublicense, and/or sell copies of the Software, and to
00025  *  permit persons to whom the Software is furnished to do so, subject to
00026  *  the following conditions:
00027  *
00028  *  The above copyright notice and this permission notice shall be
00029  *  included in all copies or substantial portions of the Software.
00030  *
00031  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00032  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00033  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00034  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00035  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00036  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00037  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00038  *
00039  */
00040 
00041 #include "gecode/set.hh"
00042 #include "gecode/set/rel.hh"
00043 #include "gecode/set/rel-op.hh"
00044 
00045 namespace Gecode {
00046   using namespace Gecode::Set;
00047   using namespace Gecode::Set::Rel;
00048   using namespace Gecode::Set::RelOp;
00049 
00050   void
00051   rel(Space* home, const IntSet& x, SetOpType op, SetVar y, SetRelType r,
00052       SetVar z) {
00053     Set::Limits::check(x, "Set::rel");
00054     ConstantView xv(home, x);
00055     rel_op_post<ConstantView,SetView,SetView>(home, xv, op, y, r, z);
00056   }  
00057 
00058   void
00059   rel(Space* home, SetVar x, SetOpType op, const IntSet& y, SetRelType r,
00060       SetVar z) {
00061     Set::Limits::check(y, "Set::rel");
00062     ConstantView yv(home, y);
00063 
00064     if (op==SOT_MINUS) {
00065       switch(r) {
00066       case SRT_EQ:
00067         {
00068           GlbRanges<ConstantView> yr(yv);
00069           RangesCompl<GlbRanges<ConstantView> > yrc(yr);
00070           IntSet yc(yrc);
00071           ConstantView cy(home, yc);
00072           GECODE_ES_FAIL(home,
00073                          (Intersection<ConstantView,
00074                           SetView,SetView>
00075                           ::post(home,cy,x,z)));
00076         }
00077         break;
00078       case SRT_NQ:
00079         {
00080           SetVar tmp(home);
00081           GECODE_ES_FAIL(home,
00082                          (Distinct<SetView,SetView>
00083                           ::post(home,z,tmp)));
00084           GlbRanges<ConstantView> yr(yv);
00085           RangesCompl<GlbRanges<ConstantView> > yrc(yr);
00086           IntSet yc(yrc);
00087           ConstantView cy(home, yc);
00088           GECODE_ES_FAIL(home,
00089                          (Intersection<ConstantView,
00090                           SetView,SetView>
00091                           ::post(home,cy,x,tmp)));
00092         }
00093         break;
00094       case SRT_SUB:
00095         {
00096           GlbRanges<ConstantView> yr(yv);
00097           RangesCompl<GlbRanges<ConstantView> > yrc(yr);
00098           IntSet yc(yrc);
00099           ConstantView cy(home, yc);
00100           GECODE_ES_FAIL(home,
00101                          (SuperOfInter<ConstantView,SetView,SetView>
00102                           ::post(home,cy,x,z)));
00103 
00104         }
00105         break;
00106       case SRT_SUP:
00107         {
00108           SetVar tmp(home);
00109           GECODE_ES_FAIL(home,
00110                          (SubSet<SetView,SetView>::post(home,z,tmp)));
00111           
00112           GlbRanges<ConstantView> yr(yv);
00113           RangesCompl<GlbRanges<ConstantView> > yrc(yr);
00114           IntSet yc(yrc);
00115           ConstantView cy(home, yc);
00116 
00117           SetView xv(x);
00118           GECODE_ES_FAIL(home,
00119                          (Intersection<ConstantView,
00120                           SetView,SetView>
00121                           ::post(home,cy,xv,tmp)));
00122         }
00123         break;
00124       case SRT_DISJ:
00125         {
00126           SetVar tmp(home);
00127           EmptyView emptyset;
00128           GECODE_ES_FAIL(home,(SuperOfInter<SetView,SetView,EmptyView>
00129                                ::post(home, z, tmp, emptyset)));
00130 
00131           GlbRanges<ConstantView> yr(yv);
00132           RangesCompl<GlbRanges<ConstantView> > yrc(yr);
00133           IntSet yc(yrc);
00134           ConstantView cy(home, yc);
00135           GECODE_ES_FAIL(home,
00136                          (Intersection<ConstantView,
00137                           SetView,SetView>
00138                           ::post(home,cy,x,tmp)));
00139         }
00140         break;
00141       case SRT_CMPL:
00142         {
00143           SetView xv(x);
00144           ComplementView<SetView> cx(xv);
00145           GECODE_ES_FAIL(home,
00146                          (Union<ConstantView,
00147                           ComplementView<SetView>,
00148                           SetView>::post(home, yv, cx, z)));
00149         }
00150         break;
00151       }
00152     } else {
00153       rel_op_post<ConstantView,SetView,SetView>(home, yv, op, x, r, z);
00154     }
00155   }  
00156 
00157   void
00158   rel(Space* home, SetVar x, SetOpType op, SetVar y, SetRelType r,
00159       const IntSet& z) {
00160     Set::Limits::check(z, "Set::rel");
00161     if (r == SRT_CMPL) {
00162       IntSetRanges zr(z);
00163       RangesCompl<IntSetRanges> zrc(zr);
00164       IntSet zc(zrc);
00165       ConstantView cz(home, zc);
00166       rel_eq<SetView,SetView,ConstantView>(home, x, op, y, cz);
00167     } else {
00168       ConstantView zv(home, z);
00169       rel_op_post_nocompl<SetView,SetView,ConstantView>(home, x, op, y, r, zv);
00170     }
00171   }  
00172 
00173   void
00174   rel(Space* home, const IntSet& x, SetOpType op, SetVar y, SetRelType r,
00175       const IntSet& z) {
00176     Set::Limits::check(x, "Set::rel");
00177     Set::Limits::check(z, "Set::rel");
00178     ConstantView xv(home, x);
00179     if (r == SRT_CMPL) {
00180       IntSetRanges zr(z);
00181       RangesCompl<IntSetRanges> zrc(zr);
00182       IntSet zc(zrc);
00183       ConstantView cz(home, zc);
00184       rel_eq<ConstantView,SetView,ConstantView>(home, xv, op, y, cz);
00185     } else {
00186       ConstantView zv(home, z);
00187       rel_op_post_nocompl<ConstantView,SetView,ConstantView>(home, xv, op, y, r, zv);
00188     }
00189   }  
00190 
00191   void
00192   rel(Space* home, SetVar x, SetOpType op, const IntSet& y, SetRelType r,
00193       const IntSet& z) {
00194     Set::Limits::check(y, "Set::rel");
00195     Set::Limits::check(z, "Set::rel");
00196     ConstantView yv(home, y);
00197     ConstantView zv(home, z);
00198 
00199     if (op==SOT_MINUS) {
00200       switch(r) {
00201       case SRT_EQ:
00202         {
00203           GlbRanges<ConstantView> yr(yv);
00204           RangesCompl<GlbRanges<ConstantView> > yrc(yr);
00205           IntSet yc(yrc);
00206           ConstantView cy(home, yc);
00207           GECODE_ES_FAIL(home,
00208                          (Intersection<ConstantView,
00209                           SetView,ConstantView>
00210                           ::post(home,cy,x,zv)));
00211         }
00212         break;
00213       case SRT_NQ:
00214         {
00215           SetVar tmp(home);
00216           GECODE_ES_FAIL(home,
00217                          (Distinct<SetView,ConstantView>
00218                           ::post(home,tmp,zv)));
00219           GlbRanges<ConstantView> yr(yv);
00220           RangesCompl<GlbRanges<ConstantView> > yrc(yr);
00221           IntSet yc(yrc);
00222           ConstantView cy(home, yc);
00223           GECODE_ES_FAIL(home,
00224                          (Intersection<ConstantView,
00225                           SetView,SetView>
00226                           ::post(home,cy,x,tmp)));
00227         }
00228         break;
00229       case SRT_SUB:
00230         {
00231           GlbRanges<ConstantView> yr(yv);
00232           RangesCompl<GlbRanges<ConstantView> > yrc(yr);
00233           IntSet yc(yrc);
00234           ConstantView cy(home, yc);
00235           GECODE_ES_FAIL(home,
00236                          (SuperOfInter<ConstantView,SetView,ConstantView>
00237                           ::post(home,cy,x,zv)));
00238 
00239         }
00240         break;
00241       case SRT_SUP:
00242         {
00243           // z <= tmp
00244           SetVar tmp(home,z,Limits::min, Limits::max);
00245           SetView xv(x);
00246 
00247           GlbRanges<ConstantView> yr(yv);
00248           RangesCompl<GlbRanges<ConstantView> > yrc(yr);
00249           IntSet yc(yrc);
00250           ConstantView cy(home, yc);
00251           
00252           GECODE_ES_FAIL(home,
00253                          (Intersection<ConstantView,
00254                           SetView,SetView>
00255                           ::post(home,cy,xv,tmp)));
00256         }
00257         break;
00258       case SRT_DISJ:
00259         {
00260           SetVar tmp(home);
00261           SetView tmpv(tmp);
00262           IntSetRanges zi(z);
00263           GECODE_ME_FAIL(home, tmpv.excludeI(home, zi));
00264           
00265           GlbRanges<ConstantView> yr(yv);
00266           RangesCompl<GlbRanges<ConstantView> > yrc(yr);
00267           IntSet yc(yrc);
00268           ConstantView cy(home, yc);
00269           GECODE_ES_FAIL(home,
00270                          (Intersection<ConstantView,
00271                           SetView,SetView>
00272                           ::post(home,cy,x,tmp)));
00273         }
00274         break;
00275       case SRT_CMPL:
00276         {
00277           SetView xv(x);
00278           ComplementView<SetView> cx(xv);
00279           GECODE_ES_FAIL(home,
00280                          (Union<ConstantView,
00281                           ComplementView<SetView>,
00282                           ConstantView>::post(home, yv, cx, zv)));
00283         }
00284         break;
00285       }
00286     } else {
00287       if (r == SRT_CMPL) {
00288         IntSetRanges zr(z);
00289         RangesCompl<IntSetRanges> zrc(zr);
00290         IntSet zc(zrc);
00291         ConstantView cz(home, zc);
00292         rel_eq<ConstantView,SetView,ConstantView>(home, yv, op, x, cz);
00293       } else {
00294         rel_op_post_nocompl<ConstantView,SetView,ConstantView>(home, yv, op, x, r, zv);
00295       }
00296     }
00297   }  
00298 
00299   namespace {
00300 
00301     GECODE_REGISTER3(RelOp::Union<ConstantView, ComplementView<SetView>, ConstantView>);
00302     GECODE_REGISTER3(RelOp::Union<ConstantView, ComplementView<SetView>, SetView>);
00303     GECODE_REGISTER3(RelOp::Union<ConstantView, SetView, ComplementView<SetView> >);
00304     GECODE_REGISTER3(RelOp::Union<ConstantView, SetView, ConstantView>);
00305     GECODE_REGISTER3(RelOp::Union<ConstantView, SetView, SetView>);
00306     GECODE_REGISTER3(RelOp::Union<SetView, SetView, ConstantView>);
00307 
00308     GECODE_REGISTER3(RelOp::Intersection<ConstantView, ComplementView<SetView>, ConstantView>);
00309     GECODE_REGISTER3(RelOp::Intersection<ConstantView, ComplementView<SetView>, SetView>);
00310     GECODE_REGISTER3(RelOp::Intersection<ConstantView, ComplementView<SetView>, ComplementView<SetView> >);
00311     GECODE_REGISTER3(RelOp::Intersection<ConstantView, SetView, ComplementView<SetView> >);
00312     GECODE_REGISTER3(RelOp::Intersection<ConstantView, SetView, ConstantView>);
00313     GECODE_REGISTER3(RelOp::Intersection<ConstantView, SetView, SetView>);
00314     GECODE_REGISTER3(RelOp::Intersection<SetView, ComplementView<SetView>, ConstantView>);
00315     GECODE_REGISTER3(RelOp::Intersection<SetView, SetView, ConstantView>);
00316 
00317     GECODE_REGISTER3(RelOp::SubOfUnion<ConstantView, SetView, ConstantView>);
00318     GECODE_REGISTER3(RelOp::SubOfUnion<ConstantView, SetView, SetView>);
00319     GECODE_REGISTER3(RelOp::SubOfUnion<SetView, SetView, ConstantView>);
00320 
00321     GECODE_REGISTER3(RelOp::SuperOfInter<ConstantView, ComplementView<SetView>, ConstantView>);
00322     GECODE_REGISTER3(RelOp::SuperOfInter<ConstantView, ComplementView<SetView>, SetView>);
00323     GECODE_REGISTER3(RelOp::SuperOfInter<ConstantView, SetView, EmptyView>);
00324     GECODE_REGISTER3(RelOp::SuperOfInter<ConstantView, SetView, ConstantView>);
00325     GECODE_REGISTER3(RelOp::SuperOfInter<ConstantView, SetView, SetView>);
00326     GECODE_REGISTER3(RelOp::SuperOfInter<SetView, ComplementView<SetView>, ConstantView>);
00327     GECODE_REGISTER3(RelOp::SuperOfInter<SetView, SetView, ConstantView>);
00328   }
00329 
00330 }
00331 
00332 // STATISTICS: set-post