Generated on Thu Mar 16 2017 03:24:23 for Gecode by doxygen 1.8.13
nogoods.cpp
Go to the documentation of this file.
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  * Last modified:
10  * $Date: 2016-06-29 17:28:17 +0200 (Wed, 29 Jun 2016) $ by $Author: schulte $
11  * $Revision: 15137 $
12  *
13  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  * Permission is hereby granted, free of charge, to any person obtaining
18  * a copy of this software and associated documentation files (the
19  * "Software"), to deal in the Software without restriction, including
20  * without limitation the rights to use, copy, modify, merge, publish,
21  * distribute, sublicense, and/or sell copies of the Software, and to
22  * permit persons to whom the Software is furnished to do so, subject to
23  * the following conditions:
24  *
25  * The above copyright notice and this permission notice shall be
26  * included in all copies or substantial portions of the Software.
27  *
28  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35  *
36  */
37 
39 
40 namespace Gecode { namespace Search { namespace Meta {
41 
43  forceinline NGL*
44  disposenext(NGL* ngl, Space& home, Propagator& p, bool c) {
45  NGL* n = ngl->next();
46  if (c)
47  ngl->cancel(home,p);
48  home.rfree(ngl,ngl->dispose(home));
49  return n;
50  }
51 
52  void
55  }
56  void
59  }
60  void
63  }
65  NoNGL::status(const Space&) const {
67  return NGL::NONE;
68  }
72  return ES_OK;
73  }
74  NGL*
75  NoNGL::copy(Space&, bool) {
77  return NULL;
78  }
79 
80  Actor*
81  NoGoodsProp::copy(Space& home, bool share) {
82  return new (home) NoGoodsProp(home,share,*this);
83  }
84 
85  PropCost
86  NoGoodsProp::cost(const Space&, const ModEventDelta&) const {
88  }
89 
90  void
92  root->reschedule(home,*this);
93  NGL* l = root->next();
94  while ((l != NULL) && l->leaf()) {
95  l->reschedule(home,*this);
96  l = l->next();
97  }
98  if (l != NULL)
99  l->reschedule(home,*this);
100  }
101 
102 
103  ExecStatus
105  restart:
106  // Start with checking the first literal
107  switch (root->status(home)) {
108  case NGL::FAILED:
109  // All no-goods are dead, let dispose() clean up
110  return home.ES_SUBSUMED(*this);
111  case NGL::SUBSUMED:
112  {
113  NGL* l = disposenext(root,home,*this,true); n--;
114  // Prune leaf-literals
115  while ((l != NULL) && l->leaf()) {
116  l->cancel(home,*this); n--;
117  GECODE_ES_CHECK(l->prune(home));
118  l = disposenext(l,home,*this,false);
119  }
120  root = l;
121  // Is there anything left?
122  if (l == NULL)
123  return home.ES_SUBSUMED(*this);
124  // Skip literal that already has a subscription
125  l = l->next();
126  // Create subscriptions for leafs
127  while ((l != NULL) && l->leaf()) {
128  l->subscribe(home,*this); n++;
129  l = l->next();
130  }
131  // Create subscription for possible non-leaf literal
132  if (l != NULL) {
133  l->subscribe(home,*this); n++;
134  }
135  goto restart;
136  }
137  case NGL::NONE:
138  break;
139  default: GECODE_NEVER;
140  }
141 
142  {
143  NGL* p = root;
144  NGL* l = p->next();
145 
146  // Check the leaves
147  while ((l != NULL) && l->leaf()) {
148  switch (l->status(home)) {
149  case NGL::SUBSUMED:
150  l = disposenext(l,home,*this,true); n--;
151  p->next(l);
152  GECODE_ES_CHECK(root->prune(home));
153  if (root->status(home) == NGL::FAILED)
154  return home.ES_SUBSUMED(*this);
155  break;
156  case NGL::FAILED:
157  l = disposenext(l,home,*this,true); n--;
158  p->next(l);
159  break;
160  case NGL::NONE:
161  p = l; l = l->next();
162  break;
163  default: GECODE_NEVER;
164  }
165  }
166 
167  // Check the next subtree
168  if (l != NULL) {
169  switch (l->status(home)) {
170  case NGL::FAILED:
171  (void) disposenext(l,home,*this,true); n--;
172  // Prune entire subtree
173  p->next(NULL);
174  break;
175  case NGL::SUBSUMED:
176  {
177  // Unlink node
178  l = disposenext(l,home,*this,true); n--;
179  p->next(l);
180  // Create subscriptions
181  while ((l != NULL) && l->leaf()) {
182  l->subscribe(home,*this); n++;
183  l = l->next();
184  }
185  if (l != NULL) {
186  l->subscribe(home,*this); n++;
187  }
188  }
189  break;
190  case NGL::NONE:
191  break;
192  default: GECODE_NEVER;
193  }
194  }
195  }
196  return ES_NOFIX;
197  }
198 
199  size_t
201  if (home.failed()) {
202  // This will be executed when one ngl returned true for notice()
203  NGL* l = root;
204  while (l != NULL) {
205  NGL* t = l->next();
206  (void) l->dispose(home);
207  l = t;
208  }
209  } else if (root != NULL) {
210  // This will be executed for subsumption
211  NGL* l = disposenext(root,home,*this,true);
212  while ((l != NULL) && l->leaf())
213  l = disposenext(l,home,*this,true);
214  if (l != NULL)
215  l = disposenext(l,home,*this,true);
216  while (l != NULL)
217  l = disposenext(l,home,*this,false);
218  }
219  home.ignore(*this,AP_DISPOSE,true);
220  (void) Propagator::dispose(home);
221  return sizeof(*this);
222  }
223 
224 }}}
225 
226 // STATISTICS: search-meta
virtual NGL::Status status(const Space &home) const
Test the status of the no-good literal.
Definition: nogoods.cpp:65
virtual void subscribe(Space &home, Propagator &p)=0
Subscribe propagator p to all views of the no-good literal.
NodeType t
Type of node.
Definition: bool-expr.cpp:234
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Definition: core.hpp:4577
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3484
virtual ExecStatus prune(Space &home)=0
Propagate the negation of the no-good literal.
Actor must always be disposed.
Definition: core.hpp:626
The literal is neither failed nor subsumed.
Definition: core.hpp:1269
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: nogoods.cpp:104
Status
The status of a no-good literal.
Definition: core.hpp:1266
Base-class for propagators.
Definition: core.hpp:1012
Computation spaces.
Definition: core.hpp:1672
Base-class for both propagators and branchers.
Definition: core.hpp:682
NGL * disposenext(NGL *ngl, Space &home, Propagator &p, bool c)
Help function to cancel and dispose a no-good literal.
Definition: nogoods.cpp:44
virtual void cancel(Space &home, Propagator &p)
Cancel propagator p from all views of the no-good literal.
Definition: nogoods.cpp:57
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition: macros.hpp:95
The literal is subsumed.
Definition: core.hpp:1268
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
bool leaf(void) const
Test whether literal is a leaf.
Definition: core.hpp:3708
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
No-good propagator.
Definition: nogoods.hh:69
bool failed(void) const
Check whether space is failed.
Definition: core.hpp:3963
virtual void reschedule(Space &home)
Schedule function.
Definition: nogoods.cpp:91
virtual NGL::Status status(const Space &home) const =0
Test the status of the no-good literal.
NGL * next(void) const
Return pointer to next literal.
Definition: core.hpp:3712
virtual NGL * copy(Space &home, bool share)
Create copy.
Definition: nogoods.cpp:75
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Const function (defined as low unary)
Definition: nogoods.cpp:86
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
Definition: core.cpp:167
The literal is failed.
Definition: core.hpp:1267
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition: core.hpp:3281
Propagation cost.
Definition: core.hpp:550
ExecStatus
Definition: core.hpp:536
virtual void subscribe(Space &home, Propagator &p)
Subscribe propagator p to all views of the no-good literal.
Definition: nogoods.cpp:53
#define forceinline
Definition: config.hpp:173
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: nogoods.cpp:200
virtual Actor * copy(Space &home, bool share)
Perform copying during cloning.
Definition: nogoods.cpp:81
Execution is okay.
Definition: core.hpp:540
virtual void cancel(Space &home, Propagator &p)=0
Cancel propagator p from all views of the no-good literal.
virtual size_t dispose(Space &home)
Dispose.
Definition: core.hpp:3740
Propagation has not computed fixpoint.
Definition: core.hpp:539
virtual void reschedule(Space &home, Propagator &p)
Schedule propagator p for all views of the no-good literal.
Definition: nogoods.cpp:61
Gecode toplevel namespace
virtual ExecStatus prune(Space &home)
Propagate the negation of the no-good literal.
Definition: nogoods.cpp:70
int ModEventDelta
Modification event deltas.
Definition: core.hpp:169
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:60
void rfree(void *p, size_t s)
Free memory previously allocated with alloc (might be reused later)
Definition: core.hpp:2749
virtual void reschedule(Space &home, Propagator &p)=0
Schedule propagator p for all views of the no-good literal.
No-good literal recorded during search.
Definition: core.hpp:1260