Generated on Wed Jul 27 2011 15:08:42 for Gecode by doxygen 1.7.4
dom.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  *
00006  *  Contributing authors:
00007  *     Gabor Szokoli <szokoli@gecode.org>
00008  *
00009  *  Copyright:
00010  *     Guido Tack, 2004, 2005
00011  *
00012  *  Last modified:
00013  *     $Date: 2010-06-07 14:18:14 +0200 (Mon, 07 Jun 2010) $ by $Author: tack $
00014  *     $Revision: 11048 $
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 
00044 namespace Gecode {
00045 
00046   void
00047   dom(Home home, SetVar s, SetRelType r, int i) {
00048     Set::Limits::check(i, "Set::dom");
00049     IntSet d(i,i);
00050     dom(home, s, r, d);
00051   }
00052 
00053   void
00054   dom(Home home, SetVar s, SetRelType r, int i, int j) {
00055     Set::Limits::check(i, "Set::dom");
00056     Set::Limits::check(j, "Set::dom");
00057     IntSet d(i,j);
00058     dom(home, s, r, d);
00059   }
00060 
00061   void
00062   dom(Home home, SetVar s, SetRelType r, const IntSet& is) {
00063     Set::Limits::check(is, "Set::dom");
00064     if (home.failed()) return;
00065 
00066     Set::SetView _s(s);
00067 
00068     switch (r) {
00069     case SRT_EQ:
00070       {
00071         if (is.ranges() == 1) {
00072           GECODE_ME_FAIL(_s.include(home, is.min(), is.max()));
00073           GECODE_ME_FAIL(_s.intersect(home, is.min(), is.max()));
00074         } else {
00075           IntSetRanges rd1(is);
00076           GECODE_ME_FAIL(_s.includeI(home, rd1));
00077           IntSetRanges rd2(is);
00078           GECODE_ME_FAIL(_s.intersectI(home, rd2));
00079         }
00080       }
00081       break;
00082     case SRT_DISJ:
00083       {
00084         if (is.ranges() == 1) {
00085           GECODE_ME_FAIL(_s.exclude(home, is.min(), is.max()));
00086         } else {
00087           IntSetRanges rd(is);
00088           GECODE_ME_FAIL(_s.excludeI(home, rd));
00089         }
00090       }
00091       break;
00092     case SRT_NQ:
00093       {
00094         Set::ConstSetView cv(home, is);
00095         GECODE_ES_FAIL(
00096                        (Set::Rel::DistinctDoit<Set::SetView>::post(home, s,
00097                                                                    cv)));
00098       }
00099       break;
00100     case SRT_SUB:
00101       {
00102          if (is.ranges() == 1) {
00103            GECODE_ME_FAIL(_s.intersect(home, is.min(), is.max()));
00104          } else {
00105           IntSetRanges rd(is);
00106           GECODE_ME_FAIL(_s.intersectI(home, rd));
00107          }
00108       }
00109       break;
00110     case SRT_SUP:
00111       {
00112         if (is.ranges() == 1) {
00113           GECODE_ME_FAIL(_s.include(home, is.min(), is.max()));
00114         } else {
00115           IntSetRanges rd(is);
00116           GECODE_ME_FAIL(_s.includeI(home, rd));
00117         }
00118       }
00119       break;
00120     case SRT_CMPL:
00121       {
00122         if (is.ranges() == 1) {
00123           GECODE_ME_FAIL(_s.exclude(home, is.min(), is.max()));
00124           GECODE_ME_FAIL(
00125                          _s.include(home,
00126                                     Set::Limits::min,
00127                                     is.min()-1) );
00128           GECODE_ME_FAIL(
00129                          _s.include(home, is.max()+1,
00130                                     Set::Limits::max) );
00131         } else {
00132           IntSetRanges rd1(is);
00133           Set::RangesCompl<IntSetRanges > rdC1(rd1);
00134           GECODE_ME_FAIL(_s.includeI(home, rdC1));
00135           IntSetRanges rd2(is);
00136           Set::RangesCompl<IntSetRanges > rdC2(rd2);
00137           GECODE_ME_FAIL(_s.intersectI(home, rdC2));
00138         }
00139       }
00140       break;
00141     default:
00142       throw Set::UnknownRelation("Set::dom");
00143     }
00144   }
00145 
00146   void
00147   dom(Home home, SetVar s, SetRelType r, int i, BoolVar b) {
00148     Set::Limits::check(i, "Set::dom");
00149     IntSet d(i,i);
00150     dom(home, s, r, d, b);
00151   }
00152 
00153   void
00154   dom(Home home, SetVar s, SetRelType r, int i, int j, BoolVar b) {
00155     Set::Limits::check(i, "Set::dom");
00156     Set::Limits::check(j, "Set::dom");
00157     IntSet d(i,j);
00158     dom(home, s, r, d, b);
00159   }
00160 
00161   void
00162   dom(Home home, SetVar s, SetRelType r, const IntSet& is, BoolVar b) {
00163     Set::Limits::check(is, "Set::dom");
00164     if (home.failed()) return;
00165     switch (r) {
00166     case SRT_EQ:
00167       {
00168         Set::ConstSetView cv(home, is);
00169         GECODE_ES_FAIL(
00170                        (Set::Rel::ReEq<Set::SetView,
00171                         Set::ConstSetView>::post(home, s, cv, b)));
00172       }
00173       break;
00174     case SRT_NQ:
00175       {
00176         BoolVar notb(home,0,1);
00177         rel(home, b, IRT_NQ, notb);
00178         Set::ConstSetView cv(home, is);
00179         GECODE_ES_FAIL(
00180                        (Set::Rel::ReEq<Set::SetView,
00181                         Set::ConstSetView>::post(home, s, cv, notb)));
00182       }
00183       break;
00184     case SRT_SUB:
00185       {
00186         Set::ConstSetView cv(home, is);
00187         GECODE_ES_FAIL(
00188                        (Set::Rel::ReSubset<Set::SetView,Set::ConstSetView>
00189                         ::post(home, s, cv, b)));
00190       }
00191       break;
00192     case SRT_SUP:
00193       {
00194         Set::ConstSetView cv(home, is);
00195         GECODE_ES_FAIL(
00196                        (Set::Rel::ReSubset<Set::ConstSetView,Set::SetView>
00197                         ::post(home, cv, s, b)));
00198       }
00199       break;
00200     case SRT_DISJ:
00201       {
00202         // x||y <=> b is equivalent to
00203         // ( y <= complement(x) and x<=complement(y) ) <=> b
00204 
00205         // compute complement of is
00206         IntSetRanges dr1(is);
00207         Set::RangesCompl<IntSetRanges > dc1(dr1);
00208         IntSet dcompl(dc1);
00209         Set::ConstSetView cvcompl(home, dcompl);
00210         GECODE_ES_FAIL(
00211                        (Set::Rel::ReSubset<Set::SetView,Set::ConstSetView>
00212                         ::post(home, s, cvcompl, b)));
00213       }
00214       break;
00215     case SRT_CMPL:
00216       {
00217         Set::SetView sv(s);
00218 
00219         IntSetRanges dr1(is);
00220         Set::RangesCompl<IntSetRanges> dc1(dr1);
00221         IntSet dcompl(dc1);
00222         Set::ConstSetView cvcompl(home, dcompl);
00223 
00224         GECODE_ES_FAIL(
00225                        (Set::Rel::ReEq<Set::SetView,Set::ConstSetView>
00226                         ::post(home, sv, cvcompl, b)));
00227       }
00228       break;
00229     default:
00230       throw Set::UnknownRelation("Set::dom");
00231     }
00232   }
00233 
00234 }
00235 
00236 // STATISTICS: set-post