Generated on Sat Feb 7 2015 02:01:29 for Gecode by doxygen 1.8.9.1
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: 2013-07-09 12:24:39 +0200 (Tue, 09 Jul 2013) $ by $Author: schulte $
11  * $Revision: 13832 $
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 
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  }
61  NoNGL::status(const Space&) const {
63  return NGL::NONE;
64  }
68  return ES_OK;
69  }
70  NGL*
71  NoNGL::copy(Space&, bool) {
73  return NULL;
74  }
75 
76  Actor*
77  NoGoodsProp::copy(Space& home, bool share) {
78  return new (home) NoGoodsProp(home,share,*this);
79  }
80 
81  PropCost
82  NoGoodsProp::cost(const Space&, const ModEventDelta&) const {
84  }
85 
86  ExecStatus
88  restart:
89  // Start with checking the first literal
90  switch (root->status(home)) {
91  case NGL::FAILED:
92  // All no-goods are dead, let dispose() clean up
93  return home.ES_SUBSUMED(*this);
94  case NGL::SUBSUMED:
95  {
96  NGL* l = disposenext(root,home,*this,true); n--;
97  // Prune leaf-literals
98  while ((l != NULL) && l->leaf()) {
99  l->cancel(home,*this); n--;
100  GECODE_ES_CHECK(l->prune(home));
101  l = disposenext(l,home,*this,false);
102  }
103  root = l;
104  // Is there anything left?
105  if (l == NULL)
106  return home.ES_SUBSUMED(*this);
107  // Skip literal that already has a subscription
108  l = l->next();
109  // Create subscriptions for leafs
110  while ((l != NULL) && l->leaf()) {
111  l->subscribe(home,*this); n++;
112  l = l->next();
113  }
114  // Create subscription for possible non-leaf literal
115  if (l != NULL) {
116  l->subscribe(home,*this); n++;
117  }
118  goto restart;
119  }
120  case NGL::NONE:
121  break;
122  default: GECODE_NEVER;
123  }
124 
125  {
126  NGL* p = root;
127  NGL* l = p->next();
128 
129  // Check the leaves
130  while ((l != NULL) && l->leaf()) {
131  switch (l->status(home)) {
132  case NGL::SUBSUMED:
133  l = disposenext(l,home,*this,true); n--;
134  p->next(l);
135  GECODE_ES_CHECK(root->prune(home));
136  if (root->status(home) == NGL::FAILED)
137  return home.ES_SUBSUMED(*this);
138  break;
139  case NGL::FAILED:
140  l = disposenext(l,home,*this,true); n--;
141  p->next(l);
142  break;
143  case NGL::NONE:
144  p = l; l = l->next();
145  break;
146  default: GECODE_NEVER;
147  }
148  }
149 
150  // Check the next subtree
151  if (l != NULL) {
152  switch (l->status(home)) {
153  case NGL::FAILED:
154  (void) disposenext(l,home,*this,true); n--;
155  // Prune entire subtree
156  p->next(NULL);
157  break;
158  case NGL::SUBSUMED:
159  {
160  // Unlink node
161  l = disposenext(l,home,*this,true); n--;
162  p->next(l);
163  // Create subscriptions
164  while ((l != NULL) && l->leaf()) {
165  l->subscribe(home,*this); n++;
166  l = l->next();
167  }
168  if (l != NULL) {
169  l->subscribe(home,*this); n++;
170  }
171  }
172  break;
173  case NGL::NONE:
174  break;
175  default: GECODE_NEVER;
176  }
177  }
178  }
179  return ES_NOFIX;
180  }
181 
182  size_t
184  if (home.failed()) {
185  // This will be executed when one ngl returned true for notice()
186  NGL* l = root;
187  while (l != NULL) {
188  NGL* t = l->next();
189  (void) l->dispose(home);
190  l = t;
191  }
192  } else if (root != NULL) {
193  // This will be executed for subsumption
194  NGL* l = disposenext(root,home,*this,true);
195  while ((l != NULL) && l->leaf())
196  l = disposenext(l,home,*this,true);
197  if (l != NULL)
198  l = disposenext(l,home,*this,true);
199  while (l != NULL)
200  l = disposenext(l,home,*this,false);
201  }
202  home.ignore(*this,AP_DISPOSE,true);
203  (void) Propagator::dispose(home);
204  return sizeof(*this);
205  }
206 
207 }}}
208 
209 // STATISTICS: search-other
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:4041
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:2973
virtual ExecStatus prune(Space &home)=0
Propagate the negation of the no-good literal.
NGL * next(void) const
Return pointer to next literal.
Definition: core.hpp:3196
Actor must always be disposed.
Definition: core.hpp:610
The literal is neither failed nor subsumed.
Definition: core.hpp:980
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: nogoods.cpp:87
Status
The status of a no-good literal.
Definition: core.hpp:977
Base-class for propagators.
Definition: core.hpp:755
unsigned int n
Number of no-good literals with subscriptions.
Definition: nogoods.hh:72
Computation spaces.
Definition: core.hpp:1362
bool failed(void) const
Check whether space is failed.
Definition: core.hpp:3442
Base-class for both propagators and branchers.
Definition: core.hpp:666
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:84
The literal is subsumed.
Definition: core.hpp:979
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
NoGoodsProp(Home home, NGL *root)
Constructor for creation.
Definition: nogoods.hh:105
virtual NGL::Status status(const Space &home) const =0
Test the status of the no-good literal.
virtual NGL * copy(Space &home, bool share)
Create copy.
Definition: nogoods.cpp:71
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Const function (defined as low unary)
Definition: nogoods.cpp:82
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
Definition: core.cpp:169
The literal is failed.
Definition: core.hpp:978
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition: core.hpp:2877
Propagation cost.
Definition: core.hpp:537
ExecStatus
Definition: core.hpp:523
virtual NGL::Status status(const Space &home) const
Test the status of the no-good literal.
Definition: nogoods.cpp:61
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:132
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: nogoods.cpp:183
virtual Actor * copy(Space &home, bool share)
Perform copying during cloning.
Definition: nogoods.cpp:77
Execution is okay.
Definition: core.hpp:527
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:3224
Propagation has not computed fixpoint.
Definition: core.hpp:526
Gecode toplevel namespace
bool leaf(void) const
Test whether literal is a leaf.
Definition: core.hpp:3192
NGL * root
Root of no-good literal tree.
Definition: nogoods.hh:70
virtual ExecStatus prune(Space &home)
Propagate the negation of the no-good literal.
Definition: nogoods.cpp:66
int ModEventDelta
Modification event deltas.
Definition: core.hpp:173
#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:2363
No-good literal recorded during search.
Definition: core.hpp:971