Generated on Sat Jul 28 2018 17:14:37 for Gecode by doxygen 1.8.14
int.hpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * David Rijsman <David.Rijsman@quintiq.com>
5  *
6  * Contributing authors:
7  * Christian Schulte <schulte@gecode.org>
8  *
9  * Copyright:
10  * David Rijsman, 2009
11  * Christian Schulte, 2009
12  *
13  * Last modified:
14  * $Date: 2016-06-29 17:28:17 +0200 (Wed, 29 Jun 2016) $
15  * $Revision: 15137 $
16  *
17  * This file is part of Gecode, the generic constraint
18  * development environment:
19  * http://www.gecode.org
20  *
21  * Permission is hereby granted, free of charge, to any person obtaining
22  * a copy of this software and associated documentation files (the
23  * "Software"), to deal in the Software without restriction, including
24  * without limitation the rights to use, copy, modify, merge, publish,
25  * distribute, sublicense, and/or sell copies of the Software, and to
26  * permit persons to whom the Software is furnished to do so, subject to
27  * the following conditions:
28  *
29  * The above copyright notice and this permission notice shall be
30  * included in all copies or substantial portions of the Software.
31  *
32  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
33  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
34  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
35  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
36  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
37  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
38  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
39  *
40  */
41 
42 namespace Gecode { namespace Int { namespace Sequence {
43 
44  template<class View, class Val>
47  int q0, int l0, int u0)
48  : Propagator(home), x(x0), s(s0), q(q0), l(l0), u(u0),
49  vvsamax(home,x,s0,q0), vvsamin(home,x,s0,q0), ac(home),
50  tofail(false) {
51  home.notice(*this,AP_DISPOSE);
52  for (int i=x.size(); i--; ) {
53  if (undecided(x[i],s)) {
54  x[i].subscribe(home,*new (home) SupportAdvisor<View>(home,*this,ac,i));
55  } else {
56  x[i].schedule(home,*this,x[i].assigned() ? ME_INT_VAL : ME_INT_BND);
57  }
58  }
59  }
60 
61  namespace {
63  template<class Val>
64  class UpdateVal {
65  public:
66  static void update(Val& n, Space& home, bool share, Val& old);
67  };
69  template<>
70  class UpdateVal<int> {
71  public:
72  static void update(int& n, Space&, bool, int& old) {
73  n = old;
74  }
75  };
77  template<>
78  class UpdateVal<IntSet> {
79  public:
80  static void update(IntSet& n, Space& home, bool share,
81  IntSet& old) {
82  n.update(home,share,old);
83  }
84  };
85  }
86 
87  template<class View, class Val>
90  : Propagator(home,share,p), q(p.q), l(p.l), u(p.u),
91  vvsamax(), vvsamin(), tofail(p.tofail) {
92  UpdateVal<Val>::update(s,home,share,p.s);
93  x.update(home,share,p.x);
94  ac.update(home,share,p.ac);
95  vvsamax.update(home,share,p.vvsamax);
96  vvsamin.update(home,share,p.vvsamin);
97  }
98 
99  template<class View,class Val>
100  ExecStatus
102  SupportAdvisor<View>& a = static_cast<SupportAdvisor<View>&>(_a);
103  ExecStatus status = vvsamax.advise(home,x,s,q,a.i,d);
104  if ( ES_NOFIX == vvsamin.advise(home,x,s,q,a.i,d) ) {
105  status = ES_NOFIX;
106  }
107 
108  if (!undecided(x[a.i],s)) {
109  if (!x[a.i].assigned())
110  x[a.i].cancel(home,a);
111 
112  if ( ES_NOFIX == status ) {
113  return home.ES_NOFIX_DISPOSE(ac,a);
114  } else {
115  return home.ES_FIX_DISPOSE(ac,a);
116  }
117  }
118 
119  if ((status == ES_FAILED) && disabled()) {
120  tofail = true;
121  return ES_FIX;
122  }
123 
124  return status;
125  }
126 
127  template<class View, class Val>
128  forceinline size_t
130  home.ignore(*this,AP_DISPOSE);
131  ac.dispose(home);
132  s.~Val();
133  (void) Propagator::dispose(home);
134  return sizeof(*this);
135  }
136 
137  template<class View, class Val>
139  Sequence<View,Val>::check(Space& home, ViewArray<View>& x, Val s, int q, int l, int u) {
140  Region r(home);
141  // could do this with an array of length q...
142  int* upper = r.alloc<int>(x.size()+1);
143  int* lower = r.alloc<int>(x.size()+1);
144  upper[0] = 0;
145  lower[0] = 0;
146  for ( int j=0; j<x.size(); j++ ) {
147  upper[j+1] = upper[j];
148  lower[j+1] = lower[j];
149  if (includes(x[j],s)) {
150  upper[j+1] += 1;
151  } else if (excludes(x[j],s)) {
152  lower[j+1] += 1;
153  }
154  if ( j+1 >= q && (q - l < lower[j+1] - lower[j+1-q] || upper[j+1] - upper[j+1-q] > u) ) {
155  return ES_FAILED;
156  }
157  }
158  return ES_OK;
159  }
160 
161  template<class View, class Val>
162  ExecStatus
163  Sequence<View,Val>::post(Home home, ViewArray<View>& x, Val s, int q, int l, int u) {
164  GECODE_ES_CHECK(check(home,x,s,q,l,u));
165  Sequence<View,Val>* p = new (home) Sequence<View,Val>(home,x,s,q,l,u);
166 
167  GECODE_ES_CHECK(p->vvsamax.propagate(home,x,s,q,l,u));
168  GECODE_ES_CHECK(p->vvsamin.propagate(home,x,s,q,l,u));
169 
170  return ES_OK;
171  }
172 
173  template<class View, class Val>
174  Actor*
175  Sequence<View,Val>::copy(Space& home, bool share) {
176  return new (home) Sequence<View,Val>(home,share,*this);
177  }
178 
179  template<class View, class Val>
180  PropCost
182  return PropCost::cubic(PropCost::HI,x.size());
183  }
184 
185  template<class View, class Val>
186  void
188  for (int i=x.size(); i--; )
189  if (!undecided(x[i],s))
190  x[i].schedule(home,*this,x[i].assigned() ? ME_INT_VAL : ME_INT_BND);
191  if (tofail)
192  View::schedule(home,*this,ME_INT_BND);
193  }
194 
195  template<class View, class Val>
196  ExecStatus
198  if (tofail)
199  return ES_FAILED;
200 
201  GECODE_ES_CHECK(vvsamax.propagate(home,x,s,q,l,u));
202  GECODE_ES_CHECK(vvsamin.propagate(home,x,s,q,l,u));
203 
204  for (int i=x.size(); i--; )
205  if (undecided(x[i],s))
206  return ES_FIX;
207 
208  return home.ES_SUBSUMED(*this);
209  }
210 
211 }}}
212 
213 // STATISTICS: int-prop
214 
bool includes(const View &x, int s)
Test whether all values of view x are included in s.
Definition: set-op.hpp:76
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
union Gecode::@579::NNF::@61 u
Union depending on nodetype t.
void post(Home home, Term *t, int n, FloatRelType frt, FloatVal c)
Post propagator for linear constraint over floats.
Definition: post.cpp:228
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3614
Actor must always be disposed.
Definition: core.hpp:630
bool assigned(void) const
Test whether view is assigned.
Definition: var.hpp:123
bool undecided(const View &x, int s)
Test whether no decision on inclusion or exclusion of values of view x in s can be made...
Definition: set-op.hpp:110
Base-class for propagators.
Definition: core.hpp:1092
Base-class for advisors.
Definition: core.hpp:1294
ExecStatus ES_NOFIX_DISPOSE(Council< A > &c, A &a)
Advisor a must be disposed and its propagator must be run
Definition: core.hpp:3938
Handle to region.
Definition: region.hpp:61
Propagation has computed fixpoint.
Definition: core.hpp:545
Computation spaces.
Definition: core.hpp:1748
Base-class for both propagators and branchers.
Definition: core.hpp:696
Gecode::IntSet d(v, 7)
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition: macros.hpp:95
struct Gecode::@579::NNF::@61::@63 a
For atomic nodes.
Single _a(2, 3)
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
Execution has resulted in failure.
Definition: core.hpp:542
Sequence propagator for array of integers
Definition: sequence.hh:105
const Gecode::ModEvent ME_INT_VAL
Domain operation has resulted in a value (assigned variable)
Definition: var-type.hpp:56
const Gecode::ModEvent ME_INT_BND
Domain operation has changed the minimum or maximum of the domain.
Definition: var-type.hpp:65
Expensive.
Definition: core.hpp:582
ExecStatus ES_FIX_DISPOSE(Council< A > &c, A &a)
Advisor a must be disposed
Definition: core.hpp:3931
View arrays.
Definition: array.hpp:234
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition: core.hpp:3321
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:784
void check(const FloatVal &n, const char *l)
Check whether float n is a valid number, otherwise throw out of limits exception with information l...
Definition: limits.hpp:48
static PropCost cubic(PropCost::Mod m, unsigned int n)
Cubic complexity for modifier m and size measure n.
Definition: core.hpp:4823
Generic domain change information to be supplied to advisors.
Definition: core.hpp:281
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
Definition: core.hpp:4141
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition: core.hpp:3354
Propagation cost.
Definition: core.hpp:554
ExecStatus
Definition: core.hpp:540
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:47
#define forceinline
Definition: config.hpp:173
Post propagator for SetVar x
Definition: set.hh:784
Execution is okay.
Definition: core.hpp:544
Propagation has not computed fixpoint.
Definition: core.hpp:543
bool excludes(const View &x, int s)
Test whether all values of view x are excluded from s.
Definition: set-op.hpp:93
Gecode toplevel namespace
void reschedule(Space &home, Propagator &p, IntSet &y)
Definition: rel.hpp:96
int ModEventDelta
Modification event deltas.
Definition: core.hpp:169
Home class for posting propagators
Definition: core.hpp:922
Class for advising the propagator.
Definition: view.hpp:48
void update(Space &home, bool share, ViewValSupportArray< View, Val, iss > &x)
Cloning.
Definition: view.hpp:466