Generated on Fri Oct 19 11:25:02 2018 for Gecode by doxygen 1.6.3

int-eq.hpp

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, 2006
00008  *
00009  *  This file is part of Gecode, the generic constraint
00010  *  development environment:
00011  *     http://www.gecode.org
00012  *
00013  *  Permission is hereby granted, free of charge, to any person obtaining
00014  *  a copy of this software and associated documentation files (the
00015  *  "Software"), to deal in the Software without restriction, including
00016  *  without limitation the rights to use, copy, modify, merge, publish,
00017  *  distribute, sublicense, and/or sell copies of the Software, and to
00018  *  permit persons to whom the Software is furnished to do so, subject to
00019  *  the following conditions:
00020  *
00021  *  The above copyright notice and this permission notice shall be
00022  *  included in all copies or substantial portions of the Software.
00023  *
00024  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00025  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00026  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00027  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00028  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00029  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00030  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00031  *
00032  */
00033 
00034 namespace Gecode { namespace Int { namespace Count {
00035 
00036   template<class VX, class VY>
00037   forceinline
00038   EqInt<VX,VY>::EqInt(Home home, ViewArray<VX>& x, int n_s, VY y, int c)
00039     : IntBase<VX,VY>(home,x,n_s,y,c) {}
00040 
00041   template<class VX, class VY>
00042   ExecStatus
00043   EqInt<VX,VY>::post(Home home, ViewArray<VX>& x, VY y, int c) {
00044     // Eliminate decided views
00045     int n_x = x.size();
00046     for (int i=n_x; i--; )
00047       switch (holds(x[i],y)) {
00048       case RT_FALSE:
00049         x[i] = x[--n_x]; break;
00050       case RT_TRUE:
00051         x[i] = x[--n_x]; c--; break;
00052       case RT_MAYBE:
00053         break;
00054       default:
00055         GECODE_NEVER;
00056       }
00057     x.size(n_x);
00058     // RHS too small or too large
00059     if ((c < 0) || (c > n_x))
00060       return ES_FAILED;
00061     // All views must be different
00062     if (c == 0)
00063       return post_false(home,x,y);
00064     // All views must be equal
00065     if (c == n_x)
00066       return post_true(home,x,y);
00067     // Compute how many subscriptions must be created
00068     int n_s = std::max(c,n_x-c)+1;
00069     assert(n_s <= n_x);
00070     (void) new (home) EqInt<VX,VY>(home,x,n_s,y,c);
00071     return ES_OK;
00072   }
00073 
00074   template<class VX, class VY>
00075   forceinline
00076   EqInt<VX,VY>::EqInt(Space& home, EqInt<VX,VY>& p)
00077     : IntBase<VX,VY>(home,p) {}
00078 
00079   template<class VX, class VY>
00080   Actor*
00081   EqInt<VX,VY>::copy(Space& home) {
00082     return new (home) EqInt<VX,VY>(home,*this);
00083   }
00084 
00085   template<class VX, class VY>
00086   ExecStatus
00087   EqInt<VX,VY>::propagate(Space& home, const ModEventDelta&) {
00088     // Eliminate decided views from subscribed views
00089     int n_x = x.size();
00090     for (int i=n_s; i--; )
00091       switch (holds(x[i],y)) {
00092       case RT_FALSE:
00093         x[i].cancel(home,*this,PC_INT_DOM);
00094         x[i]=x[--n_s]; x[n_s]=x[--n_x];
00095         break;
00096       case RT_TRUE:
00097         x[i].cancel(home,*this,PC_INT_DOM);
00098         x[i]=x[--n_s]; x[n_s]=x[--n_x]; c--;
00099         break;
00100       case RT_MAYBE:
00101         break;
00102       default:
00103         GECODE_NEVER;
00104       }
00105     x.size(n_x);
00106     if ((c < 0) || (c > n_x))
00107       return ES_FAILED;
00108     // Eliminate decided views from unsubscribed views
00109     for (int i=n_x; i-- > n_s; )
00110       switch (holds(x[i],y)) {
00111       case RT_FALSE: x[i]=x[--n_x]; break;
00112       case RT_TRUE:  x[i]=x[--n_x]; c--; break;
00113       case RT_MAYBE: break;
00114       default:       GECODE_NEVER;
00115       }
00116     x.size(n_x);
00117     if ((c < 0) || (c > n_x))
00118       return ES_FAILED;
00119     if (c == 0) {
00120       // All views must be different
00121       GECODE_ES_CHECK(post_false(home,x,y));
00122       return home.ES_SUBSUMED(*this);
00123     }
00124     if (c == n_x) {
00125       // All views must be equal
00126       GECODE_ES_CHECK(post_true(home,x,y));
00127       return home.ES_SUBSUMED(*this);
00128     }
00129     int m = std::max(c,n_x-c)+1;
00130     assert(m <= n_x);
00131     // Now, there must be new subscriptions from x[n_s] up to x[m-1]
00132     while (n_s < m)
00133       x[n_s++].subscribe(home,*this,PC_INT_DOM,false);
00134     return ES_FIX;
00135   }
00136 
00137 }}}
00138 
00139 // STATISTICS: int-prop