Generated on Wed Jan 4 17:49:08 2006 for Gecode by doxygen 1.4.6

val.icc

Go to the documentation of this file.
00001 /*
00002  *  Main authors:
00003  *     Christian Schulte <schulte@gecode.org>
00004  *
00005  *  Copyright:
00006  *     Christian Schulte, 2003
00007  *
00008  *  Last modified:
00009  *     $Date: 2005-10-23 16:23:09 +0200 (Sun, 23 Oct 2005) $ by $Author: schulte $
00010  *     $Revision: 2403 $
00011  *
00012  *  This file is part of Gecode, the generic constraint
00013  *  development environment:
00014  *     http://www.gecode.org
00015  *
00016  *  See the file "LICENSE" for information on usage and
00017  *  redistribution of this file, and for a
00018  *     DISCLAIMER OF ALL WARRANTIES.
00019  *
00020  */
00021 
00022 namespace Gecode { namespace Int { namespace Distinct {
00023 
00024   /*
00025    * Eliminating singleton variables
00026    *
00027    */
00028   template <class View, bool complete>
00029   ExecStatus
00030   prop_val(Space* home, ViewArray<View>& x) {
00031     assert(x.size() > 1);
00032     int n = x.size();
00033 
00034     GECODE_AUTOARRAY(int, stack, n);
00035     int* c_v = &stack[0];
00036     // c_n is the current number of values on stack
00037     int c_n = 0;
00038 
00039     // Collect all assigned variables on stack
00040     for (int i = n; i--; )
00041       if (x[i].assigned()) {
00042         c_v[c_n++]=x[i].val(); x[i]=x[--n];
00043       }
00044 
00045     // The number of trips
00046     int t = 0;
00047     do {
00048       t++;
00049       if (!complete && (t > 16)) {
00050         // Give up after sixteeen iterations, but the values must be
00051         // propagated first
00052         // Maybe we are lucky in that this iteration does the trick...
00053         ExecStatus es = ES_FIX;
00054         while (c_n > 0) {
00055           int v = c_v[--c_n];
00056           // Check whether value is on stack only once
00057           for (int i = c_n; i--; )
00058             if (c_v[i] == v)
00059               goto failed;
00060           // Tell and do not collect new values
00061           for (int i = n; i--; ) {
00062             ModEvent me = x[i].nq(home,v);
00063             if (me_failed(me))
00064               goto failed;
00065             if (me == ME_INT_VAL)
00066               es = ES_NOFIX;
00067           }
00068         }
00069         x.size(n);
00070         return es;
00071       }
00072       if (c_n > 31) {
00073         // Many values, use full domain operation
00074         IntSet d(&c_v[0],c_n);
00075         // Check for failure
00076         unsigned int s = 0;
00077         for (int i = d.size(); i--; )
00078           s += d.width(i);
00079         // If the size s of d is different from the number of values,
00080         // a value must have appeared multiply: failure
00081         if (s != static_cast<unsigned int>(c_n))
00082           goto failed;
00083         // We do not need the values on the stack any longer, reset
00084         c_n = 0;
00085         // Tell and collect new values
00086         for (int i = n; i--; )
00087           if ((d.min() <= x[i].max()) && (d.max() >= x[i].min())) {
00088             IntSetRanges dr(d);
00089             ModEvent me = x[i].minus(home,dr);
00090             if (me_failed(me))
00091               goto failed;
00092             if (me == ME_INT_VAL) {
00093               c_v[c_n++]=x[i].val(); x[i]=x[--n];
00094             }
00095           }
00096       } else {
00097         // Values for next iteration
00098         int* n_v = &c_v[c_n];
00099         // Stack top for the next iteration
00100         int n_n = 0;
00101         while (c_n > 0) {
00102           int v = c_v[--c_n];
00103           // Check whether value is not on current stack
00104           for (int i = c_n; i--; )
00105             if (c_v[i] == v)
00106               goto failed;
00107           // Check whether value is not on next stack
00108           for (int i = n_n; i--; )
00109             if (n_v[i] == v)
00110               goto failed;
00111           // Tell and collect new values
00112           for (int i = n; i--; ) {
00113             ModEvent me = x[i].nq(home,v);
00114             if (me_failed(me))
00115               goto failed;
00116             if (me == ME_INT_VAL) {
00117               n_v[n_n++]=x[i].val(); x[i]=x[--n];
00118             }
00119           }
00120         }
00121         c_v = n_v; c_n = n_n;
00122       }
00123     } while (c_n > 0);
00124     x.size(n);
00125     return (n < 2) ?  ES_SUBSUMED : ES_FIX;
00126   failed:
00127     x.size(0);
00128     return ES_FAILED;
00129   }
00130 
00131 
00132   /*
00133    * The propagator proper
00134    *
00135    */
00136 
00137   template <class View>
00138   forceinline
00139   Val<View>::Val(Space* home, ViewArray<View>& x)
00140     : NaryPropagator<View,PC_INT_VAL>(home,x) {}
00141 
00142   template <class View>
00143   forceinline
00144   Val<View>::Val(Space* home, bool share, Val<View>& p)
00145     : NaryPropagator<View,PC_INT_VAL>(home,share,p) {}
00146 
00147   template <class View>
00148   Actor*
00149   Val<View>::copy(Space* home, bool share) {
00150     return new (home) Val<View>(home,share,*this);
00151   }
00152 
00153   template <class View>
00154   ExecStatus
00155   Val<View>::post(Space* home, ViewArray<View>& x) {
00156     if (x.size() == 2)
00157       return Rel::Nq<View>::post(home,x[0],x[1]);
00158     if (x.size() > 2)
00159       if (x.same())
00160         return ES_FAILED;
00161       else
00162         (void) new (home) Val<View>(home,x);
00163     return ES_OK;
00164   }
00165 
00166   template <class View>
00167   ExecStatus
00168   Val<View>::propagate(Space* home) {
00169     return prop_val<View,true>(home,x);
00170   }
00171 
00172 }}}
00173 
00174 // STATISTICS: int-prop
00175