channel-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 * Guido Tack <tack@gecode.org> 00005 * Christian Schulte <schulte@gecode.org> 00006 * Gabor Szokoli <szokoli@gecode.org> 00007 * 00008 * Copyright: 00009 * Guido Tack, 2004 00010 * Christian Schulte, 2004 00011 * Gabor Szokoli, 2004 00012 * 00013 * Last modified: 00014 * $Date: 2010-07-14 17:46:18 +0200 (Wed, 14 Jul 2010) $ by $Author: schulte $ 00015 * $Revision: 11192 $ 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.hh> 00043 00044 namespace Gecode { namespace Set { namespace Int { 00045 00046 template<class View> 00047 forceinline 00048 ChannelInt<View>::ChannelInt(Home home, 00049 ViewArray<Gecode::Int::IntView>& xs0, 00050 ViewArray<View>& ys0) 00051 : Propagator(home), xs(xs0), ys(ys0) { 00052 xs.subscribe(home,*this, Gecode::Int::PC_INT_DOM); 00053 ys.subscribe(home,*this, PC_SET_ANY); 00054 } 00055 00056 template<class View> 00057 forceinline 00058 ChannelInt<View>::ChannelInt(Space& home, bool share, ChannelInt& p) 00059 : Propagator(home,share,p) { 00060 xs.update(home,share,p.xs); 00061 ys.update(home,share,p.ys); 00062 } 00063 00064 template<class View> 00065 forceinline ExecStatus 00066 ChannelInt<View>::post(Home home, ViewArray<Gecode::Int::IntView>& xs, 00067 ViewArray<View>& ys) { 00068 // Sharing of ys is taken care of in the propagator: 00069 // The ys are propagated to be disjoint, so shared variables 00070 // result in failure. 00071 int xssize = xs.size(); 00072 for (int i=ys.size(); i--;) { 00073 GECODE_ME_CHECK(ys[i].exclude(home, xssize, Limits::max)); 00074 GECODE_ME_CHECK(ys[i].exclude(home, Limits::min, -1)); 00075 } 00076 int yssize = ys.size(); 00077 if (yssize > Gecode::Int::Limits::max) 00078 return ES_FAILED; 00079 for (int i=xs.size(); i--;) { 00080 GECODE_ME_CHECK(xs[i].gq(home, 0)); 00081 GECODE_ME_CHECK(xs[i].le(home, static_cast<int>(yssize))); 00082 } 00083 00084 (void) new (home) ChannelInt(home,xs,ys); 00085 return ES_OK; 00086 } 00087 00088 template<class View> 00089 PropCost 00090 ChannelInt<View>::cost(const Space&, const ModEventDelta&) const { 00091 return PropCost::quadratic(PropCost::LO, xs.size()+ys.size()); 00092 } 00093 00094 template<class View> 00095 forceinline size_t 00096 ChannelInt<View>::dispose(Space& home) { 00097 xs.cancel(home,*this, Gecode::Int::PC_INT_DOM); 00098 ys.cancel(home,*this, PC_SET_ANY); 00099 (void) Propagator::dispose(home); 00100 return sizeof(*this); 00101 } 00102 00103 template<class View> 00104 Actor* 00105 ChannelInt<View>::copy(Space& home, bool share) { 00106 return new (home) ChannelInt(home,share,*this); 00107 } 00108 00109 template<class View> 00110 ExecStatus 00111 ChannelInt<View>::propagate(Space& home, const ModEventDelta&) { 00112 int assigned = 0; 00113 for (int v=xs.size(); v--;) { 00114 if (xs[v].assigned()) { 00115 assigned += 1; 00116 for (int i=ys.size(); i--;) { 00117 if (i==xs[v].val()) { 00118 GECODE_ME_CHECK(ys[i].include(home, v)); 00119 } 00120 else { 00121 GECODE_ME_CHECK(ys[i].exclude(home, v)); 00122 } 00123 } 00124 } else { 00125 00126 for (int i=ys.size(); i--;) { 00127 if (ys[i].notContains(v)) { 00128 GECODE_ME_CHECK(xs[v].nq(home, i)); 00129 } 00130 if (ys[i].contains(v)) { 00131 GECODE_ME_CHECK(xs[v].eq(home, i)); 00132 } 00133 } 00134 00135 Gecode::Int::ViewRanges<Gecode::Int::IntView> xsv(xs[v]); 00136 int min = 0; 00137 for (; xsv(); ++xsv) { 00138 for (int i=min; i<xsv.min(); i++) { 00139 GECODE_ME_CHECK(ys[i].exclude(home, v)); 00140 } 00141 min = xsv.max() + 1; 00142 } 00143 for (int i=min; i<ys.size(); i++) { 00144 GECODE_ME_CHECK(ys[i].exclude(home, v)); 00145 } 00146 00147 } 00148 } 00149 00150 return (assigned==xs.size()) ? home.ES_SUBSUMED(*this) : ES_NOFIX; 00151 } 00152 00153 }}} 00154 00155 // STATISTICS: set-prop