sequence.cpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * David Rijsman <David.Rijsman@quintiq.com> 00005 * 00006 * Contributing authors: 00007 * Christian Schulte <schulte@gecode.org> 00008 * 00009 * Copyright: 00010 * David Rijsman, 2009 00011 * Christian Schulte, 2009 00012 * 00013 * Last modified: 00014 * $Date: 2010-03-03 17:40:32 +0100 (Wed, 03 Mar 2010) $ 00015 * $Revision: 10365 $ 00016 * 00017 * This file is part of Gecode, the generic constraint 00018 * development environment: 00019 * http://www.gecode.org 00020 * 00021 * Permission is hereby granted, free of charge, to any person obtaining 00022 * a copy of this software and associated documentation files (the 00023 * "Software"), to deal in the Software without restriction, including 00024 * without limitation the rights to use, copy, modify, merge, publish, 00025 * distribute, sublicense, and/or sell copies of the Software, and to 00026 * permit persons to whom the Software is furnished to do so, subject to 00027 * the following conditions: 00028 * 00029 * The above copyright notice and this permission notice shall be 00030 * included in all copies or substantial portions of the Software. 00031 * 00032 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00033 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00034 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00035 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00036 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00037 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00038 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 00039 * 00040 */ 00041 00042 #include <gecode/int/sequence.hh> 00043 00044 #include <algorithm> 00045 00046 namespace Gecode { 00047 00048 using namespace Int; 00049 00050 void 00051 sequence(Home home, const IntVarArgs& x, const IntSet &s, 00052 int q, int l, int u, IntConLevel) { 00053 Limits::check(s.min(),"Int::sequence"); 00054 Limits::check(s.max(),"Int::sequence"); 00055 00056 if (x.size() == 0) 00057 throw TooFewArguments("Int::sequence"); 00058 00059 Limits::check(q,"Int::sequence"); 00060 Limits::check(l,"Int::sequence"); 00061 Limits::check(u,"Int::sequence"); 00062 00063 if (x.same(home)) 00064 throw ArgumentSame("Int::sequence"); 00065 00066 if ((q < 1) || (q > x.size())) 00067 throw Exception("Int::sequence","1<=q<=|x| invalid"); 00068 00069 if (home.failed()) 00070 return; 00071 00072 // Normalize l and u 00073 l=std::max(0,l); u=std::min(q,u); 00074 00075 // Lower bound of values taken can never exceed upper bound 00076 if (u < l) { 00077 home.fail(); return; 00078 } 00079 00080 // Already subsumed as any number of values taken is okay 00081 if ((0 == l) && (q == u)) 00082 return; 00083 00084 // All variables must take a value in s 00085 if (l == q) { 00086 for (int i=x.size(); i--; ) { 00087 IntView xv(x[i]); 00088 IntSetRanges ris(s); 00089 GECODE_ME_FAIL(xv.inter_r(home,ris,false)); 00090 } 00091 return; 00092 } 00093 00094 // No variable can take a value in s 00095 if (0 == u) { 00096 for (int i=x.size(); i--; ) { 00097 IntView xv(x[i]); 00098 IntSetRanges ris(s); 00099 GECODE_ME_FAIL(xv.minus_r(home,ris,false)); 00100 } 00101 return; 00102 } 00103 00104 ViewArray<IntView> xv(home,x); 00105 if (s.size() == 1) { 00106 GECODE_ES_FAIL( 00107 (Sequence::Sequence<IntView,int>::post 00108 (home,xv,s.min(),q,l,u))); 00109 } else { 00110 GECODE_ES_FAIL( 00111 (Sequence::Sequence<IntView,IntSet>::post 00112 (home,xv,s,q,l,u))); 00113 } 00114 } 00115 00116 void 00117 sequence(Home home, const BoolVarArgs& x, const IntSet& s, 00118 int q, int l, int u, IntConLevel) { 00119 if ((s.min() < 0) || (s.max() > 1)) 00120 throw NotZeroOne("Int::sequence"); 00121 00122 if (x.size() == 0) 00123 throw TooFewArguments("Int::sequence"); 00124 00125 Limits::check(q,"Int::sequence"); 00126 Limits::check(l,"Int::sequence"); 00127 Limits::check(u,"Int::sequence"); 00128 00129 if (x.same(home)) 00130 throw ArgumentSame("Int::sequence"); 00131 00132 if ((q < 1) || (q > x.size())) 00133 throw Exception("Int::sequence","1<=q<=|x| invalid"); 00134 00135 if (home.failed()) 00136 return; 00137 00138 // Normalize l and u 00139 l=std::max(0,l); u=std::min(q,u); 00140 00141 // Lower bound of values taken can never exceed upper bound 00142 if (u < l) { 00143 home.fail(); return; 00144 } 00145 00146 // Already subsumed as any number of values taken is okay 00147 if ((0 == l) && (q == u)) 00148 return; 00149 00150 // Check whether the set is {0,1}, then the number of values taken is q 00151 if ((s.min() == 0) && (s.max() == 1)) { 00152 if ((l > 0) || (u < q)) 00153 home.failed(); 00154 return; 00155 } 00156 assert(s.min() == s.max()); 00157 00158 // All variables must take a value in s 00159 if (l == q) { 00160 if (s.min() == 0) { 00161 for (int i=x.size(); i--; ) { 00162 BoolView xv(x[i]); GECODE_ME_FAIL(xv.zero(home)); 00163 } 00164 } else { 00165 assert(s.min() == 1); 00166 for (int i=x.size(); i--; ) { 00167 BoolView xv(x[i]); GECODE_ME_FAIL(xv.one(home)); 00168 } 00169 } 00170 return; 00171 } 00172 00173 // No variable can take a value in s 00174 if (0 == u) { 00175 if (s.min() == 0) { 00176 for (int i=x.size(); i--; ) { 00177 BoolView xv(x[i]); GECODE_ME_FAIL(xv.one(home)); 00178 } 00179 } else { 00180 assert(s.min() == 1); 00181 for (int i=x.size(); i--; ) { 00182 BoolView xv(x[i]); GECODE_ME_FAIL(xv.zero(home)); 00183 } 00184 } 00185 return; 00186 } 00187 00188 ViewArray<BoolView> xv(home,x); 00189 00190 GECODE_ES_FAIL( 00191 (Sequence::Sequence<BoolView,int>::post 00192 (home,xv,s.min(),q,l,u))); 00193 } 00194 00195 } 00196 00197 // STATISTICS: int-post