Generated on Mon Feb 8 2021 00:00:00 for Gecode by doxygen 1.8.20
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  * 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 
38 namespace Gecode { namespace Int { namespace Sequence {
39 
40  template<class View, class Val>
43  int q0, int l0, int u0)
44  : Propagator(home), x(x0), s(s0), q(q0), l(l0), u(u0),
45  vvsamax(home,x,s0,q0), vvsamin(home,x,s0,q0), ac(home),
46  tofail(false) {
47  home.notice(*this,AP_DISPOSE);
48  bool assigned = false;
49  for (int i=x.size(); i--; ) {
50  if (undecided(x[i],s))
51  x[i].subscribe(home,*new (home) SupportAdvisor<View>(home,*this,ac,i));
52  if (x[i].assigned())
53  assigned = true;
54  }
55  View::schedule(home,*this,assigned ? ME_INT_VAL : ME_INT_BND);
56  }
57 
58  template<class View, class Val>
61  : Propagator(home,p), s(p.s), q(p.q), l(p.l), u(p.u),
62  vvsamax(), vvsamin(), tofail(p.tofail) {
63  x.update(home,p.x);
64  ac.update(home,p.ac);
65  vvsamax.update(home,p.vvsamax);
66  vvsamin.update(home,p.vvsamin);
67  }
68 
69  template<class View,class Val>
73  ExecStatus status = vvsamax.advise(home,x,s,q,a.i,d);
74  if ( ES_NOFIX == vvsamin.advise(home,x,s,q,a.i,d) ) {
75  status = ES_NOFIX;
76  }
77 
78  if (!undecided(x[a.i],s)) {
79  if (!x[a.i].assigned())
80  x[a.i].cancel(home,a);
81 
82  if ( ES_NOFIX == status ) {
83  return home.ES_NOFIX_DISPOSE(ac,a);
84  } else {
85  return home.ES_FIX_DISPOSE(ac,a);
86  }
87  }
88 
89  if ((status == ES_FAILED) && disabled()) {
90  tofail = true;
91  return ES_FIX;
92  }
93 
94  return status;
95  }
96 
97  template<class View, class Val>
98  forceinline size_t
100  home.ignore(*this,AP_DISPOSE);
101  ac.dispose(home);
102  s.~Val();
103  (void) Propagator::dispose(home);
104  return sizeof(*this);
105  }
106 
107  template<class View, class Val>
109  Sequence<View,Val>::check(ViewArray<View>& x, Val s, int q, int l, int u) {
110  Region r;
111  // could do this with an array of length q...
112  int* upper = r.alloc<int>(x.size()+1);
113  int* lower = r.alloc<int>(x.size()+1);
114  upper[0] = 0;
115  lower[0] = 0;
116  for ( int j=0; j<x.size(); j++ ) {
117  upper[j+1] = upper[j];
118  lower[j+1] = lower[j];
119  if (includes(x[j],s)) {
120  upper[j+1] += 1;
121  } else if (excludes(x[j],s)) {
122  lower[j+1] += 1;
123  }
124  if ( j+1 >= q && (q - l < lower[j+1] - lower[j+1-q] || upper[j+1] - upper[j+1-q] > u) ) {
125  return ES_FAILED;
126  }
127  }
128  return ES_OK;
129  }
130 
131  template<class View, class Val>
132  ExecStatus
133  Sequence<View,Val>::post(Home home, ViewArray<View>& x, Val s, int q, int l, int u) {
134  GECODE_ES_CHECK(check(x,s,q,l,u));
135  Sequence<View,Val>* p = new (home) Sequence<View,Val>(home,x,s,q,l,u);
136 
137  GECODE_ES_CHECK(p->vvsamax.propagate(home,x,s,q,l,u));
138  GECODE_ES_CHECK(p->vvsamin.propagate(home,x,s,q,l,u));
139 
140  return ES_OK;
141  }
142 
143  template<class View, class Val>
144  Actor*
146  return new (home) Sequence<View,Val>(home,*this);
147  }
148 
149  template<class View, class Val>
150  PropCost
152  return PropCost::cubic(PropCost::HI,x.size());
153  }
154 
155  template<class View, class Val>
156  void
158  for (int i=x.size(); i--; )
159  if (!undecided(x[i],s))
160  x[i].schedule(home,*this,x[i].assigned() ? ME_INT_VAL : ME_INT_BND);
161  if (tofail)
162  View::schedule(home,*this,ME_INT_BND);
163  }
164 
165  template<class View, class Val>
166  ExecStatus
168  if (tofail)
169  return ES_FAILED;
170 
171  GECODE_ES_CHECK(vvsamax.propagate(home,x,s,q,l,u));
172  GECODE_ES_CHECK(vvsamin.propagate(home,x,s,q,l,u));
173 
174  for (int i=x.size(); i--; )
175  if (undecided(x[i],s))
176  return ES_FIX;
177 
178  return home.ES_SUBSUMED(*this);
179  }
180 
181 }}}
182 
183 // STATISTICS: int-prop
184 
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition: core.hpp:3219
void update(Space &home, ViewValSupportArray< View, Val, iss > &x)
Cloning.
Definition: view.hpp:461
Post propagator for SetVar x
Definition: set.hh:767
ExecStatus ES_NOFIX_DISPOSE(Council< A > &c, A &a)
Advisor a must be disposed and its propagator must be run
Definition: core.hpp:3887
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3563
Single _a(2, 3)
void post(Home home, Term *t, int n, FloatRelType frt, FloatVal c)
Post propagator for linear constraint over floats.
Definition: post.cpp:238
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:43
Computation spaces.
Definition: core.hpp:1742
Base-class for both propagators and branchers.
Definition: core.hpp:628
bool assigned(void) const
Test whether view is assigned.
Definition: var.hpp:111
const Gecode::ModEvent ME_INT_VAL
Domain operation has resulted in a value (assigned variable)
Definition: var-type.hpp:56
Gecode toplevel namespace
Base-class for propagators.
Definition: core.hpp:1064
union Gecode::@602::NNF::@65 u
Union depending on nodetype t.
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition: macros.hpp:91
void reschedule(Space &home, Propagator &p, IntSet &y)
Definition: rel.hpp:92
Generic domain change information to be supplied to advisors.
Definition: core.hpp:204
Home class for posting propagators
Definition: core.hpp:856
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:106
static PropCost cubic(PropCost::Mod m, unsigned int n)
Cubic complexity for modifier m and size measure n.
Definition: core.hpp:4778
Handle to region.
Definition: region.hpp:55
@ AP_DISPOSE
Actor must always be disposed.
Definition: core.hpp:562
const Gecode::ModEvent ME_INT_BND
Domain operation has changed the minimum or maximum of the domain.
Definition: var-type.hpp:65
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:767
struct Gecode::@602::NNF::@65::@67 a
For atomic nodes.
bool excludes(const View &x, int s)
Test whether all values of view x are excluded from s.
Definition: set-op.hpp:89
Propagation cost.
Definition: core.hpp:486
NNF * l
Left subtree.
Definition: bool-expr.cpp:240
Sequence propagator for array of integers
Definition: sequence.hh:101
Gecode::IntSet d(v, 7)
Base-class for advisors.
Definition: core.hpp:1292
@ ES_FIX
Propagation has computed fixpoint.
Definition: core.hpp:477
Class for advising the propagator.
Definition: view.hpp:44
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:44
#define forceinline
Definition: config.hpp:192
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
Definition: core.hpp:4074
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition: core.hpp:3252
@ HI
Expensive.
Definition: core.hpp:514
View arrays.
Definition: array.hpp:253
@ ES_FAILED
Execution has resulted in failure.
Definition: core.hpp:474
int ModEventDelta
Modification event deltas.
Definition: core.hpp:89
bool includes(const View &x, int s)
Test whether all values of view x are included in s.
Definition: set-op.hpp:72
@ ES_NOFIX
Propagation has not computed fixpoint.
Definition: core.hpp:475
ExecStatus ES_FIX_DISPOSE(Council< A > &c, A &a)
Advisor a must be disposed
Definition: core.hpp:3880
Gecode::IntArgs i({1, 2, 3, 4})
@ ES_OK
Execution is okay.
Definition: core.hpp:476
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
ExecStatus
Definition: core.hpp:472