rel.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-03-03 17:40:32 +0100 (Wed, 03 Mar 2010) $ by $Author: schulte $ 00014 * $Revision: 10365 $ 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/rel.hh> 00042 #include <gecode/set/rel-op.hh> 00043 #include <gecode/set/int.hh> 00044 00045 namespace Gecode { 00046 using namespace Set; 00047 using namespace Set::Rel; 00048 using namespace Set::RelOp; 00049 00050 template<class View0, class View1> 00051 void 00052 rel_post(Home home, View0 x0, SetRelType r, View1 x1) { 00053 if (home.failed()) return; 00054 switch (r) { 00055 case SRT_EQ: 00056 { 00057 GECODE_ES_FAIL( 00058 (Eq<View0,View1>::post(home,x0,x1))); 00059 } 00060 break; 00061 case SRT_NQ: 00062 { 00063 GECODE_ES_FAIL( 00064 (Distinct<View0,View1>::post(home,x0,x1))); 00065 } 00066 break; 00067 case SRT_SUB: 00068 { 00069 GECODE_ES_FAIL( 00070 (Subset<View0,View1>::post(home, x0,x1))); 00071 } 00072 break; 00073 case SRT_SUP: 00074 { 00075 GECODE_ES_FAIL( 00076 (Subset<View1,View0>::post(home, x1,x0))); 00077 } 00078 break; 00079 case SRT_DISJ: 00080 { 00081 EmptyView emptyset; 00082 GECODE_ES_FAIL((SuperOfInter<View0,View1,EmptyView> 00083 ::post(home, x0, x1, emptyset))); 00084 } 00085 break; 00086 case SRT_CMPL: 00087 { 00088 ComplementView<View0> cx0(x0); 00089 GECODE_ES_FAIL( 00090 (Eq<ComplementView<View0>, View1> 00091 ::post(home, cx0, x1))); 00092 } 00093 break; 00094 default: 00095 throw UnknownRelation("Set::rel"); 00096 } 00097 } 00098 00099 template<class View0, class View1> 00100 void 00101 rel_re(Home home, View0 x, SetRelType r, View1 y, BoolVar b) { 00102 if (home.failed()) return; 00103 switch (r) { 00104 case SRT_EQ: 00105 { 00106 GECODE_ES_FAIL( 00107 (ReEq<View0,View1>::post(home, x,y,b))); 00108 } 00109 break; 00110 case SRT_NQ: 00111 { 00112 BoolVar notb(home, 0, 1); 00113 rel(home, b, IRT_NQ, notb); 00114 GECODE_ES_FAIL( 00115 (ReEq<View0,View1>::post(home,x,y,notb))); 00116 } 00117 break; 00118 case SRT_SUB: 00119 { 00120 GECODE_ES_FAIL( 00121 (ReSubset<View0,View1>::post(home, x,y,b))); 00122 } 00123 break; 00124 case SRT_SUP: 00125 { 00126 GECODE_ES_FAIL( 00127 (ReSubset<View1,View0>::post(home, y,x,b))); 00128 } 00129 break; 00130 case SRT_DISJ: 00131 { 00132 // x||y <=> b is equivalent to 00133 // ( y <= complement(x) ) <=> b 00134 00135 ComplementView<View0> xc(x); 00136 GECODE_ES_FAIL( 00137 (ReSubset<View1,ComplementView<View0> > 00138 ::post(home, y, xc, b))); 00139 } 00140 break; 00141 case SRT_CMPL: 00142 { 00143 ComplementView<View0> xc(x); 00144 GECODE_ES_FAIL( 00145 (ReEq<ComplementView<View0>,View1> 00146 ::post(home, xc, y, b))); 00147 } 00148 break; 00149 default: 00150 throw UnknownRelation("Set::rel"); 00151 } 00152 } 00153 00154 void 00155 rel(Home home, SetVar x, SetRelType r, SetVar y) { 00156 rel_post<SetView,SetView>(home,x,r,y); 00157 } 00158 00159 void 00160 rel(Home home, SetVar s, SetRelType r, IntVar x) { 00161 Gecode::Int::IntView xv(x); 00162 SingletonView xsingle(xv); 00163 rel_post<SetView,SingletonView>(home,s,r,xv); 00164 } 00165 00166 void 00167 rel(Home home, IntVar x, SetRelType r, SetVar s) { 00168 switch (r) { 00169 case SRT_SUB: 00170 rel(home, s, SRT_SUP, x); 00171 break; 00172 case SRT_SUP: 00173 rel(home, s, SRT_SUB, x); 00174 break; 00175 default: 00176 rel(home, s, r, x); 00177 } 00178 } 00179 00180 void 00181 rel(Home home, SetVar x, SetRelType r, SetVar y, BoolVar b) { 00182 rel_re<SetView,SetView>(home,x,r,y,b); 00183 } 00184 00185 void 00186 rel(Home home, SetVar s, SetRelType r, IntVar x, BoolVar b) { 00187 Gecode::Int::IntView xv(x); 00188 SingletonView xsingle(xv); 00189 rel_re<SetView,SingletonView>(home,s,r,xsingle,b); 00190 } 00191 00192 void 00193 rel(Home home, IntVar x, SetRelType r, SetVar s, BoolVar b) { 00194 switch (r) { 00195 case SRT_SUB: 00196 rel(home, s, SRT_SUP, x, b); 00197 break; 00198 case SRT_SUP: 00199 rel(home, s, SRT_SUB, x, b); 00200 break; 00201 default: 00202 rel(home, s, r, x, b); 00203 } 00204 } 00205 00206 } 00207 00208 // STATISTICS: set-post