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