Generated on Thu Mar 22 10:39:35 2012 for Gecode by doxygen 1.6.3

val.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, 2003
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 namespace Gecode { namespace Int { namespace Distinct {
00039 
00040   /*
00041    * Eliminating singleton variables
00042    *
00043    */
00044   template<class View, bool complete>
00045   ExecStatus
00046   prop_val(Space& home, ViewArray<View>& x) {
00047     assert(x.size() > 1);
00048     int n = x.size();
00049 
00050     Region r(home);
00051     int* stack = r.alloc<int>(n);
00052     int* c_v = &stack[0];
00053     // c_n is the current number of values on stack
00054     int c_n = 0;
00055 
00056     // Collect all assigned variables on stack
00057     for (int i = n; i--; )
00058       if (x[i].assigned()) {
00059         c_v[c_n++]=x[i].val(); x[i]=x[--n];
00060       }
00061 
00062     // The number of trips
00063     int t = 0;
00064     do {
00065       t++;
00066       if (!complete && (t > 16)) {
00067         // Give up after sixteen iterations, but the values must be
00068         // propagated first
00069         // Maybe we are lucky in that this iteration does the trick...
00070         ExecStatus es = ES_FIX;
00071         while (c_n > 0) {
00072           int v = c_v[--c_n];
00073           // Check whether value is on stack only once
00074           for (int i = c_n; i--; )
00075             if (c_v[i] == v)
00076               goto failed;
00077           // Tell and do not collect new values
00078           for (int i = n; i--; ) {
00079             ModEvent me = x[i].nq(home,v);
00080             if (me_failed(me))
00081               goto failed;
00082             if (me == ME_INT_VAL)
00083               es = ES_NOFIX;
00084           }
00085         }
00086         x.size(n);
00087         return es;
00088       }
00089       if (c_n > 31) {
00090         // Many values, use full domain operation
00091         IntSet d(&c_v[0],c_n);
00092         // If the size s of d is different from the number of values,
00093         // a value must have appeared multiply: failure
00094         if (d.size() != static_cast<unsigned int>(c_n))
00095           goto failed;
00096         // We do not need the values on the stack any longer, reset
00097         c_n = 0;
00098         // Tell and collect new values
00099         for (int i = n; i--; )
00100           if ((d.min() <= x[i].max()) && (d.max() >= x[i].min())) {
00101             IntSetRanges dr(d);
00102             ModEvent me = x[i].minus_r(home,dr,false);
00103             if (me_failed(me))
00104               goto failed;
00105             if (me == ME_INT_VAL) {
00106               c_v[c_n++]=x[i].val(); x[i]=x[--n];
00107             }
00108           }
00109       } else {
00110         // Values for next iteration
00111         int* n_v = &c_v[c_n];
00112         // Stack top for the next iteration
00113         int n_n = 0;
00114         while (c_n > 0) {
00115           int v = c_v[--c_n];
00116           // Check whether value is not on current stack
00117           for (int i = c_n; i--; )
00118             if (c_v[i] == v)
00119               goto failed;
00120           // Check whether value is not on next stack
00121           for (int i = n_n; i--; )
00122             if (n_v[i] == v)
00123               goto failed;
00124           // Tell and collect new values
00125           for (int i = n; i--; ) {
00126             ModEvent me = x[i].nq(home,v);
00127             if (me_failed(me))
00128               goto failed;
00129             if (me == ME_INT_VAL) {
00130               n_v[n_n++]=x[i].val(); x[i]=x[--n];
00131             }
00132           }
00133         }
00134         c_v = n_v; c_n = n_n;
00135       }
00136     } while (c_n > 0);
00137     x.size(n);
00138     return ES_FIX;
00139   failed:
00140     x.size(0);
00141     return ES_FAILED;
00142   }
00143 
00144 
00145   /*
00146    * The propagator proper
00147    *
00148    */
00149   template<class View>
00150   forceinline
00151   Val<View>::Val(Home home, ViewArray<View>& x)
00152   : NaryPropagator<View,PC_INT_VAL>(home,x) {}
00153 
00154   template<class View>
00155   forceinline
00156   Val<View>::Val(Space& home, bool share, Val<View>& p)
00157     : NaryPropagator<View,PC_INT_VAL>(home,share,p) {}
00158 
00159   template<class View>
00160   Actor*
00161   Val<View>::copy(Space& home, bool share) {
00162     return new (home) Val<View>(home,share,*this);
00163   }
00164 
00165   template<class View>
00166   ExecStatus
00167   Val<View>::propagate(Space& home, const ModEventDelta&) {
00168     GECODE_ES_CHECK((prop_val<View,true>(home,x)));
00169     return (x.size() < 2) ? home.ES_SUBSUMED(*this) : ES_FIX;
00170   }
00171 
00172   template<class View>
00173   ExecStatus
00174   Val<View>::post(Home home, ViewArray<View>& x) {
00175     if (x.size() == 2)
00176       return Rel::Nq<View>::post(home,x[0],x[1]);
00177     if (x.size() > 2)
00178       (void) new (home) Val<View>(home,x);
00179     return ES_OK;
00180   }
00181 
00182 }}}
00183 
00184 // STATISTICS: int-prop
00185