int.hpp
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-10 11:36:44 +0100 (Wed, 10 Mar 2010) $ 00015 * $Revision: 10387 $ 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 namespace Gecode { namespace Int { namespace Sequence { 00043 00044 template<class View, class Val> 00045 forceinline 00046 Sequence<View,Val>::Sequence(Home home, ViewArray<View>& x0, Val s0, 00047 int q0, int l0, int u0) 00048 : Propagator(home), x(x0), s(s0), q(q0), l(l0), u(u0), 00049 vvsamax(home,x,s0,q0), vvsamin(home,x,s0,q0), ac(home) { 00050 home.notice(*this,AP_DISPOSE); 00051 for (int i=x.size(); i--; ) { 00052 if (undecided(x[i],s)) { 00053 x[i].subscribe(home,*new (home) SupportAdvisor<View>(home,*this,ac,i)); 00054 } else { 00055 x[i].schedule(home,*this,x[i].assigned() ? ME_INT_VAL : ME_INT_BND); 00056 } 00057 } 00058 } 00059 00060 template<class View, class Val> 00061 forceinline 00062 Sequence<View,Val>::Sequence(Space& home, bool share, Sequence& p) 00063 : Propagator(home,share,p), s(p.s), q(p.q), l(p.l), u(p.u), 00064 vvsamax(), vvsamin() { 00065 x.update(home,share,p.x); 00066 ac.update(home,share,p.ac); 00067 vvsamax.update(home,share,p.vvsamax); 00068 vvsamin.update(home,share,p.vvsamin); 00069 } 00070 00071 template<class View,class Val> 00072 ExecStatus 00073 Sequence<View,Val>::advise(Space& home, Advisor& _a, const Delta& d) { 00074 SupportAdvisor<View>& a = static_cast<SupportAdvisor<View>&>(_a); 00075 ExecStatus status = vvsamax.advise(home,x,s,q,a.i,d); 00076 if ( ES_NOFIX == vvsamin.advise(home,x,s,q,a.i,d) ) { 00077 status = ES_NOFIX; 00078 } 00079 00080 if (!undecided(x[a.i],s)) { 00081 if (!x[a.i].assigned()) 00082 x[a.i].cancel(home,a); 00083 00084 if ( ES_NOFIX == status ) { 00085 return home.ES_NOFIX_DISPOSE(ac,a); 00086 } else { 00087 return home.ES_FIX_DISPOSE(ac,a); 00088 } 00089 } 00090 00091 return status; 00092 } 00093 00094 template<class View, class Val> 00095 forceinline size_t 00096 Sequence<View,Val>::dispose(Space& home) { 00097 home.ignore(*this,AP_DISPOSE); 00098 ac.dispose(home); 00099 s.~Val(); 00100 (void) Propagator::dispose(home); 00101 return sizeof(*this); 00102 } 00103 00104 template<class View, class Val> 00105 forceinline ExecStatus 00106 Sequence<View,Val>::check(Space& home, ViewArray<View>& x, Val s, int q, int l, int u) { 00107 Region r(home); 00108 // could do this with an array of length q... 00109 int* upper = r.alloc<int>(x.size()+1); 00110 int* lower = r.alloc<int>(x.size()+1); 00111 upper[0] = 0; 00112 lower[0] = 0; 00113 for ( int j=0; j<x.size(); j++ ) { 00114 upper[j+1] = upper[j]; 00115 lower[j+1] = lower[j]; 00116 if (includes(x[j],s)) { 00117 upper[j+1] += 1; 00118 } else if (excludes(x[j],s)) { 00119 lower[j+1] += 1; 00120 } 00121 if ( j+1 >= q && (q - l < lower[j+1] - lower[j+1-q] || upper[j+1] - upper[j+1-q] > u) ) { 00122 return ES_FAILED; 00123 } 00124 } 00125 return ES_OK; 00126 } 00127 00128 template<class View, class Val> 00129 ExecStatus 00130 Sequence<View,Val>::post(Home home, ViewArray<View>& x, Val s, int q, int l, int u) { 00131 GECODE_ME_CHECK(check(home,x,s,q,l,u)); 00132 Sequence<View,Val>* p = new (home) Sequence<View,Val>(home,x,s,q,l,u); 00133 00134 GECODE_ME_CHECK(p->vvsamax.propagate(home,x,s,q,l,u)); 00135 GECODE_ME_CHECK(p->vvsamin.propagate(home,x,s,q,l,u)); 00136 00137 return ES_OK; 00138 } 00139 00140 template<class View, class Val> 00141 Actor* 00142 Sequence<View,Val>::copy(Space& home, bool share) { 00143 return new (home) Sequence<View,Val>(home,share,*this); 00144 } 00145 00146 template<class View, class Val> 00147 PropCost 00148 Sequence<View,Val>::cost(const Space&, const ModEventDelta&) const { 00149 return PropCost::cubic(PropCost::HI,x.size()); 00150 } 00151 00152 template<class View, class Val> 00153 ExecStatus 00154 Sequence<View,Val>::propagate(Space& home, const ModEventDelta&) { 00155 GECODE_ME_CHECK(vvsamax.propagate(home,x,s,q,l,u)); 00156 GECODE_ME_CHECK(vvsamin.propagate(home,x,s,q,l,u)); 00157 00158 for (int i=x.size(); i--; ) 00159 if (undecided(x[i],s)) 00160 return ES_FIX; 00161 00162 return home.ES_SUBSUMED(*this); 00163 } 00164 00165 }}} 00166 00167 // STATISTICS: int-prop 00168