1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 2 /* 3 * Main authors: 4 * Christian Schulte <schulte@gecode.org> 5 * 6 * Copyright: 7 * Christian Schulte, 2013 8 * 9 * This file is part of Gecode, the generic constraint 10 * development environment: 11 * http://www.gecode.org 12 * 13 * Permission is hereby granted, free of charge, to any person obtaining 14 * a copy of this software and associated documentation files (the 15 * "Software"), to deal in the Software without restriction, including 16 * without limitation the rights to use, copy, modify, merge, publish, 17 * distribute, sublicense, and/or sell copies of the Software, and to 18 * permit persons to whom the Software is furnished to do so, subject to 19 * the following conditions: 20 * 21 * The above copyright notice and this permission notice shall be 22 * included in all copies or substantial portions of the Software. 23 * 24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 25 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 26 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 27 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 28 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 29 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 30 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 31 * 32 */ 33 34 #include <gecode/search/nogoods.hh> 35 36 namespace Gecode { namespace Search { 37 38 /// Help function to cancel and dispose a no-good literal 39 forceinline NGL* disposenext(NGL * ngl,Space & home,Propagator & p,bool c)40 disposenext(NGL* ngl, Space& home, Propagator& p, bool c) { 41 NGL* n = ngl->next(); 42 if (c) 43 ngl->cancel(home,p); 44 home.rfree(ngl,ngl->dispose(home)); 45 return n; 46 } 47 48 void subscribe(Space &,Propagator &)49 NoNGL::subscribe(Space&, Propagator&) { 50 GECODE_NEVER; 51 } 52 void cancel(Space &,Propagator &)53 NoNGL::cancel(Space&, Propagator&) { 54 GECODE_NEVER; 55 } 56 void reschedule(Space &,Propagator &)57 NoNGL::reschedule(Space&, Propagator&) { 58 GECODE_NEVER; 59 } 60 NGL::Status status(const Space &) const61 NoNGL::status(const Space&) const { 62 GECODE_NEVER; 63 return NGL::NONE; 64 } 65 ExecStatus prune(Space &)66 NoNGL::prune(Space&) { 67 GECODE_NEVER; 68 return ES_OK; 69 } 70 NGL* copy(Space &)71 NoNGL::copy(Space&) { 72 GECODE_NEVER; 73 return nullptr; 74 } 75 76 Actor* copy(Space & home)77 NoGoodsProp::copy(Space& home) { 78 return new (home) NoGoodsProp(home,*this); 79 } 80 81 PropCost cost(const Space &,const ModEventDelta &) const82 NoGoodsProp::cost(const Space&, const ModEventDelta&) const { 83 return PropCost::linear(PropCost::LO,n); 84 } 85 86 void reschedule(Space & home)87 NoGoodsProp::reschedule(Space& home) { 88 root->reschedule(home,*this); 89 NGL* l = root->next(); 90 while ((l != nullptr) && l->leaf()) { 91 l->reschedule(home,*this); 92 l = l->next(); 93 } 94 if (l != nullptr) 95 l->reschedule(home,*this); 96 } 97 98 99 ExecStatus propagate(Space & home,const ModEventDelta &)100 NoGoodsProp::propagate(Space& home, const ModEventDelta&) { 101 restart: 102 // Start with checking the first literal 103 switch (root->status(home)) { 104 case NGL::FAILED: 105 // All no-goods are dead, let dispose() clean up 106 return home.ES_SUBSUMED(*this); 107 case NGL::SUBSUMED: 108 { 109 NGL* l = disposenext(root,home,*this,true); n--; 110 // Prune leaf-literals 111 while ((l != nullptr) && l->leaf()) { 112 l->cancel(home,*this); n--; 113 GECODE_ES_CHECK(l->prune(home)); 114 l = disposenext(l,home,*this,false); 115 } 116 root = l; 117 // Is there anything left? 118 if (l == nullptr) 119 return home.ES_SUBSUMED(*this); 120 // Skip literal that already has a subscription 121 l = l->next(); 122 // Create subscriptions for leafs 123 while ((l != nullptr) && l->leaf()) { 124 l->subscribe(home,*this); n++; 125 l = l->next(); 126 } 127 // Create subscription for possible non-leaf literal 128 if (l != nullptr) { 129 l->subscribe(home,*this); n++; 130 } 131 goto restart; 132 } 133 case NGL::NONE: 134 break; 135 default: GECODE_NEVER; 136 } 137 138 { 139 NGL* p = root; 140 NGL* l = p->next(); 141 142 // Check the leaves 143 while ((l != nullptr) && l->leaf()) { 144 switch (l->status(home)) { 145 case NGL::SUBSUMED: 146 l = disposenext(l,home,*this,true); n--; 147 p->next(l); 148 GECODE_ES_CHECK(root->prune(home)); 149 if (root->status(home) == NGL::FAILED) 150 return home.ES_SUBSUMED(*this); 151 break; 152 case NGL::FAILED: 153 l = disposenext(l,home,*this,true); n--; 154 p->next(l); 155 break; 156 case NGL::NONE: 157 p = l; l = l->next(); 158 break; 159 default: GECODE_NEVER; 160 } 161 } 162 163 // Check the next subtree 164 if (l != nullptr) { 165 switch (l->status(home)) { 166 case NGL::FAILED: 167 (void) disposenext(l,home,*this,true); n--; 168 // Prune entire subtree 169 p->next(nullptr); 170 break; 171 case NGL::SUBSUMED: 172 { 173 // Unlink node 174 l = disposenext(l,home,*this,true); n--; 175 p->next(l); 176 // Create subscriptions 177 while ((l != nullptr) && l->leaf()) { 178 l->subscribe(home,*this); n++; 179 l = l->next(); 180 } 181 if (l != nullptr) { 182 l->subscribe(home,*this); n++; 183 } 184 } 185 break; 186 case NGL::NONE: 187 break; 188 default: GECODE_NEVER; 189 } 190 } 191 } 192 return ES_NOFIX; 193 } 194 195 size_t dispose(Space & home)196 NoGoodsProp::dispose(Space& home) { 197 if (home.failed()) { 198 // This will be executed when one ngl returned true for notice() 199 NGL* l = root; 200 while (l != nullptr) { 201 NGL* t = l->next(); 202 (void) l->dispose(home); 203 l = t; 204 } 205 } else if (root != nullptr) { 206 // This will be executed for subsumption 207 NGL* l = disposenext(root,home,*this,true); 208 while ((l != nullptr) && l->leaf()) 209 l = disposenext(l,home,*this,true); 210 if (l != nullptr) 211 l = disposenext(l,home,*this,true); 212 while (l != nullptr) 213 l = disposenext(l,home,*this,false); 214 } 215 home.ignore(*this,AP_DISPOSE,true); 216 (void) Propagator::dispose(home); 217 return sizeof(*this); 218 } 219 220 }} 221 222 // STATISTICS: search-other 223