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(r, lubs, x.size());
00069
00070 Iter::Ranges::ToValues<Iter::Ranges::NaryUnion<LubRanges<SetView> > >
00071 as(bigT);
00072
00073 while (as()) {
00074 int a = as.val(); ++as;
00075
00076
00077 int cardSa = 0;
00078 for (int i=x.size(); i--;)
00079 if (x[i].contains(a))
00080 cardSa++;
00081
00082
00083 GLBndSet bigTa(home);
00084 for (int i=x.size(); i--;) {
00085 if (!x[i].notContains(a)) {
00086 LubRanges<SetView> xilub(x[i]);
00087 bigTa.includeI(home, xilub);
00088 }
00089 }
00090
00091
00092 int maxa = static_cast<int>((bigTa.size() - 1) / (c - 1));
00093 bigTa.dispose(home);
00094
00095
00096
00097 if (maxa < cardSa)
00098 return ES_FAILED;
00099
00100 if (maxa == cardSa) {
00101
00102
00103
00104 for (int i=x.size(); i--;) {
00105 if (!x[i].contains(a)) {
00106 GECODE_ME_CHECK(x[i].exclude(home, a));
00107 }
00108 }
00109 } else {
00110 LubRanges<SetView>* lubs2 = r.alloc<LubRanges<SetView> >(x.size());
00111 for (int i = x.size(); i--; ) {
00112 lubs2[i].init(x[i]);
00113 }
00114 Iter::Ranges::NaryUnion<LubRanges<SetView> > bigT2(r, lubs2, x.size());
00115
00116 GlbRanges<SetView>* glbs = r.alloc<GlbRanges<SetView> >(cardSa);
00117 int count = 0;
00118 for (int i=x.size(); i--; ) {
00119 if (x[i].contains(a)) {
00120 glbs[count].init(x[i]);
00121 count++;
00122 }
00123 }
00124 Iter::Ranges::NaryUnion<GlbRanges<SetView> > glbsa(r, glbs, cardSa);
00125 Iter::Ranges::Diff<Iter::Ranges::NaryUnion<LubRanges<SetView> >,
00126 Iter::Ranges::NaryUnion<GlbRanges<SetView> > > deltaA(bigT2, glbsa);
00127 Iter::Ranges::Cache<
00128 Iter::Ranges::Diff<Iter::Ranges::NaryUnion<LubRanges<SetView> >,
00129 Iter::Ranges::NaryUnion<GlbRanges<SetView> > > > deltaAC(r,deltaA);
00130
00131
00132
00133
00134
00135 if (Iter::Ranges::size(deltaAC) == c - 1) {
00136
00137
00138
00139
00140
00141
00142
00143
00144 for (int i=x.size(); i--; ) {
00145 if (!x[i].contains(a) && !x[i].notContains(a)) {
00146 deltaAC.reset();
00147 LubRanges<SetView> xilub(x[i]);
00148 if (!Iter::Ranges::subset(deltaAC, xilub)) {
00149 GECODE_ME_CHECK(x[i].exclude(home, a));
00150 }
00151 }
00152 }
00153 }
00154
00155 }
00156
00157 }
00158
00159 return ES_NOFIX;
00160 }
00161
00162 }}}
00163
00164