nogoods.hh
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 #ifndef __GECODE_SEARCH_META_NO_GOODS_HH__
00039 #define __GECODE_SEARCH_META_NO_GOODS_HH__
00040
00041 #include <gecode/search.hh>
00042
00043 namespace Gecode { namespace Search { namespace Meta {
00044
00046 class GECODE_VTABLE_EXPORT NoNGL : public NGL {
00047 public:
00049 NoNGL(void);
00051 NoNGL(Space& home);
00053 NoNGL(Space& home, bool share, NoNGL& ngl);
00055 virtual void subscribe(Space& home, Propagator& p);
00057 virtual void reschedule(Space& home, Propagator& p);
00059 virtual void cancel(Space& home, Propagator& p);
00061 virtual NGL::Status status(const Space& home) const;
00063 virtual ExecStatus prune(Space& home);
00065 virtual NGL* copy(Space& home, bool share);
00066 };
00067
00069 class GECODE_SEARCH_EXPORT NoGoodsProp : public Propagator {
00070 protected:
00072 NGL* root;
00074 unsigned int n;
00076 NoGoodsProp(Space& home, NGL* root);
00078 NoGoodsProp(Space& home, bool shared, NoGoodsProp& p);
00079 public:
00081 virtual Actor* copy(Space& home, bool share);
00083 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00085 virtual void reschedule(Space& home);
00087 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00089 template<class Path>
00090 static ExecStatus post(Space& home, const Path& p);
00092 virtual size_t dispose(Space& home);
00093 };
00094
00095 forceinline
00096 NoNGL::NoNGL(void) {}
00097
00098 forceinline
00099 NoNGL::NoNGL(Space& home)
00100 : NGL(home) {}
00101
00102 forceinline
00103 NoNGL::NoNGL(Space& home, bool share, NoNGL& ngl)
00104 : NGL(home,share,ngl) {}
00105
00106
00107
00108 forceinline
00109 NoGoodsProp::NoGoodsProp(Space& home, NGL* root0)
00110 : Propagator(Home(home)), root(root0), n(0U) {
00111
00112 root->subscribe(home,*this); n++;
00113 bool notice = root->notice();
00114 NGL* l = root->next();
00115 while ((l != NULL) && l->leaf()) {
00116 l->subscribe(home,*this); n++;
00117 notice = notice || l->notice();
00118 l = l->next();
00119 }
00120 if (l != NULL) {
00121 l->subscribe(home,*this); n++;
00122 }
00123 while (!notice && (l != NULL)) {
00124 notice = notice || l->notice();
00125 l = l->next();
00126 }
00127 if (notice)
00128 home.notice(*this,AP_DISPOSE);
00129 }
00130
00131 forceinline
00132 NoGoodsProp::NoGoodsProp(Space& home, bool shared, NoGoodsProp& p)
00133 : Propagator(home,shared,p), n(p.n) {
00134 assert(p.root != NULL);
00135 NoNGL s;
00136 NGL* c = &s;
00137 for (NGL* pc = p.root; pc != NULL; pc = pc->next()) {
00138 NGL* n = pc->copy(home,shared);
00139 n->leaf(pc->leaf());
00140 c->next(n); c=n;
00141 }
00142 root = s.next();
00143 }
00144
00145
00146
00147 template<class Path>
00148 forceinline ExecStatus
00149 NoGoodsProp::post(Space& home, const Path& p) {
00150 int s = 0;
00151 int n = std::min(p.ds.entries(),static_cast<int>(p.ngdl()));
00152
00153 unsigned long int n_nogood = 0;
00154
00155
00156 while ((n > s) && (p.ds[n-1].truealt() == 0U))
00157 n--;
00158
00159
00160 NoNGL nn;
00161
00162 NGL* c = &nn;
00163
00164
00165 while ((s < n) && (p.ds[s].truealt() > 0U))
00166
00167 if (p.ds[s].rightmost()) {
00168
00169 home.trycommit(*p.ds[s].choice(),p.ds[s].truealt());
00170 s++;
00171 } else {
00172
00173 for (unsigned int a=0U; a<p.ds[s].truealt(); a++) {
00174 NGL* l = home.ngl(*p.ds[s].choice(),a);
00175
00176 if (l == NULL)
00177 return ES_OK;
00178 GECODE_ES_CHECK(l->prune(home));
00179 }
00180
00181 if (NGL* l = home.ngl(*p.ds[s].choice(),p.ds[s].truealt())) {
00182 c = c->add(l,false);
00183 s++; break;
00184 }
00185 }
00186
00187
00188 if (home.failed())
00189 return ES_FAILED;
00190 if (s >= n)
00191 return ES_OK;
00192
00193
00194 assert((n-s > 1) ||
00195 ((n-s == 1) && (c != &nn)));
00196
00197
00198 NGL* ll = NULL;
00199
00200
00201 for (int i=s; i<n; i++) {
00202
00203 for (unsigned int a=0U; a<p.ds[i].truealt(); a++) {
00204 NGL* l = home.ngl(*p.ds[i].choice(),a);
00205 if (l == NULL) {
00206
00207 if (ll == NULL)
00208 return ES_OK;
00209 ll->next(NULL);
00210 break;
00211 }
00212 c = c->add(l,true); ll = c;
00213 n_nogood++;
00214 }
00215
00216 if (NGL* l = home.ngl(*p.ds[i].choice(),p.ds[i].truealt())) {
00217 c = c->add(l,false);
00218 } else if (!p.ds[i].rightmost()) {
00219
00220 if (ll == NULL)
00221 return ES_OK;
00222 ll->next(NULL);
00223 break;
00224 }
00225 }
00226
00227 const_cast<Path&>(p).ng(n_nogood);
00228
00229 (void) new (home) NoGoodsProp(home,nn.next());
00230 return ES_OK;
00231 }
00232
00233 }}}
00234
00235 #endif
00236
00237