val.icc
Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022 namespace Gecode { namespace Int { namespace Distinct {
00023
00024
00025
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
00037 int c_n = 0;
00038
00039
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
00046 int t = 0;
00047 do {
00048 t++;
00049 if (!complete && (t > 16)) {
00050
00051
00052
00053 ExecStatus es = ES_FIX;
00054 while (c_n > 0) {
00055 int v = c_v[--c_n];
00056
00057 for (int i = c_n; i--; )
00058 if (c_v[i] == v)
00059 goto failed;
00060
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
00074 IntSet d(&c_v[0],c_n);
00075
00076 unsigned int s = 0;
00077 for (int i = d.size(); i--; )
00078 s += d.width(i);
00079
00080
00081 if (s != static_cast<unsigned int>(c_n))
00082 goto failed;
00083
00084 c_n = 0;
00085
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
00098 int* n_v = &c_v[c_n];
00099
00100 int n_n = 0;
00101 while (c_n > 0) {
00102 int v = c_v[--c_n];
00103
00104 for (int i = c_n; i--; )
00105 if (c_v[i] == v)
00106 goto failed;
00107
00108 for (int i = n_n; i--; )
00109 if (n_v[i] == v)
00110 goto failed;
00111
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
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
00175