this repo has no description
dekker.one
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
36namespace Gecode { namespace Search {
37
38 /// Help function to cancel and dispose a no-good literal
39 forceinline NGL*
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
49 NoNGL::subscribe(Space&, Propagator&) {
50 GECODE_NEVER;
51 }
52 void
53 NoNGL::cancel(Space&, Propagator&) {
54 GECODE_NEVER;
55 }
56 void
57 NoNGL::reschedule(Space&, Propagator&) {
58 GECODE_NEVER;
59 }
60 NGL::Status
61 NoNGL::status(const Space&) const {
62 GECODE_NEVER;
63 return NGL::NONE;
64 }
65 ExecStatus
66 NoNGL::prune(Space&) {
67 GECODE_NEVER;
68 return ES_OK;
69 }
70 NGL*
71 NoNGL::copy(Space&) {
72 GECODE_NEVER;
73 return nullptr;
74 }
75
76 Actor*
77 NoGoodsProp::copy(Space& home) {
78 return new (home) NoGoodsProp(home,*this);
79 }
80
81 PropCost
82 NoGoodsProp::cost(const Space&, const ModEventDelta&) const {
83 return PropCost::linear(PropCost::LO,n);
84 }
85
86 void
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
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
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