Generated on Tue Oct 22 2013 00:49:07 for Gecode by doxygen 1.8.4
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