00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037 #include "test/cpltset.hh"
00038
00039 using namespace Gecode;
00040 using namespace Test::Set;
00041
00042 namespace Test { namespace CpltSet {
00043
00045 namespace Selection {
00046
00052
00053 static IntSet ds_012(0,2);
00054 static IntSet ds_1012(-1,2);
00055
00056
00057
00058
00059
00061 class CpltSetSelectUnion : public CpltSetTest {
00062 private:
00063 int selector_pos;
00064 int union_pos;
00065 int xsize;
00066 public:
00067
00069 CpltSetSelectUnion(const char* t)
00070 : CpltSetTest(t, 4, ds_012, false, 0, 100, 10000), xsize(4) {
00071 union_pos = xsize - 1;
00072 selector_pos = xsize - 2;
00073 }
00075 virtual bool solution(const SetAssignment& x) const {
00076 int selected = 0;
00077
00078 CountableSetValues count_sel(x.lub, x[selector_pos]);
00079 for ( ; count_sel(); ++count_sel, selected++);
00080
00081 CountableSetValues xunion(x.lub, x[union_pos]);
00082 if (selected==0) {
00083 bool valid = !xunion();
00084 return valid;
00085 }
00086
00087 GECODE_AUTOARRAY(CountableSetRanges, sel, selected);
00088 CountableSetValues selector(x.lub, x[selector_pos]);
00089 for (int i=selected; i--;++selector) {
00090 if (selector.val()>=selector_pos || selector.val()<0) {
00091 return false;
00092 }
00093 sel[i].init(x.lub, x[selector.val()]);
00094 }
00095 Iter::Ranges::NaryUnion<CountableSetRanges> u(sel, selected);
00096
00097 CountableSetRanges z(x.lub, x[union_pos]);
00098 bool valid = Iter::Ranges::equal(u,z);
00099 return valid;
00100 }
00102 virtual void post(Space* home, CpltSetVarArray& x, IntVarArray&) {
00103 int vars = selector_pos;
00104 CpltSetVarArgs xs(vars);
00105 for (int i=vars; i--;)
00106 xs[i]=x[i];
00107 Gecode::selectUnion(home, xs, x[selector_pos], x[union_pos]);
00108 }
00109 };
00110 CpltSetSelectUnion _cpltsetselectUnion("Select::SelectUnion");
00111
00113 class CpltSetSelectNonEmptySub : public CpltSetTest {
00114 private:
00115 int selector_pos;
00116 int union_pos;
00117 int xsize;
00118 public:
00120 CpltSetSelectNonEmptySub(const char* t)
00121 : CpltSetTest(t, 4, ds_1012,false, 0, 8000, 15000), xsize(4) {
00123 union_pos = xsize - 1;
00124 selector_pos = xsize - 2;
00125 }
00127 virtual bool solution(const SetAssignment& x) const {
00128 int selected = 0;
00129
00130 CountableSetValues count_sel(x.lub, x[selector_pos]);
00131 for ( ; count_sel(); ++count_sel, selected++);
00132
00133 CountableSetRanges xunion(x.lub, x[union_pos]);
00134 if (selected==0) {
00135 GECODE_AUTOARRAY(CountableSetRanges, sel, selector_pos);
00136
00137 bool valid = true;
00138 for (int i = selector_pos; i--; ) {
00139 sel[i].init(x.lub, x[i]);
00140 CountableSetRanges t(x.lub, x[union_pos]);
00141 bool non_empty_union = t();
00142 bool non_empty = sel[i]();
00143 bool subset = Iter::Ranges::subset(sel[i], t);
00144
00145 if (!non_empty_union) {
00146 return true;
00147 } else {
00148 valid &= (!non_empty || !subset);
00149 }
00150 }
00151 return valid;
00152 }
00153
00154 if (!xunion()) {
00155 return false;
00156 }
00157
00158 GECODE_AUTOARRAY(CountableSetRanges, sel, selected);
00159
00160 CountableSetValues selector(x.lub, x[selector_pos]);
00161 for (int i=selected; i--;++selector) {
00162 if (selector.val()>=selector_pos || selector.val()<0) {
00163 return false;
00164 }
00165 sel[i].init(x.lub, x[selector.val()]);
00166 }
00167
00168 Iter::Ranges::NaryUnion<CountableSetRanges> u(sel, selected);
00169
00170 bool select_valid = true;
00171 CountableSetValues select_val(x.lub, x[selector_pos]);
00172 for (int i = 0; i < selector_pos; i++) {
00173 CountableSetRanges cur_sel(x.lub, x[i]);
00174 bool subset = false;
00175 bool non_empty = false;
00176 CountableSetRanges tunion(x.lub, x[union_pos]);
00177 non_empty = cur_sel();
00178 subset = Iter::Ranges::subset(cur_sel, tunion);
00179
00180 if (select_val()) {
00181 if (i == select_val.val()) {
00182 select_valid &= (subset && non_empty);
00183 ++select_val;
00184 } else {
00185 select_valid &= (!non_empty || !subset);
00186 }
00187 } else {
00188 select_valid &= (!non_empty || !subset);
00189 }
00190 }
00191
00192 bool valid = select_valid && Iter::Ranges::subset(u, xunion);
00193 return valid;
00194 }
00195
00197 virtual void post(Space* home, CpltSetVarArray& x, IntVarArray&) {
00198 int vars = selector_pos;
00199 CpltSetVarArgs xs(vars);
00200 for (int i=vars; i--;)
00201 xs[i]=x[i];
00202
00203 Gecode::selectNonEmptySub(home, xs, x[selector_pos], x[union_pos]);
00204 }
00205 };
00206
00207
00208
00209
00210
00211
00213
00214 }}}
00215
00216