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