Generated on Mon May 10 06:46:34 2010 for Gecode by doxygen 1.6.3

link-multi.cpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Christian Schulte, 2007
00008  *
00009  *  Last modified:
00010  *     $Date: 2010-03-03 17:32:21 +0100 (Wed, 03 Mar 2010) $ by $Author: schulte $
00011  *     $Revision: 10364 $
00012  *
00013  *  This file is part of Gecode, the generic constraint
00014  *  development environment:
00015  *     http://www.gecode.org
00016  *
00017  *  Permission is hereby granted, free of charge, to any person obtaining
00018  *  a copy of this software and associated documentation files (the
00019  *  "Software"), to deal in the Software without restriction, including
00020  *  without limitation the rights to use, copy, modify, merge, publish,
00021  *  distribute, sublicense, and/or sell copies of the Software, and to
00022  *  permit persons to whom the Software is furnished to do so, subject to
00023  *  the following conditions:
00024  *
00025  *  The above copyright notice and this permission notice shall be
00026  *  included in all copies or substantial portions of the Software.
00027  *
00028  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00029  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00030  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00031  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00032  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00033  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00034  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00035  *
00036  */
00037 
00038 #include <gecode/int/channel.hh>
00039 
00040 namespace Gecode { namespace Int { namespace Channel {
00041 
00043   class BoolIter {
00044   private:
00046     const ViewArray<BoolView>& x;
00048     const int o;
00050     int i;
00051   public:
00053     BoolIter(const ViewArray<BoolView>& x0, int o0);
00055     bool operator ()(void) const;
00057     int val(void) const;
00059     void operator ++(void);
00060   };
00061 
00062   forceinline
00063   BoolIter::BoolIter(const ViewArray<BoolView>& x0, int o0) :
00064     x(x0), o(o0), i(0) {
00065     while ((i<x.size()) && !x[i].zero())
00066       i++;
00067   }
00068   forceinline bool
00069   BoolIter::operator ()(void) const {
00070     return i<x.size();
00071   }
00072   forceinline int
00073   BoolIter::val(void) const {
00074     assert(x[i].zero());
00075     return i+o;
00076   }
00077   forceinline void
00078   BoolIter::operator ++(void) {
00079     do {
00080       i++;
00081     } while ((i<x.size()) && !x[i].zero());
00082   }
00083 
00084 
00085   forceinline
00086   LinkMulti::LinkMulti(Space& home, bool share, LinkMulti& p)
00087     : MixNaryOnePropagator<BoolView,PC_BOOL_VAL,IntView,PC_INT_DOM>
00088   (home,share,p), o(p.o) {}
00089 
00090   Actor*
00091   LinkMulti::copy(Space& home, bool share) {
00092     return new (home) LinkMulti(home,share,*this);
00093   }
00094 
00095   PropCost
00096   LinkMulti::cost(const Space&, const ModEventDelta& med) const {
00097     if (IntView::me(med) == ME_INT_VAL)
00098       return PropCost::unary(PropCost::LO);
00099     else
00100       return PropCost::linear(PropCost::LO, x.size());
00101   }
00102 
00103   ExecStatus
00104   LinkMulti::propagate(Space& home, const ModEventDelta& med) {
00105     int n = x.size();
00106 
00107     // Always maintain the invariant that y lies inside the x-array
00108     assert((y.min()-o >= 0) && (y.max()-o < n));
00109 
00110     if (y.assigned()) {
00111       int j=y.val()-o;
00112       GECODE_ME_CHECK(x[j].one(home));
00113       for (int i=0; i<j; i++)
00114         GECODE_ME_CHECK(x[i].zero(home));
00115       for (int i=j+1; i<n; i++)
00116         GECODE_ME_CHECK(x[i].zero(home));
00117       return home.ES_SUBSUMED(*this);
00118     }
00119 
00120   redo:
00121 
00122     // Assign all Boolean views to zero that are outside bounds
00123     {
00124       int min=y.min()-o;
00125       for (int i=0; i<min; i++)
00126         GECODE_ME_CHECK(x[i].zero(home));
00127       x.drop_fst(min); o += min; n = x.size();
00128 
00129       int max=y.max()-o;
00130       for (int i=max+1; i<n; i++)
00131         GECODE_ME_CHECK(x[i].zero(home));
00132       x.drop_lst(max); n = x.size();
00133     }
00134 
00135     {
00136       // Remove zeros on the left
00137       int i=0;
00138       while ((i < n) && x[i].zero()) i++;
00139       if (i >= n)
00140         return ES_FAILED;
00141       x.drop_fst(i); o += i; n = x.size();
00142     }
00143 
00144     {
00145       // Remove zeros on the right
00146       int i=n-1;
00147       while ((i >= 0) && x[i].zero()) i--;
00148       assert(i >= 0);
00149       x.drop_lst(i); n = x.size();
00150     }
00151 
00152     assert(n >= 1);
00153 
00154     // Is there only one left?
00155     if (n == 1) {
00156       GECODE_ME_CHECK(x[0].one(home));
00157       GECODE_ME_CHECK(y.eq(home,o));
00158       return home.ES_SUBSUMED(*this);
00159     }
00160 
00161     // Update bounds
00162     GECODE_ME_CHECK(y.gq(home,o));
00163     GECODE_ME_CHECK(y.lq(home,o+n-1));
00164     if ((y.min() > o) || (y.max() < o+n-1))
00165       goto redo;
00166 
00167     // Check whether there is a one somewhere else
00168     for (int i=n; i--; )
00169       if (x[i].one()) {
00170         for (int j=0; j<i; j++)
00171           GECODE_ME_CHECK(x[j].zero(home));
00172         for (int j=i+1; j<n; j++)
00173           GECODE_ME_CHECK(x[j].zero(home));
00174         GECODE_ME_CHECK(y.eq(home,i+o));
00175         return home.ES_SUBSUMED(*this);
00176       }
00177 
00178     assert((n >= 2) && x[0].none() && x[n-1].none());
00179     assert((y.min()-o == 0) && (y.max()-o == n-1));
00180 
00181     // Propagate from y to Boolean views
00182     if ((IntView::me(med) == ME_INT_BND) || (IntView::me(med) == ME_INT_DOM)) {
00183       ViewValues<IntView> v(y);
00184       int i=0;
00185       do {
00186         int j = v.val()-o;
00187         if (i < j) {
00188           GECODE_ME_CHECK(x[i].zero(home));
00189           ++i;
00190         } else if (i > j) {
00191           ++v;
00192         } else {
00193           assert(i == j);
00194           ++i; ++v;
00195         }
00196       } while (v() && (i < n));
00197     }
00198 
00199     // Propagate from Boolean views to y
00200     if (BoolView::me(med) == ME_BOOL_VAL) {
00201       BoolIter bv(x,o);
00202       GECODE_ME_CHECK(y.minus_v(home,bv,false));
00203     }
00204     return ES_FIX;
00205   }
00206 
00207 }}}
00208 
00209 // STATISTICS: int-prop
00210