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/search/meta/nogoods.hh>
00039
00040 namespace Gecode { namespace Search { namespace Meta {
00041
00043 forceinline NGL*
00044 disposenext(NGL* ngl, Space& home, Propagator& p, bool c) {
00045 NGL* n = ngl->next();
00046 if (c)
00047 ngl->cancel(home,p);
00048 home.rfree(ngl,ngl->dispose(home));
00049 return n;
00050 }
00051
00052 void
00053 NoNGL::subscribe(Space&, Propagator&) {
00054 GECODE_NEVER;
00055 }
00056 void
00057 NoNGL::cancel(Space&, Propagator&) {
00058 GECODE_NEVER;
00059 }
00060 void
00061 NoNGL::reschedule(Space&, Propagator&) {
00062 GECODE_NEVER;
00063 }
00064 NGL::Status
00065 NoNGL::status(const Space&) const {
00066 GECODE_NEVER;
00067 return NGL::NONE;
00068 }
00069 ExecStatus
00070 NoNGL::prune(Space&) {
00071 GECODE_NEVER;
00072 return ES_OK;
00073 }
00074 NGL*
00075 NoNGL::copy(Space&, bool) {
00076 GECODE_NEVER;
00077 return NULL;
00078 }
00079
00080 Actor*
00081 NoGoodsProp::copy(Space& home, bool share) {
00082 return new (home) NoGoodsProp(home,share,*this);
00083 }
00084
00085 PropCost
00086 NoGoodsProp::cost(const Space&, const ModEventDelta&) const {
00087 return PropCost::linear(PropCost::LO,n);
00088 }
00089
00090 void
00091 NoGoodsProp::reschedule(Space& home) {
00092 root->reschedule(home,*this);
00093 NGL* l = root->next();
00094 while ((l != NULL) && l->leaf()) {
00095 l->reschedule(home,*this);
00096 l = l->next();
00097 }
00098 if (l != NULL)
00099 l->reschedule(home,*this);
00100 }
00101
00102
00103 ExecStatus
00104 NoGoodsProp::propagate(Space& home, const ModEventDelta&) {
00105 restart:
00106
00107 switch (root->status(home)) {
00108 case NGL::FAILED:
00109
00110 return home.ES_SUBSUMED(*this);
00111 case NGL::SUBSUMED:
00112 {
00113 NGL* l = disposenext(root,home,*this,true); n--;
00114
00115 while ((l != NULL) && l->leaf()) {
00116 l->cancel(home,*this); n--;
00117 GECODE_ES_CHECK(l->prune(home));
00118 l = disposenext(l,home,*this,false);
00119 }
00120 root = l;
00121
00122 if (l == NULL)
00123 return home.ES_SUBSUMED(*this);
00124
00125 l = l->next();
00126
00127 while ((l != NULL) && l->leaf()) {
00128 l->subscribe(home,*this); n++;
00129 l = l->next();
00130 }
00131
00132 if (l != NULL) {
00133 l->subscribe(home,*this); n++;
00134 }
00135 goto restart;
00136 }
00137 case NGL::NONE:
00138 break;
00139 default: GECODE_NEVER;
00140 }
00141
00142 {
00143 NGL* p = root;
00144 NGL* l = p->next();
00145
00146
00147 while ((l != NULL) && l->leaf()) {
00148 switch (l->status(home)) {
00149 case NGL::SUBSUMED:
00150 l = disposenext(l,home,*this,true); n--;
00151 p->next(l);
00152 GECODE_ES_CHECK(root->prune(home));
00153 if (root->status(home) == NGL::FAILED)
00154 return home.ES_SUBSUMED(*this);
00155 break;
00156 case NGL::FAILED:
00157 l = disposenext(l,home,*this,true); n--;
00158 p->next(l);
00159 break;
00160 case NGL::NONE:
00161 p = l; l = l->next();
00162 break;
00163 default: GECODE_NEVER;
00164 }
00165 }
00166
00167
00168 if (l != NULL) {
00169 switch (l->status(home)) {
00170 case NGL::FAILED:
00171 (void) disposenext(l,home,*this,true); n--;
00172
00173 p->next(NULL);
00174 break;
00175 case NGL::SUBSUMED:
00176 {
00177
00178 l = disposenext(l,home,*this,true); n--;
00179 p->next(l);
00180
00181 while ((l != NULL) && l->leaf()) {
00182 l->subscribe(home,*this); n++;
00183 l = l->next();
00184 }
00185 if (l != NULL) {
00186 l->subscribe(home,*this); n++;
00187 }
00188 }
00189 break;
00190 case NGL::NONE:
00191 break;
00192 default: GECODE_NEVER;
00193 }
00194 }
00195 }
00196 return ES_NOFIX;
00197 }
00198
00199 size_t
00200 NoGoodsProp::dispose(Space& home) {
00201 if (home.failed()) {
00202
00203 NGL* l = root;
00204 while (l != NULL) {
00205 NGL* t = l->next();
00206 (void) l->dispose(home);
00207 l = t;
00208 }
00209 } else if (root != NULL) {
00210
00211 NGL* l = disposenext(root,home,*this,true);
00212 while ((l != NULL) && l->leaf())
00213 l = disposenext(l,home,*this,true);
00214 if (l != NULL)
00215 l = disposenext(l,home,*this,true);
00216 while (l != NULL)
00217 l = disposenext(l,home,*this,false);
00218 }
00219 home.ignore(*this,AP_DISPOSE,true);
00220 (void) Propagator::dispose(home);
00221 return sizeof(*this);
00222 }
00223
00224 }}}
00225
00226