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