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