Generated on Fri Jan 28 2022 04:43:06 for Gecode by doxygen 1.8.13
single.hpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Christopher Mears <Chris.Mears@monash.edu>
5  *
6  * Contributing authors:
7  * Christian Schulte <schulte@gecode.org>
8  * Guido Tack <tack@gecode.org>
9  *
10  * Copyright:
11  * Christopher Mears, 2011
12  * Christian Schulte, 2011
13  * Guido Tack, 2011
14  *
15  * This file is part of Gecode, the generic constraint
16  * development environment:
17  * http://www.gecode.org
18  *
19  * Permission is hereby granted, free of charge, to any person obtaining
20  * a copy of this software and associated documentation files (the
21  * "Software"), to deal in the Software without restriction, including
22  * without limitation the rights to use, copy, modify, merge, publish,
23  * distribute, sublicense, and/or sell copies of the Software, and to
24  * permit persons to whom the Software is furnished to do so, subject to
25  * the following conditions:
26  *
27  * The above copyright notice and this permission notice shall be
28  * included in all copies or substantial portions of the Software.
29  *
30  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
31  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
32  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
33  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
34  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
35  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
36  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
37  *
38  */
39 
40 namespace Gecode { namespace Set { namespace Precede {
41 
42  template<class View>
45  Council<Index>& c, int i0)
46  : Advisor(home,p,c), i(i0) {}
47 
48  template<class View>
51  : Advisor(home,a), i(a.i) {}
52 
53 
54  template<class View>
57  int n = x.size();
58  while (alpha < n) {
59  if (x[alpha].notContains(s)) {
60  GECODE_ME_CHECK(x[alpha].exclude(home, t));
61  } else if (x[alpha].contains(t)) {
62  GECODE_ME_CHECK(x[alpha].include(home, s));
63  } else {
64  break;
65  }
66  alpha++;
67  }
68  return ES_OK;
69  }
70 
71  template<class View>
74  int n = x.size();
75  do {
76  beta++;
77  } while ((beta < n) &&
78  (x[beta].notContains(s) || x[beta].contains(t)));
79  if (beta > gamma) {
80  GECODE_ME_CHECK(x[alpha].exclude(home, t));
81  GECODE_ME_CHECK(x[alpha].include(home, s));
82  }
83  return ES_OK;
84  }
85 
86  template<class View>
89  int s0, int t0, int b, int g)
90  : NaryPropagator<View, PC_SET_NONE>(home,x0),
91  c(home), s(s0), t(t0), alpha(0), beta(b), gamma(g) {
92  for (int i=x.size(); i--; )
93  if (!x[i].assigned())
94  x[i].subscribe(home,*new (home) Index(home,*this,c,i));
95  View::schedule(home, *this, ME_SET_BB);
96  }
97 
98  template<class View>
99  inline ExecStatus
101  {
102  int alpha = 0;
103  while (alpha < x.size()) {
104  if (x[alpha].notContains(s)) {
105  GECODE_ME_CHECK(x[alpha].exclude(home, t));
106  } else if (x[alpha].contains(t)) {
107  GECODE_ME_CHECK(x[alpha].include(home, s));
108  } else {
109  break;
110  }
111  alpha++;
112  }
113  x.drop_fst(alpha);
114  if (x.size() == 0)
115  return ES_OK;
116  }
117  // alpha has been normalized to 0
118  int beta = 0, gamma = 0;
119  do {
120  gamma++;
121  } while ((gamma < x.size()) &&
122  (!x[gamma].notContains(s) || !x[gamma].contains(t)));
123  do {
124  beta++;
125  } while ((beta < x.size()) &&
126  (x[beta].notContains(s) || x[beta].contains(t)));
127  if (beta > gamma) {
128  GECODE_ME_CHECK(x[0].exclude(home, t));
129  GECODE_ME_CHECK(x[0].include(home, s));
130  return ES_OK;
131  }
132  if (gamma < x.size())
133  x.drop_lst(gamma);
134  (void) new (home) Single<View>(home, x, s, t, beta, gamma);
135  return ES_OK;
136  }
137 
138 
139 
140  template<class View>
143  : NaryPropagator<View,PC_SET_NONE>(home, p),
144  s(p.s), t(p.t),
145  alpha(p.alpha), beta(p.beta), gamma(p.gamma) {
146  c.update(home, p.c);
147  }
148  template<class View>
149  Propagator*
151  // Try to eliminate assigned views at the beginning
152  if (alpha > 0) {
153  int i = 0;
154  while ((i < alpha) && x[i].assigned())
155  i++;
156  x.drop_fst(i);
157  for (Advisors<Index> as(c); as(); ++as)
158  as.advisor().i -= i;
159  alpha -= i; beta -= i; gamma -= i;
160  }
161  // Try to eliminate assigned views at the end
162  if (gamma < x.size()) {
163  int i = x.size()-1;
164  while ((i > gamma) && x[i].assigned())
165  i--;
166  x.drop_lst(i);
167  }
168  return new (home) Single<View>(home, *this);
169  }
170 
171 
172  template<class View>
173  inline size_t
175  // Cancel remaining advisors
176  for (Advisors<Index> as(c); as(); ++as)
177  x[as.advisor().i].cancel(home,as.advisor());
178  c.dispose(home);
180  return sizeof(*this);
181  }
182 
183  template<class View>
184  PropCost
185  Single<View>::cost(const Space&, const ModEventDelta&) const {
186  return PropCost::linear(PropCost::LO, x.size());
187  }
188 
189  template<class View>
190  void
192  View::schedule(home, *this, ME_SET_BB);
193  }
194 
195  template<class View>
196  ExecStatus
197  Single<View>::advise(Space& home, Advisor& a0, const Delta&) {
198  Index& a(static_cast<Index&>(a0));
199  int i = a.i;
200  // Check for gamma
201  if ((beta <= gamma) && (i < gamma) &&
202  x[i].notContains(s) && x[i].contains(t))
203  gamma = i;
204  if (x[i].assigned()) {
205  a.dispose(home,c);
206  if (c.empty())
207  return ES_NOFIX;
208  } else if ((i < alpha) || (i > gamma)) {
209  x[i].cancel(home,a);
210  a.dispose(home,c);
211  return (c.empty()) ? ES_NOFIX : ES_FIX;
212  }
213  if (beta > gamma)
214  return ES_NOFIX;
215  if ((alpha == i) || (beta == i))
216  return ES_NOFIX;
217  return ES_FIX;
218  }
219 
220  template<class View>
221  ExecStatus
223  int n = x.size();
224  if (beta > gamma) {
225  GECODE_ME_CHECK(x[alpha].exclude(home, t));
226  GECODE_ME_CHECK(x[alpha].include(home, s));
227  return home.ES_SUBSUMED(*this);
228  }
229  if (alpha < n && (x[alpha].notContains(s) || x[alpha].contains(t))) {
230  if (x[alpha].notContains(s)) {
231  GECODE_ME_CHECK(x[alpha].exclude(home, t));
232  } else {
233  GECODE_ME_CHECK(x[alpha].include(home, s));
234  }
235  alpha++;
236  while (alpha < beta) {
237  if (x[alpha].notContains(s)) {
238  GECODE_ME_CHECK(x[alpha].exclude(home, t));
239  } else {
240  GECODE_ME_CHECK(x[alpha].include(home, s));
241  }
242  alpha++;
243  }
245  beta = alpha;
246  if (alpha < n)
248  } else if ((beta < n) && (x[beta].notContains(s) || x[beta].contains(t))) {
250  }
251 
252  return (c.empty()) ? home.ES_SUBSUMED(*this) : ES_FIX;
253  }
254 
255 }}}
256 
257 // STATISTICS: set-prop
Council of advisors
Definition: core.hpp:154
Council< Index > c
The advisor council.
Definition: precede.hh:77
virtual Propagator * copy(Space &home)
Copy propagator during cloning.
Definition: single.hpp:150
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Definition: core.hpp:4723
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3490
Single(Home home, ViewArray< View > &x, int s, int t, int beta, int gamma)
Constructor for posting.
Definition: single.hpp:88
const Gecode::ModEvent ME_SET_BB
Domain operation has changed both greatest lower and least upper bound.
Definition: var-type.hpp:172
ViewArray< View > x
Array of views.
Definition: pattern.hpp:145
Base-class for propagators.
Definition: core.hpp:1023
Base-class for advisors.
Definition: core.hpp:1251
const Gecode::PropCond PC_SET_NONE
Propagation condition to be ignored (convenience)
Definition: var-type.hpp:199
int i
The position of the view in the view array.
Definition: precede.hh:70
ExecStatus updateAlpha(Space &home)
Update the alpha pointer.
Definition: single.hpp:56
Class to iterate over advisors of a council.
Definition: core.hpp:155
#define forceinline
Definition: config.hpp:185
Propagation has computed fixpoint.
Definition: core.hpp:476
static ExecStatus post(Home home, ViewArray< View > &x, int s, int t)
Post propagator that s precedes t in x.
Definition: single.hpp:100
virtual ExecStatus advise(Space &home, Advisor &a, const Delta &d)
Give advice to propagator.
Definition: single.hpp:197
Computation spaces.
Definition: core.hpp:1701
ModEvent exclude(Space &home, View &x, int s)
Prune view x to exclude all values from s.
Definition: set-op.hpp:137
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition: macros.hpp:91
Gecode::FloatVal c(-8, 8)
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
void drop_lst(int i)
Drop views from positions i+1 to size()-1 from array.
Definition: array.hpp:1231
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
Gecode::IntArgs i({1, 2, 3, 4})
ExecStatus updateBeta(Space &home)
Update the beta pointer.
Definition: single.hpp:73
void subscribe(Space &home, Propagator &p, IntSet &y)
Definition: rel.hpp:71
int alpha
Pointers updated during propagation.
Definition: precede.hh:81
struct Gecode::@593::NNF::@62::@63 b
For binary nodes (and, or, eqv)
Advisors for views (by position in array)
Definition: precede.hh:67
n-ary propagator
Definition: pattern.hpp:142
View arrays.
Definition: array.hpp:235
void drop_fst(int i)
Drop views from positions 0 to i-1 from array.
Definition: array.hpp:1224
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:52
Single value precedence propagator.
Definition: precede.hh:63
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: single.hpp:174
virtual void reschedule(Space &home)
Schedule function.
Definition: single.hpp:191
Generic domain change information to be supplied to advisors.
Definition: core.hpp:203
void dispose(Space &home, Council< A > &c)
Dispose the advisor.
Definition: core.hpp:3791
Propagation cost.
Definition: core.hpp:485
ModEvent include(Space &home, View &x, int s)
Prune view x to only include values from s.
Definition: set-op.hpp:123
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: single.hpp:222
ExecStatus
Definition: core.hpp:471
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:43
Execution is okay.
Definition: core.hpp:475
Propagation has not computed fixpoint.
Definition: core.hpp:474
Index(Space &home, Propagator &p, Council< Index > &c, int i)
Create index advisor.
Definition: single.hpp:44
Gecode toplevel namespace
int s
The value s must precede t.
Definition: precede.hh:79
virtual PropCost cost(const Space &, const ModEventDelta &) const
Cost function.
Definition: single.hpp:185
int ModEventDelta
Modification event deltas.
Definition: core.hpp:89
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1138
Home class for posting propagators
Definition: core.hpp:853
struct Gecode::@593::NNF::@62::@64 a
For atomic nodes.