atmostOne.cpp
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
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034 #include <gecode/set/distinct.hh>
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045 namespace Gecode { namespace Set { namespace Distinct {
00046
00047
00048
00049
00050
00051
00052 Actor*
00053 AtmostOne::copy(Space& home) {
00054 return new (home) AtmostOne(home,*this);
00055 }
00056
00057 ExecStatus
00058 AtmostOne::propagate(Space& home, const ModEventDelta&) {
00059 Region r;
00060 LubRanges<SetView>* lubs = r.alloc<LubRanges<SetView> >(x.size());
00061 for (int i = x.size(); i--; ) {
00062 lubs[i].init(x[i]);
00063 }
00064 Iter::Ranges::NaryUnion bigT(r, lubs, x.size());
00065
00066 Iter::Ranges::ToValues<Iter::Ranges::NaryUnion>
00067 as(bigT);
00068
00069 while (as()) {
00070 int a = as.val(); ++as;
00071
00072
00073 int cardSa = 0;
00074 for (int i=x.size(); i--;)
00075 if (x[i].contains(a))
00076 cardSa++;
00077
00078
00079 GLBndSet bigTa(home);
00080 for (int i=x.size(); i--;) {
00081 if (!x[i].notContains(a)) {
00082 LubRanges<SetView> xilub(x[i]);
00083 bigTa.includeI(home, xilub);
00084 }
00085 }
00086
00087
00088 int maxa = static_cast<int>((bigTa.size() - 1) / (c - 1));
00089 bigTa.dispose(home);
00090
00091
00092
00093 if (maxa < cardSa)
00094 return ES_FAILED;
00095
00096 if (maxa == cardSa) {
00097
00098
00099
00100 for (int i=x.size(); i--;) {
00101 if (!x[i].contains(a)) {
00102 GECODE_ME_CHECK(x[i].exclude(home, a));
00103 }
00104 }
00105 } else {
00106 LubRanges<SetView>* lubs2 = r.alloc<LubRanges<SetView> >(x.size());
00107 for (int i = x.size(); i--; ) {
00108 lubs2[i].init(x[i]);
00109 }
00110 Iter::Ranges::NaryUnion bigT2(r, lubs2, x.size());
00111
00112 GlbRanges<SetView>* glbs = r.alloc<GlbRanges<SetView> >(cardSa);
00113 int count = 0;
00114 for (int i=x.size(); i--; ) {
00115 if (x[i].contains(a)) {
00116 glbs[count].init(x[i]);
00117 count++;
00118 }
00119 }
00120 Iter::Ranges::NaryUnion glbsa(r, glbs, cardSa);
00121 Iter::Ranges::Diff<Iter::Ranges::NaryUnion,
00122 Iter::Ranges::NaryUnion> deltaA(bigT2, glbsa);
00123 Iter::Ranges::Cache deltaAC(r,deltaA);
00124
00125
00126
00127
00128
00129 if (Iter::Ranges::size(deltaAC) == c - 1) {
00130
00131
00132
00133
00134
00135
00136
00137
00138 for (int i=x.size(); i--; ) {
00139 if (!x[i].contains(a) && !x[i].notContains(a)) {
00140 deltaAC.reset();
00141 LubRanges<SetView> xilub(x[i]);
00142 if (!Iter::Ranges::subset(deltaAC, xilub)) {
00143 GECODE_ME_CHECK(x[i].exclude(home, a));
00144 }
00145 }
00146 }
00147 }
00148
00149 }
00150
00151 }
00152
00153 return ES_NOFIX;
00154 }
00155
00156 }}}
00157
00158